Презентация на тему: програмирование на алгоретмическом языке

* Программирование на алгоритмическом языке (7 класс) Введение Ветвления Сложные условия Циклы Графика Вспомогательные алгоритмы Алгоритмы-функции Анимация Случайные числа К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 1. Введение К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Алгоритм * Свойства алгоритма дискретность: состоит из отдельных шагов (команд) понятность: должен включать только команды, известные исполнителю конечность: позволяет получить решение задачи за конечное число шагов определенность: при одинаковых исходных данных всегда выдает один и тот же результат массовость: может применяться при различных исходных данных Алгоритм – это четко определенный план решения задачи для исполнителя. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программа – это алгоритм, записанный на каком-либо языке программирования набор команд для исполнителя Команда – это описание действий, которые должен выполнить исполнитель. откуда взять исходные данные? что нужно с ними сделать? Программа Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Простейшая программа * алг Первый нач | начало алгоритма кон | конец алгоритма комментарии после | не обрабатываются название алгоритма Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

алг Вывод на экран нач вывод "2+" вывод "2=?", нс вывод "Ответ: 4" кон Вывод текста на экран * Протокол: 2+2=? Ответ: 4 новая строка Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «4»: Вывести на экран текст «лесенкой» Вася пошел гулять «5»: Вывести на экран рисунок из букв Ж ЖЖЖ ЖЖЖЖЖ ЖЖЖЖЖЖЖ HH HH ZZZZZ Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Переменные * Задача. Ввести с клавиатуры два числа и найти их сумму. Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь компьютер считает сам! Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Программа * алг Сумма нач | ввести два числа | вычислить их сумму | вывести сумму на экран кон Псевдокод – алгоритм на русском языке с элементами языка программирования. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Переменные * Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы. Значение Имя Другой тип данных Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Имена переменных * МОЖНО использовать латинские буквы (A-Z), русские буквы (А-Я) цифры знак подчеркивания _ заглавные и строчные буквы различаются имя не может начинаться с цифры Какие имена правильные? AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Объявление переменных * Типы переменных: цел | целая вещ | вещественная и другие… Объявление переменных: цел a, b, c выделение места в памяти тип – целые список имен переменных Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Как записать значение в переменную? * a := 5 Оператор присваивания 5 Оператор – это команда языка программирова-ния (инструкция). Оператор присваивания – это команда для записи нового значения в переменную. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Блок-схема линейного алгоритма * начало конец c := a + b ввод a, b блок «начало» блок «ввод» блок «процесс» блок «вывод» блок «конец» вывод c Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Как ввести значение с клавиатуры? * ввод a Оператор ввода 5 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Ввод значений двух переменных * через пробел: 25 30 через запятую: 25,30 ввод a, b Ввод значений двух переменных. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Изменение значения переменной * алг Тест нач цел a, b a := 5 b := a + 2 a := (a + 2)*(b – 3) b := b + 1 кон a ? 5 5 b ? 5+2 7 a 5 7*4 28 Пример: b 7 7+1 8 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Арифметические операции * + сложение – вычитание * умножение / деление div деление нацело (остаток отбрасывается) mod остаток от деления цел a, b a := 7*3 - 4 | 17 a := a * 5 | 85 b := div(a,10) | 8 a := mod(a,10) | 5 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вывод данных * |вывод значения |переменной a |вывод значения |переменной a и переход |на новую строчку |вывод текста |вывод текста и значения переменной c вывод a вывод a, нс вывод "Привет!" вывод "Ответ: ", c вывод a, "+", b, "=", c Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задача: сложение чисел * Задача. Ввести два целых числа и вывести на экран их сумму. Простое решение: алг Сумма нач цел a, b, c ввод a, b c := a + b вывод c кон Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Полное решение * алг Сумма нач цел a, b, c вывод "Введите два целых числа" ввод a, b c := a + b вывод a, "+", b, "=", c кон Протокол: Введите два целых числа 25 30 25+30=55 компьютер пользователь подсказка Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести три числа, найти их сумму. Пример: Введите три числа: 4 5 7 4+5+7=16 «4»: Ввести три числа, найти их сумму и произведение. Пример: Введите три числа: 4 5 7 4+5+7=16 4*5*7=140 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Ввести три числа, найти их сумму, произведение и среднее арифметическое. Пример: Введите три числа: 4 5 7 4+5+7=16 4*5*7=140 (4+5+7)/3=5.333333 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Какие операторы неправильные? * алг Ошибки нач цел a, b вещ x, y a := 5 10 := x y := 7,8 b := 2.5 x := 2*(a + y) a := b + x кон имя переменной должно быть слева от знака := целая и дробная часть отделяются точкой нельзя записывать вещественное значение в целую переменную Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Порядок выполнения операций * вычисление выражений в скобках умножение, деление, div, mod слева направо сложение и вычитание слева направо z := (5*a+c)/a*(b-c)/ b x:=(5*c*c-d*(a+b))/((c+d)*(d-2*a)) 1 2 4 5 3 6 2 3 5 4 1 10 6 9 8 7 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Ручная прокрутка программы * алг Тест нач цел a, b a := 5 b := a + 2 a := (a + 2)*(b – 3) b := div(a,5) a := mod(a,b) a := a + 1 b := mod(a+14,7) кон a b ? ? 5 7 28 5 3 4 4 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Команда «вывод» * цел a = 1, b = 3 вывод a, "+", b, "=", a+b список вывода элементы разделяются запятыми элементы в кавычках – выводятся без изменений выражения (элементы без кавычек) вычисляются и выводится их результат 1+3=4 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Что будет выведено? * цел a = 1, b = 3 вывод "a+", b, "=a+b" a+3=a+b цел a = 1, b = 3 вывод a, "=F(", b, ")" 1=F(3) цел a = 1, b = 3 вывод "a=F(", b, ");" цел a = 1, b = 3 вывод a+b, ">", b, "!" цел a = 1, b = 3 вывод "F(", b, ")=X(", a, ")" a=F(3); 4>3! F(3)=X(1) Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Как записать оператор «вывод»? * цел a = 1, b = 3 вывод "X(", b, ")=", a X(3)=1 4=1+3 f(1)>f(3) 1+3=? цел a = 1, b = 3 вывод a+b, "=", a, "+", b цел a = 1, b = 3 вывод "f(", a, ")>f(", b, ")" цел a = 1, b = 3 вывод "" цел a = 1, b = 3 вывод a, "+", b, "=?" Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 2. Ветвления К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Разветвляющиеся алгоритмы * Задача. Ввести два целых числа и вывести на экран наибольшее из них. Идея решения: надо вывести на экран первое число, если оно больше второго, или второе, если оно больше первого. Особенность: действия исполнителя зависят от некоторых условий (если … иначе …). Алгоритмы, в которых последовательность шагов зависит от выполнения некоторых условий, называются разветвляющимися. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вариант 1. Блок-схема * полная форма ветвления блок «решение» Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Вариант 1. Программа алг Максимум нач цел a, b, M вывод "Введите два целых числа", нс ввод a, b если a > b то иначе все вывод "Наибольшее число ", M кон M:=a M:=b полная форма условного оператора Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Условный оператор * если условие то | что делать, если условие верно иначе | что делать, если условие неверно все Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вариант 2. Блок-схема * неполная форма ветвления Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вариант 2. Программа * алг Максимум 2 нач цел a, b, M вывод "Введите два целых числа", нс ввод a, b M:= a если b > a то M:= b все вывод "Наибольшее число ", M кон неполная форма условного оператора Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вариант 2б. Программа * алг Максимум 2б нач цел a, b, M вывод "Введите два целых числа", нс ввод a, b M:= b если ??? то ??? все вывод "Наибольшее число ", M кон M:= a a > b Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести два числа и вывести их в порядке возрастания. Пример: Введите два числа: 15 9 Ответ: 9 15 «4»: Ввести три числа и найти наибольшее из них. Пример: Введите три числа: 4 15 9 Наибольшее число 15 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Ввести пять чисел и найти наибольшее из них. Пример: Введите пять чисел: 4 15 9 56 4 Наибольшее число 56 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 3. Сложные условия К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Сложные условия Задача. Фирма набирает сотрудников от 25 до 40 лет включительно. Ввести возраст человека и определить, подходит ли он фирме (вывести ответ «подходит» или «не подходит»). Особенность: надо проверить, выполняются ли два условия одновременно. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вариант 1. Алгоритм * начало ввод x конец да нет x >= 25? да нет x

Вариант 1. Программа * алг Сотрудник нач цел x вывод "Введите ваш возраст", нс ввод x если x >= 25 то если x

Вариант 2. Алгоритм * начало ввод x да нет x >= 25 и x

Вариант 2. Программа * сложное условие алг Сотрудник нач цел x вывод "Введите ваш возраст", нс ввод x если x >= 25 и x

Сложные условия * Простые условия (отношения) < >= = Сложное условие – это условие, состоящее из нескольких простых условий (отношений), связанных с помощью логических операций: И – одновременное выполнение условий x >= 25 И x 25) ??? равно не равно x

Сложные условия * Порядок выполнения (приоритет = старшинство) выражения в скобках НЕ =, =, И ИЛИ Пример 2 1 6 3 5 4 если не (a > 2) или c 5 и b < a то ... все Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Сложные условия * Истинно или ложно при a := 2; b := 3; c := 4; не (a > b) a < b и b < c a > c или b > c a < b и b > c a > c и b > d не (a >= b) или c = d a >= b или не (c < b) a > c или b > c или b > a Да Да Нет Да Да Нет Нет Да Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Сложные условия * Для каких значений x истинны условия: x < 6 и x < 10 x < 6 и x > 10 x > 6 и x < 10 x > 6 и x > 10 x < 6 или x < 10 x < 6 или x > 10 x > 6 или x < 10 x > 6 или x > 10 x < 6 x > 10 x < 10 x > 6 нет таких 6 < x < 10 все x Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Задания «3»: Ввести три числа и определить, верно ли, что они вводились в порядке возрастания. Пример: Введите три числа: 4 5 17 да «4»: Ввести номер месяца и вывести название времени года. Пример: Введите номер месяца: 4 весна Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Задания «5»: Ввести возраст человека (от 1 до 150 лет) и вывести его вместе с последующим словом «год», «года» или «лет». Пример: Введите возраст: Введите возраст: 24 57 Вам 24 года Вам 57 лет Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 4. Циклы К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Циклы * Цикл – это многократное выполнение одинаковых действий. цикл с известным числом шагов цикл с неизвестным числом шагов (цикл с условием) Задача. Вывести на экран 5 раз слово «Привет». Особенность: одинаковые действия выполняются 5 раз. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Циклы * алг Привет нач вывод "Привет", нс вывод "Привет", нс вывод "Привет", нс вывод "Привет", нс вывод "Привет", нс кон Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Циклы * алг Привет нач нц 5 раз вывод "Привет!", нс кц кон конец цикла начало цикла вывод "Привет!", нс тело цикла Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Циклы * начало конец Блок-схема: да нет тело цикла Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Число шагов – переменная * алг Привет нач цел N вывод "Сколько раз?", нс ввод N нц N раз вывод "Привет!", нс кц кон Задача: ввести количество повторения с клавиатуры. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести натуральное число и вывести в строчку все числа от 1 до этого числа. Пример: Введите натуральное число: 4 Ответ: 1 2 3 4 «4»: Ввести два целых числа, найти их произведение, не используя операцию умножения. Пример: Введите два числа: 4 15 4*15=60 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Ввести натуральное число N и найти сумму всех чисел от 1 до N (1+2+3+…+N). Пример: Введите число слагаемых: 100 Сумма чисел от 1 до 100 равна 5050 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Циклы * алг Привет нач нц 5 раз вывод "Привет!", нс кц кон N := N + 1 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Блок-схема алгоритма * начало конец да нет N = 5? N := 0 N := N + 1 еще не сделали ни одного раза проверить, все ли сделали считаем очередной шаг цикл Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с условием * алг Привет 2 нач цел N N:= 0 нц пока N 5 вывод "Привет!", нс N:= N + 1 кц кон Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с условием * алг Привет 3 нач цел N N:= 5 нц пока N ??? вывод "Привет!", нс ??? кц кон Вместо знаков вопроса добавьте числа и операторы так, чтобы цикл выполнился ровно 5 раз: 0 N:= N - 1 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Что получим? * алг Пример 1 нач цел N N:= 1 нц пока N

Что получим? * алг Пример 2 нач цел N N:= 1 нц пока N

Что получим? * алг Пример 3 нач цел N N:= 2 нц пока N 5 вывод N, нс N:= N + 2 кц кон 2 4 6 8 10 12 14 16 ... Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Что получим? * алг Пример 4 нач цел N N:= 1 нц пока N

Что получим? * алг Пример 5 нач цел N N:= 5 нц пока N >= 1 вывод N*N*N, нс N:= N - 1 кц кон 125 64 27 8 1 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести натуральное число вывести квадраты и кубы всех чисел от 1 до этого числа. Пример: Введите натуральное число: 3 1: 1 1 2: 4 8 3: 9 27 «4»: Ввести два целых числа a и b (a ≤ b) и вывести квадраты все чисел от a до b. Пример: Введите два числа: 4 5 4*4=16 5*5=25 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Ввести два целых числа a и b (a ≤ b) и вывести сумму квадратов всех чисел от a до b. Пример: Введите два числа: 4 10 Сумма квадратов 371 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Циклы с условием * Пример: Отпилить полено от бревна. Сколько раз надо сделать движения пилой? Задача: Ввести целое число (

Блок-схема алгоритма * начало конец нет да n 0? count := 0 count := count + 1 n := div(n, 10) обнулить счетчик цифр ввод n выполнять «пока n 0» вывод count Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Программа * алг Число цифр нач цел n, count вывод "Введите целое число", нс ввод n count:= 0 вывод "В числе ", n, " нашли ", count, " цифр" кон нц пока n0 count:= count + 1 n:= div(n,10) кц , n1 ; n1:= n n1, Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с условием * Особенности: можно использовать сложные условия: можно записывать в одну строчку, разделяя команды точкой с запятой: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с условием * Особенности: условие пересчитывается при каждом входе в цикл если условие на входе в цикл ложно, цикл не выполняется ни разу если условие никогда не станет ложным, программа зацикливается a := 4; b := 6 нц пока a > b; a:= a – b кц a:= 4; b:= 6 нц пока a < b; d:= a + b кц Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Сколько раз выполняется цикл? * a:= 4; b:= 6 нц пока a < b; a:= a + 1 кц 2 раза a = 6 a:= 4; b:= 6 нц пока a < b; a:= a + b кц 1 раз a = 10 a:= 4; b:= 6 нц пока a > b; a:= a + 1 кц 0 раз a = 4 a:= 4; b:= 6 нц пока a < b; b:= a – b кц 1 раз b = -2 a:= 4; b:= 6 нц пока a < b; a:= a – 1 кц зацикливание Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести целое число и определить, верно ли, что в нём ровно 3 цифры. Пример: Введите число: Введите число: 123 1234 Да. Нет. «4»: Ввести целое число и найти сумму его цифр. Пример: Введите целое число: 1234 Сумма цифр числа 1234 равна 10. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример: Введите целое число: Введите целое число: 1232 1224 Нет. Да. «6»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, НЕ обязательно стоящие рядом. Пример: Введите целое число: Введите целое число: 1234 1242 Нет. Да. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания-2 * «3»: Ввести целое число и определить, верно ли, что в нём ровно 1 цифра «9». Пример: Введите число: Введите число: 193 1994 Да. Нет. «4»: Ввести целое число и определить, верно ли, что все его цифры четные. Пример: Введите число: Введите число: 2684 2994 Да. Нет. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания-2 * «5»: Ввести целое число и определить, верно ли, что все его цифры расположены в порядке возрастания. Пример: Введите целое число: Введите целое число: 1238 1274 Да. Нет. «6»: Ввести целое число и «перевернуть» его, так чтобы первая цифра стала последней и т.д. Пример: Введите целое число: Введите целое число: 1234 782 4321 287 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вычисление НОД * НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. Перебор: Записать в переменную k минимальное из двух чисел. Если a и b без остатка делятся на k, то стоп. Уменьшить k на 1. Перейти к шагу 2. это цикл с условием! Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Алгоритм Евклида * Евклид (365-300 до. н. э.) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7) НОД (1998, 2) = НОД (1996, 2) = … = 2 Пример: много шагов при большой разнице чисел: = НОД (7, 7) = 7 Надо: вычислить наибольший общий делитель (НОД) чисел a и b. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Блок-схема алгоритма * начало конец Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Алгоритм Евклида * нц пока a b если a > b то a:= a - b иначе b:= b - a все кц Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Модифицированный алгоритм Евклида * НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Еще один вариант: НОД(2·a,2·b)= 2·НОД(a, b) НОД(2·a,b)= НОД(a, b) | при нечетном b Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Алгоритм Евклида * «3»: Составить программу для вычисления НОД с помощью алгоритма Евклида. «4»: Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу: a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД(a,b) Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Алгоритм Евклида * «5»: Выполнить задание на «4» и подсчитать число шагов алгоритма для каждого случая. a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД(a,b) шагов Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с переменной * Задача: вывести кубы чисел от 1 до 8. Нужны ли переменные? Сколько? Как они должны изменяться? Нужен ли цикл? Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Блок-схема алгоритма * начало конец нет да N

Цикл с переменной * Задача: вывести кубы натуральных чисел от 1 до 8. алг Кубы нач цел N, кубN N:= 1 нц пока N

Цикл с переменной * Задача: вывести кубы натуральных чисел от 1 до 8. алг Кубы нач цел N, кубN кон нц для N от 1 до 8 кубN:= N*N*N вывод кубN, нс кц для 1,2,3,…,8 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с переменной * Задача: вывести кубы чётных чисел от 2 до 8. алг Кубы нач цел N, кубN кон нц для N от 2 до 8 шаг 2 кубN:= N*N*N вывод кубN, нс кц для 2,4,6,8 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Сколько раз выполняется цикл? * a := 1 нц для i от 1 до 3; a:=a+1 кц a = 4 a := 1 нц для i от 3 до 1; a:=a+1 кц a = 1 a := 1 нц для i от 1 до 3 шаг -1; a:=a+1 кц a = 1 a := 1 нц для i от 3 до 1 шаг -1; a:=a+1 кц a = 4 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цикл с переменной * Особенности: переменная цикла может быть только целой (цел) начальное и конечное значения и шаг – целые можно записывать в одну строчку, разделяя команды точкой с запятой: если шаг > 0 и конечное значение < начального, цикл не выполняется ни разу (проверка условия в начале цикла, цикл с предусловием) если шаг < 0 и конечное значение > начального, цикл не выполняется ни разу Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Замена одного вида цикла на другой * нц для i от 1 до 10 | тело цикла кц i:= 1 нц пока i = b | тело цикла i:= i - 1 кц Замена пока на для возможна только тогда, когда можно заранее вычислить число шагов цикла. Замена цикла для на пока возможна всегда. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести натуральное число N и вывести числа от N до 1 (через одно) в порядке убывания. Пример: Введите натуральное число: 8 Ответ: 8 6 4 2 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «4»: Ввести два целых числа a и b (a ≤ b) и вывести кубы всех чисел от a до b. Пример: Введите два числа: 4 6 4*4*4=64 5*5*5=125 6*6*6=216 «5»: Ввести целое число a и вывести сумму квадратов всех чисел от 1 до a с шагом 0.1. Пример: Введите последнее число: 3 Сумма 91.7 12 + 1.12 + 1.22 +…+ a2 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «4»: Ввести a и b и вывести квадраты и кубы чисел от a до b. Пример: Введите границы интервала: 4 6 4: 16 64 5: 25 125 6: 36 216 «5»: Вывести квадраты и кубы 10 чисел следующей последовательности: 1, 2, 4, 7, 11, 16, … Пример: 1: 1 1 2: 4 8 4: 16 64 ... 46: 2116 97336 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 5. Графика К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Система координат * (0,0) (x,y) X Y x y Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Исполнитель Рисователь * использовать Рисователь алг нач | текст программы кон Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цвет и толщина линий: перо(2, "синий") Линии * толщина линии перо(1, "зеленый") линия(10, 15, 90, 80) перо(1, "красный“) в точку(5, 5) линия в точку(50, 5) линия в точку(70, 50) линия в точку(30, 80) линия в точку(5, 60) Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Фигуры с заливкой * перо(1, "синий") кисть("желтый") прямоугольник(0, 0, 80, 40) перо(1, "красный") кисть("зеленый") эллипс(0, 0, 100, 50) кисть("фиолетовый") залить(70, 80) кисть(""); | отменить заливку Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Пример использовать Рисователь алг Домик нач перо(2, "фиолетовый") кисть("синий") прямоугольник(100, 100, 300, 200) в точку(100, 100) линия в точку(200, 50) линия в точку(300, 100) кисть("желтый") залить(200, 75); перо(2, "белый"); кисть("зеленый"); эллипс(150, 100, 250, 200); кон (200, 50) (100, 100) (300, 200)

«3»: «Домик» «4»: «Лягушка» Задания Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

«5»: «Корона» Задания Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Штриховка * (x1, y1) (x2, y2) N линий (N=5) h прямоугольник (x1, y1, x2, y2) x:= x1 + h линия(x, y1, x, y2) x:= x + h линия(x, y1, x, y2) x:= x + h ... x y2 y1 цикл N раз Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Штриховка (программа) * использовать Рисователь алг Штриховка нач цел N = 5 | число линий цел x1 = 100, x2 = 300 цел y1 = 100, y2 = 200 вещ h, x h:=(x2 - x1)/(N + 1) прямоугольник(x1, y1, x2, y2) x:= x1 + h нц N раз линия(int(x), y1, int(x), y2) x:= x + h кц кон целая часть вещ h, x Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Штриховка * (x1, y1) (x2, y2) hx hy x:= x1 + hx; y:= y1 + hy линия(x1, int(y), int(x), int(y)) x:= x + hx; y:= y + hy линия(x1, int(y), int(x), int(y)) x:= x + hx; y:= y + hy ... цикл N раз Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Штриховка * (x1, y1) (x2, y2) hx hy вещ hx, hy, x, y hx:=(x2 - x1)/(N + 1) hy:=(y2 - y1)/(N + 1) в точку(x1, y1) линия в точку(x1, y2) линия в точку(x2, y2) линия в точку(x1, y1) x:= x1 + hx; y:= y1 + hy нц N раз линия(x1,int(y),int(x),int(y)) x:= x + hx y:= y + hy кц Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Ввести с клавиатуры количество линий, построить фигуру и выполнить штриховку: «4»: Ввести с клавиатуры количество линий, построить фигуру и выполнить штриховку: или Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Ввести с клавиатуры количество линий и построить фигуру: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 6. Вспомогательные алгоритмы К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задача * Особенность: три похожие фигуры. общее: размеры, угол поворота отличия: координаты, цвет Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

С чего начать? * найти похожие действия (три фигуры) найти общее (размеры, форма, угол поворота) и отличия (координаты, цвет) отличия = параметры алгоритма (доп. данные) (x+100, y) (x, y-60) использовать Рисователь алг Тр (цел x, y, лит цвет) нач в точку(x, y) линия в точку(x, y-60) линия в точку(x+100, y) линия в точку(x, y) кисть(цвет) залить(x+20, y-20) кон цепочка символов Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Если запустить? * (50,100) Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Как использовать? * использовать Рисователь алг Треугольники нач перо(1, "черный") Тр(100, 100, "синий") Тр(200, 100, "зеленый") Тр(200, 160, "красный") кон (100,100) 100 60 вызовы алгоритма алг Тр(цел x, y, лит цвет) нач ... кон основной алгоритм вспомогательный алгоритм Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вспомогательные алгоритмы * расположены ниже основного в заголовке перечисляются формальные параметры, они обозначаются именами для каждого параметра указывают тип однотипные параметры перечисляются через запятую при вызове в скобках указывают фактические параметры в том же порядке алг Тр(цел x, y, лит цвет) Тр(200, 100, "зеленый") x y цвет Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Используя одну процедуру, построить фигуру. «4»: Используя одну процедуру, построить фигуру. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Используя одну процедуру, построить фигуру. Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Рекурсивные объекты * Рекурсивный объект – это объект, определяемый через один или несколько таких же объектов. У попа была собака, он ее любил. Она съела кусок мяса, он ее убил. В ямку закопал, надпись написал: Сказка о попé и собаке Примеры: Сказка о попé и собаке: Факториал: если если Рисунок с рекурсией: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Рекурсивная фигура * 3 уровня: Фигура из N уровней – это окружность и 4 фигуры из N-1 уровней N-1 N-1 N-1 N-1 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Рекурсивная фигура: алгоритм * алг РекОк(цел x, y, R, N) нач если N

Рекурсивная фигура: программа * использовать Рисователь алг Рекурсия нач РекОк(200, 200, 100, 3) кон алг РекОк(цел x, y, R, N) нач ... кон Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Рекурсивные алгоритмы * вызывают сами себя прямо … или через другой алгоритм: должно быть условие окончания рекурсии (иначе?) рекурсия может стать бесконечной все задачи могут быть решены без рекурсии, но… часто рекурсивные алгоритмы проще и понятнее как правило, алгоритмы без рекурсии работают быстрее и требуют меньше памяти A A B прямая рекурсия косвенная рекурсия Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

«3»: Нарисовать рекурсивную фигуру, число уровней вводить с клавиатуры: «4»: Нарисовать рекурсивную фигуру, число уровней вводить с клавиатуры: Задания * Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

«5»: Нарисовать рекурсивную фигуру, число уровней вводить с клавиатуры: Задания * Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 8. Анимация К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Анимация * Анимация (англ. animation) – оживление изображения на экране. Задача: внутри синего квадрата 200 на 200 пикселей слева направо двигается желтый квадрат 20 на 20 пикселей. Программа останавливается, если нажата клавиша Esc или квадрат дошел до границы синей области. Проблема: как изобразить перемещение объекта на экране? Привязка: состояние объекта задается координатами (x,y) Принцип анимации: рисуем объект в точке (x,y) задержка на несколько миллисекунд стираем объект изменяем координаты (x,y) переходим к шагу 1 Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Процедура (рисование и стирание) * алг Фигура(цел x, y, лит цвет) нач кисть(цвет) прямоугольник(x,y,x+20,y+20) кон (x, y) (x+20, y+20) одна процедура рисует и стирает стереть = рисовать цветом фона границу квадрата отключить рисуем: цвет кисти – желтый стираем: цвет кисти – синий Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Полная программа * использовать Рисователь алг Анимация нач цел x, y | текущие координаты кисть("синий") перо(1, "") | отключить контур прямоугольник(0, 0, 200, 200) | синий фон x:= 0; y:= 100 | начальные координаты кон алг Фигура(цел x, y, лит цвет) нач ... кон нц пока x < 180 Фигура(x, y, "желтый") delay(50) Фигура(x, y, "синий") x:= x + 5 кц пока не дошли до границы Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Квадрат двигается справа налево: «4»: Два квадрата двигаются в противоположных направлениях: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Два квадрата двигаются в противоположных направлениях и отталкиваются от стенок синего квадрата: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Управление клавишами * Задача: жёлтый квадрат внутри синего квадрата управляется клавишами-стрелками. Коды клавиш: влево – 16777234 вверх – 16777235 вправо – 16777236 вниз – 16777237 Проблема: как изменять направление движения? Решение: c:= клав выбор при c = 16777234: x:= x – 5 | влево при c = 16777235: y:= y – 5 | вверх при c = 16777236: x:= x + 5 | вправо при c = 16777237: y:= y + 5 | вниз все ждать нажатия на клавишу, записать ее код в переменную c Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Программа * использовать Рисователь алг Управление клавишами нач цел x, y, c | нарисовать синий квадрат x:= 100; y:= 100 | начальная точка нц пока x < 180 Фигура(x, y,"желтый") | рисуем фигуру c:= клав | ждем нажатия клавиши Фигура(x, y,"синий") | стираем фигуру выбор при c = 16777234: x:= x - 5 при c = 16777235: y:= y - 5 при c = 16777236: x:= x + 5 при c = 16777237: y:= y + 5 все кц кон Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Квадрат в самом начале стоит в правом нижнем углу, и двигается при нажатии стрелок только вверх или влево: «4»: Квадрат двигается при нажатии стрелок, однако не может выйти за границы синего квадрата: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Квадрат непрерывно двигается, при нажатии стрелок меняет направление и отталкивается от стенок синего квадрата: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Программирование на алгоритмическом языке Тема 9. Случайные числа К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Случайно… встретить друга на улице разбить тарелку найти 10 рублей выиграть в лотерею Случайный выбор: жеребьевка на соревнованиях выигравшие номера в лотерее Как получить случайность? * Случайность и ее моделирование Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Электронный генератор нужно специальное устройство нельзя воспроизвести результаты 318458191041 564321 209938992481 458191 938992 малый период (последовательность повторяется через 106 чисел) Метод середины квадрата (Дж. фон Нейман) в квадрате Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле. * Случайные числа на компьютере Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Модель: снежинки падают на отрезок [a,b] распределение равномерное неравномерное * Распределение случайных чисел Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Особенности: распределение – это характеристика всей последовательности, а не одного числа равномерное распределение одно, компьютерные датчики случайных чисел дают равномерное распределение неравномерных – много любое неравномерное можно получить с помощью равномерного a b a b * Распределение случайных чисел Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Вещественные числа в интервале [0,10): * Генератор случайных чисел вещ X, Y X:= rand(0, 10) | интервал от 0 до 10 (

Случайные числа * Задача: заполнить прямоугольник 200 на 150 пикселей равномерно точками случайного цвета Как получить случайные координаты пикселя? Как добиться равномерности? автоматически при использовании irand цел X, Y X:= irand(0, 200) Y:= irand(0, 150) Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Цвет пикселя на мониторе * Вывод: цвет можно разложить на составляющие (каждая кодируется числом от 0 до 255). Модель RGB: RGB(0,0,0) R G B RGB(255,255,255) RGB(255,0,0) RGB(0,255,0) RGB(0,0,255) RGB(255,0,255) RGB(255,255,0) RGB(0,255,255) RGB(100,100,100) Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Случайный цвет пикселя * цел r, g, b r:= irand(0, 255) g:= irand(0, 255) b:= irand(0, 255) Случайные составляющие цвета: это разные числа! Управление цветом пикселя: пиксель(X, Y, RGB(r,g,b)) случайный цвет Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Программа * использовать Рисователь алг Случайные точки нач цел x, y, r, g, b нц пока да x:=irand(0,200) y:=irand(0,100) r:=irand(0,255) g:=irand(0,255) b:=irand(0,255) пиксель(x,y,RGB(r,g,b)) кц кон это бесконечный цикл: нц пока да … кц Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «3»: Заполнить квадрат точками случайного цвета. размер квадрата ввести с клавиатуры: Пример: Введите размер квадрата: 150 «4»: Заполнить область точками случайного цвета: Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

Задания * «5»: Заполнить область точками случайного цвета: или Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru

* Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ № 163, г. Санкт-Петербург [email protected] Программирование на алгоритмическом языке К. Поляков, 2010-2011 http://kpolyakov.narod.ru