- •Зміст пояснювальної записки
- •Постановка задачі Організаційно-інформаційна сутність задачі [1]
- •Математична модель задачі [1]
- •Опис методів розв’язання задачі Метод гілок та границь
- •Алгоритм гілок і границь [1]
- •Зображення даних в оперативній пам’яті [2]
- •Опис алгоритму програмного модуля [2]
- •Оцінка складності алгоритму
- •Метод решета [2]
- •Алгоритм решета [2]
- •Зображення даних в оперативній пам’яті [2]
- •Опис алгоритму програмного модуля [2]
- •Оцінка складності алгоритму
- •Опис програми Методи та засоби розробки програми
- •Сценарій роботи програми
- •Функціональна структура програми Специфікація модулів
- •Специфікація функцій
- •Технологія створення програми
- •Опис алгоритму методу[2]
- •Алгоритм програми
- •Вхідні та вихідні тести
- •Опис алгоритму методу
- •Алгоритм програми
- •Опис алгоритму методу
- •Алгоритм програми
- •Висновок.
- •Список використаної літератури.
- •Додаток 1 cd та опис його змісту
Вхідні та вихідні тести
Користувач вводить з клавіатури кількість биків та корів, загаданої комбінації цифр. Програма визначає цю комбінацію цифр за обмежену кількість спроб.
Приклад 1:
Користувач загадав число:
Програма за 6 спроб визначила комбінацію цифр
Приклад 2(модифікована):
Користувач загадав число:
Програма за 7 спроб визначила комбінацію цифр
Опис алгоритму методу
Алгоритм полягає у побудові послідовності всіх можливих чисел (від 0123 до 9876) та відсіюванні (метод решета) непідходящих після кожної спроби відгадування. Побудувавши послідовність таких чисел, кількість яких ставноить (у програмі зберігаються у двовимірному масиві ), ми також заповнюємо булевий масив allVariantsChecks[5040], який по замовчуванню заповнюємо значеннями true, цей масив, показує чи відповідна (по індексу) чотрицифрова комбінація з може бути правильним рішенням. До першої спроби відгадати число, всі елементи будуть рівними true, після першої спроби програми відгадати число (перше число, яке називає програма в нашому випадку завжди рівне 1234), коли користувач введе кількість биків і корів для 1234 і свого загаданого числа, програма проведе розрахунок для всіх варіантів четвірок, і якщо кількість корів і кількість биків для якоїсь n-тої четвірки не співпадає, то відповідний . Наступним ходом компьютера буде n-та четвірка з allVariants[n][4] де це найменший індекс, такий що . Після чого користувач у відповідь на спробу програми відгадати число, знову вводить кількість биків і корів. Програма, отримавши нові значення биків і корів, перебирає тепер лише ті варіанти з , які відмічені у і знову рахує для них кількість биків і корів, присвоюючи , якщо ця кількість не відповідає введеній користувачем. Таким чином, з кожною спробою лишається все менше і менше четвірок, котрі задовольняють всім підказкам користувача, і на решті, якщо користувач ніде не помилився, на ітерації меншій десяти програма виведе загадане користувачем число.
Підрахунок биків і корів для цього випадку дуже простий, спочатку ми рахуємо биків, тобто в циклі від 1 до 4 позиції порівнюємо цифри виведеного програмою і вибраного з решти можливих числа, якщо числа рівні, і позиція співпадає, то кількість биків збільшуємо на 1, далі, якщо кількість биків, все ще рівна кількості биків введеній користувачем програми, починаємо аналіз корів, інакше, відкидаємо вибране число з можливих, відмічаючи у масиві його непридатність виставивши відповідний елемент масиву значення . Для аналізу корів нам знадобиться більше операцій, так як необхідно знайти одинакові цифри, що стоять на різних позиціях, для цього була написана допоміжна функція , де – четвірка цифр що перевіряється, element – одна з цифр виведеної комп’ютером четвірки, – позиція, на якій міститься element у виведеній комп’ютером четвірці. Якщо, повертає , і ми збільшуємо кількість корів на одиницю. Якщо для якоїсь четвірки цифр з усіх можливих співпадає кількість биків і корів, то ми вважаємо таку четвірку претендентом на вірну відповідь, і відмічаєм її індекс у значенням інакше – .
Модифікація задачі Суханова[2]. Хоча дана гра і має менше комбінацій замість , ускладнюється підрахунок биків і корів, за рахунок можливих повторень цифр. Програмна реалізація даної гри дещо складніша за попередньою.
Так само як і в попередньому випадку ми заповнюємо масив четвірок всіма можливими комбінаціями від , до першого ходу заповнюємо масив allVariantsChecks значеннями . Користувач загадує число, комп’ютер видає першу спробу , після чого користувач вводить кількість биків і корів для цього числа. Потім здійснюється підрахунок биків і корів для кожної з 1296 четвірок, і виставляється [i] значеннями , для яких кількість биків і корів не співпадає. Після чого комп'ютер перебираючи вcі четвірки виводить у якості наступного варіанту першу, для якої , користувач знову вводить кількість биків і корів, компьютер знову «просіює» варіанти, що лишилися на предмет їх відповідності, і так продовжується до тих пір, поки не буде знайдене вірне рішення.
Відмінність з попередньою задачею полягає у підрахунку биків і корів. Ми так само рахуємо биків, але якщо нам трапляється бик, то його позицію в числі ми відмічаємо у допоміжному масиві bool skipDigits[4] (всі елементи якого початково ініціалізуються значенням false), значенням true. Відмінність у підрахунку корів полягає в тому, що корів, ми шукаємо не по всім чотирьом позиціям, а лише по тим позиціям на яких нема бика.