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

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

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

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

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

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

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

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

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 – это тип переменной

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

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 Такой метод сортировки называется «сортировка выбором минимума».

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

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

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 перевод строки после того, как выведены все элементы

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

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 ;

Обработка массива 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 соседей.

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

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

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

Наибольший общий делитель Функция 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 . Получить к ним доступ из других функций нельзя.

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

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

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

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

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

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

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

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