Презентация - Программирование (лекция 1)


Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)Программирование (лекция 1)
На весь экран

Слайды и текст этой презентации

Слайд 1

Программирование Лекция 1

Слайд 2

Массивы. Вектор Задача. Упорядочить 100 000 чисел. В языке C есть несколько способов хранить последовательности чисел, и мы рассмотрим только один из них — vector . Он назван в честь математического термина «вектор», который обозначает занумерованную последовательность объектов. #include

Слайд 3

Пример 1 задано число N — количество элементов последовательности, а затем N целых чисел A i — это члены последовательности. Необходимо развернуть и вывести эту последовательность чисел.

Слайд 4

int n; cin n; vector a(n); //считывание for (int i 0; i n; i ) cin a i ; //обработка и вывод for (int i n - 1; i 0; i--) cout

Слайд 5

Пример 2 Нужно считать последовательность и вывести задом наперед только положительные элементы. 2способа: считать всю последовательность и при выводе печатать только положительные элементы. запоминать только положительные элементы на этапе считывания данных.

Слайд 6

int n; cin n; vector a; //считывание for (int i 0; i n; i ) int temp; cin temp; if (temp 0) a. push back (temp); //обработка и вывод for (i a. size() - 1; i 0; i--) cout

Слайд 7

Поиск минимума в последовательности Часто возникает задача найти минимум (или максимум) в последовательности из N чисел. Рассмотрим задачу: есть последовательность чисел, в ней нужно поменять местами то число, что стоит в начале последовательности, и самое маленькое число.

Слайд 8

int n; cin n; vector a; //считывание for (int i 0; i n; i ) int temp; cin temp; a.push back(temp); //обработка int num min 0; //номер минимального элемента for (int i 0; i n; i ) if (a i a num min ) num min i; //обмен значений элементов a 0 и a num min int temp; temp a 0 ; a 0 a num min ; a num min temp; //вывод for ( auto now : a) cout auto – это тип переменной

Слайд 9

Сортировка массива Нужно расположить числа, записанные в массиве, в порядке неубывания (это то же самое, что порядок возрастания, только в нём могут быть одинаковые элементы)

Слайд 10

int n; cin n; vector a; //считывание for (int i 0; i n; i ) int temp; cin temp; a.push back(temp); //обработка for (int j 0; j n; j ) // j – начиная с какого номера ищем наименьший int num min j; // номер минимального элемента for (int i j; i n; i ) // ищем только в еще не упорядоченной части if (a i a num min ) num min i; //обмен значений элементов a j и a num min int temp; temp a j ; a j a num min ; a num min temp; //вывод for (auto now : a) cout Такой метод сортировки называется «сортировка выбором минимума».

Слайд 11

Двумерные массивы

Слайд 12

Создание и заполнение двумерных массивов Задача: нарисовать на экране квадратный флаг Туапсинского района, где цвета обозначены разными цифрами. Точнее, задача формулируется так: по заданному числу N вывести на экран квадратную таблицу размером N на N, где главная диагональ (идущая из левого верхнего угла в правый нижний) заполнена единицами, в верхней правой половине таблицы стоят нули, а в левой нижней – двойки. Чтобы создать двумерный массив размером 100 на 100 чисел нужно написать int a 100 100 ;

Слайд 13

for (int i 0; i n; i ) //перебор строк for (int j 0; j n; j ) //перебор столбцов if ( i j ) a i j 1; else if ( i j ) a i j 0; else a i j 2; //вывод for (int i 0; i n; i ) //перебор строк for (int j 0; j n; j ) //вывод одной строки cout cout перевод строки после того, как выведены все элементы

Слайд 14

Поле для сапера В некоторых клетках на прямоугольном поле лежат мины, а в остальных клетках — числа, обозначающие количество мин, которые окружают клетку (от 0 до 8). Наша задача - по известному расположению мин на поле необходимо расставить числа во все свободные клетки, а на месте мин выводить «звездочку».

Слайд 15

int n, m; cin n m; int mines 100 100 ; // чтение for (int i 0; i n; i ) for (int j 0; j m; j ) cin mines i j ; // 1 – мина, 0 – пусто Но лучше чтение сделать так: int mines 102 102 for (int i 0; i n 1 ; i ) for (int j 0; j m 1 ; j ) mines i j 0; // чтение for (int i 1; i ) for (int j 1; j ) cin mines i j ;

Слайд 16

Обработка массива int ans 102 102 ; for (int i 1; i for (int j 1; j // координаты соседей (сдвиги) int dx 8 1, 1, 1, 0, 0, -1, -1, -1 ; int dy 8 -1, 0, 1, -1, 1, -1, 0, 1 ; // перебор соседей int temp 0; for (int k 0; k 8; k ) temp mines i dy k j dx k ; ans i j temp; Для каждой клетки поля нужно посмотреть на 8 соседей.

Слайд 17

Вывод массива // вывод for (int i 1; i for (int j 1; j if (mines i j 1) cout else cout cout

Слайд 18

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

Слайд 19

Наибольший общий делитель Рассмотрим такую задачу: нужно найти наибольший общий делитель двух чисел. Наибольшим общим делителем для двух целых чисел A и B будет такое наибольшее целое число C, на которое и A, и B делятся без остатка. Например, есть две пиццы: одна разрезана на 12 кусков, а другая на 8. Нужно раздать максимальному числу людей одинаковое количество кусочков, как первой, так и второй пиццы. В данном случае ответ будет равен 4 — наибольшему общему делителю чисел 8 и 12. Функция main() Создавать новые функции нужно между using namespace std и функцией main .

Слайд 20

Наибольший общий делитель Функция gcd (от английского greatest common divisor, наибольший общий делитель). Функция будет принимать два параметра a и b (числа, наибольший общий делитель которых нужно найти) и возвращать в ответ одно число. Алгоритм Евклида int gcd(int a, int b) while (b ! 0) int c a % b; a b; b c; return a; Локальные переменные a , b . Получить к ним доступ из других функций нельзя.

Слайд 21

Вызов функции int main() int n, m; cin n m; cout n , m ); return 0; Visual studio Пошаговое выполнение программы: «шаг с заходом» (step into, кнопка F11), который входит внутрь функции, «шаг с обходом» (step over, кнопка F10), который не входит внутрь функции, а сразу подставляет на место ее вызова результат.

Слайд 22

Сокращение дроби Например, дробь 12/8 нужно превратить в несократимую дробь 3/2. Для сокращения дроби нужно найти наибольший общий делитель числителя и знаменателя, а затем разделить их на него. Функция принимает на вход два числа и должна возвращать также два числа — новые числитель и знаменатель: void reduce(int & a, int & b) int c gcd(a, b); a / c; b / c; & означает, что у нас не будет создаваться копия переменных внутри функций.

Слайд 23

Пример вызова функции int main() int n, m; cin n m; reduce(n, m); cout return 0; При вызове функции сначала выполняется она, а когда результат подсчитан, выполнение продолжается с того места, где функция была вызвана

Слайд 24

Рекурсия Функция может вызывать другие экземпляры себя самой. Это называется рекурсия. void rec() int n; cin n; if (n ! 0) rec(); cout Функция не принимает параметров. Чтобы запустить разворот последовательности, нужно вызвать функцию один раз из main.

Слайд 25

Факториал Факториалом числа N называется произведение всех чисел от 1 до N. Например, 4! 1 2 3 4 24. int fact(int n) if (n 0) return 1; return n fact(n – 1);

Слайд 26

Число сочетаний С помощью функции подсчета факториала можно посчитать число сочетаний. Пусть у нас есть N человек и из них нужно выбрать K добровольцев. Нужно посчитать, сколькими различными способами можно это сделать. int cnk(int n, int k) return fact(n) / (fact(k) fact(n – k));

Слайд 27

Функции, возвращающие логическое значение bool is even(int n) return n % 2 0; if (is even(n)) cout else cout

Слайд 28

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