Классические алгоритмы и игры на C# для школьников

Классические алгоритмы и игры на C# для
школьников

2-е издание, исправленное

Биллиг В.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Классические алгоритмы и игры на C# для школьников/ В.А. Биллиг - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

Цель курса - научить алгоритмическому мышлению школьников и всех тех, кто осваивает основы
программирования.
Практическая задача курса – это научить программированию в процедурах и функциях. Достижению
этой цели способствует рассмотрение большого числа примеров. В курсе подробно обсуждаются
вариации классических алгоритмов над числами – нахождение делителей числа, нахождение простых
и совершенных чисел, алгоритм Эвклида, решето Эратосфена. Рассматриваются классические
алгоритмы работы с массивами, начиная от задач вычисления суммы, максимального и
минимального элемента массива при возможных ограничениях на элементы, до задач поиска и
сортировки элементов массива. Важная часть курса посвящена программированию игр.
Рассматриваются игры, основанные на различных стратегиях поиска числа, или комбинации
графических объектов, задуманной компьютером. Выпускная работа курса также связана с игрой -
моделирование игрового автомата «Однорукий бандит».

(c) ООО “ИНТУИТ.РУ”, 2017-2016
(c) Биллиг В.А., 2017-2016

3

Вычисление суммы, максимального и минимального элементов
небольшого множества

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

Видео

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

Рассмотрим конкретную задачу:

Задача:

Аня, Витя и Саша пошли в лес. Аня собрала m грибов, Витя – n, Саша – p грибов.

Вот вопросы, которые можно задать в связи с этой задачей:

1. Сколько грибов собрали дети?
2. Какое максимальное число грибов было найдено одним подростком?
3. Какое минимальное число грибов было найдено одним подростком?
4. Кто собрал больше всех грибов?
5. Кто собрал меньше всех грибов?
6. Сколько в среднем грибов, собирали дети?

Ответы на эти вопросы так или иначе требуют вычисления суммы элементов,
нахождения максимального (минимального) элемента.

Давайте напишем функцию, вычисляющую сумму трех переменных, которую будем
использовать при решении нашей задачи:

/// <summary>
        /// Сумма трех аргументов
        /// </summary>
        /// <param name="x1">аргумент1</param>
        /// <param name="x2">аргумент2</param>

4

        /// <param name="x3">аргумент3</param>
        /// <returns>сумма x1 + x2 + x3</returns>
        int Sum(int x1, int x2, int x3)
        {
            // return x1 + x2 + x3;
            int sum = 0;//вводим переменную для суммы с начальным значением 0
            sum = sum + x1; //прибавляем первое слагаемое
            sum = sum + x2; //прибавляем второе слагаемое
            sum = sum + x3; //прибавляем третье слагаемое
            return sum;  
//возвращаем результат

        }

Заголовок функции и заголовочный комментарий

Заголовок функции:

int Sum(int x1, int x2, int x3)

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

В качестве имени функции выбрано содержательное имя, - для суммы это обычно Sum
или Summa. Имя указано в латинице, хотя можно использовать и имя, заданное
кириллицей, например, - Сумма. Латиница предпочтительнее, поскольку не требует
частых переключений с одного алфавита на другой при работе с программой. Конечно,
когда речь идет о вводе и выводе сообщений, предназначенных пользователю, то здесь
нужно использовать родной язык, для нас – это русский язык.

Далее в заголовке функции в скобках перечисляются имена аргументов функции и их
типы.

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

Для задания заголовочного комментария достаточно в строке, предшествующей
заголовку, набрать три слеша. Тогда по заголовку автоматически строится шаблон
комментария. Вначале идет тэг summary, в котором следует указать, что делает
функция. Затем для каждого параметра функции строится тэг param, в котором следует
указать смысл каждого параметра. Затем идет тэг returns, в котором следует задать
описание возвращаемого значения.

5

Заголовочные комментарии играют крайне важную роль в понимании того, что делает
ваш проект и отдельные его части. Помимо того, что они обеспечивают то, что
называют intellisense, - интеллектуальную подсказку, комментарии составляют
важную часть отчета о работе программы, который автоматически строится по тексту
программы.

В приведенном тексте функции используются и другой вид комментариев, - так
называемые строчные комментарии, которые начинаются с двух слешей, позволяя
комментировать код данной строки.

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

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

Тело функции. Два алгоритма

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

return x1 + x2 + x3;

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

Предпочтительнее другой, более сложный алгоритм, приведенный в нашем тексте
программы:

int sum = 0;//вводим переменную для суммы с начальным значением 0
            sum = sum + x1; //прибавляем первое слагаемое
            sum = sum + x2; //прибавляем второе слагаемое
            sum = sum + x3; //прибавляем третье слагаемое
            return sum;  
//возвращаем результат

В чем принципиальное отличие этого алгоритма? Здесь введена переменная с именем

sum (заметьте, в C# имена sum и Sum различны), в которой и будет постепенно
накапливаться сумма элементов множества. Важно обратить внимание на
инициализацию этой переменной. Вначале ее значение равно нулю. Прибавив к ней

6

первую переменную, получим сумму для множества из одного элемента. К этой
переменной последовательно прибавляются значения элементов суммируемого
множества.

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

Этот же прием с введением специальной переменной мы используем при построении
функции, вычисляющей максимальный элемент:

        /// <summary>
        /// Максимум трех аргументов
        /// </summary>
        /// <param name="x1">аргумент1</param>
        /// <param name="x2">аргумент2</param>
        /// <param name="x3">аргумент3</param>
        /// <returns>максимум из(x1, x2, x3)</returns>
        int Max(int x1, int x2, int x3)
        {
          int max = int.MinValue;   //переменная max с начальным значением MinValue
          if (x1 > max) max = x1; //максимум из одного значения
          if (x2 > max) max = x2; //максимум из двух значений
          if (x3 > max) max = x3; //максимум из трех значения
          return max;  
//возвращаем результат

 }

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

Заметьте, когда мы вычисляем сумму элементов, то переменную, в которой
накапливается сумма, инициализируется нулем, - это гарантирует, что при сложении с
первым элементом сумма будет равна первому элементу. При вычислении
произведения переменная инициализируется единицей, - это гарантирует, что при
умножении на первый элемент произведение будет равно первому элементу. При
вычислении минимума переменная инициализируется максимально возможным
элементом, - это гарантирует, что при сравнении с первым элементом минимум будет
равен первому элементу.

Интерфейс проекта

Для решения нашей задачи по сбору грибов построим Windows проект со следующим

7

интерфейсом:

Рис. 1.1.  Интерфейс проекта “Собираем грибы”

Интерфейс проекта достаточно прост. Есть метка (label) в начале формы с заголовком
проекта. Есть окошки (textbox) “кто”, в которых следует задать имена сборщиков
грибов, окошки “сколько”, в которых указывается, кто сколько грибов собрал. И есть
командные кнопки, позволяющие ответить на поставленные вопросы. Ответы на
вопросы будут появляться в окне сообщений. Когда пользователь проекта нажмет
соответствующую кнопку, то в ответ на это событие, обработчик события прочитает
данные из окошек, вызовет соответствующую написанную нами функцию, передаст ей
данные, и результат ее работы поместит в окно сообщений.

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

Вот как выглядит обработчик события командной кнопки, на которой написано
“сколько собрали”:

private void buttonSum_Click(object sender, EventArgs e)
        {
            int value1, value2, value3;
            value1 = int.Parse(textBoxValue1.Text);
            value2 = int.Parse(textBoxValue2.Text);
            value3 = int.Parse(textBoxValue3.Text);
            int sum = Sum(value1, value2, value3);
            textBoxMessage.Text = sum.ToString(); 
        }

Имя процедуры, представляющей обработчик события, строится из имени кнопки –

buttonSum и имени события – Click.

8

В обработчике события объявляются три переменные. Значения эти переменные
получают в соответствии с данными, прочитанными из окошек. Обратите внимание, в
текстовых окнах пользователь задает значения как текст. Поэтому данные,
представляющие целые числа, должны быть преобразованы, - из типа string
приведены к типу int. Это преобразование выполняет метод Parse, разбирающий
строку, преобразуя ее в число. Конечно, в строке должно быть записано число, чтобы
такое преобразование могло выполниться без ошибок.

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

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

        /// <summary>
        /// Максимум трех аргументов
        /// </summary>
        /// <param name="x1">аргумент1</param>
        /// <param name="x2">аргумент2</param>
        /// <param name="x3">аргумент3</param>
        /// <returns>максимум из(x1, x2, x3)</returns>
        int Max(int x1, int x2, int x3)
        {
          //  return Math.Max(Math.Max(x1, x2), x3);
            int max = int.MinValue; //вводим переменную для максимума с начальным значением MinV
            if (x1 > max) max = x1; //максимум из одного значения
            if (x2 > max) max = x2; //максимум из двух значений
            if (x3 > max) max = x3; //максимум из трех значения
            return max;  
//возвращаем результат

        }

А вот текст обработчика события, позволяющего вычислить максимум:

        private void buttonMax_Click(object sender, EventArgs e)
        {
            int value1, value2, value3;
            value1 = int.Parse(textBoxValue1.Text);
            value2 = int.Parse(textBoxValue2.Text);
            value3 = int.Parse(textBoxValue3.Text);
            int max = Max(value1, value2, value3);
            textBoxMessage.Text = max.ToString();
        }

Сложнее задача определения того, кто же достиг максимума. Здесь необходима
согласованная работа по одновременному изменению переменной, хранящей
максимальное значение, и переменной, хранящей имя того, кто достиг максимума.

9

Приведу текст соответствующего метода, решающего эту задачу:

        /// <summary>
        /// Кто достиг максимума
        /// </summary>
        /// <param name="x1">значение 1</param>
        /// <param name="x2">значение 2</param>
        /// <param name="x3">значение 3</param>
        /// <param name="name1">имя первого претендента</param>
        /// <param name="name2">имя второго претендента</param>
        /// <param name="name3">имя третьего претендента</param>
        /// <param name="max">максимум</param>
        /// <param name="name_max">имя того, кто достиг максимума</param>
        void MaxAndName(int x1, int x2, int x3,
            string name1, string name2, string name3,
            out int max, out string name_max)
        {
            max = int.MinValue; 
//вводим переменную для максимума с начальным значением MinValue
            name_max = "";
            if (x1 > max)
            {
                max = x1; name_max = name1;
                //максимум из одного значения и имя 
            }
            if (x2 > max)
            {
                max = x2; name_max = name2;
                //максимум из двух значений и имя 
            }
            if (x3 > max)
            {
                max = x3; name_max = name3;
                //максимум из трех значений и имя 
            }
        }

Заметьте, здесь метод вычисляет два результата, - значение максимума и имя того, кто
достиг максимума. Поэтому метод следует реализовать как процедуру, у которой два
параметра, представляющих результаты (out параметра).

Обработчик события соответствующей командной кнопки немногим отличается от
выше приведенных обработчиков события. Вот его текст:

private void buttonMaxName_Click(object sender, EventArgs e)
        {
            //входные данные. Ввод значений
            int value1, value2, value3;

10

            string name1, name2, name3;
            value1 = int.Parse(textBoxValue1.Text);
            value2 = int.Parse(textBoxValue2.Text);
            value3 = int.Parse(textBoxValue3.Text);
            name1 = textBoxName1.Text;
            name2 = textBoxName2.Text;
            name3 = textBoxName3.Text;

            //результаты
            int max_value;
            string max_name;

            //вычисления
            MaxAndName(value1, value2, value3,
                name1, name2, name3,
                out max_value, out max_name);

            //вывод результатов
            textBoxMessage.Text = max_name + " собрал(а) грибов " +
                max_value + ". Больше всех!";
        }

Приведу снимок экрана работающего проекта, в тот момент, когда нажата кнопка,
позволяющая определить того, кто собрал больше всех грибов:

Рис. 1.2.  Проект “Собираем грибы” в процессе работы

Заметьте, приведенное решение нельзя признать полностью корректным. Оно не
учитывает тот факт, что несколько человек могут достичь максимума и несправедливо
отмечать только одного из них. Так часто бывает на практике, что разработанная нами
программа несовершенна. Вы можете попробовать улучшить приведенное решение.

11