KNOWLEDGE HYPERMARKET


ДОСЯГНИ МЕТИ ПЕРШИМ
Строка 1: Строка 1:
'''[[Гіпермаркет Знань - перший в світі!|Гіпермаркет Знань]]&gt;&gt;[[Інформатика|Інформатика]]&gt;&gt;[[Інформатика 6 клас|Інформатика 6 клас]]&gt;&gt;Інформатика: Досягни мети першим'''<metakeywords>Інформатика, клас, урок, на Тему, Досягни мети першим</metakeywords>  
'''[[Гіпермаркет Знань - перший в світі!|Гіпермаркет Знань]]&gt;&gt;[[Інформатика|Інформатика]]&gt;&gt;[[Інформатика 6 клас|Інформатика 6 клас]]&gt;&gt;Інформатика: Досягни мети першим'''<metakeywords>Інформатика, клас, урок, на Тему, Досягни мети першим</metakeywords>  
-
ДОСЯГНИ МЕТИ ПЕРШИМ
+
'''Досягни мети першим'''
-
<br>Математики різних часів і народів намагалися створити алгоритми для перемоги в різноманітних іграх. Одні робили це з чисто наукового інтересу, інші — з надією розбагатіти завдяки перемозі в азартних іграх, особливо іграх в карти. Математики сподівалися розбагатіти, використовуючи у своїй грі надійні алгоритми.  
+
Математики різних часів і народів намагалися створити &nbsp;[http://school.xvatit.com/index.php?title=%D0%A2%D0%B5%D0%BC%D0%B0_28._%D0%9F%D0%BE%D0%BD%D1%8F%D1%82%D1%82%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%83. алгоритми] для перемоги в різноманітних іграх. Одні робили це з чисто наукового інтересу, інші — з надією розбагатіти завдяки перемозі в азартних іграх, особливо іграх в карти. Математики сподівалися розбагатіти, використовуючи у своїй грі надійні [http://school.xvatit.com/index.php?title=%D0%A2%D0%B5%D0%BC%D0%B0_28._%D0%9F%D0%BE%D0%BD%D1%8F%D1%82%D1%82%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%83. алгоритми].  
<br>Виявляється, що не для будь-якої гри можна скласти алгоритм, який завжди забезпечить перемогу. Це стосується тих ігор, хід яких залежить від випадкових подій (наприклад, ігор у карти), а також ігор, в яких кількість можливих варіантів надзвичайно велика (наприклад, шахи).  
<br>Виявляється, що не для будь-якої гри можна скласти алгоритм, який завжди забезпечить перемогу. Це стосується тих ігор, хід яких залежить від випадкових подій (наприклад, ігор у карти), а також ігор, в яких кількість можливих варіантів надзвичайно велика (наприклад, шахи).  
-
<br>Проте є багато ігор, повністю досліджених. Для них існують алгоритми-стратегії, користуючись якими можна завжди перемогти, незалежно від дій суперника. Можна також, не розпочинаючи гру, визначити, що при заданих початкових умовах і правильних діях суперника перемогти неможливо.  
+
<br>Проте є багато ігор, повністю досліджених. Для них існують [http://school.xvatit.com/index.php?title=%D0%A2%D0%B5%D0%BC%D0%B0_28._%D0%9F%D0%BE%D0%BD%D1%8F%D1%82%D1%82%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%83. алгоритми]-стратегії, користуючись якими можна завжди перемогти, незалежно від дій суперника. Можна також, не розпочинаючи гру, визначити, що при заданих початкових умовах і правильних діях суперника перемогти неможливо.  
<br>Розглянемо один з прикладів такої гри.  
<br>Розглянемо один з прикладів такої гри.  
Строка 21: Строка 21:
<br>Міркуємо аналогічним чином далі.  
<br>Міркуємо аналогічним чином далі.  
-
<br>Для того, щоб за будь-яких обставин ми мали змогу поставити фішку в 11-у клітинку, вона повинна перед нашим ходом знаходитись або в 10-й, або в 9-й, або у 8-й клітинці. Тобто, ми повинні змусити суперника поставити фішку в одну з цих трьох клітинок. А для цього своїм иопсреднімходом нам необхідно поставити фішку в 7-у клітинку. Тоді, якщо суперник пересуне фішку па одну клітинку, ми пересунемо її на 3; якщо він пересуне фішку на 2 клітинки, ми пересунемо її теж на 2; якщо ж він пересуне фішку на 3 клітинки, ми пересунемо її на 1. При такому алгоритмі гри фішка обов'язково опиниться в 11-й клітинці.  
+
<br>Для того, щоб за будь-яких обставин ми мали змогу поставити фішку в 11-у клітинку, вона повинна перед нашим ходом знаходитись або в 10-й, або в 9-й, або у 8-й клітинці. Тобто, ми повинні змусити суперника поставити фішку в одну з цих трьох клітинок. А для цього своїм иопсреднімходом нам необхідно поставити фішку в 7-у клітинку. Тоді, якщо суперник пересуне фішку па одну клітинку, ми пересунемо її на 3; якщо він пересуне фішку на 2 клітинки, ми пересунемо її теж на 2; якщо ж він пересуне фішку на 3 клітинки, ми пересунемо її на 1. При такому [http://school.xvatit.com/index.php?title=%D0%A2%D0%B5%D0%BC%D0%B0_28._%D0%9F%D0%BE%D0%BD%D1%8F%D1%82%D1%82%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%83. алгоритмі] гри фішка обов'язково опиниться в 11-й клітинці.  
-
<br>Проводячи аналогічні міркування, бачимо, що для того, аби ми змогли зробити хід у 7-у клітинку, свій попередній хід ми повинні -, зробити в 3-ю клітинку. А цю клітинку ми можемо зайняти фішкою вже першим ходом, якщо він наш. Для цього треба пересунути першим ходом фішку на 2 клітинки.  
+
<br>Проводячи аналогічні міркування, бачимо, що для того, аби ми змогли зробити хід у 7-у клітинку, свій попередній хід ми повинні, зробити в 3-ю клітинку. А цю клітинку ми можемо зайняти фішкою вже першим ходом, якщо він наш. Для цього треба пересунути першим ходом фішку на 2 клітинки.  
-
<br>З наведених вище міркувань випливає, що існують клітинки, пос-лідонно займаючи які, ми нпевгіепо наближатимемося до перемоги, незалежно від ходів нашого суперника. Такими є 3-я, 7-а, 11-а і 15-а клітинки. Назвемо умовно їх виграшними.  
+
<br>З наведених вище міркувань випливає, що існують клітинки, послідовно займаючи які, ми наближатимемося до перемоги, незалежно від ходів нашого суперника. Такими є 3-я, 7-а, 11-а і 15-а клітинки. Назвемо умовно їх виграшними.  
<br>Відстані між послідовними виграшними клітинками однакові і дорівнюють 4. Тому наш хід-відповІдь на хід суперника повинен бутті таким, щоб сума відстаней двох ходів (ходу суперника та нашого ходу-відповіді) становила 4 клітинки.<br><br>Отже, гравець, який починає гру, завжди переможе, якщо використає такий алгоритм:<br>1. Пересунути першим ходом фішку на 2 клітинки.<br>2. Поки не досягнемо останньої клітинки, якщо суперник пересунув фішку па х клітинок, пересунути її на (4 — х) клітинок.<br><br>Проводячи аналогічні міркування, визначте виграшні клітинки і алгоритм гри, якщо довжина поля 16 клітинок.  
<br>Відстані між послідовними виграшними клітинками однакові і дорівнюють 4. Тому наш хід-відповІдь на хід суперника повинен бутті таким, щоб сума відстаней двох ходів (ходу суперника та нашого ходу-відповіді) становила 4 клітинки.<br><br>Отже, гравець, який починає гру, завжди переможе, якщо використає такий алгоритм:<br>1. Пересунути першим ходом фішку на 2 клітинки.<br>2. Поки не досягнемо останньої клітинки, якщо суперник пересунув фішку па х клітинок, пересунути її на (4 — х) клітинок.<br><br>Проводячи аналогічні міркування, визначте виграшні клітинки і алгоритм гри, якщо довжина поля 16 клітинок.  
Строка 33: Строка 33:
<br>Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 18,19, 20, 30 клітинок.  
<br>Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 18,19, 20, 30 клітинок.  
-
<br>Визначте виграшні клітинки і алгоритм гри, якщо довжина поля 15, 16,17,18,19, 20, 30 клітинок і гравець за один хід може пересунути фішку на одну, дві, три або чотири клітинки.<br>  
+
<br>Визначте виграшні клітинки і [http://school.xvatit.com/index.php?title=%D0%A2%D0%B5%D0%BC%D0%B0_28._%D0%9F%D0%BE%D0%BD%D1%8F%D1%82%D1%82%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%83. алгоритм] гри, якщо довжина поля 15, 16,17,18,19, 20, 30 клітинок і гравець за один хід може пересунути фішку на одну, дві, три або чотири клітинки.<br>  
<br>  
<br>  

Версия 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 клас

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


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


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

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

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

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

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


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

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