|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Моделирование поиска решений арифметических задачдипломная работа (Бакалавр)
- Научный руководитель: Борисенко В.В.
- Автор: Рахматов Рахим Рабиевич
- Тип: Бакалавр
- Организация, в которой проходила защита: Филиал МГУ им. М.В.Ломоносова в г. Душанбе
- Год защиты: 2019
- Аннотация: Работа относится к области моделирования элементов искусственного интеллекта. Первые программы подобного типа реализовывали одну из популярных игр – шахматы, Реверси, Го и т. п. В этих играх компьютерные программы соревнуются с человеком и зачастую переигрывают его. В работе реализована программа для игры «Получить сотню из автобусного билета». Номер автобусного билета содержит 6 цифр, нужно путем расстановки знаков арифметических операций и скобок между некоторыми цифрами билета получить формулу, значением которой является число 100. Например, из номера 123456 сотню можно получить так: (1+2/3)*(4+56)=100. В свое время подобное развлечение было очень популярно и представляло собой хорошее упражнение на сообразительность и умение быстро считать; купив в автобусе билет, люди тотчас же пытались получить из него сотню и соревновались, кто быстрее это сделает. Тогда же было высказано предположение, что из любого номера, содержащего 6 разных цифр и начинающегося не с нуля, можно получить сотню. В работе реализована программа на С++, которая решает эту задачу, причем намного быстрее и эффективнее, чем человек. Также требовалось доказать или опровергнуть высказанную гипотезу. В принципе такую программу можно было бы реализовать путем полного перебора всех деревьев с 6 терминальными вершинами, соответствующих всем арифметическим выражениям. Однако перебор очень большой, он усложняется тем, что помимо четырех арифметических операций есть операция унарного минуса, а также операция приписывания цифры справа к числу. В работе такая программа реализована не путем полного перебора всех деревьев, а с помощью более интеллектуального представления формулы в виде комбинации подформул с использованием идей динамического программирования. Высказанная выше гипотеза опровергнута – программа нашла много номеров, состоящих из шести различных цифр и начинающихся не с нуля, из которых сотню получить не удается. Например, из номеров 103459, 207459, 302456 и др. сотню получить невозможно.
- Добавил в систему: Борисенко Владимир Витальевич