Игра Быки и коровы

Как растут функции или эффективные алгоритмы

Наигравшись, стоит немного заняться математикой, связанной с этой задачей. Давайте рассмотрим три функции:

F1(n) = Log(n); F2(n) = n; F3(n) = 2n

Эти функции соответственно называются: логарифмической, линейной, экспоненциальной. Они часто появляются в самых разных задачах, связанных с программированием. Хорошо бы понимать, как ведут себя эти функции, как они растут при изменении аргумента n. Когда n мало, то значения функций не сильно отличаются. Например, при n, равном три, все значения находятся в пределах десяти. При n, равном десяти, разность между линейной и логарифмической функцией все еще находится в пределах десятка, но экспоненциальная функция превосходит линейную функцию уже в сто раз. С ростом n экспонента взмывает как ракета и уходит в небеса. При n, равном 100, 2¹⁰⁰– это невообразимо большое число, превосходящее число атомов в нашей вселенной. Но также как экспонента превосходит линейную функцию, так линейная функция превосходит логарифмическую. Например, при n, равном одному миллиону, значение логарифмической функции близко к двадцати.

Какое отношение это имеет к алгоритмам? Самое прямое. Если число операций задается логарифмической функцией, то человек может справиться с задачей даже при больших значениях n, например, равных миллиону. Если число операций определяется линейной функцией, то человек уже не в состоянии выполнить такое количество операций, но компьютер легко справится с такой задачей. Когда же число операций задается экспоненциальной функцией, то эта задача не по силам компьютеру уже при значениях n, больших 30 – 40.

Вернемся к нашей задаче поиска задуманного числа. Существует ли более простой алгоритм, чем тот, который был реализован при поиске задуманного числа компьютером. Конечно, есть простой переборный алгоритм. Перебираем число за числом в заданном интервале, пока не наткнемся на задуманное число. Число операций в таком алгоритме определяется линейной функцией. Как нам понятно, переборный алгоритм в нашей игре можно применять, только тогда, когда задуманное число находится в малом интервале, содержащем не более одного, двух десятков чисел. Когда в интервале чисел миллион, человек не может найти задуманное число, применяя переборный алгоритм. Ему может помочь только алгоритм бинарного поиска, число операций в котором определяется логарифмической функцией.

А встречаются ли в программировании задачи, например, игры, в которых число операций задается экспонентой? В математике существует много легенд, связанных с экспонентой, ее взрывным ростом, не заметным при малых значениях. Давайте познакомимся с игрой "Ханойские башни". Вот цветистое описание этой игры:

В величественном храме Бенареса под куполом, отмечающим центр мира, на медной плите установлены три бриллиантовых стержня. Каждый стержень, высотой в локоть, и тонок, как пчелиная талия. На один из этих стержней в начале мироздания Бог поместил 64 диска из чистого золота. Самый большой диск покоится на медной плите, а остальные, друг друга меньше, создают пирамиду, подымающуюся к вершине стержня. Это и есть священная башня Брахмы.

Ночью и днем неустанно священники, сменяя друг друга, работают, чтобы перенести священную башню на третий бриллиантовый стержень, не нарушив при этом священных правил, установленных Брахмой. Когда их работа будет закончена, падет башня, падут брахманы и наступит конец мира.

Правило Брахмы требует, чтобы при переносе колец на всех стержнях присутствовала пирамида. Это означает, что нельзя положить диск поверх диска меньшего размера. Нетрудно решить эту задачу, когда число дисков равно трем, - понадобится всего семь перекладываний. Когда в детстве я играл в эту игру, то дисков было 6 или 7. За несколько минут я мог решить поставленную задачу. А как обстоит дело с брахманами, которые работают уже несколько сотен лет. Скоро ли они закончат свою работу и наступит конец мира? Можно не беспокоиться. Их работа не будет закончена в обозримом будущем, скорее погаснет наше солнце. Дело в том, что число перекладываний определяется экспонентой, оно равно 2ⁿ– 1. При n, равном 64, число перекладываний равно 2⁶⁴, что примерно равно $$$2\cdot10^{19}$$$. Это огромное число. Не только человек, но и ни один компьютер не может справиться с этой задачей.

Сегодня все развитые страны соревнуются в построении суперкомпьютера, работающего с экзафлопной производительностью, то есть способного выполнять 10¹⁸операций в секунду. Но и такой суперкомпьютер не справится с нашей задачей. Дело в том, что суперкомпьютеры обладают столь высокой производительностью за счет того, что у них миллионы параллельно работающих ядер. Но задача "Ханойские башни" не допускает параллельного решения. Золотые диски нужно перекладывать последовательно. Поэтому только одно ядро суперкомпьютера будет участвовать в решении задач и жизни многих поколений не хватит компьютеру, чтобы справиться с задачей.

Какой вывод следует из наших рассмотрений? Когда мы строим наши алгоритмы, то иногда приходится думать о построении эффективных алгоритмов. Алгоритм бинарного поиска эффективнее алгоритма полного перебора.

На этом разбор этого проекта закончим и перейдем к рассмотрению следующей игры на эту же тему.

Игра "Быки и коровы"

В этой игре также, как и в предыдущей, компьютер загадывает число из некоторого интервала, а игрок должен отгадать заданное число за K вопросов, чтобы получить звание "Магистр игры". Игра более сложная, поскольку компьютеру можно задавать вопрос только одного типа: "Задуманное число равно N?". Число N имеет столько же цифр, как и задуманное число. В ответ на вопрос компьютер сообщает сколько в предъявленном числе N быков и сколько коров. Быком называется цифра числа N, совпадающая по значению и по месту с цифрой задуманного числа. Корова – это цифра, совпадающая по значению, но не совпадающая по месту. Рассмотрим пару чисел, в которой первым является задуманное число, а вторым числом пары является предъявляемой число N. Для пары чисел (1254, 5237) ответом будет "один бык, одна корова". Число отгадано, когда все цифры предъявленного числа являются быками.

В определении коровы есть момент, допускающий неоднозначное толкование. Рассмотрим следующую пару чисел (1254, 2222). В этой ситуации возможны два ответа: "один бык и три коровы" и "один бык и ноль коров". В нашем алгоритме правильным считается второй ответ. Если некоторая цифра отождествлена с быком, то она не участвует в поисках коров.

Рассмотрим интерфейс игры:

Можно видеть, что во-многом интерфейс схож с интерфейсом предыдущей игры. Давайте рассмотрим логику рассуждений, приведшую к разгадке задуманного числа. Поскольку вначале никакой информации нет, то предлагается любое число из трех цифр, в данном случае 123. Из ответа ясно, что одна из этих цифр присутствует в задуманном числе, причем стоит на своем месте. Перестановка цифр дает дополнительную информацию. Из ответа на второй вопрос ясно, что цифры 3 в задуманном числе нет, поэтому кандидатом является либо цифра 1, либо 2. Из ответа на третий вопрос становится ясно, что быком является цифра 2. Поэтому далее испытываются оставшиеся цифры. Из ответов на 4-й и 5-й вопросы следует, что в задуманном числе нет цифр 4, 5, 6, 7. Из ответа на 6-й вопрос следует, что в задуманном числе могут быть цифры 0, 8, 9, стоящие на первом и третьем месте. Проба 920 оказалась решающей, поиск завершился успехом.

Способ рассуждений понятен человеку, и он может успешно решать поставленную задачу, создавая разумную комбинацию, зависящую от ответов компьютера. Так что человек разумный вполне может стать Магистром игры. А можно ли написать программу для компьютера столь же эффективную, как и для предыдущей игры, где компьютер не проигрывает человеку. Ответ не очевиден.

Давайте рассмотрим, как устроен код нашей игры. Начнем с рассмотрения переменных.

Переменные и константы игры

Искусство программирования состоит в том, чтобы придумать, спроектировать алгоритм, решающий задачу. Не менее важной, дополняющей стороной этого процесса является умение спроектировать необходимую структуру данных, с которой и работает алгоритм. Как видите, для нашей, не простой, но и не слишком сложной задачи требуется определить более десятка переменных и большое количество констант, поддерживающих вывод разумных ответов, понятных пользователю.

Поскольку данная игра во многом совпадает с предыдущей, то и можно отметить существенное пересечение списков констант и переменных в обеих играх. Вот список переменных и констант, используемых в данной игре:

//переменные, необходимые для организации игры
        int level_game;             //уровень игры
        Random rnd = new Random();  //генератор случайных чисел
        int digits;             //число цифр в задуманном числе
        int min;                //минимальное значение задуманного числа
        int max;                //максимальное значение задуманного числа
        int number;             //задуманное число
        int N;                  //число вопросов для звания Магистр
        int answer;             //текущий ответ
        int ox_n;               //число быков  в текущем ответе
        int cow_n;              //число коров  в текущем ответе        
        int countQuestion = 0; //текущее число заданных вопросов
        string question;        //очередной вопрос

        //константы для организации диалога
        const string ANSW =
               "Я задумал число в замкнутом интервале [";
        const string ANSW1 =
            "Если отгадаешь число за ";
        const string ANSW2 =
            " вопросов, - станешь Магистром игры!\r\n";
        const string ANSW3 =
            "Ответом на вопрос является число быков и число коров!\r\n";
        const string ANSW31 =
            "Бык -цифра в ответе, совпадающая по месту и значению" +
            " с цифрой в задуманном числе!\r\n";
        const string ANSW32 =
            "Корова -цифра в ответе, совпадающая только по значению" +
            " с цифрой в задуманном числе!\r\n";
        const string ANSW33 =
            "Если в твоем ответе все цифры - быки, " +
            " то ты отгадал задуманном число!\r\n";
        const string ANSW4 =
            "Поздравляю! Вы Магистр игры!\r\n";
        const string ANSW44 = "Ваш уровень - ";
        const string ANSW5 = "Вы угадали! Я задумал число ";

Как компьютер задумывает число в данной игре

Ранее мы уже объясняли, как генерируются случайные равномерно распределенные числа в некотором заданном интервале. Разбирался также код, позволявший генерировать число в предыдущей игре. В данной игре ситуация схожа. По-другому формируется интервал, используемый для генерирования "задуманного числа". По-другому рассчитывается число вопросов, достаточных для получения звания "Магистр игры". Но в целом приводимый ниже код должен быть понятен без особых пояснений:

/// <summary>
        /// Компьютер задумывает число и определяет N
        /// число вопросов, достаточное для отгадывания
        /// и получения звания Магистр игры
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void buttonThink_Click(object sender, EventArgs e)
        {
            //Анализ уровня игры
            //определяет интервал, 
            //в котором находится задуманное число
            level_game = int.Parse(textBoxLevelGame.Text);
            //ограничение уровня
            if (level_game > 5) level_game = 5;
             
            //число цифр в задуманном числе зависит от уровня
            digits = level_game + 2;
            min = (int)Math.Pow(10, digits - 1);
            max = min * 10 - 1;

            //задуманное случайное число             
              number = rnd.Next(min, max);
            
            //Число вопросов для звания магистр
            N = (level_game + 2) * 5;
            
            //Вывод ответа компьютера о задуманном числе
            //и числе вопросов для звания магистр
            textBoxMin.Text = min.ToString();
            textBoxMax.Text = max.ToString();
            string answer = ANSW + min + ", " + max + "]\r\n" +
                ANSW1 + N + ANSW2 + ANSW3 + ANSW31 + ANSW32 + ANSW33;
            textBoxAnswer.Text = answer;
        }

Как компьютер отвечает на вопрос "Задуманное равно N?"

Общая схема обработчика события Click соответствующей командной кнопки понятна, - читается число N, вызывается функция, подсчитывающая число быков и коров в числе N, формируется ответ, который и выводится в соответствующее окно. Вот код этого обработчика события:

private void buttonEqual_Click(object sender, EventArgs e)
        {
            countQuestion++;
            question = countQuestion.ToString() + ". ";
            question += "Число равно ";
            answer = int.Parse(textBoxE.Text);
            if (answer < min || answer > max)
            {
                textBoxResult.Text += "Введенное число вне интервала!";
                return;
            }
            question += answer + "?";
            question += OxAndCow();
            listBoxQA.Items.Add(question);
            if (ox_n == digits)
            {
                if (countQuestion <= N)
                    textBoxResult.Text = ANSW4 + ANSW44 + level_game +
                        "!\r\n" + ANSW5 + number;
                else
                    textBoxResult.Text = ANSW5 + number;
            }
        }

Как считать быков и коров

Прежде, чем считать быков и коров, сравнивая два числа, эти числа разбираются на цифры и числа представляются массивами, каждый элемент которых представляет отдельную цифру. Такое представление позволяет достаточно просто и понятно решать поставленную задачу, сравнивая отдельные цифры. Важно отметить, что, когда некоторые цифры получают статус "быка" или "коровы", то они уже не участвуют в дальнейшем рассмотрении. В программе это достигается за счет того, что цифры получают значение -1, невозможное для настоящей цифры.

Вот соответствующий код:

/// <summary>
        /// Подсчет числа быков и коров, используя
        /// number - задуманное число и
        /// answer - текущий ответ
        /// </summary>
        /// <returns>строку с числом быков и коров в ответе </returns>
        string OxAndCow()
        {
            string res = "";
            ox_n = 0;
            cow_n = 0;
            int[] ar_number = new int[digits];
            int[] ar_answer = new int[digits];

            //Расщепление на цифры
            ar_number = Split(number, digits);
            ar_answer = Split(answer, digits);

            //Подсчет быков
            for(int i = 0; i < digits; i++)
            {
                if ( ar_answer[i] == ar_number[i])
                {
                    ox_n++;
                    ar_number[i] = -1;  //бык найден
                    ar_answer[i] = -1;
                } 
            }

            //Подсчет коров
            for (int i = 0; i < digits; i++)
            {
                int d = ar_answer[i];
                if(d >= 0) //не бык, но может быть корова
                for(int j = 0; j < digits; j++)
                    if (d == ar_number[j])
                    {
                        cow_n++;
                        ar_number[j] = -1;  //корова найдена
                        ar_answer[i] = -1;
                        break;
                    }
            }
            res = "  Быков - " + ox_n + "  Коров - " + cow_n;
            return res;
         }

Как разобрать число на цифры

Для разбора целого десятичного числа на цифры используются две замечательные операции, применимые к целым числам. Остаток от деления числа на 10 дает последнюю цифру числа. Деление нацело числа на 10 отрезает от числа последнюю цифру. Циклическое применение этих двух операций решает поставленную задачу. Вот код функции Split:

/// <summary>
        /// Разбор числа на цифры
        /// создание массива цифр
        /// </summary>
        /// <param name="number">число</param>
        /// <param name = "n">число цифр числа</param>
        /// <returns>массив цифр</returns>
        int[] Split(int number, int n)
        {
            int[] res = new int[n];
            for (int i = 0; i < n; i++)
            {
                res[n - i - 1] = number % 10;
                number = number / 10;
            }
            return res;
        }

Разбор и сборка числа

В нашем алгоритме нам потребовалось разобрать число на цифры. Функция int[] Split(int number, int n) из числа number, содержащего n цифр создает массив из n элементов, каждый из которых содержит одну цифру исходного числа.

Давайте рассмотрим более сложную задачу, важную для основ программирования и связанную с представлением чисел в разных системах счисления и перевода числа из одной системы счисления в другую. Пусть нам дано десятичное число, а нам требуется узнать, как оно представлено в системе счисления с основанием p. Число N в системе счисления с основанием p можно представить в виде: $$$N=M \cdot p + c_{0}$$$

Остаток от деления нацело числа N на основание системы счисления дает последнюю (младшую) цифру числа N, а деление нацело дает число, от которого отрезана последняя цифра.

Пример:

Int N = 1237;
Int digit = N % 10;
N = N/10;
Результат: digit = 7 (последняя цифра числа N) 
N = 123 (исходное число, от которого отрезана последняя цифра.

Пусть N – десятичное число, p – основание системы счисления, $$${d_{0}, d_{1}, d_{2},\hdots d_{p-1},}$$$ -цифры системы счисления.

Основное соотношение.

Пусть число N записано в системе с основанием p в виде последовательности из k + 1 цифр:

Эта запись означает следующее:

Можно вынести p за скобки и представить запись N в виде:

Число в скобках – это целое число. Обозначим его через M. Тогда

Теперь нетрудно с помощью наших замечательных операций повторить процесс и получить младшую цифру в записи десятичного числа M в системе с основанием p, а также получить число, в котором эта цифра отрезана.

Нетрудно, используя эти операции написать функцию, которая переводит десятичное число N в систему с основанием p.

string From10ToP(int N, int p)
        {
            int digit;
            string res = "";
            while (N != 0)
            {
                digit = N % p;  //младшая цифра
                N = N / p;      //отрезаем младшую цифру
                res = digit + res;  //присоединяем цифру слева к строке результата
            }
            return res;
        }

Сборка числа

Если известна запись числа N в системе с основанием p, то используя соотношение (5.1) можно получить десятичное значение N. Кажется, что для этого нужно возводить в степень основание системы p. Однако существует красивый алгоритм, называемый схемой Горнера, позволяющий обходиться только операциями умножения и сложения.

Пусть M вначале равно ck – старшей цифре. Вычислим теперь новое значение M

Продолжим этот процесс, каждый раз умножая M на основание системы счисления и прибавляя следующую цифру. Последний шаг будет соответствовать соотношению (5.2) и даст десятичное значение N.

Вот как может выглядеть соответствующая функция перевода числа из системы P в десятичную систему:

int FromPTo10(string Np, int p)
        {
            int res = 0; 
            int n = Np.Length;
            int digit; 
            for(int i = 0; i < n; i++)
            {
                digit = Np[i] - '0'; //из строки выделяем очередную цифру
                res = res * p + digit; 
            }
            return res;
        }

Работа в классе

Построить Windows проект перевода чисел из 10-ичной системы в систему с основанием P (P 10) и обратного перевода из P в 10.

Домой

Используя построенный проект перевода чисел, пройти тест 6 курса Информация и данные.

Быки и коровы в картинках

(краткое содержание пропущенной записи следующего урока)

На следующем уроке рассматривался вариант игры "Быки и коровы", в котором компьютер задумывал комбинацию, состоящую из картинок, случайным образом выбранных из некоторого множества картинок. Задача игрока состояла в отгадывании задуманной комбинации, предъявляя свой вариант комбинации. Принципиально алгоритмы схожи. Роль цифр в данном варианте играют картинки. Помимо того, что играть с картинками интереснее, чем с цифрами, нам это дает возможность продемонстрировать работу с графическими объектами как в интерфейсе Windows проекта, так и в программном коде.

На следующем рисунке показан интерфейс проекта в процессе игры:

На рисунке можно видеть большое число элементов управления типа PictureBox. Эти объекты имеют свойство Image, позволяющее хранить и отображать картинки – объекты типа Image. Двенадцать таких объектов хранят картинки геометрических фигур разного цвета и формы, которые используются как для комбинации, задуманной компьютером, так и для варианта комбинации, предлагаемой игроком.

Как компьютер "задумывает" комбинацию из картинок

Приведем фрагмент кода обработчика события Click командной кнопки "Компьютер, задумай комбинацию", создающий комбинацию:

//задуманная комбинация
            for (int i = 0; i < N; i++)
            {
                index = rnd.Next(0, M);                
                comb[i] = images[index];
                comb_text[i] = images_text[index];
            }

Здесь N – размер комбинации, определяемый в зависимости от уровня игры. Как обычно, метод Next, вызываемый переменной rnd класса Random, возвращает случайное число, которое задает индекс элемента массива images. Этот элемент и становится очередной картинкой комбинации – элементом массива comb. Массивы comb и images хранят элементы типа Image. Параллельно создается массив comb_text, содержащий текстовое описание картинки. Тексты используются при сравнении задуманной комбинации с предлагаемым игроком вариантом. Конечно можно отображать картинки в числа, но для понимания программы работа с текстами предпочтительнее.

Я не буду останавливаться на других деталях работы алгоритма. Идейно он похож на вариант, где работа ведется с числами. Конечно для полного понимания следует разобрать код прилагаемого проекта, выполняя его в пошаговом режиме.

Как компьютер "отгадывает" комбинацию из картинок

Ранее отмечалось, что сформулировать эффективный алгоритм для компьютера, который бы отгадывал комбинацию лучше человека, совсем не просто. Приведу алгоритм игры компьютера, который находит нужную комбинацию, но работает не лучшим образом. Вот соответствующий код:

/// <summary>
        /// Стратегия компьютера отгадывания задуманной комбинации
        /// </summary>
        void CompStrategy()
        {
            Init();     //Инициализация данных
            int i = 0;
            while (i < M  !all_oxes)
            {
                //Определение фигур, участвующих в комбинации
                FormComb(i);    //variant_text - комбинация из элемента i
                string q = OxAndCow();  // подсчет быков в комбинации
                Question(q);  //вывод вопроса и ответа 
                Answer_Analyze(i);
                //Если все фигуры определены и определена фигура,
                //не участвующая в комбинации
                if (Index == N  exist_null)
                {
                    PlaceIn_oxes(); //Расставить быков по местам
                }
                i++;
            }
            listBoxQA.Items.Add(COMP_FINAL);        } 

Алгоритм достаточно примитивен. Вначале, используя варианты с одной фигурой, определяется, какие фигуры входят в комбинацию, для чего понадобится максимум 12 вопросов, по числу элементов множества картинок. Затем простым перебором определяется место каждой фигуры в комбинации, для чего может понадобиться максимум $$$N \cdot N / 2$ $$ вопросов.

Не буду приводить код всех функций, вызываемых в Comp_Strategy. – их можно посмотреть в проекте. В коде проекта можно увидеть еще один вариант возможной более оптимальной стратегии игры компьютера, но он нуждается в доработке.