Пт, 23.08.2019, 06:36
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

 
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Модератор форуму: Ktara, Bandalak, НІКОЛЯ, volevikt  
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Всеукраїнська олімпіада з інформатики (програмування) (Висталяємо завдання та розв'язки)
Всеукраїнська олімпіада з інформатики (програмування)
Ковальчук_Олександр Дата: Вт, 20.11.2007, 20:07 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3709
Нагороди: 18
Рейтинг: 209
Шановні учасники форуму! Скоро районна олімпіада по інформатиці. Допоможіть мені та іншим вчителям інформатикам, які погано розуміються на задачах олімпіадного рівня, підвищити свої знання в області програмування.

Увага! При публікуванні розв’язку обов’язково, окрім самої паскаль-програми писати математичну модель задачі і роз’яснювати ваш розв’язок максимально зрозуміло. Бо із самого тексту програм, не завжди все зрозуміло для пересічного інформатика.


[admin]Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!![/admin]
fox11 Дата: Ср, 07.12.2016, 20:56 | Повідомлення № 226
Прописаний назавжди
Повідомлень: 334
Нагороди: 4
Рейтинг: 81
ЦитатаOxana_cher ()
На каком это языке написано?
На Builder C++, вот только матрицу надо бы не через Label, а DataGridViewhttps://www.youtube.com/watch?v=_kL1jF3H2mY )


Відредаговано: fox11 - Ср, 07.12.2016, 20:58
Oxana_cher Дата: Ср, 07.12.2016, 22:00 | Повідомлення № 227
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
ЦитатаBandalak ()
Oxana_cher, раджу написати самостійно програму по цьому алгоритму на Паскалі і буде Вам щастя!

Ура!
Сделала всё-таки его на Паскале! Этот алгоритм - БОМБА!!!
Работает моментально и с любой начальной позиции!
Всем спасибо!

PS.
Звиняйте, но по одной причине покажу программку завтра после обеда!
Пилипчук_О_П Дата: Ср, 07.12.2016, 23:05 | Повідомлення № 228
Ветеран спілкування
Повідомлень: 4308
Нагороди: 38
Рейтинг: 406
ЦитатаBandalak ()
Ну, це ж якщо маршрут замкнутий. Але бачив такі тільки незамкнуті. Щось жодного замкнутого для n=8 не бачив.
Чи не так?

У Вікіпедії читаємо: "Спочатку спробуємо з незамкненого маршруту зробити замкнений". Далі описано, як це зробити. Звідси висновок: замкнений маршрут 8х8 існує. В російській Вікіпедії один з них є намальований, плюс наведено віршик, в якому закодовано замкнений маршрут.
Пилипчук_О_П Дата: Ср, 07.12.2016, 23:14 | Повідомлення № 229
Ветеран спілкування
Повідомлень: 4308
Нагороди: 38
Рейтинг: 406
ЦитатаDPV ()
Поясніть, що взагалі це таке - Замкнутий маршрут?

Якщо з 64-ї клітинки можна перейти на 1-шу.
ЦитатаDPV ()
Покажіть на прикладі, це якийсь абсурд.

Робимо масив з координатами клітинок замкнутого маршруту (за малюнком з російської Вікіпедії): a1, c2, e1, g2, і т.д. Знаходимо в масиві бажану початкову клітинку і виводимо, починаючи з неї, всі елементи масиву. Якщо досягли кінця - переходимо на початок.

Це не абсурд, а один з варіантів розв'язування. Для тих, хто знає, що не перевірятиметься алгоритм, а лише наявність шляху. Колись на обласній олімпіаді був випадок: задача виявилась математичною з відповіддю 1/3. Знайшлись учасники, які посиділи з ручкою і листочком, а потім написали writeln (1/3). В правилах олімпіади було наголошено, що журі алгоритму не аналізуватиме.
Bandalak Дата: Чт, 08.12.2016, 00:08 | Повідомлення № 230
Лідер форуму
Повідомлень: 6206
Нагороди: 44
Рейтинг: 285
https://uk.wikipedia.org/wiki....D%D1%8F
Цитата
Спочатку спробуємо з незамкненого маршруту зробити замкнений. Для цього розглянемо, куди можна піти з полів 1 та 60. З поля 1 можна піти на поля 2, 32 і 52, а з 60 — на 29, 51 і 59. У ціх двох наборах є поля, що розрізняються на одиницю, а саме — 51 і 52. Завдяки цьому можна Зробити маршрут замкнутим, звернувши його частини. Для цього пронумеруємо поля з 52 по 60 в зворотному порядку. Після цього у отримуємо замкнений маршрут:

57 54 29 40 27 44 19 22
52 39 56 43 30 21 26 45
55 58 53 28 41 18 23 20
38 51 42 31 8 25 46 17
59 32 37 a 47 16 9 24
50 3 60 33 36 7 12 15
1 34 5 48 b 14 c 10
4 49 2 35 6 11 d 13
Тепер можна включити в маршрут деякі з непройдених клітинок. Оскільки наш маршрут замкнутий, то його можна розірвати в довільному місці і до одного з кінців причепити відповідний ланцюжок з непройдених клітинок. Наприклад, якщо розірвати ланцюжок у клітинці 51 (перенумерувати клітинки і зробивши її останньою, а 52 — першою), то зможемо подовжити наш ланцюжок на клітинки a, b і d, які стануть клітинками 61, 62 і 63.


Мабуть замкнутим є тільки частина маршруту, а не весь.

ЦитатаПилипчук_О_П ()
В російській Вікіпедії один з них є намальований, плюс наведено віршик, в якому закодовано замкнений маршрут.

Хочемо бачити посилання.
Пилипчук_О_П Дата: Чт, 08.12.2016, 08:29 | Повідомлення № 231
Ветеран спілкування
Повідомлень: 4308
Нагороди: 38
Рейтинг: 406
ЦитатаBandalak ()
Мабуть замкнутим є тільки частина маршруту, а не весь.

Частина правильного маршруту не може бути замкнутою, оскільки на всіх клітинках треба побувати 1 раз. У цитаті проілюстровано проміжний етап побудови замкнутого маршруту.
ЦитатаBandalak ()
Хочемо бачити посилання.

https://ru.wikipedia.org/wiki....our.svg
https://ru.wikipedia.org/wiki....D%D1%8F
beregok Дата: Чт, 08.12.2016, 16:57 | Повідомлення № 232
Прописаний назавжди
Повідомлень: 283
Нагороди: 10
Рейтинг: 52
Колись як вчився в школі, 90-ті, грали в ігри на папері: в землі (точки), футбол, морбский бій
Пам'ятаю була така гра заповнити ходом коня поле 10Х10
Я тоді ділив поле на чотири частини (5х5) і по черзі їх проходив конем
Oxana_cher Дата: Чт, 08.12.2016, 22:17 | Повідомлення № 233
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
Цитата Oxana_cher ()
покажу программку завтра после обеда

Работает моментально и с любой начальной позиции!



Цитата beregok ()
ходом коня поле 10Х10

На 10х10 тоже работает. Надо только поменять константу N из 8 на 10.
Прикріплення: Kin_Consol.pas(2.1 Kb)
swetikccc Дата: Пт, 09.12.2016, 10:00 | Повідомлення № 234
Ветеран спілкування
Повідомлень: 4158
Нагороди: 31
Рейтинг: 387
Цитата Oxana_cher ()
Работает моментально и с любой начальной позиции!
А "допомагальникам" коментарі добавити в програму "мона"  ;)
Oxana_cher Дата: Пт, 09.12.2016, 11:39 | Повідомлення № 235
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
Цитата swetikccc ()
А "допомагальникам" коментарі добавити в програму "мона" 

Вот!

Додано (09.12.2016, 11:39)
---------------------------------------------
А здесь второй вариант прграммы

Прикріплення: 2240251.doc(237.0 Kb)
DPV Дата: Пт, 09.12.2016, 16:55 | Повідомлення № 236
Прописаний назавжди
Повідомлень: 475
Нагороди: 7
Рейтинг: 76
Цитата Oxana_cher ()
Прикріплення: 2240251.doc(237Kb)

Опис ходів не відповідає малюнку, чи я помиляюсь?


Відредаговано: DPV - Пт, 09.12.2016, 18:12
Bandalak Дата: Пт, 09.12.2016, 18:27 | Повідомлення № 237
Лідер форуму
Повідомлень: 6206
Нагороди: 44
Рейтинг: 285
Так. Там написано:
hor [] = {2, 1, -1, -2, -2, -1, 1, 2};
ver [] = {-1, -2, -2, -1, 1, 2, 2, 1};

А судячи, по малюнку мало би бути:
hor [] = {1, -1, -2, -2, -1, 1, 2, 2};
ver [] = {-2, -2, -1, 1, 2, 2, 1, -1};

Хоча це на сам процес не впливає. Думаю, що різниці немає
звідки починати пошук можливих ходів.

До речі, у неї в коді самої програми ще інакший порядок ходів:

ver[1]:=-2;hor[1]:=-1;
ver[2]:=-2;hor[2]:=1;
ver[3]:=-1;hor[3]:=-2;
ver[4]:=-1;hor[4]:=2;
ver[5]:=1;hor[5]:=-2;
ver[6]:=1;hor[6]:=2;
ver[7]:=2;hor[7]:=-1;
ver[8]:=2;hor[8]:=1;

Впевнений, що цьому алгоритму глибоко пофіг на порядок пошуку.
Oxana_cher Дата: Пт, 09.12.2016, 19:18 | Повідомлення № 238
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
Цитата DPV ()
Опис ходів не відповідає малюнку, чи я помиляюсь?
Где именно?

Цитата Bandalak ()
До речі, у неї в коді самої програми ще інакший порядок ходів:
А какая разница?
DPV Дата: Пт, 09.12.2016, 19:53 | Повідомлення № 239
Прописаний назавжди
Повідомлень: 475
Нагороди: 7
Рейтинг: 76
Цитата Bandalak ()
Хоча це на сам процес не впливає. Думаю, що різниці немає звідки починати пошук можливих ходів.

Дійсно на сам процес пошуку це не впливає, але в пояснені краще виправити, якщо його десь будуть використовувати надалі, просто змінити малюнок.
Oxana_cher Дата: Пт, 09.12.2016, 20:52 | Повідомлення № 240
Місцева кадра
Повідомлень: 397
Нагороди: 2
Рейтинг: 44
Цитата DPV ()
Дійсно на сам процес пошуку це не впливає, але в пояснені краще виправити, якщо його десь будуть використовувати надалі, просто змінити малюнок.



Так?
Прикріплення: 8887287.jpg(37.8 Kb)
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » Всеукраїнська олімпіада з інформатики (програмування) (Висталяємо завдання та розв'язки)
Пошук:


© Форум інформатиків України, 2007-2019.