Версия 11:54, 11 сентября 2012

Гіпермаркет Знань>>Інформатика>>Інформатика 6 клас>>Інформатика: Досягни мети першим

Досягни мети першим

Математики різних часів і народів намагалися створити  алгоритми для перемоги в різноманітних іграх. Одні робили це з чисто наукового інтересу, інші — з надією розбагатіти завдяки перемозі в азартних іграх, особливо іграх в карти. Математики сподівалися розбагатіти, використовуючи у своїй грі надійні алгоритми.

Виявляється, що не для будь-якої гри можна скласти алгоритм, який завжди забезпечить перемогу. Це стосується тих ігор, хід яких залежить від випадкових подій (наприклад, ігор у карти), а також ігор, в яких кількість можливих варіантів надзвичайно велика (наприклад, шахи).

Проте є багато ігор, повністю досліджених. Для них існують алгоритми-стратегії, користуючись якими можна завжди перемогти, незалежно від дій суперника. Можна також, не розпочинаючи гру, визначити, що при заданих початкових умовах і правильних діях суперника перемогти неможливо.

Розглянемо один з прикладів такої гри.

Є горизонтальний ряд з 15 клітинок. У крайній лівій клітинці стоїть фішка. У грі беруть участь двоє гравців, які роблять хід по черзі. За один хід можна пересунути фішку вправо па одну, дві або три клітинки. Виграє той, хто поставить фішку в крайню праву клітинку.

Для зручності, пронумеруємо клітинки зліва направо числами від 1 до 15.

Щоб перемогти, необхідно своїм ходом поставити фішку в 15-у клітинку. Оскільки пересувати фішку можна на одну, дві або три клітинки, хід у 15-у клітинку може бути зроблений або з 14-ї, або з 13-ї, або з 12-ї клітинки. Отже, необхідно примусити суперника поставити фішку в одну з цих трьох клітинок. А для цього ми повинні свій попередній хід зробити в 11-у клітинку.

Дійсно, якщо фішка знаходиться в 11-й клітинці, то, за правилами гри, суперник може зробити з неї хід тільки в 12-у, 13-у або 14-у клітинку. Отже, якщо передостаннім ходом ми поставимо фішку в 11-у клітинку, то при будь-якому ході-відповіді суперника ми зможемо поставити фішку в 15-у клітинку і перемогти.

Міркуємо аналогічним чином далі.

Для того, щоб за будь-яких обставин ми мали змогу поставити фішку в 11-у клітинку, вона повинна перед нашим ходом знаходитись або в 10-й, або в 9-й, або у 8-й клітинці. Тобто, ми повинні змусити суперника поставити фішку в одну з цих трьох клітинок. А для цього своїм иопсреднімходом нам необхідно поставити фішку в 7-у клітинку. Тоді, якщо суперник пересуне фішку па одну клітинку, ми пересунемо її на 3; якщо він пересуне фішку на 2 клітинки, ми пересунемо її теж на 2; якщо ж він пересуне фішку на 3 клітинки, ми пересунемо її на 1. При такому алгоритмі гри фішка обов'язково опиниться в 11-й клітинці.

Проводячи аналогічні міркування, бачимо, що для того, аби ми змогли зробити хід у 7-у клітинку, свій попередній хід ми повинні, зробити в 3-ю клітинку. А цю клітинку ми можемо зайняти фішкою вже першим ходом, якщо він наш. Для цього треба пересунути першим ходом фішку на 2 клітинки.

З наведених вище міркувань випливає, що існують клітинки, послідовно займаючи які, ми наближатимемося до перемоги, незалежно від ходів нашого суперника. Такими є 3-я, 7-а, 11-а і 15-а клітинки. Назвемо умовно їх виграшними.

Відстані між послідовними виграшними клітинками однакові і дорівнюють 4. Тому наш хід-відповІдь на хід суперника повинен бутті таким, щоб сума відстаней двох ходів (ходу суперника та нашого ходу-відповіді) становила 4 клітинки.

Отже, гравець, який починає гру, завжди переможе, якщо використає такий алгоритм:
1. Пересунути першим ходом фішку на 2 клітинки.
2. Поки не досягнемо останньої клітинки, якщо суперник пересунув фішку па х клітинок, пересунути її на (4 — х) клітинок.

Проводячи аналогічні міркування, визначте виграшні клітинки і алгоритм гри, якщо довжина поля 16 клітинок.

Дещо інша ситуація виникне, якщо довжина поля 17 клітинок. Міркуючи аналогічно, з'ясовуємо, що виграшними є клітинки 17-а, 13-а, 9-а, 5-а і 1-а. Але гравець, який ходить першим, не може зробити хід ні в 1-у, ні в 5-у клітинку. Це означає, що в цій грі для нього виграшної стратегії не існує. Він може виграти тільки тоді, коли ного суперник деяким своїм ходом не займе одну з виграшних клітинок.

Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 18,19, 20, 30 клітинок.

Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 15, 16,17,18,19, 20, 30 клітинок і гравець за один хід може пересунути фішку на одну, дві, три або чотири клітинки.

Ломаковська Г.В., Колесніков С.Я., Ривкінд Й.Я. Інформатика 6 клас

Вислано читачаму з інтернет-сайту

_{Книги, підручники інформатики, шкільний план, відкритий урок з інформатики}

Зміст уроку
 конспект уроку і опорний каркас                      
 презентація уроку 
 акселеративні методи та інтерактивні технології
 закриті вправи (тільки для використання вчителями)
 оцінювання 

Практика
 задачі та вправи,самоперевірка 
 практикуми, лабораторні, кейси
 рівень складності задач: звичайний, високий, олімпійський
 домашнє завдання 

Ілюстрації
 ілюстрації: відеокліпи, аудіо, фотографії, графіки, таблиці, комікси, мультимедіа
 реферати
 фішки для допитливих
 шпаргалки
 гумор, притчі, приколи, приказки, кросворди, цитати

Доповнення
 зовнішнє незалежне тестування (ЗНТ)
 підручники основні і допоміжні 
 тематичні свята, девізи 
 статті 
 національні особливості
 словник термінів                          
 інше 

Тільки для вчителів
 ідеальні уроки 
 календарний план на рік 
 методичні рекомендації 
 програми
 обговорення

Если у вас есть исправления или предложения к данному уроку, напишите нам.

Если вы хотите увидеть другие корректировки и пожелания к урокам, смотрите здесь - Образовательный форум.