Введение Переменные Ветвления Сложные условия Циклы Циклы с переменной Оператор выбора Отладка программ Графика Графики функций Процедуры Анимация Функции Случайные числа
Тема 1. Введение
3 Алгоритм Свойства алгоритма дискретность : состоит из отдельных шагов (команд) понятность : должен включать только команды, известные исполнителю (входящие в СКИ) определенность : при одинаковых исходных данных всегда выдает один и тот же результат конечность : заканчивается за конечное число шагов массовость : может применяться многократно при различных исходных данных корректность : дает верное решение при любых допустимых исходных данных Алгоритм – это четко определенный план действий для исполнителя.
4 Программа Программа – это алгоритм, записанный на каком-либо языке программирования набор команд для компьютера Команда – это описание действий, которые должен выполнить компьютер. откуда взять исходные данные? что нужно с ними сделать? куда поместить результат?
5 Языки программирования Машинно-ориентированные (низкого уровня) - каждая команда соответствует одной команде процессора (ассемблер) Языки высокого уровня – приближены к естественному (английскому) языку, легче воспринимаются человеком, не зависят от конкретного компьютера для обучения : Бейсик, ЛОГО, Паскаль профессиональные : Си, Фортран, Паскаль для задач искусственного интеллекта : Пролог, ЛИСП для Интернета : JavaScript, Java, Perl, PHP, ASP
6 Язык Си 197 2-1974 – Б. Керниган, Д. Ритчи высокая скорость работы программ много возможностей стал основой многих современных языков (С++, С #, Javascript, Java, ActionScript, PHP ) много шансов сделать ошибку, которая не обнаруживается автоматически
7 Простейшая программа main() { } главная (основная) программа всегда имеет имя main начало программы «тело» программы (основная часть) конец программы Что делает эта программа? ?
8 Что происходит дальше? main() { } first. cpp исходный файл first. o транслятор ЪБzЦ2?|ё3БКа n/36ШпIC+И- ЦЗ_5МyРЧб s6bд^:/@:лЖ1_ объектный файл стандартные функции редактор связей ( компоновка ) MZPо:ЄPэ_еЗ"!_ `кn,ЦbЄ-Щр1 G_БАC, _Ощях¤9жФ first. exe исполняемый файл по исходному файлу можно восстановить остальные исполняемый файл можно запустить ! текст программы на Си или Си++
9 Вывод текста на экран #include <stdio.h> main() { printf(" Привет! "); } include = включить файл stdio.h : описание стандартных функций ввода и вывода вызов стандартной функции printf = print format ( форматный вывод ) этот текст будет на экране
10 Как начать работу? здесь мы набираем программу сообщения об ошибках Открыть Новый Сохранить Закрыть
11 Оболочка Dev C ++ 4.9 IDE = Integrated Development Environment интегрированная среда разработки: текстовый редактор для создания и редактирования текстов программ транслятор для перевода текстов программ на Си и Си++ в команды процессора компоновщик для создания исполняемого файла ( EXE- файла), подключаются стандартные функции отладчик для поиска ошибок в программах
12 Управление клавишами Новый файл (Создать) Ctrl+N Открыть файл Ctrl+O Сохранить файл Ctrl+S Закрыть окно с программой Ctrl-F4 Запуск программы F9 Отменить Ctrl-Z Восстановить отмененное Shift-Ctrl-Z
13 Где ошибки? 2 x ЛКМ эта ошибка обнаружена здесь! Ошибка может быть в конце предыдущей строки! !
14 Наиболее «популярные» ошибки xxx.h : No such file or directory не найден заголовочный файл 'xxx.h' (неверно указано его имя, он удален или т.п.) 'xxx‘ undeclared (first use this function) функция или переменная 'xxx' неизвестна missing terminating " character не закрыты кавычки " expected ; нет точки с запятой в конце оператора в предыдущей строке expected } не закрыта фигурная скобка
15 Ждем нажатия любой клавиши #include < stdio.h > #include < conio.h > main() { printf ( " Привет! " ); // вывод на экран /* ждать нажатия клавиши */ } файл conio.h : описание функций для работы с клавиатурой и монитором ждать нажатия на любую клавишу комментарий до конца строки комментарий между /* и */ getch();
16 Переход на новую строку #include < stdio.h > #include < conio.h > main() { printf ( " Привет,\ n Вася! " ); getch (); } Привет, Вася! на экране: последовательность \n (код 10) переход на новую строку \ n
17 Задания «4»: Вывести на экран текст "лесенкой" Вася пошел гулять «5»: Вывести на экран рисунок из букв Ж ЖЖЖ ЖЖЖЖЖ ЖЖЖЖЖЖЖ HH HH ZZZZZ
Тема 2. Переменные
19 Что такое переменная? Переменная – это ячейка в памяти компьютера, которая имеет имя и хранит некоторое значение. Значение переменной может меняться во время выполнения программы. При записи в ячейку нового значения старое стирается. Типы переменных int – целое число ( 4 байта) float – вещественное число, floating point (4 байта) char – символ, character (1 байт)
20 Имена переменных Могут включать латинские буквы ( A-Z, a-z) знак подчеркивания _ цифры 0-9 НЕ могут включать русские буквы пробелы скобки, знаки +, =, !, ? и др. Имя не может начинаться с цифры! ! Какие имена правильные? AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B
21 Объявление переменных Объявить переменную = определить ее имя, тип, начальное значение, и выделить ей место в памяти. main() { int a; float b, c; int Tu104, Il86=23, Yak42; float x=4.56, y, z; char c, c2= 'A', m; } Если начальное значение не задано, в этой ячейке находится «мусор»! ! целая переменная a вещественные переменные b и c целые переменные Tu104, Il86 и Yak42 Il86 = 23 вещественные переменные x, y и z x = 4,56 · целая и дробная части отделяются точкой символьные переменные c, c2 и m c2 = 'A'
22 Оператор присваивания Оператор – это команда языка программирования высокого уровня. Оператор присваивания служит для изменения значения переменной. Пример a = 5; x = a + 20; y = (a + x) * (x – a); ? a 5 5 ? x 5+20 25 ? y 600 30*20
23 Оператор присваивания Общая структура: Арифметическое выражение может включать константы ( постоянные) имена переменных знаки арифметических операций: + - * / % вызовы функций круглые скобки ( ) умножение деление остаток от деления имя переменной = выражение ; куда записать что Для чего служат круглые скобки? ?
24 Сложение двух чисел Задача. Ввести два целых числа и вывести на экран их сумму. Простейшее решение: #include < stdio.h > #include < conio.h > main() { int a, b, c; printf ( " Введите два целых числа \n" ); scanf ( "% d%d ", &a, &b); c = a + b; printf ( "%d", c); getch (); } подсказка для ввода ввод двух чисел с клавиатуры вывод результата
25 Ввод чисел с клавиатуры scanf ( "% d%d ", & a, & b); формат ввода scanf – форматный ввод адреса ячеек, куда записать введенные числа Формат – символьная строка, которая показывает, какие числа вводятся (выводятся). % d – целое число %f – вещественное число %c – 1 символ %s – символьная строка 12 7652 a – значение переменной a &a – адрес переменной a ждать ввода с клавиатуры двух целых чисел (через пробел или Enter ), первое из них записать в переменную a, второе – в b
26 Что неправильно? int a, b; scanf ( "%d", a); scanf ( "%d", &a, &b); scanf ( "% d%d ", &a); scanf ( "%d %d", &a, &b); scanf ( "% f%f ", &a, &b); &a %d%d &a, &b убрать пробел %d%d
27 Вывод чисел на экран printf ( "%d", c); здесь вывести целое число это число взять из ячейки c printf ( " Результат: %d", c); printf ( "%d +% d=%d", a, b, c ); формат вывода список значений a, b, c printf ( "%d +% d=%d", a, b, a+b ); арифметическое выражение
28 Вывод целых чисел int x = 1234; printf ( "%d", x); 1234 printf ( "%9d", x); минимальное число позиций 1234 всего 9 позиций или " %i" или " %9i" 5 4
29 Вывод вещественных чисел float x = 123.4567; printf ( "%f", x); 123.456700 printf ( "% 9.3 f", x); минимальное число позиций, 6 цифр в дробной части 123.456 всего 9 позиций, 3 цифры в дробной части printf ( "%e", x); 1.234560e+02 стандартный вид: 1,23456 ·10 2 printf ( "%10.2e", x); 1.23e+02 всего 10 позиций, 2 цифры в дробной части мантиссы
30 Полное решение #include < stdio.h > #include < conio.h > main() { int a, b, c; printf ( " Введите два целых числа \n" ); scanf ( "% d%d ", &a, &b); c = a + b; printf ( "%d+%d=%d", a, b, c); getch (); } Протокол : Введите два целых числа 25 30 25+30=55 это выводит компьютер это вводит пользователь
31 Блок-схема линейного алгоритма начало конец c = a + b; ввод a, b вывод c блок «начало» блок «ввод» блок «процесс» блок «вывод» блок «конец»
32 Задания « 3 »: Ввести три числа, найти их сумму. Пример: Введите три числа: 4 5 7 4+5+7=16 « 4 »: Ввести три числа, найти их сумму и произведение. Пример: Введите три числа: 4 5 7 4+5+7=16 4*5*7=140
33 Задания «5»: Ввести три числа, найти их сумму, произведение и среднее арифметическое. Пример: Введите три числа: 4 5 7 4+5+7=16 4*5*7=140 (4+5+7) / 3 =5.33
34 main() { int a, b; float x, y; a = 5; 10 = x; y = 7, 8; b = 2.5; x = 2*(a + y); a = b + x; } Какие операторы неправильные? имя переменной должно быть слева от знака = целая и дробная часть отделяются точкой при записи вещественного значения в целую переменную дробная часть будет отброшена
35 Особенность деления в Си При делении целых чисел остаток отбрасывается! ! main() { int a = 7; float x; x = a / 4 ; x = 4 / a; x = float (a) / 4 ; x = 1.*a / 4 ; } 1 0 1.75 1.75
36 Сокращенная запись операций в Си полная запись сокращенная запись инкремент декремент a = a + 1; a++; a = a + b; a += b; a = a - 1; a--; a = a – b; a -= b; a = a * b; a *= b; a = a / b; a /= b; a = a % b; a %= b;
37 вычисление выражений в скобках умножение, деление и % (остаток от деления) слева направо сложение и вычитание слева направо 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
38 Ручная прокрутка программы main() { int a, b; a = 5; b = a + 2; a = (a + 2)*(b – 3); b = a / 5; a = a % b; a++; b = (a + 14) % 7; } a b 5 7 28 5 3 4 4 ? ?
39 int a = 1, b = 3 ; printf ( "%d+%d=%d", a, b, a+b ); список вывода элементы списка разделяются запятыми форматы вывода начинаются с % выражения (элементы без кавычек) вычисляются и выводится их результат 1+3=4 Что будет выведено? ? формат вывода
40 int a = 1, b = 3 ; printf( " a + %d= a+b ", b ); a +3= a+b int a = 1, b = 3 ; printf( " %d = F(%d) ", a, b ) ; 1= F(3) int a = 1, b = 3 ; printf( " a = F(%d); ", b); int a = 1, b = 3 ; printf( " %d>%d! ", a+b, b); int a = 1, b = 3 ; printf( " F(%d)=X(%d) ", b, a); a = F(3); 4 >3! F(3) = X(1)
41 int a = 1, b = 3 printf( " X(%d)=%d ", b, a); X(3)=1 4=1+ 3 f(1)>f(3) <1<>3> 1+3 = ? int a = 1, b = 3 printf( " %d=%d+%d ", a + b,a, b); int a = 1, b = 3 printf( " f(%d)>f(%d) ", a, b); int a = 1, b = 3 printf( " <%d<>%d> ", a, b); int a = 1, b = 3 printf( " %d+%d=? ", a, b);
Тема 3. Ветвления
43 Разветвляющиеся алгоритмы Задача. Ввести два целых числа и вывести на экран наибольшее из них. Идея решения: надо вывести на экран первое число, если оно больше второго, или второе, если оно больше первого. Особенность: действия исполнителя зависят от некоторых условий ( если … иначе … ). Алгоритмы, в которых последовательность шагов зависит от выполнения некоторых условий, называются разветвляющимися.
44 Вариант 1. Блок-схема начало max = a; ввод a,b вывод max a > b? max = b; конец да нет полная форма ветвления блок «решение» Если a = b? ?
45 Вариант 1. Программа main() { int a, b, max; printf( " Введите два целых числа \n" ); scanf( "%d%d", & a, & b ); if (a > b) { } else { } printf( " Наибольшее число %d", max); } max = a ; max = b ; полная форма условного оператора
46 Условный оператор if ( условие ) { // что делать, если условие верно } else { // что делать, если условие неверно } Особенности: вторая часть ( else …) может отсутствовать (неполная форма) если в блоке один оператор, можно убрать { }
47 Что неправильно? if a > b { a = b; } else b = a; if ( a > b ) { a = b; else b = a; if ( a > b ) else b = a; if ( a > b ) a = b; c = 2*a; else b = a; } ( ) } { a = b;
48 Вариант 2. Блок-схема неполная форма ветвления начало max = a; ввод a,b вывод max max = b; конец да нет b > a?
49 Вариант 2. Программа main() { int a, b, max; printf( " Введите два целых числа \n" ); scanf( "%d%d", &a, &b ); max = a; if (b > a) printf( " Наибольшее число %d", max); } max = b ; неполная форма условного оператора
50 main() { int a, b, max; printf ( " Введите два целых числа \n" ); scanf ( "% d%d ", &a, &b ); max = b; if ( ??? ) ??? printf ( " Наибольшее число %d", max); } Вариант 2Б. Программа max = a; a > b
51 Задания « 3 »: Ввести два числа и вывести их в порядке возрастания. Пример: Введите два числа: 15 9 Ответ: 9 15 «4»: Ввести три числа и найти наибольшее из них. Пример: Введите три числа: 4 15 9 Наибольшее число 15
52 Задания «5»: Ввести пять чисел и найти наибольшее из них. Пример: Введите пять чисел: 4 15 9 56 4 Наибольшее число 5 6
Тема 4. Сложные условия
54 Сложные условия Задача. Фирма набирает сотрудников от 25 до 40 лет включительно. Ввести возраст человека и определить, подходит ли он фирме (вывести ответ «подходит» или «не подходит» ). Особенность: надо проверить, выполняются ли два условия одновременно. Можно ли решить известными методами ? ?
55 Вариант 1. Алгоритм начало ввод x ' подходит ' конец да нет x >= 25? да нет x < = 40? ' не подходит ' ' не подходит '
56 Вариант 1. Программа main() { int x; printf( " Введите возраст \n" ); scanf( "%d", &x); if (x >= 25) if (x <= 40) printf( " Подходит " ); else printf( " Не подходит " ); else printf( " Не подходит " ); }
57 Вариант 2. Алгоритм начало ввод x ' подходит ' да нет x >= 25 и x <= 40? ' не подходит ' конец
58 Вариант 2. Программа main() { int x; printf( " Введите возраст \n" ); scanf( "%d", &x); if ( x >= 25 && x <= 40 ) printf( " Подходит " ); else printf( " Не подходит " ); } сложное условие
59 Сложные условия Сложное условие – это условие, состоящее из нескольких простых условий (отношений), связанных с помощью логических операций : ! – НЕ ( not, отрицание, инверсия) && – И ( and, логическое умножение, конъюнкция, одновременное выполнение условий) || – ИЛИ ( or, логическое сложение, дизъюнкция, выполнение хотя бы одного из условий) Простые условия (отношения) < <= > >= == != равно не равно
60 Сложные условия Порядок выполнения сложных условий: выражения в скобках ! (НЕ, отрицание) <, <=, >, >= = =, != && ( И) || ( ИЛИ) Пример: 2 1 6 3 5 4 if ( ! (a > b) || c != d && b == a) { ... }
61 Истинно или ложно при a = 2; b = 3; c = 4; ! (a > b) a < b && b < c !(a >= b) || c == d a < c || b < c && b < a a > b || !(b < c) Для каких значений 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 Сложные условия 1 1 0 (- , 6) (6, 10) (10, ) (- , 10) (- , 6) (10, ) (- , ) (6, ) x < 6 x > 10 x < 10 x > 6 1 1
62 Задания «3»: Ввести три числа и определить, верно ли, что они вводились в порядке возрастания. Пример: Введите три числа: 4 5 17 да «4»: Ввести номер месяца и вывести название времени года. Пример: Введите номер месяца: 4 весна
63 Задания «5»: Ввести возраст человека (от 1 до 150 лет) и вывести его вместе с последующим словом «год», «года» или «лет». Пример: Введите возраст: Введите возраст: 24 57 Вам 24 года Вам 57 лет
Тема 5. Циклы
65 Цикл – это многократное выполнение одинаковых действий. цикл с известным числом шагов цикл с неизвестным числом шагов (цикл с условием) Задача. Вывести на экран 5 раз слово «Привет». Особенность: одинаковые действия выполняются 5 раз. Можно ли решить известными методами ? ?
66 #include < stdio.h > main() { printf ( " Привет!\ n " ) ; printf ( " Привет!\ n " ) ; printf ( " Привет!\ n " ) ; printf ( " Привет!\ n " ) ; printf ( " Привет!\ n " ) ; } Что плохо ? ?
67 начало конец Блок-схема: да нет тело цикла сделали 5 раз ? printf( "Привет! \n " );
68 Как отсчитать ровно 5 раз ? ? Как запоминать, сколько раз уже сделали ? ? N := N + 1
69 начало конец да нет N == 5 ? N = 0 ; N = N + 1; еще не сделали ни одного раза всё ли сделали считаем очередной шаг printf ( "Привет! \n " ); цикл N++;
70 main() { int N; N = 0 ; while ( N != 5 ) { printf ( " Привет ! \n " ); N ++; } }
71 Вместо знаков вопроса добавьте числа и операторы так, чтобы цикл выполнился ровно 5 раз: main() { int N; N = 5 ; while ( N != ??? ) { printf ( " Привет ! \n " ); ??? ; } } 0 N = N - 1 ; N --;
72 // Пример 1 main() { int N; N = 1 ; while ( N <= 5 ) { printf ( " %d\n ", N); N ++; } } 1 2 3 4 5
73 // Пример 2 main() { int N; N = 1 ; while ( N <= 5 ) { printf ( " %d\n ", N); N = N + 2 ; } } 1 3 5 N += 2 ;
74 // Пример 3 main() { int N; N = 2 ; while ( N ! = 5 ) { printf ( " %d\n ", N); N += 2 ; } } 2 4 6 8 10 12 14 16 ... Условие цикла никогда не станет ложным – это зацикливание ! !
75 // Пример 4 main() { int N; N = 1 ; while ( N ! = 5 ) { printf ( " %d\n ", N * N*N); N = N + 1 ; } } 1 8 27 64 125
76 // Пример 4 main() { int N; N = 5 ; while ( N >= 1 ) { printf ( " %d\n ", N * N*N); N = N - 1 ; } } 1 25 64 27 8 1
77 «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
78 «5»: Ввести два целых числа a и b ( a ≤ b ) и вывести сумму квадратов всех чисел от a до b. Пример: Введите два числа: 4 10 Сумма квадратов 371
79 Цикл с неизвестным числом шагов Пример: Отпилить полено от бревна. Сколько раз надо сделать движения пилой? Задача: Ввести целое число ( <2000000) и определить число цифр в нем. Идея решения: Отсекаем последовательно последнюю цифру, увеличиваем счетчик. Проблема: Неизвестно, сколько шагов надо сделать. Решение: Надо остановиться, когда n = 0, т.е. надо делать «пока n != 0 ». n count 123 0 12 1 1 2 0 3
80 Алгоритм начало count конец нет да n != 0? count = 0 ; count = count + 1; n = n / 10; обнулить счетчик цифр ввод n выполнять «пока n != 0 »
81 Программа main() { int n, count ; printf( " Введите целое число \n" ); scanf( "%d", &n); count = 0; while (n != 0) { count ++; n = n / 10; } printf( " В числе %d нашли %d цифр ", n, count ); } n1 = n; n1, выполнять «пока n != 0 » Что плохо ? ? , n1;
82 Цикл с условием while ( условие ) { // тело цикла } Особенности: можно использовать сложные условия: если в теле цикла только один оператор, скобки {} можно не писать: while ( a < b && b < c ) {... } while ( a < b ) a ++;
83 Цикл с условием Особенности: условие пересчитывается каждый раз при входе в цикл если условие на входе в цикл ложно, цикл не выполняется ни разу если условие никогда не станет ложным, программа зацикливается a = 4; b = 6; while ( a > b ) a = a– b; a = 4; b = 6; while ( a < b ) d = a + b;
84 Сколько раз выполняется цикл ? a = 4; b = 6; while ( a < b ) a ++; 2 раза a = 6 a = 4; b = 6; while ( a < b ) a += b ; 1 раз a = 10 a = 4; b = 6; while ( a > b ) a ++; 0 раз a = 4 a = 4; b = 6; while ( a < b ) b = a - b; 1 раз b = -2 a = 4; b = 6; while ( a < b ) a --; зацикливание
85 Задания «3»: Ввести целое число и определить, верно ли, что в нём ровно 3 цифры. Пример: Введите число: Введите число: 123 1234 Да. Нет. «4»: Ввести целое число и найти сумму его цифр. Пример: Введите целое число: 1234 Сумма цифр числа 1234 равна 10.
86 «5»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом. Пример: Введите целое число: Введите целое число: 1232 1224 Нет. Да. «6»: Ввести целое число и определить, верно ли, что в его записи есть две одинаковые цифры, НЕ обязательно стоящие рядом. Пример: Введите целое число: Введите целое число: 1234 1242 Нет. Да.
87 «3»: Ввести целое число и определить, верно ли, что в нём ровно 1 цифра «9». Пример: Введите число: Введите число: 193 1994 Да. Нет. «4»: Ввести целое число и определить, верно ли, что все его цифры четные. Пример: Введите число: Введите число: 2684 2994 Да. Нет.
88 «5»: Ввести целое число и определить, верно ли, что все его цифры расположены в порядке возрастания. Пример: Введите целое число: Введите целое число: 1238 1274 Да. Нет. «6»: Ввести целое число и «перевернуть» его, так чтобы первая цифра стала последней и т.д. Пример: Введите целое число: Введите целое число: 1234 782 4321 287
89 НОД = наибольший общий делитель двух натуральных чисел – это наибольшее число, на которое оба исходных числа делятся без остатка. Перебор: Записать в переменную k минимальное из двух чисел. Если a и b без остатка делятся на k, то стоп. Уменьшить k на 1. Перейти к шагу 2. Где будет НОД? ? Почему алгоритм обязательно закончится? ? это цикл с условием!
90 Евклид (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.
91 a = b? да нет a > b? да a = a - b нет b = b - a начало конец
92 while ( a != b ) { if ( a > b ) a = a – b; else b = b – a; } Где будет НОД? Как его вывести? ? Как вывести НОД в формате НОД(14,21) = 7? ? А без дополнительных переменных? ?
93 НОД( a,b )= НОД( a % b, b) = НОД( a, b % a) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД. НОД (14, 21 ) = НОД (14, 7 ) = НОД (0, 7 ) = 7 Пример: Еще один вариант: НОД( 2 · a,2 · b)= 2 · НОД( a, b) НОД( 2 · a,b)= НОД( a, b) | при нечетном b
94 «3» : Составить программу для вычисления НОД с помощью алгоритма Евклида. « 4 » : Составить программу для вычисления НОД с помощью модифицированного алгоритма Евклида и заполнить таблицу: a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД( a,b )
95 «5» : Выполнить задание на «4» и подсчитать число шагов алгоритма для каждого случая. a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД( a,b ) шагов
96 Последовательности Примеры: 1, 2, 3, 4, 5, … 1, 2, 4, 7, 11, 16, … 1, 2, 4, 8, 1 6, 32, … a n = n a 1 = 1, a n +1 = a n +1 a 1 = 1, a n +1 = a n + n a n = 2 n-1 a 1 = 1, a n +1 = 2 a n b 1 = 1, b n +1 = b n +1 c 1 = 2, c n +1 = 2 c n
97 Последовательности Задача: найти сумму всех элементов последовательности, которые по модулю больше 0,001: Элемент последовательности (начиная с №2): n 1 2 3 4 5 ... b 1 2 3 4 5 ... c 2 4 8 16 32 ... z -1 1 -1 1 -1 ... b = b+1; c = 2*c; z = -z;
98 Алгоритм начало S конец нет да |a| > 0.001? S = S + a; S = 0 ; b = 1; c = 2 ; z = -1; a = 1; начальные значения a = z*b/c; b = b + 1; c = 2*c; z = -z; первый элемент a = 1; S = 0 ; новый элемент изменение Перестановка ? ?
99 Программа #include <math.h> main() { int b, c, z; float S, a; S = 0; z = -1; b = 1; c = 2; a = 1; while (fabs(a) > 0.001) { S += a; a = z * b / c; z = - z; b ++; c *= 2; } printf ( "S = %10.3f", S); } переход к следующему слагаемому начальные значения увеличение суммы расчет элемента последовательности математические функции fabs – модуль вещественного числа Что плохо? ? , b; чтобы не было округления при делении
100 Задания «4»: Найти сумму элементов последовательности с точностью 0,001: Ответ: S = 1.157 «5»: Найти сумму элементов последовательности с точностью 0,001: Ответ: S = 1.220
101 Цикл с постусловием Задача: Ввести целое положительное число ( <2000000) и определить число цифр в нем. Проблема: Как не дать ввести отрицательное число или ноль? Решение: Если вводится неверное число, вернуться назад к вводу данных (цикл!). Особенность: Один раз тело цикла надо сделать в любом случае проверку условия цикла надо делать в конце цикла (цикл с постусловием ). Цикл с постусловием – это цикл, в котором проверка условия выполняется в конце цикла.
102 Цикл с постусловием: алгоритм начало конец нет да n <= 0? тело цикла условие блок «типовой процесс» ввод n основной алгоритм
103 Программа main() { int n; do { printf( " Введите положительное число \n" ); scanf( "%d", &n); } while ( n <= 0 ); ... // основной алгоритм } условие Особенности: тело цикла всегда выполняется хотя бы один раз после слова while («пока…» ) ставится условие продолжения цикла
104 Сколько раз выполняется цикл ? a = 4; b = 6; do { a ++; } while (a <= b); 3 раза a = 7 a = 4; b = 6; do { a += b ; } while ( a <= b ); 1 раз a = 10 a = 4; b = 6; do { a += b ; } while ( a >= b ); зацикливание a = 4; b = 6; do b = a - b ; while ( a >= b ); 2 раза b = 6 a = 4; b = 6; do a += 2 ; while ( a >= b ); зацикливание
105 Задания (с защитой от неверного ввода) «4»: Ввести натуральное число и определить, верно ли, что сумма его цифр равна 10. Пример: Введите число >= 0 : Введите число >= 0 : -234 1233 Нужно положительное число. Нет Введите число >= 0 : 1234 Да «5»: Ввести натуральное число и определить, какие цифры встречаются несколько раз. Пример: Введите число >= 0 : Введите число >= 0 : 2323 1234 Повторяются: 2, 3 Нет повторов.
Тема 6. Циклы с переменной
107 Цикл c переменной Цикл – это многократное выполнение одинаковой последовательности действий. цикл с известным числом шагов цикл с неизвестным числом шагов (цикл с условием) Задача. Вывести на экран кубы целых чисел от 1 до 8 (от a до b ). Особенность: одинаковые действия выполняются 8 раз. Можно ли решить известными методами ? ?
108 Алгоритм начало конец нет да N <= 8 ? N = 1; N ++; вывод cubeN cubeN = N*N*N;
109 Задача: вывести кубы натуральных чисел от 1 до 8. main() { int N, cubeN ; N = 1 ; while ( N <= 8 ) { cube N = N*N*N; printf( "% 4d\n", cubeN ); N++; } } N = 1 ; N <= 8 N++; 3 действия с N
110 Алгоритм ( с блоком «цикл») начало N, cubeN конец cubeN = N*N*N; N = 1,8 блок «цикл» тело цикла
111 Программа main() { int N, cubeN; for (i=1; i<=8; i++) { cubeN = N*N*N; printf( "%4d %4d\n", N, cubeN); } } for (N=1; N<=8; N++) { cubeN = N*N*N;; printf( "%4d %4d\n", N, cubeN ); } переменная цикла начальное значение конечное значение изменение на каждом шаге: i=i+1 ровные столбики цикл работает, пока это условие верно цикл начало цикла конец цикла заголовок цикла for (N=1; N<=8; N++) cubeN = N*N*N; printf( "%4d %4d\n", N, cubeN ); тело цикла
112 Цикл с уменьшением переменной Задача. Вывести на экран кубы целых чисел от 8 до 1 (в обратном порядке). Особенность: переменная цикла должна уменьшаться. Решение: for ( ) { cubeN = N*N*N; printf ( "%4d % 4d\n", N, cubeN); } N = 8; N >= 1; N --
113 Цикл с переменной for ( начальные значения ; условие продолжения цикла ; изменение на каждом шаге ) { // тело цикла } Примеры: for (a = 2; a < b; a+=2) {... } for (a = 2, b = 4; a < b; a+=2) {... } for (a = 1; c < d; x++) {... } for (; c < d; x++) {... } for (; c < d; ) {... }
114 Цикл с переменной Особенности: условие проверяется в начале очередного шага цикла, если оно ложно цикл не выполняется; изменения (третья часть в заголовке) выполняются в конце очередного шага цикла; если условие никогда не станет ложным, цикл может продолжаться бесконечно ( зацикливание ) если в теле цикла один оператор, скобки {} можно не ставить: for ( i= 1 ; i <8; i ++) { i -- ; } for ( i = 1 ; i < 8; i ++) a += b ; Не рекомендуется менять переменную цикла в теле цикла! !
115 for ( i=8 ; i >=1; i --) printf( " Привет " ); printf ( " i =%d", i ) ; Цикл с переменной Особенности: после выполнения цикла во многих системах устанавливается первое значение переменной цикла, при котором нарушено условие: for ( i= 1 ; i <=8; i ++) printf( " Привет " ); printf ( " i =%d", i ) ; i=9 i=0
116 Сколько раз выполняется цикл? a = 1; for (i= 1 ; i <4; i ++) a++; a = 4 a = 1; b=2; for (i=3; i >= 1; i --)a += b; a = 7 a = 1; for (i= 1 ; i >= 3; i --)a = a+1; a = 1 a = 1; for (i=1; i<= 4; i--) a ++; зацикливание a = 1; for (i= 1 ; i <4; i ++) a = a+i ; a = 7
117 Замена for на while и наоборот for ( i=1; i<=10; i++) { // тело цикла } i = 1; while ( i <= 10 ) { // тело цикла i ++; } for ( i=a; i>=b; i--) { // тело цикла } i = a; while ( i > = b ) { // тело цикла i --; } В языке Си замена цикла for на while и наоборот возможна всегда ! !
118 «3»: Ввести натуральное число N и вывести числа от N до 1 (через одно) в порядке убывания. Пример: Введите натуральное число: 8 Ответ: 8 6 4 2
119 «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
120 Задания «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
121 Задания «5»: Ввести два целых числа a и b ( a ≤ b ) и вывести сумму квадратов всех чисел от a до b. Пример: Введите два числа: 4 10 Сумма квадратов 371
Тема 7. Оператор выбора
123 Оператор выбора Задача: Ввести номер месяца и вывести количество дней в этом месяце. Решение: Число дней по месяцам: 28 дней – 2 (февраль) 30 дней – 4 (апрель), 6 (июнь), 9 (сентябрь), 11 (ноябрь) 31 день – 1 (январь), 3 (март), 5 (май), 7 (июль), 8 (август), 10 (октябрь), 12 (декабрь) Особенность: Выбор не из двух, а из нескольких вариантов в зависимости от номера месяца. Можно ли решить известными методами ? ?
124 Алгоритм начало конец оператор выбора ни один вариант не подошел ввод M да нет M = 1? D = 31; нет M = 2? D = 28; да нет M = 12? D = 31; да вывод D ошибка
125 Программа main() { int M, D; printf(" Введите номер месяца: \n"); scanf("%d", &M); switch ( M ) { case 2: D = 28; case 4: case 6: case 9: case 11: D = 30; case 1: case 3: case 5: case 7: case 8: case 10: case 12: D = 31; default: D = -1; } if (D > 0) printf(" В этом месяце %d дней. ", D); else printf(" Неверный номер месяца "); } ни один вариант не подошел break; break; break; выйти из switch
126 Оператор выбора Задача: Ввести букву и вывести название животного на эту букву. Особенность: выбор по символьной величине. main() { char c; printf(" Введите первую букву названия животного: \n"); scanf("%c", &c); switch ( c ) { case ' а ': printf(" Антилопа "); break; case ' б ': printf(" Бизон "); break; case ' в ': printf(" Волк "); break; default: printf(" Я не знаю! "); } } Что будет, если везде убрать break ? ?
127 Оператор выбора Особенности: после switch может быть имя переменной или арифметическое выражение целого типа ( int ) или символьного типа ( char ) нельзя ставить два одинаковых значения: switch ( i+3 ) { case 1: a = b; break; case 2: a = c; } switch ( x ) { case 1: a = b; break; case 1 : a = c; }
128 Задания (с защитой от неверного ввода) «4»: Ввести номер месяца и вывести количество дней в нем, а также число ошибок при вводе. Пример: Введите номер месяца: Введите номер месяца: -2 2 Введите номер месяца: В этом месяце 28 дней. 1 1 Вы вводили неверно 0 раз. В этом месяце 30 дней. Вы вводили неверно 1 раз. «5»: Ввести номер месяца и номер дня, вывести число дней, оставшихся до Нового года. Пример: Введите номер месяца: 12 Введите день: 25 До Нового года осталось 6 дней.
Тема 8. Отладка программ
130 Отладка программ Отладка – поиск и исправление ошибок в программе. Англ. debugging, bug = моль, жучок Методы: трассировка – вывод сигнальных сообщений отключение части кода (в комментарии) пошаговое выполнение – выполнить одну строчку программы и остановиться точки останова – выполнение программы останавливается при достижении отмеченных строк (переход в пошаговый режим) просмотр и изменение значений переменных в пошаговом режиме
131 Трассировка printf ( " Введено X=%d\n", X); printf(" В цикле: i=%d, X=%d\n", i, X); printf(" После цикла: X=%d\n", X); main() { int i, X; printf(" Введите целое число: \n"); scanf("%d", &X); for(i=1; i<10; i++) { ... } ... }
132 Отключение части кода (комментарии) main() { int i, X; printf(" Введите целое число: \n"); scanf("%d", &X); X *= X + 2; for(i=1; i<10; i++) X *= i; while ( X > 5 ) { ... } ... } // X *= X + 2; /* while ( X > 5 ) { ... } */ комментарий до конца строки // закомментированный блок /* … */
133 Точки останова это точка останова ЛКМ или Ctrl+F5 F8 – запустить и выполнить до следующей точки останова F7 – выполнить одну строку Shift+F7 – войти в процедуру (функцию) Ctrl-F7 – выполнять дальше Ctrl-Alt-F2 – остановить программу
134 Просмотр значений переменных навести мышь на имя переменной ПКМ
Тема 9. Графика
136 Система координат (0,0) ( x, y ) X Y x y
137 Принцип сэндвича рисование в графическом режиме открыть окно для графики закрыть окно для графики
138 #include <graphics.h> #include <conio.h> main() { initwindow ( 400, 300 ); ... // рисуем на экране getch(); closegraph(); } initwindow ( 400, 300 ); closegraph(); Структура графической программы открыть окно для графики закрыть окно чтобы посмотреть результат библиотека для работы с графикой ширина высота
139 Цвета Код Название 0 BLACK 1 BLUE 2 GREEN 3 CYAN 4 RED 5 MAGENTA 6 BROWN 7 LIGHTGRAY Код Название 8 DARKGRAY 9 LIGHTBLUE 10 LIGHTGREEN 11 LIGHTCYAN 12 LIGHTRED 13 LIGHTMAGENTA 14 YELLOW 15 WHITE
140 Полная палитра цветов цвет = R + G + B Red красный 0..255 Blue синий 0..255 Green зеленый 0..255 R = 218 G = 164 B = 32 R = 135 G = 206 B = 250 Сколько разных цветов? ? 256 · 256 · 256 = 16 777 216 ( True Color )
141 Управление цветом Цвет линий и текста: set color = установить цвет setcolor ( 12 ); setcolor ( COLOR(255,255,0) ); Цвет и стиль заливки: set fill style = установить стиль заливки setfillstyle ( стиль, цвет ); 0 – выключить 3..6 – наклонные линии 1 – сплошная 7..8 – сетка 9..11 – точечная номер цвета R G B
142 Точки, отрезки и ломаные ( x 1, y 1 ) ( x 2, y 2 ) setcolor ( 10 ) ; line (x1, y1, x2, y2) ; ( x, y ) putpixel (x, y, 9 ); ( x 1, y 1 ) ( x 2, y 2 ) ( x 3, y 3 ) ( x 4, y 4 ) ( x 5, y 5 ) setcolor ( 12 ) ; moveto (x1, y1) ; lineto (x2, y2) ; lineto (x3, y3) ; lineto (x4, y4) ; lineto (x5, y5) ; цвет
143 Прямоугольники ( x 1, y 1 ) ( x 2, y 2 ) setcolor ( 9 ) ; rectangle (x1, y1, x2, y2) ; ( x 1, y 1 ) ( x 2, y 2 ) setfillstyle ( 1, 12 ) ; bar (x1, y1, x2, y2) ; ( x 1, y 1 ) ( x 2, y 2 ) setfillstyle ( 1, 12 ); bar (x1, y1, x2, y2); setcolor ( 9 ) ; rectangle (x1, y1, x2, y2) ; цвет стиль (1 - сплошная)
144 Окружность, заливка, текст setcolor ( COLOR(255,0,0) ) ; circle ( x, y, R ) ; setfillstyle ( 1, 11 ) ; floodfill ( x, y, 0) ; ( x, y ) ( x, y ) R стиль (1 - сплошная) цвет границы цвет заливки ( x, y ) Вася setcolor ( 9 ) ; outtextxy ( x, y, " Вася " ) ;
145 Пример (200, 50) (100, 100) (300, 200) setfillstyle (1, 9); bar (100,100,300,200); setcolor (13); rectangle (100,100,300,200); moveto (100,100); lineto (200, 50); lineto (300,100); setfillstyle (1, 14); floodfill (200, 75, 13); setcolor (15); circle (200, 150,50); setfillstyle (1, 10); floodfill (200,150, 15); setcolor (12); outtextxy (100, 2 3 0, "Sharik's house."); Sharik's house
146 «5»: «Корона»
147 «3»: «Домик» «4»: «Лягушка»
148 Штриховка ( x 1, y 1 ) ( x 2, y 2 ) N линий ( N=5) h rectangle (x1, y1, x2, y2) ; line( x1+h, y1, x1+h, y2) ; line( x1+2*h, y1, x1+2*h, y2) ; line( x1+3*h, y1, x1+3*h, y2) ; ... rectangle(x1, y1, x2, y2) ; h = (x2 – x1) / (N + 1.); for (x = x1+h; x < x2; x += h) line(x, y1, x, y2) ; x дробная часть x отбрасывается x float x, h; ! результат – дробное число
149 Штриховка (программа) ( x 1, y 1 ) ( x 2, y 2 ) h #include <graphics.h> #include <conio.h> main() { int N = 10, x1 = 100, x2 = 300, y1 = 100, y2 = 200; float h, x; initwindow(800,600); rectangle (x1, y1, x2, y2); getch(); closegraph(); } прямоугольник штриховка N h = (x2 – x1) / (N + 1.); for (x = x1+h; x < x2; x += h) line(x, y1, x, y2);
150 Штриховка ( x 1, y 1 ) ( x 2, y 2 ) ( x 3, y 2 ) a h ( x 3 + a, y 1 ) line( x1+h, y1, x1+h-a, y2) ; line( x1+2*h, y1, x1+2*h-a, y2) ; line( x1+3*h, y1, x1+3*h-a, y2) ; ... h = (x3 – x2) / (N + 1.); a = x2 – x1; x = x1 + h; for (i = 1; i <= N; i ++, x += h ) line(x, y1, x-a, y2) ; x x-a i ++, x += h после каждого шага выполняются две команды Плюсы и минусы? ?
151 Штриховка ( x 1, y 1 ) ( x 2, y 2 ) h x h y y x y line( x1, y1+hy, x1+hx, y1+hy ) ; line( x1, y1+2* hy, x1+2* hx, y1+2* hy ) ; line( x1, y1+3* hy, x1+3* hx, y1+3* hy ) ; ... hx = (x2 – x1) / (N + 1.); hy = (y2 – y1) / (N + 1.); x = x1 + hx; y = y1 + hy; for (i=1; i <= N; i++) { line( x1, y, x, y ) ; x += hx; y += hy; }
152 Задания « 3 »: Ввести с клавиатуры количество линий, построить фигуру и выполнить штриховку : «4»: Ввести с клавиатуры количество линий, построить фигуру и выполнить штриховку : или
153 «5»: Ввести с клавиатуры количество линий и построить фигуру:
COLOR(c, c, c) 154 Как менять цвет? ( x 1, y 1 ) ( x 2, y 2 ) hc = 255 / N; c = 0; for ( i=1; i<=N+1; i++ ) { setfillstyle ( 1, COLOR(c,c,c) ); floodfill( ???, ???, 15 ); c + = hc; } цвет границы Шаг изменения c : серый: R = G = B Цвет : Изменение c : 0,..., 255 N
155 Как менять цвет? setfillstyle( 1, COLOR(c,c,c) ); floodfill ( ???, ???, 15 ); hc = 255 / N; c = 0; x = x1 + h; for ( i=1; i <= N+1; i++ ) { setfillstyle(1,COLOR(c,c,c)); floodfill ( x-1, y1+1, 15 ); x += h; c += hc; } c = 0 ; COLOR(c,c,c) c += hc; правая граница полосы Как объединить циклы штриховки и заливки? ? ( x 1, y 1 ) ( x 2, y 2 ) ( x-1, y 1 +1 ) x
156 Задания «4»: Ввести с клавиатуры число линий штриховки и построить фигуру, залив все области разным цветом. «5»: Ввести с клавиатуры число окружностей и построить фигуру, залив все области разным цветом.
Тема 10. Графики функций (только с 9 класса)
158 Построение графиков функций Задача: построить график функции y = 3 sin(x ) на интервале от 0 до 2 π. Анализ: максимальное значение y max = 3 при x = π /2 минимальное значение y min = -3 при x = 3 π /2 Проблема: функция задана в математической системе координат, строить надо на экране, указывая координаты в пикселях.
159 Преобразование координат ( x, y ) X Y x y Математическая система координат Экранная система координат (пиксели) ( x э, y э ) x э y э ( 0, 0 ) ( 0, 0 ) a b k – масштаб (длина изображения единичного отрезка на экране) x э = a + kx y э = b - ky
160 Программа const a = 50, b = 200, k = 50; const float xmin = 0, xmax =2*M_PI; float x, y, h = 0.01; int xe, ye, w; w = (xmax - xmin)*k; line(a-10, b, a+w, b); line(a, 0, a, 2*b); for (x = xmin; x < xmax; x += h) { y = 3*sin(x); xe = a + k*x; ye = b - k*y; putpixel (xe, ye, 12); } Что плохо ? ? 2 π h – шаг изменения x w – длина оси ОХ в пикселях координаты точки на экране оси координат обязательно #include <math.h>
161 Как соединить точки? Алгоритм: Если первая точка перейти в точку ( x э, y э ) иначе отрезок в точку ( x э, y э ) Программа: выбор варианта действий переменная-флаг (1 или 0) int first; ... first = 1 ; for (x = xmin; x < xmax; x += h) { ... if ( first ) { moveto(xe, ye); first = 0; } else lineto(xe, ye); ... } начальное значение
162 Задания «4»: Построить график функции y = x 2 на интервале [-3,3]. «5»: Построить график функции ( эллипс)
Тема 11. Процедуры
164 Процедуры Задача: Построить фигуру: Особенность: Три похожие фигуры. общее : размеры, угол поворота отличия : координаты, цвет Можно ли решить известными методами ? ? Сколько координат надо задать ? ?
165 Процедуры Процедура – это вспомогательный алгоритм, который предназначен для выполнения некоторых действий. Применение: выполнение одинаковых действий в разных местах программы разбивка программы (или другой процедуры) на подзадачи для лучшего восприятия Подзадача1 Подзадача 2 Подзадача3 1.1 1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3 Задача
166 Процедуры Порядок разработки: выделить одинаковое или похожее ( три фигуры ) найти в них общее (размеры, форма, угол поворота) и отличия (координаты, цвет) отличия записать в виде неизвестных переменных, они будут параметрами процедуры ( x, y ) 100 60 ( x +100, y ) ( x, y -60) void Tr( int x, int y, int c ) { ... } имя процедуры тело координаты цвет void – «пустой» (некоторые действия) параметры
167 Процедуры ( x, y ) 100 60 ( x +100, y ) ( x, y -60) void Tr( int x, int y, int c ) { moveto ( x, y ); lineto ( x, y-60 ); lineto ( x+100, y ); lineto ( x, y ); setfillstyle ( 1, c ); floodf ill ( x+20, y-20, 15); } тело процедуры формальные параметры « Формальные параметры » могут изменяться, заранее неизвестны (обозначаются именами, как переменные).
168 Программа #include <conio.h> #include <graphics.h> main() { initwindow (400, 300); Tr (100, 100, COLOR(0,0,255)); Tr (200, 100, COLOR(0,255,0)); Tr (200, 160, COLOR(255,0,0)); getch(); closegraph(); } ( 100, 100 ) 100 60 фактические параметры вызовы процедуры void Tr( int x, int y, int c) { ... } формальные параметры процедура
169 Процедуры Особенности: обычно процедуры расположены выше основной программы в заголовке процедуры перечисляются формальные параметры, они обозначаются именами, поскольку могут меняться при вызове процедуры в скобках указывают фактические параметры (числа или арифметические выражения) в том же порядке void Tr( int x, int y, int c ) Tr ( 200, 100, COLOR(255,0,0) ); x y c
170 Процедуры Особенности: для каждого формального параметра в заголовке процедуры указывают его тип внутри процедуры параметры используются так же, как и переменные в процедуре можно объявлять дополнительные локальные переменные, остальные процедуры не имеют к ним доступа void A ( int x, float y, char z ) {... } void A ( int x, float y, char z ) { int a2, bbc = 345; ... } локальные переменные int a2, bbc = 345;
171 Как поменять местами? 2 3 1 Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти. 4 6 ? 4 6 4 x y c c = x; x = y; y = c ; x = y; y = x; 3 2 1 Можно ли обойтись без c ? ?
172 Параметры-переменные Задача: составить процедуру, которая меняет местами значения двух переменных. Особенности: надо, чтобы изменения, сделанные в процедуре, стали известны вызывающей программе. main() { int x = 1, y = 2; Swap ( x, y ); printf ( "x = %d, y = %d", x, y ); } void Swap ( int a, int b ) { int c; c = a; a = b; b = c; } эта процедура работает с копиями параметров x = 1, y = 2
173 Параметры-переменные Применение: таким образом процедура (и функция) может возвращать несколько значений Запрещенные варианты вызова Swap ( 2, 3 ); // числа Swap ( x + z, y+2 ); // выражения void Swap ( int & a, int & b ) { int c; c = a; a = b; b = c; } & параметры могут изменяться &
174 « 3 »: Используя одну процедуру, построить фигуру. « 4 »: Используя одну процедуру, построить фигуру.
175 «5»: Используя одну процедуру, построить фигуру.
Тема 1 2. Анимация
177 Анимация Анимация (англ. animation ) – оживление изображения на экране. Задача : внутри синего квадрата 400 на 400 пикселей слева направо двигается желтый квадрат 20 на 20 пикселей. Программа останавливается, если нажата клавиша Esc или квадрат дошел до границы синей области. Проблема : как изобразить перемещение объекта на экране? Привязка: состояние объекта задается координатами ( x,y) Принцип анимации: рисуем объект в точке ( x,y) задержка на несколько миллисекунд стираем объект изменяем координаты ( x,y ) переходим к шагу 1
178 Как «поймать» нажатие клавиши? kbhit() – функция, определяет, было ли нажатие на (любую!) клавишу ( 0 – не было, не 0 – было). getch() – функция, которая определяет код нажатой клавиши: 27 = Esc, 13 = Enter, 32 = пробел, … if ( kbhit() ) printf(" Нажата какая-то клавиша... "); else printf(" Нет нажатия... "); if ( kbhit() ) { printf(" Нажата какая-то клавиша... "); c = getch(); printf(" Код клавиши %d", c); } int c; if ( kbhit() != 0 )
179 Как выйти из цикла ? #include <conio.h> main() { ... while ( x + 20 < 400 ) { if ( kbhit() ) if ( getch() == 27 ) break; ... } ... } если нажата клавиша... если нажата клавиша с кодом 27 ( Esc ), выйти из цикла для kbhit() и getch() пока не вышли за границу синего квадрата Как не допустить выход за границу поля ? ? x + 20 < 400
180 Процедура (рисование и стирание) void Draw( int x, int y, int color ) { setfillstyle ( 1, color ); bar ( x, y, x+20, y+20 ); } ( x, y ) ( x +20, y +20) Идеи одна процедура рисует и стирает стереть = нарисовать цветом фона границу квадрата отключить (в основной программе) цвет : желтым рисуем, синим стираем сплошная заливка цветом color залитый прямоугольник
181 Полная программа #include < conio.h > #include < graphics.h > void Draw ( int x, int y, int color ) { ... } main() { int x, y; initwindow (500, 500); setfillstyle (1, COLOR(0,0,255)); bar (0, 0, 399, 399); x = 0; y = 240; /* анимация */ closegraph (); } процедура начальные координаты синий фон
182 Цикл анимации while ( x + 20 < 400 ) { if ( kbhit() ) if ( getch() == 27 ) break; Draw ( x, y, COLOR(255,255,0) ); delay ( 20 ); Draw ( x, y, COLOR(0,0,255) ); x ++; } выход по клавише Esc ждем 20 мс пока не вышли из синего квадрата
183 «3»: Квадрат двигается справа налево: «4»: Два квадрата двигаются в противоположных направлениях:
184 «5»: Два квадрата двигаются в противоположных направлениях и отталкиваются от стенок синего квадрата:
185 Управление клавишами Задача : жёлтый квадрат внутри синего квадрата управляется клавишами-стрелками. Коды клавиш: влево – 75 вверх – 72 Esc – 27 вправо – 77 вниз – 80 Проблема : как изменять направление движения? Решение : if нажата клавиша { получить код клавиши - code if ( code = = 27) break; if ( code = = 75) x -- ; if ( code = = 77) x ++ ; if ( code = = 7 2 ) y -- ; if ( code = = 80 ) y ++ ; } ( kbhit() ) code = getch(); switch ( code ) { case 75: x -- ; break; case 77: x ++; break; case 72: y --; break; case 80: y ++; } } если было нажатие на клавишу, … получить код клавиши выход по Esc перемещение
186 Программа void Draw (int x, int y, int color) { ... } if ( kbhit() ) { ... } Что плохо ? ? процедура основной цикл обработка нажатия на клавишу main() { int x, y, code; ... while ( 1 ) { Draw(x, y, COLOR(255,255,0)); delay(20); Draw(x, y, COLOR(0,0,255)); } } Как убрать мигание ? ?
187 Задания « 3 »: Квадрат в самом начале стоит в правом нижнем углу, и двигается при нажатии стрелок только вверх или влево: «4»: Квадрат двигается при нажатии стрелок, однако не может выйти за границы синего квадрата:
188 « 5 »: Квадрат непрерывно двигается, при нажатии стрелок меняет направление и отталкивается от стенок синего квадрата:
189 Вращение (для 8-11 класса) Задача : изобразить модель вращения Земли вокруг Солнца. Проблема : движение по окружности, как изменять координаты? Решение : использовать в качестве независимой переменной (менять в цикле) угол поворота α ( x 0, y 0 ) α L ( x, y ) x = x 0 + L · cos( α ) y = y 0 – L · sin( α )
190 Процедура void Draw( int x, int y, int color ) { const int r = 10; setcolor ( color ); circle ( x, y, r ); } цвет : желтый – рисуем, черный – стираем установили цвет линий радиус Земли ( x, y ) r постоянная
191 Константы и переменные #include <math.h> // математические функции main() { const int rSun = 60, // радиус Солнца L = 150, // радиус орбиты Земли x0 = 200, // координаты центра Солнца y0 = 200; int x, y, // координаты Земли code; // код нажатой клавиши float a, ha; // угол поворота, шаг initwindow( 500, 500 ); ... } void Draw ( int x, int y, int color ) { ... }
192 Основной цикл circle ( x0, y0, rSun ); setfillstyle(1, COLOR(255,255,0)); floodfill(x0, y0, COLOR(255,255,255)); a = 0; // начальный угол ha = M_PI/180; // шаг 1 o за 20 мс while(1) { x = x0 + L*cos(a); y = y0 - L*sin(a); Draw ( x, y, COLOR(0, 255,255) ); delay ( 20 ); Draw(x, y, 0); a = a + ha; } closegraph(); рисуем Солнце : белый контур, желтая заливка if ( kbhit() ) if ( 27 == getch() ) break; #include<math.h> // sin, cos, M_PI ! новые координаты поворот на ha ждем 2 0 мс выход по Esc
193 «4»: Изобразить модель Солнца с двумя планетами, которые вращаются в противоположные стороны: «5»: Изобразить модель системы Солнце-Земля-Луна: Задания
Тема 1 3. Функции
195 Функции Функция – это вспомогательный алгоритм (подпрограмма), результатом работы которого является некоторое значение. Примеры : вычисление модуля числа, расчет значений по сложным формулам ответ на вопрос (простое число или нет?) Зачем? для выполнения одинаковых расчетов в различных местах программы для создания общедоступных библиотек функций В чем отличие от процедур ? ?
196 Функции Задача: составить функцию, которая вычисляет наибольшее из двух значений, и привести пример ее использования Функция: формальные параметры int Max ( int a, int b ) { if ( a > b ) return a ; else return b ; } return - вернуть результат функции тип результата
197 Функции Особенности: в начале заголовка ставится тип результата формальные параметры описываются так же, как и для процедур можно использовать параметры-переменные функции обычно располагаются до основной программы Max ( int a, int b ) int float qq ( ) int a, float x, char c int Vasya (int a, int b ) & &
198 Функции Особенности: можно объявлять и использовать локальные переменные float qq ( int a, int b) { ... } float x, y; локальные переменные Локальные переменные недоступны в основной программе и других процедурах и функциях. !
199 Программа main() { int a, b, с ; printf ( " Введите два числа \n" ); scanf ( "%d%d", &a, &b ); c = Max ( a, b ); printf ( " Наибольшее число %d", c ); } int Max ( int a, int b ) { ... } фактические параметры вызов функции формальные параметры
200 Задания «4»: Составить функцию, которая определяет сумму всех чисел от 1 до N и привести пример ее использования. Пример: Введите число: 1 00 сумма чисел от 1 до 100 = 5050 «5»: Составить функцию, которая определяет, сколько зерен попросил положить на N- ую клетку изобретатель шахмат (на 1-ую – 1 зерно, на 2-ую – 2 зерна, на 3-ю – 4 зерна, …) Пример: Введите номер клетки: 28 На 28-ой клетке 134217728 зерен.
201 Задания (вариант 2 для 9 -11 класса) «4»: Составить функцию, которая определяет наибольший общий делитель двух натуральных и привести пример ее использования. Пример: Введите два числа: 14 21 НОД(14,21)=7 «5»: Составить функцию, которая вычисляет функцию синус как сумму ряда (с точностью 0.001) Пример: Введите угол в градусах: 45 sin(45) = 0.707 x в радианах!
202 Логические функции Задача: составить функцию, которая определяет, верно ли, что заданное число – простое. Особенности: ответ – логическое значение: «да» (1) или «нет» ( 0 ) результат функции можно использовать как логическую величину в условиях ( if, while ) Алгоритм: считаем число делителей в интервале от 2 до N-1, если оно не равно нулю – число составное. Как улучшить ? ? count = 0; for ( i = 2; i < N; i ++) if ( N % i == 0) count ++; if ( count = = 0 ) // число N простое } else // число N составное
203 Функция: простое число или нет int Prime ( int N ) { int count = 0, i; for (i = 2; i*i <= N; i++) if (N % i == 0) count ++; return (count == 0); } перебор только до if (count == 0) return 1; else return 0;
204 Логические функции #include <stdio.h> main() { int N; printf ( " Введите целое число \n" ); scanf ( "%d", &N ); if ( Prime( N ) ) printf ("%d - простое число ", N); else printf ("%d - составное число ", N); } int Prime ( int N ) { ... } функция Prime( N )
205 Задания «4»: Составить функцию, которая определяет, верно ли, что сумма его цифр – четное число. Пример: Введите число: 1 36 Сумма цифр четная. «5»: Составить функцию, которая определяет, верно ли, что в заданном числе все цифры стоят по возрастанию. Пример: Введите число: 258 Верно. Введите число: 528 Неверно. Введите число: 245 Сумма цифр нечетная.
Тема 1 4. Случайные числа
207 Случайные числа Случайные явления : везде… бросание монеты («орел» или «решка») падение снега броуновское движение помехи при телефонной связи шум радиоэфира Случайные числа – это такая последовательность чисел, для которой невозможно предсказать следующее даже зная все предыдущие. Проблема : как получить на компьютере? Возможные решения : использовать внешний источник шумовых помех с помощью математических преобразований
208 Псевдослучайные числа Псевдослучайные числа – это такая последовательность чисел, которая обладает свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле. Примеры : Случайные целые числа [0,m) ( линейный конгруэнтный метод ) Случайные вещественные числа [0,1] Литература : Д. Кнут, Искусство программирования для ЭВМ, т.2. дробная часть числа a, c, m - целые числа простое число 2 30 -1 например, k = 5 остаток от деления
209 Распределение случайных чисел Модель : снежинки падают на отрезок [a,b] a b a b распределение равномерное неравномерное Сколько может быть разных распределений ? ?
210 Распределение случайных чисел Особенности : распределение – это характеристика всей последовательности, а не одного числа равномерное распределение одно, компьютерные датчики (псевдо)случайных чисел дают равномерное распределение неравномерных – много любое неравномерное можно получить с помощью равномерного a b a b равномерное распределение равномерное распределение
211 Генератор случайных чисел в Си RAND_MAX – максимальное случайное целое число (обычно RAND_MAX = 32767 ) rand() – случайное целое число в интервале [0,RAND_MAX] srand ( N ) – установить начальное значение последовательности случайных чисел N : #include <stdlib.h> // случайные числа int x, y; x = rand(); // первое число [0,RAND_MAX] y = rand(); // уже другое число srand ( 345 ); // начнем с 345
212 Целые числа в заданном интервале Целые числа в интервале [0,N-1] : Примеры: Целые числа в интервале [a,b] : int random(int N) { return rand() % N; } x = random ( 100 ); // интервал [0,99] x = random ( z ); // интервал [0,z-1] x = random ( z ) + a; // интервал [a,z-1+a] x = random (b – a + 1) + a; // интервал [ a,b ]
213 Генератор случайных чисел в Си Вещественные числа в интервале [0,1] float x; x = 1.*rand() / RAND_MAX; // интервал [0,1] Вещественные числа в интервале [0,z] x = 1.*z*rand() / RAND_MAX; Вещественные числа в интервале [ a,z+a ] x = 1.*z*rand() / RAND_MAX + a; Вещественные числа в интервале [ a,b ] x = 1.*(b-a)*rand() / RAND_MAX + a; [0,RAND_MAX] = [0,32767]
214 Случайные числа Задача : заполнить прямоугольник 4 00 на 3 00 пикселей равномерно точками случайного цвета Как получить случайные координаты точки? x = random ( 400 ); y = random ( 300 ); Как добиться равномерности? обеспечивается автоматически при использовании функции random Как получить случайный цвет? R = random( 25 6 ); G = random ( 25 6 ); B = random( 25 6 ); COLOR(R,G,B)
215 Программа #include <graphics.h> #include <conio.h> #include <stdlib.h> main() { int x, y, R, G, B; initwindow ( 500, 500 ); // цикл до нажатия на Esc closegraph(); } int random(int N) { return rand() % N; } функция для получения случайного числа от 0 до N-1
216 Основной цикл while ( 1 ) { x = random(400); y = random(300); R = random(25 6 ); G = random(25 6 ); B = random(25 6 ); putpixel ( x, y, COLOR(R,G,B)); } if ( kbhit() ) if ( 27 == getch() ) break; случайные координаты случайный цвет выход по Esc бесконечный цикл???
217 Задания «3»: Заполнить квадрат точками случайного цвета. размер квадрата ввести с клавиатуры: Пример: Введите размер квадрата: 150 «4»: Заполнить область точками случайного цвета:
218 «5»: Заполнить область точками случайного цвета: или
219 ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru
