Гра Бики та корови
б) Правила гри самі, але загадується 6-значне число з цифрами від 1 до 9, причому серед цифр допускаються однакові.
Примітка: Запитане число має задовольняти правила для загадуваного; комп'ютеру на хід дається 1 хвилина.
Отже, перше що спадає на думку грати за таким правилом: називати перше що потрапило число, яке може бути задумана, тобто. при зіставленні будь-якого раніше запитаного числа з новим повинно вийде така ж кількість 'биків' і 'корів'. Число будемо представляти у вигляді масиву цифр.>
(Прим. вебмайстра - перепрошую за помилки у вихідниках: їх становив не я. Сподіваюся, Вам не важко відновити правильні програми за алгоритмами.)
Отже, наша програма працює наступним чином: ми шляхом послідовного збільшення на 1 генеруємо всі можливі 6-значні числа, відбираємо серед них ті, в яких всі цифри різні, і, нарешті, ті з них, які задовольняють відповідям, що зберігаються в масиві Info, задається користувачеві як питання. Виникає низка резонних питань: скільки всього цікавих для нас 4-значних цифр і яка їх частина не містить повторень.
За скільки кроків може вгадати відповідь найшвидший алгоритм і наскільки гарна наша стратегія?
Спробуємо відповісти на них. Тож скільки всього чисел? Нехай k цифр та m позицій. У першій позиції може стояти будь-яка
З k цифр, що дає k варіантів. У другій-кожна з k цифр, тобто. k 2 . І так далі m разів, тобто. всього k m варіантів. Узагальним цю ідею.
Визначення: розміщення з n повторенням з k елементів m називається m-елементний масив натуральних чисел, кожне з яких не перевищує k.
Твердження: Число розміщень з повтореннями з k до m дорівнює k m . Доведенняпроводимо за індукцією:
Базис індукції: При m=1 ми рівно k варіантів.
Індуктивний перехід: Нехай твердження правильне за m=n-1. Доведемо, що воно вірне за m=n. Зафіксуємо число 1. Праворуч до цього числа припишемо k n=1 розміщень з k по n-1. Аналогічно надійдемо з 1,2,3. k. Отримаємо k n-1 * k = k n варіантів.
Таким чином, число 4-значних чисел з цифрами від 1 до 6 дорівнює 64 = 1296. Тепер подивимося, скільки з них не містить цифр, що повторюються.
Визначення: розміщенням з k елементів m називається m-елементний масив кожна компонента якого не перевищує k і серед них не зустрічаються однакові. Очевидно, що безліч розміщень не порожня лише при m
Таким чином, число 4-значних чисел з цифрами від 1 до 6 без повторень дорівнює A46 = 6 * 5 * 4 * 3 = 360, тобто. у 3 рази менше, ніж кількість варіантів, які ми перебирали. Отже ми знайшли один спосіб для оптимізації нашої програми: генерувати не всі числа, а лише ті, які не містять цифр, що повторюються. Візьмемо це на замітку, а зараз спробуємо оцінити максимальну кількість кроків, за які відгадує найкращий гравець. Варіантів відповіді у нас:
Нехай угадано 4 цифри. Серед них може бути 2,1,0 "биків". Нехай вгадано 3 цифри. Серед них може бути 3,2,1,0 "биків". І так далі: отримуємо 3+4+2+1=10 варіантів.
Таким чином, за кожне запитання кількість допустимих чисел зменшується, якщо ми розглядаємо найгірший випадок, не більше ніж у 10 разів. Число кроків, за які вгадує найкращий гравець, не менше ніж [log 10 360]+1=3
А тепер спробуємо підвищити ефективність роботи програми. Як було зазначено вище, нам досить перебрати не 1096 комбінацій, а лише 360. Не позначиться на швидкості вгадування, тобто. числа кроків, тому що не змінимо стратегії "перший, що трапився звідповідних", але зменшить час обмірковування ходу.
Генерувати числа будемо наступним чином: для початку виберемо безліч цифр, що в нього входить, а потім переставлятимемо елементи цієї множини між собою. Безліч цифр зручно, для наших цілей, подати у вигляді масиву довжини 4, елементи якого розташовані в порядку зростання. Будемо генерувати ці масиви у лексикографічному порядку, тобто. спочатку порівнюються перші цифри, якщо вони рівні – другі, і так далі. Тобто: