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

Возведение в степень

Разбить на страницы
Показывать лекцию целиком

Предугадывая возможные вопросы к проекту игры "Однорукий бандит", дадим некоторые пояснения.

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

Покажу мой вариант интерфейса:

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

Опущу многие детали реализации этого интерфейса, остановлюсь лишь на том, как можно реализовать анализ сформированной комбинации, позволяющий установить, является ли комбинация проигрышной для игрока или дает ему выигрыш. Комбинация представляет собой три фигуры, случайным образом выбираемых из заданного множества 12 фигур. Достаточно просто установить, дает ли комбинация главный выигрыш. Каковы бы ни были объекты, их всегда можно сравнивать на равенство. Значительно труднее определить, являются ли все картинки комбинации одного цвета или одинаковыми фигурами. Исходно наши объекты в комбинации, отображаемые в форме, являются рисунками типа image. Для таких объектов определить такие свойства, как цвет или какова фигура сложная задача. Как же быть в подобных ситуациях?

Рассмотрим общую ситуацию. Пусть есть некоторое множество объектов определенного типа. Требуется определить, обладают ли объекты заданным свойством (задать своего рода фильтр). Как быть, если задать фильтр для объектов такого типа довольно сложно. Один из приемов состоит в том, чтобы задать некоторое множество объектов другого типа той же мощности, что и исходное множество, установив между объектами двух множеств взаимно –однозначное соответствие. Может оказаться, что установление свойств объектов для второго множества является более простой задачей. Свойства, установленные для объектов второго множества, переносятся на соответствующие объекты первого множества.

Этот прием применим в нашей задаче. Игорь, как я понимаю, картинкам поставил в соответствие буквы алфавита. Если комбинация содержит буквы "a", "b", "c", то это означает, что выпали три круга, а комбинация из букв "a", "e", "c" является проигрышной для игрока.

Я в своей реализации, каждой картинке поставил в соответствие текст: картинке с синим кругом соответствует строка "синий круг". Затем я устанавливал свойства комбинации, работая с текстами.

Мы с вами с текстами и символами текста работали мало. Можно ли предложить другой вариант, работая с более привычным типом данных – числами? Конечно, можно. Любое конечное множество объектов можно пронумеровать и работать не с самими объектами, а их номерами. Тогда синему кругу будет соответствовать число 1, красному – 2, желтому -3.

Как записать в этом случае условие того, что "все картинки одного цвета" или "все картинки – одна и та же фигура".

Предложите свои варианты.

Работа у доски

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

/// <summary>
        /// Выигрыш, если у всех картинок один цвет
        /// или одна и та же фигура 
        /// </summary>
        /// <returns>true, если выигрыш</returns>
        bool IsPayment_Num()
        {
            return IsSameColor() || IsSameShape();
        }
        /// <summary>
        /// анализ цвета 
        /// </summary>
        /// <returns>true, если у всех картинок один цвет </returns>
        bool IsSameColor()
        {
            return (comb_num[0] - comb_num[1]) % 3 == 0 
                (comb_num[2] - comb_num[1]) % 3 == 0;
        }
        /// <summary>
        /// анализ фигуры
        /// </summary>
        /// <returns>true,если на всех картинках одна и та же фигура </returns>
        bool IsSameShape()
        {
					/*
					//Эта реализация построена для случая отображения картинок
					//на интервал [1 – 12]
            Array.Sort(comb_num); 
            return (comb_num[2] < 4)  ||         //три круга
                (comb_num[0] >= 4   comb_num[2] <= 6) ||     //три квадрата
                (comb_num[0] >= 7  comb_num[2] <= 9) ||   //три ромба
                comb_num[0] >= 10;                //три треугольника
					*/
					//Можно построить более красивую реализацию
					//при использовании интервала [0 – 11]
return 
                //для каждой группы фигур результат деления на 3 одинаков
                 comb_num[0] / 3 == comb_num[1] / 3 
                 comb_num[1] / 3 == comb_num[2] / 3;
        }

Обратите внимание, оба алгоритма не очевидны и требуют алгоритмического мышления.

Эффективный алгоритм возведения в целую степень

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

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

        /// <summary>
        /// Возведение числа в целую степень
        /// </summary>
        /// <param name="x">число</param>
        /// <param name="n">степень</param>
        /// <returns>x в степени n</returns>
        static double Pow_Simple(double x, int n)
        {
            double res = 1;
            for (int i = 0; i < n; i++)
                res *= x;
            return res;
        }

А есть ли лучший по сложности алгоритм? Да, такой алгоритм существует. Если наш Simple алгоритм требует n умножений, то эффективный алгоритм требует не более 2 * log n умножений. Нужно понимать, что для больших n логарифм от n значительно меньше n. Например, при n = 220 (n больше миллиона), log n = 20.

Приведу функцию, реализующую эффективный алгоритм. Комментарии позволяют понять идею эффективного алгоритма. Сам по себе алгоритм весьма элегантен. Заодно он демонстрирует способ доказательства корректности алгоритма:

        /// <summary>
        /// Возведение числа в целую степень
        /// эффективный алгоритм
        /// </summary>
        /// <param name="x">число</param>
        /// <param name="n">степень</param>
        /// <returns>x в степени n</returns>
        static double Pow_Effective(double x, int n)
        {
            double z = x;
            double y = 1;
            int m = n;
            //выполняется условие (инвариант цикла):
            // Invariant: z ^ m * y == x ^ n 
            while (m != 0)
            {
                if( m % 2 == 0) //IsEven(m)
                { m /= 2; z *= z; } //инвариант выполняется
                else
                { m -= 1; y *= z; }
            }
             //Invariant  (m == 0) => y == x ^ n  
            return y;
        }

Пример:

n = 33; z = x; y = 1; m = 33; => m = 32; z = x; y = x; => m = 16; z = x ^2; y = x; =>

m = 8; z = x ^ 4; y = x; => m = 4; z = x ^ 8; y = x; => m = 2; z = x ^ 16; y = x; =>

m = 1; z = x ^ 32; y = x; => m = 0; z = x ^ 32; y = x ^ 33; (Всего 6 умножений, а не 33)

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

Программа на миллион долларов. Числа "градины" или проблема 3x + 1

Рассмотрим короткую программу в несколько строчек:

        /// <summary>
        /// Знаменитая программа
        /// Пока никому не удалось доказать ее завершаемость
        /// для любого целого n
        /// Объявлена награда в миллион долларов
        /// </summary>
        /// <param name="n">целое</param>
        /// <returns>число проходов по циклу</returns>
        static int Grad(long n)
        {
            int res = 0;
            while (n != 1)
            {
                if (n % 2 == 0) //IsEven(n)
                    n /= 2;
                else
                    n = 3 * n + 1;
                res++;
            }
            return res;
        }

Доказано, что программа завершается для любых nN, где N – большое число. Но пока никому не удалось доказать ее завершаемость для любого n.

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

        /// <summary>
        /// Наибольшая "градина"
        /// в интервале [3, N]
        /// </summary>
        /// <param name="N">верхняя граница</param>
        /// <param name="Max">наибольшая градина в интервале</param>
        /// <param name="K_max">число колебаний градины</param>
        public static void MaxGrad(int N, out int Max, out int K_max )
        {
            K_max = 0;
            int n;
            Max = 0;
            for (int i = 3; i < N; i += 2 )
            {
                n = Grad(i);
                if (n > K_max)
                {
                    K_max = n;
                    Max = i;
                }
            }
        }

Приведу интерфейс проекта, анализирующего поведение чисел "градин":

Этой замечательной программой мы завершим эту часть нашего курса.

Итоги

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

https://youtu.be/-ooc_rJIe6o

Страницы:

Предугадывая возможные вопросы к проекту игры "Однорукий бандит", дадим некоторые пояснения.

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

Покажу мой вариант интерфейса:

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

Опущу многие детали реализации этого интерфейса, остановлюсь лишь на том, как можно реализовать анализ сформированной комбинации, позволяющий установить, является ли комбинация проигрышной для игрока или дает ему выигрыш. Комбинация представляет собой три фигуры, случайным образом выбираемых из заданного множества 12 фигур. Достаточно просто установить, дает ли комбинация главный выигрыш. Каковы бы ни были объекты, их всегда можно сравнивать на равенство. Значительно труднее определить, являются ли все картинки комбинации одного цвета или одинаковыми фигурами. Исходно наши объекты в комбинации, отображаемые в форме, являются рисунками типа image. Для таких объектов определить такие свойства, как цвет или какова фигура сложная задача. Как же быть в подобных ситуациях?

Рассмотрим общую ситуацию. Пусть есть некоторое множество объектов определенного типа. Требуется определить, обладают ли объекты заданным свойством (задать своего рода фильтр). Как быть, если задать фильтр для объектов такого типа довольно сложно. Один из приемов состоит в том, чтобы задать некоторое множество объектов другого типа той же мощности, что и исходное множество, установив между объектами двух множеств взаимно –однозначное соответствие. Может оказаться, что установление свойств объектов для второго множества является более простой задачей. Свойства, установленные для объектов второго множества, переносятся на соответствующие объекты первого множества.

Этот прием применим в нашей задаче. Игорь, как я понимаю, картинкам поставил в соответствие буквы алфавита. Если комбинация содержит буквы "a", "b", "c", то это означает, что выпали три круга, а комбинация из букв "a", "e", "c" является проигрышной для игрока.

Я в своей реализации, каждой картинке поставил в соответствие текст: картинке с синим кругом соответствует строка "синий круг". Затем я устанавливал свойства комбинации, работая с текстами.

Мы с вами с текстами и символами текста работали мало. Можно ли предложить другой вариант, работая с более привычным типом данных – числами? Конечно, можно. Любое конечное множество объектов можно пронумеровать и работать не с самими объектами, а их номерами. Тогда синему кругу будет соответствовать число 1, красному – 2, желтому -3.

Как записать в этом случае условие того, что "все картинки одного цвета" или "все картинки – одна и та же фигура".

Предложите свои варианты.

Работа у доски

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

/// <summary>
        /// Выигрыш, если у всех картинок один цвет
        /// или одна и та же фигура 
        /// </summary>
        /// <returns>true, если выигрыш</returns>
        bool IsPayment_Num()
        {
            return IsSameColor() || IsSameShape();
        }
        /// <summary>
        /// анализ цвета 
        /// </summary>
        /// <returns>true, если у всех картинок один цвет </returns>
        bool IsSameColor()
        {
            return (comb_num[0] - comb_num[1]) % 3 == 0 
                (comb_num[2] - comb_num[1]) % 3 == 0;
        }
        /// <summary>
        /// анализ фигуры
        /// </summary>
        /// <returns>true,если на всех картинках одна и та же фигура </returns>
        bool IsSameShape()
        {
					/*
					//Эта реализация построена для случая отображения картинок
					//на интервал [1 – 12]
            Array.Sort(comb_num); 
            return (comb_num[2] < 4)  ||         //три круга
                (comb_num[0] >= 4   comb_num[2] <= 6) ||     //три квадрата
                (comb_num[0] >= 7  comb_num[2] <= 9) ||   //три ромба
                comb_num[0] >= 10;                //три треугольника
					*/
					//Можно построить более красивую реализацию
					//при использовании интервала [0 – 11]
return 
                //для каждой группы фигур результат деления на 3 одинаков
                 comb_num[0] / 3 == comb_num[1] / 3 
                 comb_num[1] / 3 == comb_num[2] / 3;
        }

Обратите внимание, оба алгоритма не очевидны и требуют алгоритмического мышления.

Эффективный алгоритм возведения в целую степень

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

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

        /// <summary>
        /// Возведение числа в целую степень
        /// </summary>
        /// <param name="x">число</param>
        /// <param name="n">степень</param>
        /// <returns>x в степени n</returns>
        static double Pow_Simple(double x, int n)
        {
            double res = 1;
            for (int i = 0; i < n; i++)
                res *= x;
            return res;
        }

А есть ли лучший по сложности алгоритм? Да, такой алгоритм существует. Если наш Simple алгоритм требует n умножений, то эффективный алгоритм требует не более 2 * log n умножений. Нужно понимать, что для больших n логарифм от n значительно меньше n. Например, при n = 220 (n больше миллиона), log n = 20.

Приведу функцию, реализующую эффективный алгоритм. Комментарии позволяют понять идею эффективного алгоритма. Сам по себе алгоритм весьма элегантен. Заодно он демонстрирует способ доказательства корректности алгоритма:

        /// <summary>
        /// Возведение числа в целую степень
        /// эффективный алгоритм
        /// </summary>
        /// <param name="x">число</param>
        /// <param name="n">степень</param>
        /// <returns>x в степени n</returns>
        static double Pow_Effective(double x, int n)
        {
            double z = x;
            double y = 1;
            int m = n;
            //выполняется условие (инвариант цикла):
            // Invariant: z ^ m * y == x ^ n 
            while (m != 0)
            {
                if( m % 2 == 0) //IsEven(m)
                { m /= 2; z *= z; } //инвариант выполняется
                else
                { m -= 1; y *= z; }
            }
             //Invariant  (m == 0) => y == x ^ n  
            return y;
        }

Пример:

n = 33; z = x; y = 1; m = 33; => m = 32; z = x; y = x; => m = 16; z = x ^2; y = x; =>

m = 8; z = x ^ 4; y = x; => m = 4; z = x ^ 8; y = x; => m = 2; z = x ^ 16; y = x; =>

m = 1; z = x ^ 32; y = x; => m = 0; z = x ^ 32; y = x ^ 33; (Всего 6 умножений, а не 33)

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

Программа на миллион долларов. Числа "градины" или проблема 3x + 1

Рассмотрим короткую программу в несколько строчек:

        /// <summary>
        /// Знаменитая программа
        /// Пока никому не удалось доказать ее завершаемость
        /// для любого целого n
        /// Объявлена награда в миллион долларов
        /// </summary>
        /// <param name="n">целое</param>
        /// <returns>число проходов по циклу</returns>
        static int Grad(long n)
        {
            int res = 0;
            while (n != 1)
            {
                if (n % 2 == 0) //IsEven(n)
                    n /= 2;
                else
                    n = 3 * n + 1;
                res++;
            }
            return res;
        }

Доказано, что программа завершается для любых nN, где N – большое число. Но пока никому не удалось доказать ее завершаемость для любого n.

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

        /// <summary>
        /// Наибольшая "градина"
        /// в интервале [3, N]
        /// </summary>
        /// <param name="N">верхняя граница</param>
        /// <param name="Max">наибольшая градина в интервале</param>
        /// <param name="K_max">число колебаний градины</param>
        public static void MaxGrad(int N, out int Max, out int K_max )
        {
            K_max = 0;
            int n;
            Max = 0;
            for (int i = 3; i < N; i += 2 )
            {
                n = Grad(i);
                if (n > K_max)
                {
                    K_max = n;
                    Max = i;
                }
            }
        }

Приведу интерфейс проекта, анализирующего поведение чисел "градин":

Этой замечательной программой мы завершим эту часть нашего курса.

Итоги

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

https://youtu.be/-ooc_rJIe6o

Вернуться к учебному плану