Программирование (C++)

Содержание

Слайд 2

Программирование (C++)

§ 19. Символьные строки

Программирование (C++) § 19. Символьные строки

Слайд 3

Что такое символьная строка?

Символьная строка – это последовательность символов.

Хочется:
строка – единый объект
длина

Что такое символьная строка? Символьная строка – это последовательность символов. Хочется: строка
строки может меняться во время работы программы

string s; // символьная строка

строковый тип

string s = "Ура!"; // начальное значение

string s(5, '*'); // "*****"

Слайд 4

Символьные строки

Присваивание:

s = "Вася пошёл гулять";

Ввод с клавиатуры:

cin >> s;

Вывод на экран:

cout

Символьные строки Присваивание: s = "Вася пошёл гулять"; Ввод с клавиатуры: cin
<< s;

Длина строки:

int n;
n = s.size();

string s;

до конца слова (до пробела)

getline( cin, s );

до конца строки

метод для строк

точечная запись

Слайд 5

Сравнение строк

string s;
...
cout << "Введите пароль: ";
cin >> s;
if( s == "sEzAm"

Сравнение строк string s; ... cout cin >> s; if( s ==
)
cout << "Слушаюсь и повинуюсь!";
else
cout << "Пароль неправильный";

стоит раньше в отсортированном списке

Слайд 6

Сравнение строк

string s1, s2;
...
s1 = "паровоз";
s2 = "пароход";
if( s1 < s2 )

Сравнение строк string s1, s2; ... s1 = "паровоз"; s2 = "пароход";
cout << s1 << "<" << s2;
else
if( s1 == s2 )
cout << s1 << "=" << s2;
else
cout << s1 << ">" << s2;

паровоз < пароход

первые отличающиеся буквы

паровоз
пароход

Сравниваем с начала:

«в»: код 1074

«х»: код 1093

Слайд 7

Посимвольная обработка строк

s[4] = 'a'; // нумерация символов с 0!

Задача. Ввести строку

Посимвольная обработка строк s[4] = 'a'; // нумерация символов с 0! Задача.
и заменить в ней все буквы «э» на буквы «е».

for( int i=0; i if( s[i] == 'э' )
s[i] = 'е';

для каждого символа строки

нумерация с 0!

С++11:

for( auto& sym: s )
if( sym == 'э' )
sym = 'е';

Слайд 8

Задачи

«A»: Напишите программу, которая вводит строку, состоящую только из точек и букв

Задачи «A»: Напишите программу, которая вводит строку, состоящую только из точек и
Х, и заменяет в ней все точки на нули и все буквы X на единицы.
Пример:
Введите строку: ..X.XX.
Двоичный код: 0010110

«B»: Напишите программу, которая в символьной строке заменяет все нули на единицы и наоборот. Остальные символы не должны измениться.
Пример:
Введите строку: 10а01Bx1010c
Инверсия: 01a10Bx0101c

Слайд 9

Задачи

«С»: Введите битовую строку и дополните её последним битом, который должен быть

Задачи «С»: Введите битовую строку и дополните её последним битом, который должен
равен 0, если в исходной строке чётное число единиц, и равен 1, если нечётное (в получившейся строке должно всегда быть чётное число единиц).
Пример:
Введите битовую строку: 01101010110
Результат: 011010101100

Слайд 10

Операции со строками

Объединение (конкатенация) :

s1 = "Привет" ;
s2 = "Вася" ;

Операции со строками Объединение (конкатенация) : s1 = "Привет" ; s2 =

s = s1 + ", " + s2 + "!" ;

"Привет, Вася!"

Срез (выделение части строки = подстроки):

s = "0123456789" ;
s1 = s.substr(3,5); // "34567"

с какого символа

сколько символов

s1 = s.substr(3); // "3456789"

до конца

Слайд 11

Операции со строками

Вставка:

s = "0123456789";
s.insert(3, "ABC"); // "012ABC3456789"

что

с какого символа

Удаление:

s =

Операции со строками Вставка: s = "0123456789"; s.insert(3, "ABC"); // "012ABC3456789" что
"0123456789";
s.erase( 3, 6); // "0129"

с какого символа

сколько символов

Слайд 12

Поиск в строках

s = "Здесь был Вася.";
int n = s.find('с');
if( n !=

Поиск в строках s = "Здесь был Вася."; int n = s.find('с');
string::npos )
cout << "Номер символа " << n;
else
cout << "Символ не найден.";

что

где

no position

Слайд 13

Задачи

«A»: Ввести с клавиатуры в одну строку фамилию и имя, разделив их

Задачи «A»: Ввести с клавиатуры в одну строку фамилию и имя, разделив
пробелом. Вывести первую букву имени с точкой и потом фамилию.
Пример:
Введите фамилию и имя:
Иванов Петр
П. Иванов

«B»: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
П.С. Иванов

Слайд 14

Задачи

«C»: Ввести адрес файла и «разобрать» его на части, разделенные знаком "/".

Задачи «C»: Ввести адрес файла и «разобрать» его на части, разделенные знаком
Каждую часть вывести в отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2015/Байкал/shaman.jpg
C:
Фото
2015
Байкал
shaman.jpg

Слайд 15

Преобразования «строка» → «число»

Целое число:

string s = "12.345бе-бе-бе6789";
int n =

Преобразования «строка» → «число» Целое число: string s = "12.345бе-бе-бе6789"; int n
stoi( s ); // n = 12

до первой ошибки

string s = "12.345бе-бе-бе6789";
float x = stof( s ); // x = 123.456

Вещественное число:

Слайд 16

Преобразования «число» → «строка»

int N = 123;
string sN = to_string( N

Преобразования «число» → «строка» int N = 123; string sN = to_string(
); // "123"
double X = 123.45;
string sX = to_string( X ); // "123.450000"

Слайд 17

Задачи

«A»: Напишите программу, которая вычисляет сумму двух чисел, введенную в форме символьной

Задачи «A»: Напишите программу, которая вычисляет сумму двух чисел, введенную в форме
строки. Все числа целые.
Пример:
Введите выражение:
12+3
Ответ: 15

«B»: Напишите программу, которая вычисляет сумму трёх чисел, введенную в форме символьной строки. Все числа целые.
Пример:
Введите выражение:
12+3+45
Ответ: 60

Слайд 18

Задачи

«D»: Напишите программу, которая вычисляет выражение, содержащее целые числа и знаки сложения

Задачи «D»: Напишите программу, которая вычисляет выражение, содержащее целые числа и знаки
и вычитания.
Пример:
Введите выражение:
12+134–45–17
Ответ: 84

«C»: Напишите программу, которая вычисляет сумму произвольного количества чисел, введенную в форме символьной строки. Все числа целые.
Пример:
Введите выражение:
12+3+45+10
Ответ: 70

Слайд 19

Программирование (C++)

§ 20. Обработка массивов

Программирование (C++) § 20. Обработка массивов

Слайд 20

Обработка потока данных

Задача. С клавиатуры вводятся числа, ввод завершается числом 0. Определить,

Обработка потока данных Задача. С клавиатуры вводятся числа, ввод завершается числом 0.
сколько было введено положительных чисел.

счётчик = 0;
пока не введён 0:
если введено число > 0 то
счётчик = счётчик + 1

нужен счётчик
счётчик увеличивается если число > 0
нужен цикл
это цикл с условием (число шагов неизвестно)

Слайд 21

Обработка потока данных

int x, count = 0;
cin >> x;
while( x != 0

Обработка потока данных int x, count = 0; cin >> x; while(
) {
if( x > 0 )
count++;
cin >> x;
}
cout << count;

откуда взять x?

Слайд 22

Найди ошибку!

int x, count = 0;
cin >> x;
while( x != 0 )

Найди ошибку! int x, count = 0; cin >> x; while( x

if( x > 0 )
count++;
cin >> x;

}
cout << count;

cin >> x;

Слайд 23

Найди ошибку!

int x, count;
cin >> x;
while( x == 0 ) {
if(

Найди ошибку! int x, count; cin >> x; while( x == 0
x > 0 )
count++;
cin >> x;
}
cout << count;

= 0;

!=

Слайд 24

Обработка потока данных

Задача. С клавиатуры вводятся числа, ввод завершается числом 0. Найти

Обработка потока данных Задача. С клавиатуры вводятся числа, ввод завершается числом 0.
сумму введённых чисел, оканчивающихся на цифру "5".

сумма = 0;
пока не введён 0
если число оканчивается на "5" то
сумма += число

нужна переменная для суммы
число добавляется к сумме, если оно заканчивается на "5"
нужен цикл с условием

if( x % 10 == 5 )

Слайд 25

Обработка потока данных

Задача. С клавиатуры вводятся числа, ввод завершается числом 0. Найти

Обработка потока данных Задача. С клавиатуры вводятся числа, ввод завершается числом 0.
сумму введённых чисел, оканчивающихся на цифру "5".

int x, sum = 0;
cin >> x;
while( x != 0 ) {
if( x % 10 == 5 )
sum += x;
cin >> x;
}
cout << sum;

Слайд 26

Найди ошибку!

int x, sum = 0;
cin >> x;

while( x != 0 )

Найди ошибку! int x, sum = 0; cin >> x; while( x
{
if( x % 10 == 5 )
sum += x;
cin >> x;
}
cout << sum;

cin >> x;

Слайд 27

Задачи

«A»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём.

Задачи «A»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается
Определить, сколько получено чисел, которые делятся на 3.
«B»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сколько получено двузначных чисел, которые заканчиваются на 3.

Слайд 28

Задачи

«C»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём.

Задачи «C»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается
Найти среднее арифметическое всех двузначных чисел, которые делятся на 7.
«D»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Найти максимальное из введённых чётных чисел.

Слайд 29

Перестановка элементов массива

с = a;
a = b;
b = c;

элементы массива:

с = A[i];
A[i]

Перестановка элементов массива с = a; a = b; b = c;
= A[k];
A[k] = c;

Слайд 30

Перестановка пар соседних элементов

Задача. Массив A содержит чётное количество элементов N. Нужно

Перестановка пар соседних элементов Задача. Массив A содержит чётное количество элементов N.
поменять местами пары соседних элементов: первый со вторым, третий — с четвёртым и т. д.

Слайд 31

Перестановка пар соседних элементов

for(int i=0; i поменять местами A[i] и

Перестановка пар соседних элементов for(int i=0; i поменять местами A[i] и A[i+1]
A[i+1]
}

?

выход за границы массива

Слайд 32

Перестановка пар соседних элементов

for( int i=0; i // переставляем

Перестановка пар соседних элементов for( int i=0; i // переставляем A[i] и
A[i] и A[i+1]
int с = A[i];
A[i] = A[i+1];
A[i+1] = c;
}

не выходим за границу

A[0]↔A[1],A[2]↔A[3], …,A[N-2]↔A[N-1]

i+=2

«шагаем» через один

Слайд 33

Реверс массива

Задача. Переставить элементы массива в обратном порядке (выполнить реверс).

A[0]↔A[N-1]
A[1]↔A[N-2]
A[i]↔A[N-1-i]
A[N-1]↔A[0]

0+N-1 =

Реверс массива Задача. Переставить элементы массива в обратном порядке (выполнить реверс). A[0]↔A[N-1]
N-1
1+N-2 = N-1
i+??? = N-1
N-1+0 = N-1

Слайд 34

Реверс массива

for(int i=0; i поменять местами A[i] и A[N+1-i]
}

i=0

i=1

i=2

i=3

;

Реверс массива for(int i=0; i поменять местами A[i] и A[N+1-i] } i=0
i++) {

N/2

Слайд 35

Линейный поиск в массиве

Задача. Найти в массиве элемент, равный X, и его

Линейный поиск в массиве Задача. Найти в массиве элемент, равный X, и
номер.

X = 5

5

int i = 0;
while( A[i] != X )
i++;
cout << "A[" << i << "]=" << X;

Слайд 36

Линейный поиск в массиве

int i = 0;
while( i

Линейный поиск в массиве int i = 0; while( i i++; if(
i++;
if( i < N )
cout << "A[" << i << "]=" << X;
else
cout << "Не нашли!";

i

не выходим за границу

Слайд 37

Досрочный выход из цикла

Задача. Найти в массиве элемент, равный X, и его

Досрочный выход из цикла Задача. Найти в массиве элемент, равный X, и
номер.

int nX = -1; // недействительный номер
for( int i=0; i if( A[i] == X ) {
nX = i; // запомнить номер
break;
}
if( nX >= 0 )
cout << "A[" << nX << "]=" << X;
else
cout << "Не нашли!";

нашли!

break;

сразу выйти из цикла

Слайд 38

Задачи

«A»: Напишите программу, которая заполняет массив из N = 10 элементов случайными

Задачи «A»: Напишите программу, которая заполняет массив из N = 10 элементов
числами в диапазоне [0,20], выводит его на экран, а затем находит индекс первого элемента, равного введённому числу X. Программа должна вывести ответ «не найден», если в массиве таких элементов нет.
Пример:
Массив: 5 16 2 13 3 14 18 13 16 9
Что ищем: 13
A[3] = 13

Слайд 39

Задачи

«B»: Напишите программу, которая заполняет массив из N = 10 элементов случайными

Задачи «B»: Напишите программу, которая заполняет массив из N = 10 элементов
числами в диапазоне [-10,10], выводит его на экран, а затем находит индекс последнего элемента, равного введённому числу X. Программа должна вывести ответ «не найден», если в массиве таких элементов нет.
Пример:
Массив: -5 -6 2 3 -3 0 8 -3 0 9
Что ищем: 0
A[8] = 0

Слайд 40

Задачи

«C»: Напишите программу, которая заполняет массив из N = 10 элементов случайными

Задачи «C»: Напишите программу, которая заполняет массив из N = 10 элементов
числами в диапазоне [10,50], выводит его на экран, а затем находит индексы всех элементов, равных введённому числу X. Программа должна вывести ответ «не найден», если в массиве таких элементов нет.
Пример:
Массив: 12 45 30 18 30 15 30 44 32 17
Что ищем: 30
A[2] = 30
A[4] = 30
A[6] = 30

Слайд 41

Поиск максимального элемента

Поиск максимального элемента

Слайд 42

Поиск максимального элемента

for( int i=0; i if( A[i] > M

Поиск максимального элемента for( int i=0; i if( A[i] > M )
)
M = A[i];
cout << M;

M – значение, которое заведомо меньше всех элементов массива или
M = A[0] (или любой другой элемент)

Слайд 43

Поиск максимального элемента

M = A[0];
for( int i=1; i if( A[i]

Поиск максимального элемента M = A[0]; for( int i=1; i if( A[i]
> M )
M = A[i];
cout << M;

начинаем с A[1], так как A[0] мы уже посмотрели

Слайд 44

Номер максимального элемента

Задача. Найти в массиве максимальный элемент и его номер.

int M

Номер максимального элемента Задача. Найти в массиве максимальный элемент и его номер.
= A[0];
int nMax = 1;
for( int i=1; i if( A[i] > M ) {
M = A[i];
nMax = i;
}
cout << "A[" << nMax << "]=" << M;

int nMax = 0;

nMax = i;

Слайд 45

Номер максимального элемента

int M = A[0];
int nMax = 0;
for( int i=1;

Номер максимального элемента int M = A[0]; int nMax = 0; for(
i if( A[i] > M ) {
M = A[i];
nMax = i;
}
cout << "A[" << nMax << "]="
<< M;

) {

;

A[nMax]

A[nMax]

Слайд 46

Максимальный не из всех

Задача. Найти в массиве максимальный из отрицательных элементов.

M =

Максимальный не из всех Задача. Найти в массиве максимальный из отрицательных элементов.
A[0];
for( int i=1; i if( A[i]<0 and A[i]>M )
M = A[i];
cout << M;

M = 5

Слайд 47

Максимальный не из всех

Задача. Найти в массиве максимальный из отрицательных элементов.

M =

Максимальный не из всех Задача. Найти в массиве максимальный из отрицательных элементов.
A[0];
for( int i=1; i if( A[i]<0 )
if( M>=0 or A[i]>M )
M = A[i];
cout << M;

M>=0

сначала записали неотрицательный!

Слайд 48

Задачи

«A»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на

Задачи «A»: Напишите программу, которая заполняет массив из 20 элементов случайными числами
отрезке [50; 150] и находит в нём минимальный и максимальный элементы и их номера.
«B»: Напишите программу, которая заполняет массив следующим образом: int A[N]={10,2,3,10,5,6,7,8,9,10}; и выводит количество элементов, имеющих максимальное значение.
«C»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [100; 200] и находит в нём пару соседних элементов, сумма которых минимальна.

Слайд 49

Задачи

«D»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на

Задачи «D»: Напишите программу, которая заполняет массив из 20 элементов случайными числами
отрезке [–100; 100] и находит в каждой половине массива пару соседних элементов, сумма которых максимальна.

Слайд 50

Задачи-2 (максимум в потоке)

«A»: На вход программы поступает неизвестное количество целых чисел,

Задачи-2 (максимум в потоке) «A»: На вход программы поступает неизвестное количество целых
ввод заканчивается нулём. Напишите программу, которая находит минимальное и максимальное среди полученных чисел.
«B»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Напишите программу, которая находит минимальное число, делящееся на 3, среди полученных чисел.
«C»: На вход программы поступает неизвестное количество чисел целых, ввод заканчивается нулём. Напишите программу, которая находит максимальное двузначное число, заканчивающееся на 6, среди полученных чисел.

Слайд 51

Задачи-2 (максимум в потоке)

«D»: На вход программы поступает неизвестное количество чисел целых,

Задачи-2 (максимум в потоке) «D»: На вход программы поступает неизвестное количество чисел
ввод заканчивается нулём. Напишите программу, которая находит среди полученных чисел пару полученных друг за другом чисел, сумма которых максимальна.

Слайд 52

Сортировка

Сортировка — это расстановка элементов списка (массива) в заданном порядке.

Задача. Отсортировать

Сортировка Сортировка — это расстановка элементов списка (массива) в заданном порядке. Задача.
элементы в порядке возрастания (неубывания – если есть одинаковые).

Алгоритмы сортировки:
простые, но медленные (при больших N)
быстрые, но сложные…

Слайд 53

Сортировка выбором

нашли минимальный, поставили его на первое место
из оставшихся нашли минимальный, поставили

Сортировка выбором нашли минимальный, поставили его на первое место из оставшихся нашли
его на второе место и т.д.

с = A[nMin];
A[nMin] = A[0];
A[0] = c;

Слайд 54

Сортировка выбором

for( int i=0; i // ищем минимальный среди

Сортировка выбором for( int i=0; i // ищем минимальный среди A[i]..A[N-1] int
A[i]..A[N-1]
int nMin = i;
for( int j=i+1; j if( A[j] < A[nMin] )
nMin = j;
// переставляем A[i] и A[nMin]
int c = A[i];
A[i] = A[nMin];
A[nMin] = c;
}

не трогаем те, которые уже поставлены

Слайд 55

Задачи

«A»: Напишите программу, которая заполняет массив из N = 10 элементов случайными

Задачи «A»: Напишите программу, которая заполняет массив из N = 10 элементов
числами в диапазоне [0,20] и сортирует его в порядке убывания.
Пример:
Массив: 5 16 2 13 3 14 18 13 16 9
Сортировка: 18 16 16 14 13 13 9 5 3 2
«B»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [10,100] и сортирует его по возрастанию последней цифры числа (сначала идут все числа, которые заканчиваются на 0, потом все, которые заканчиваются на 1, и т.д.).
Пример:
Массив: 12 10 31 40 55 63 28 87 52 92
Сортировка: 10 40 31 12 52 92 63 55 87 28

Слайд 56

Задачи

«C»: Напишите программу, которая заполняет массив из N = 10 элементов случайными

Задачи «C»: Напишите программу, которая заполняет массив из N = 10 элементов
числами в диапазоне [0,20] и сортирует его в порядке возрастания. На каждом шаге цикла выполняется поиск максимального (а не минимального!) элемента.
Пример:
Массив: 5 16 2 13 3 14 18 13 16 9
Сортировка: 2 3 5 9 13 13 14 16 16 18

Слайд 57

Программирование (C++)

§ 21. Матрицы (двумерные массивы)

Программирование (C++) § 21. Матрицы (двумерные массивы)

Слайд 58

Что такое матрица?

Матрица — это прямоугольная таблица, составленная из элементов одного типа

Что такое матрица? Матрица — это прямоугольная таблица, составленная из элементов одного
(чисел, строк и т.д.).

нет знака

нолик

крестик

строка 1, столбец 2

Каждый элемент матрицы имеет два индекса – номера строки и столбца.

Слайд 59

Объявление матриц

const int N = 3, M = 4;
int A[N][M] = {

Объявление матриц const int N = 3, M = 4; int A[N][M]
{ 2, 3, 5, 1},
{ 4, 8, 3, 12},
{14, 4, 7, 11}
};
float X[4][M] = { {2, 6, 10} };
bool L[N][2] = {};

остальные нули

все false

строки

столбцы

Слайд 60

Простые алгоритмы

Заполнение случайными числами:

for( int i=0; i for( int

Простые алгоритмы Заполнение случайными числами: for( int i=0; i for( int j=0;
j=0; j cout << A[i][j] << " ";
}
cout << endl;
}

Суммирование:

int sum = 0;
for( int i=0; i for( int j=0; j sum += A[i][j];

в одной строке через пробел

следующий – с новой строки

Слайд 61

Перебор элементов матрицы

Главная диагональ:

for( int i=0; i // работаем

Перебор элементов матрицы Главная диагональ: for( int i=0; i // работаем с
с  A[i][i]
}

Побочная диагональ:

for( int i=0; i // работаем с  A[i][N-1-i]
}

Главная диагональ и под ней:

for( int i=0; i for( int j=0; j // работаем с  A[i][j]
}

Слайд 62

Перестановка строк

2-я и 4-я строки:

for( int j=0; j int

Перестановка строк 2-я и 4-я строки: for( int j=0; j int c
c = A[2][j];
A[2][j] = A[4][j];
A[4][j] = c;
}

Слайд 63

Задачи

«A»: Напишите программу, которая заполняет матрицу случайными числами и находит максимальный элемент

Задачи «A»: Напишите программу, которая заполняет матрицу случайными числами и находит максимальный
на главной диагонали квадратной матрицы.
Пример:
Матрица А:
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
Результат: A[4,4] = 92

Слайд 64

Задачи

«B»: Напишите программу, которая заполняет матрицу случайными числами и находит максимальный элемент

Задачи «B»: Напишите программу, которая заполняет матрицу случайными числами и находит максимальный
матрицы и его индексы (номера строки и столбца).
Пример:
Матрица А:
12 34 14 65
71 88 23 98
87 46 53 39
76 58 24 92
Максимум: A[2,4] = 98

Слайд 65

Задачи

«C»: Напишите программу, которая заполняет матрицу случайными числами и находит минимальный из

Задачи «C»: Напишите программу, которая заполняет матрицу случайными числами и находит минимальный
чётных положительных элементов матрицы. Учтите, что таких элементов в матрице может и не быть.
Пример:
Матрица А:
16 34 14 65
71 88 23 45
87 12 53 39
76 58 24 92
Результат: A[3,2] = 12

Слайд 66

Программирование (C++)

§ 22. Сложность алгоритмов

Программирование (C++) § 22. Сложность алгоритмов

Слайд 67

Как сравнивать алгоритмы?

быстродействие (временна́я сложность)
объём требуемой памяти (пространственная сложность)
понятность

Время работы алгоритма –

Как сравнивать алгоритмы? быстродействие (временна́я сложность) объём требуемой памяти (пространственная сложность) понятность
это количество элементарных операций T, выполненных исполнителем.

зависит от количества данных (размера массива N)

Функция T(N) называется
временно́й сложностью алгоритма

T(N) = 2N3

Слайд 68

Примеры определения сложности

Задача 1. Вычислить сумму первых трёх элементов массива (при N

Примеры определения сложности Задача 1. Вычислить сумму первых трёх элементов массива (при
≥ 3).

sum = A[1] + A[2] + A[3];

T(N) = 3

2 сложения + запись в память

Задача 2. Вычислить сумму всех элементов массива.

sum = 0;
for( int i=0; i sum += A[i];

T(N) = 2N + 1

N сложений, N+1 операций записи

Слайд 69

Примеры определения сложности

Задача 3. Отсортировать все элементы массива по возрастанию методом выбора.

Примеры определения сложности Задача 3. Отсортировать все элементы массива по возрастанию методом

for( int i=0; i int nMin = i;
for( int j=i+1; j if( A[j] < A[nMin] )
nMin = j;
int c = A[i]; A[i] = A[nMin]; A[nMin] = c;
}

Число сравнений:

Число перестановок: Tn(N) = N – 1

Слайд 70

Примеры определения сложности

Задача 4. Найти сумму элементов квадратной матрицы размером N×N.

int

Примеры определения сложности Задача 4. Найти сумму элементов квадратной матрицы размером N×N.
sum = 0;
for( int i=0; i for( int j=0; j sum = sum + A[ij];

Слайд 71

Сравнение алгоритмов по сложности

при N < 100:

при N > 100:

Сравнение алгоритмов по сложности при N при N > 100:

Слайд 72

Асимптотическая сложность

Асимптотическая сложность – это оценка скорости роста количества операций при больших

Асимптотическая сложность Асимптотическая сложность – это оценка скорости роста количества операций при
значениях N.

сложность O(N) ⇔ T(N) ≤ c⋅ N для N ≥ N0

постоянная

линейная

сумма элементов массива:

T(N) = 2⋅ N – 1 ≤ 2⋅ N для N ≥ 1 ⇒ O(N)

сложность O(N2) ⇔ T(N) ≤ c⋅ N2 для N ≥ N0

квадратичная

сортировка методом выбора:

для N ≥ 0 ⇒ O(N2)

Слайд 73

Асимптотическая сложность

сложность O(N3) ⇔ T(N) ≤ c⋅ N3 для N ≥ N0

кубичная

сложность

Асимптотическая сложность сложность O(N3) ⇔ T(N) ≤ c⋅ N3 для N ≥
O(2N)

сложность O(N!)

задачи оптимизации, полный перебор вариантов

Факториал числа N: N ! = 1 ⋅ 2 ⋅ 3 … ⋅ N

N = 100,
1 млрд оп/с

Слайд 74

Асимптотическая сложность

Алгоритм относится к классу O( f(N) ), если найдется такая постоянная

Асимптотическая сложность Алгоритм относится к классу O( f(N) ), если найдется такая
c, что начиная с некоторого N = N0 выполняется условие
T(N) ≤ c⋅ f (N)

это верхняя оценка!

O( N ) ⇒ O( N2 ) ⇒ O( N3 ) ⇒ O( 2N )

«Алгоритм имеет сложность O(N2)».

обычно – наиболее точная верхняя оценка!

Слайд 75

Программирование (C++)

§ 23. Как разрабатывают программы

Программирование (C++) § 23. Как разрабатывают программы

Слайд 76

Этапы разработки программ

I. Постановка задачи

Документ: техническое задание.

II. Построение модели

Формализация: запись модели в

Этапы разработки программ I. Постановка задачи Документ: техническое задание. II. Построение модели
виде формул (на формальном языке).

III. Разработка алгоритма и способа хранения данных

«Алгоритмы + структуры данных = программы»
(Н. Вирт)

Слайд 77

Этапы разработки программ

IV. Кодирование

Запись алгоритма на языке программирования.

V. Отладка

Поиск и исправление ошибок

Этапы разработки программ IV. Кодирование Запись алгоритма на языке программирования. V. Отладка
в программах:
синтаксические – нарушение правил языка программирования
логические – ошибки в алгоритме
могут приводить к отказам – аварийным ситуациям во время выполнения (run-time error)

Слайд 78

Этапы разработки программ

VI. Тестирование

Тщательная проверка программы во всех режимах:
альфа-тестирование – внутри компании

Этапы разработки программ VI. Тестирование Тщательная проверка программы во всех режимах: альфа-тестирование
(тестировщики)
бета-тестирование – (доверенные) пользователи

VII. Документирование

Технические писатели

VIII. Внедрение и сопровождение

обучение пользователей
исправление найденных ошибок
техподдержка

Слайд 79

Методы проектирования программ

«Сверху вниз» (последовательное уточнение)

Задача

30-40 строк каждая

Методы проектирования программ «Сверху вниз» (последовательное уточнение) Задача 30-40 строк каждая

Слайд 80

Методы проектирования программ

«Сверху вниз» (последовательное уточнение)

сначала задача решается «в целом»
легко распределить работу
легче

Методы проектирования программ «Сверху вниз» (последовательное уточнение) сначала задача решается «в целом»
отлаживать программу (всегда есть полный работающий вариант)

в нескольких подзадачах может потребоваться решение одинаковых подзадач нижнего уровня
быстродействие не известно до последнего этапа (определяется нижним уровнем)

Слайд 81

Методы проектирования программ

«Снизу вверх» (восходящее)

Задача

библиотека функций

Методы проектирования программ «Снизу вверх» (восходящее) Задача библиотека функций

Слайд 82

Методы проектирования программ

«Снизу вверх» (восходящее)

нет дублирования
сразу видно быстродействие

сложно распределять работу
сложнее отлаживать

Методы проектирования программ «Снизу вверх» (восходящее) нет дублирования сразу видно быстродействие сложно
(увеличение числа связей)
плохо видна задача «в целом», может быть нестыковка на последнем этапе

Слайд 83

Пример отладки программы

int main()
{
float a, b, c, D, x1, x2;

Пример отладки программы int main() { float a, b, c, D, x1,
cout << "Введите a, b, c: ";
cin >> a >> b >> c;
D = b*b - 4*a*a;
x1 = (-b + sqrt(D))/2*a;
x2 = (-b - sqrt(D))/2*a;
cout << "x1=" << x1
<< " x2=" << x2);
}

Программа решения квадратного уравнения

Слайд 84

Тестирование

Тест 1. a = 1, b = 2, c = 1.

x1=-1 x2=-1

x1=-1

Тестирование Тест 1. a = 1, b = 2, c = 1.
x2=-1

Реальность:

Тест 2. a = 1, b = – 5, c = 6.

x1=3 x2=2

x1=4.79129 x2=0.208712

Ожидание:

Найден вариант, когда программа работает неверно. Ошибка воспроизводится!

Возможные причины:
неверный ввод данных
неверное вычисление дискриминанта
неверное вычисление корней
неверный вывод результатов

Слайд 85

Отладочная печать

cin >> a >> b >> c;
cout << a << "

Отладочная печать cin >> a >> b >> c; cout D =
" << b << " " << c;
D = b*b - 4*a*a;
cout << "D=" << D);
...

cout << a << " " << b << " " << c << endl;

cout << "D=" << D << endl;

Введите a, b, c: 1 -5 6
1 -5 6
D=21

Результат:

D=21

Идея: выводить все промежуточные результаты.

Слайд 86

Документирование программы

назначение программы
формат входных данных
формат выходных данных
примеры использования программы

Назначение: программа для решения

Документирование программы назначение программы формат входных данных формат выходных данных примеры использования
уравнения

Формат входных данных: значения коэффициентов a, b и c вводятся с клавиатуры через пробел в одной строке

Слайд 87

Документирование программы

Формат выходных данных: значения вещественных корней уравнения; если вещественных корней нет,

Документирование программы Формат выходных данных: значения вещественных корней уравнения; если вещественных корней
выводится слово «нет»

Примеры использования программы: 1. Решение уравнения

Введите a, b, c: 1 -5 6
x1=3 x2=2

2. Решение уравнения

Введите a, b, c: 1 1 6
Нет.

Слайд 88

Программирование (C++)

§ 24. Процедуры

Программирование (C++) § 24. Процедуры

Слайд 89

Два типа подпрограмм

Процедуры

Функции

Подпрограммы

выполняют действия

+ возвращают некоторый
результат

а) рисует окружность на экране
б)

Два типа подпрограмм Процедуры Функции Подпрограммы выполняют действия + возвращают некоторый результат
определяет площадь круга
в) вычисляет значение синуса угла
г) изменяет режим работы программы
д) возводит число x в степень y
е) включает двигатель автомобиля
ж) проверяет оставшееся количество бензина в баке
з) измеряет высоту полёта самолёта

Слайд 90

Простая процедура

#include
using namespace std;
int main() {
...

Простая процедура #include using namespace std; int main() { ... printLine(); ...
printLine();
...
}

какие-то операторы

void printLine() {
cout << "----------" << endl;
}

вызов процедуры

можно вызывать сколько угодно раз
нет дублирования кода
изменять – в одном месте

Слайд 91

Линии разной длины

void printLine5() {
cout << "-----" << endl;

Линии разной длины void printLine5() { cout } void printLine10() { cout
}

void printLine10() {
cout << "----------" << endl;
}

void printLine10() {
for( int i=0; i<10; i++ )
cout << "-";
cout << endl;
}

void printLine10( int n ) {
for( int i=0; i cout << "-";
cout << endl;
}

параметр процедуры

Слайд 92

Процедура с параметром

#include
using namespace std;
int main() {
...
printLine(10);
...

Процедура с параметром #include using namespace std; int main() { ... printLine(10);
printLine(7);
printLine(5);
printLine(3);
}

void printLine10( int n ) {
...
}

Слайд 93

Несколько параметров

void printLine( string c, int n ) {
for( int

Несколько параметров void printLine( string c, int n ) { for( int
i=0; i cout << c;
cout << endl;
}

символьная строка

printLine( 5, "+" );

printLine( "+", 5 );

printLine( "+-+", 5 );

Слайд 94

В других языках программирования

Паскаль:

procedure printLine(n: integer);
var i: integer;
begin
for i:=1 to n

В других языках программирования Паскаль: procedure printLine(n: integer); var i: integer; begin
do
write( '-' );
writeln;
end;

def printLine (n):
print("-"*n)

Python:

Слайд 95

Задачи

«A»: Напишите процедуру, которая принимает параметр – натуральное число N – и

Задачи «A»: Напишите процедуру, которая принимает параметр – натуральное число N –
выводит на экран две линии из N символов "–".
Пример:
Длина цепочки: 7
-------
-------
«B»: Напишите процедуру, которая принимает один параметр – натуральное число N, – и выводит на экран прямоугольник длиной N и высотой 3 символа.
Пример:
Длина прямоугольника: 7
ooooooo
o o
ooooooo

Слайд 96

Задачи

«C»: Напишите процедуру, которая выводит на экран квадрат со стороной N символов.

Задачи «C»: Напишите процедуру, которая выводит на экран квадрат со стороной N
При запуске программы N нужно ввести с клавиатуры.
Пример:
Сторона квадрата: 5
ooooo
o o
o o
o o
ooooo

Слайд 97

Задачи

«D»: Напишите процедуру, которая выводит на экран треугольник со стороной N символов.

Задачи «D»: Напишите процедуру, которая выводит на экран треугольник со стороной N
При запуске программы N нужно ввести с клавиатуры.
Пример:
Сторона: 5
o
oo
ooo
oooo
ooooo

Слайд 98

Рекурсия

Задача. Вывести на экран двоичный код натурального числа.

void printBin( int n )

Рекурсия Задача. Вывести на экран двоичный код натурального числа. void printBin( int
{
...
}

Алгоритм перевода через остатки:

while( n!=0 ) {
cout << n % 2;
n = n / 2;
}

011

в обратном порядке!

Слайд 99

Рекурсия

Чтобы вывести двоичную запись числа n, нужно сначала вывести двоичную запись числа

Рекурсия Чтобы вывести двоичную запись числа n, нужно сначала вывести двоичную запись
(n/2), а за- тем — его последнюю двоичную цифру, равную (n % 2).

110

Это и есть рекурсия!

Слайд 100

Рекурсивная процедура

Рекурсивная процедура — это процедура, которая вызывает сама себя.

void printBin( int

Рекурсивная процедура Рекурсивная процедура — это процедура, которая вызывает сама себя. void
n ) {
printBin( n / 2 );
cout << n % 2;
}

вызывает сама себя!

printBin(6);

printBin(3);

printBin(1);

printBin(0);

printBin(0);

бесконечные вызовы

Слайд 101

Рекурсивная процедура

void printBin( int n ) {
if( n == 0 )

Рекурсивная процедура void printBin( int n ) { if( n == 0
return;
printBin( n / 2 );
cout << n % 2;
}

printBin(6);

printBin(3);

printBin(1);

printBin(0);

if( n == 0 ) return;

cout << 1 % 2;

cout << 3 % 2;

cout << 6 % 2;

1

1

0

рекурсия заканчивается!

Слайд 102

Задачи

«A»: Напишите рекурсивную процедуру, которая переводит число в восьмеричную систему.
Пример:
Введите число:

Задачи «A»: Напишите рекурсивную процедуру, которая переводит число в восьмеричную систему. Пример:
66
В восьмеричной: 102
«B»: Напишите рекурсивную процедуру, которая переводит число в любую систему счисления с основанием от 2 до 9.
Пример:
Введите число: 75
Основание: 6
В системе с основанием 6: 203

Слайд 103

Задачи

«С»: Напишите рекурсивную процедуру, которая переводит число в шестнадцатеричную систему.
Пример:
Введите число:

Задачи «С»: Напишите рекурсивную процедуру, которая переводит число в шестнадцатеричную систему. Пример:
123
В шестнадцатеричной: 7B
«D»: Напишите рекурсивную процедуру, которая переводит число в любую систему счисления с основанием от 2 до 36.
Пример:
Введите число: 350
Основание: 20
В системе с основанием 20: HA

Слайд 104

Программирование (C++)

§ 25. Функции

Программирование (C++) § 25. Функции

Слайд 105

Что такое функция?

Функция — это вспомогательный алгоритм, который возвращает результат (число, строку

Что такое функция? Функция — это вспомогательный алгоритм, который возвращает результат (число,
символов и др.).

Задача. Написать функцию, которая вычисляет среднее арифметическое двух целых чисел.

цел

вещ

float Avg( int a, int b ) {
float sred =(a+b)/2.;
return sred;
}

это результат!

Слайд 106

Как вызывать функцию?

Запись результата в переменную:

float sr;
sr = Avg(5, 8);

int x

Как вызывать функцию? Запись результата в переменную: float sr; sr = Avg(5,
= 2, y = 5;
float sr = Avg(x, 2*y+8);

6.5

10

Вывод на экран:

int x = 2, y = 5;
float sr = Avg(x, y+3);
cout << Avg(12, 7); cout << sr + Avg(x, 12);

5

9.5

12

Слайд 107

Как вызывать функцию?

Использование в условных операторах:

int a, b;
cin >> a >>

Как вызывать функцию? Использование в условных операторах: int a, b; cin >>
b;
if( Avg(a,b) > 5 )
cout << "Да!";
else
cout << "Нет!";

Слайд 108

Как вызывать функцию?

Использование в циклах:

int a, b;
cin >> a >> b;
while(

Как вызывать функцию? Использование в циклах: int a, b; cin >> a
Avg(a,b) > 0 ) {
cout << "Нет!";
cin >> a >> b;
}
cout << "Угадал!";

Слайд 109

В других языках программирования

def Avg(a, b):
return(a+b)/2

Python:

Паскаль:

function Avg( a, b: integer): real;
begin

В других языках программирования def Avg(a, b): return(a+b)/2 Python: Паскаль: function Avg(
Avg := (a+b)/2;
end;

Слайд 110

Максимум из двух (трёх) чисел

Задача. Составить функцию, которая определяет наибольшее из двух

Максимум из двух (трёх) чисел Задача. Составить функцию, которая определяет наибольшее из
целых чисел.

int Max( int a, int b ) {
if( a > b )
return a;
else
return b;
}

цел

цел

int Max3( int a, int b, int c ) {
return Max( Max(a,b), c );
}

Слайд 111

Сумма цифр числа

Задача. Составить функцию, которая вычисляет сумму значений цифр натурального числа.

Сумма цифр числа Задача. Составить функцию, которая вычисляет сумму значений цифр натурального

int sumDigits( int N ) {
int d, sum = 0; // накапливаем сумму с 0
while( N != 0 ) {
d = N % 10; // выделим последнюю цифру
sum += d; // добавим к сумме
N = N / 10; // удалим последнюю цифру
}
return sum; // возвращаем результат
}

Слайд 112

Задачи

«A»: Напишите функцию, которая вычисляет среднее арифметическое пяти целых чисел.
Пример:
Введите 5

Задачи «A»: Напишите функцию, которая вычисляет среднее арифметическое пяти целых чисел. Пример:
чисел: 1 2 3 4 6
Среднее: 3.2
«B»: Напишите функцию, которая находит количество цифр в десятичной записи числа.
Пример:
Введите число: 751
Количество цифр: 3

Слайд 113

Задачи

«С»: Напишите функцию, которая находит количество единиц в двоичной записи числа.
Пример:
Введите

Задачи «С»: Напишите функцию, которая находит количество единиц в двоичной записи числа.
число: 75
Количество единиц: 4

Слайд 114

Логические функции

Логическая функция — это функция, возвращающая логическое значения (да или нет).

можно

Логические функции Логическая функция — это функция, возвращающая логическое значения (да или
ли применять операцию?
успешно ли выполнена операция?
обладают ли данные каким-то свойством?

Слайд 115

Логические функции

bool Even( int N ) {
if( N % 2

Логические функции bool Even( int N ) { if( N % 2
== 0 )
return true;
else
return false;
}

Задача. Составить функцию, которая возвращает «true», если она получила чётное число и «false», если нечётное.

bool Even( int N ) {
return (N % 2 == 0);
}

Слайд 116

Рекурсивные функции

Рекурсивная функция — это функция, которая вызывает сама себя.

Задача. Составить рекурсивную

Рекурсивные функции Рекурсивная функция — это функция, которая вызывает сама себя. Задача.
функцию, которая вычисляет сумму цифр числа.

Сумму цифр числа N нужно выразить через сумму цифр другого (меньшего) числа.

Сумма цифр числа N равна значению последней цифры плюс сумма цифр числа, полученного отбрасыванием последней цифры.

sumDig(12345) = 5 + sumDig(1234)

Слайд 117

Рекурсивная функция

Вход: натуральное число N.
Шаг 1: d = N % 10
Шаг 2:

Рекурсивная функция Вход: натуральное число N. Шаг 1: d = N %
M = N / 10
Шаг 3: s = сумма цифр числа M
Шаг 4: sum = s + d
Результат: sum.

Сумма цифр числа N

последняя цифра

число без последней цифры

Слайд 118

Сумма цифр числа (рекурсия)

int sumDigRec( int N ) {
if( N ==

Сумма цифр числа (рекурсия) int sumDigRec( int N ) { if( N
0 ) return 0;
int d = N % 10;
int sum = sumDigRec(N /10);
return sum+d;
}

if( N == 0 ) return 0;

Слайд 119

Задачи

«A»: Напишите логическую функцию, которая возвращает значение «истина», если десятичная запись числа

Задачи «A»: Напишите логическую функцию, которая возвращает значение «истина», если десятичная запись
заканчивается на цифру 0 или 1.
Пример:
Введите число: 1230
Ответ: Да
«B»: Напишите логическую функцию, которая возвращает значение «истина», если переданное ей число помещается в 8-битную ячейку памяти.
Пример:
Введите число: 751
Ответ: Нет

Слайд 120

Задачи

«C»: Напишите логическую функцию, которая возвращает значение «истина», если переданное ей число

Задачи «C»: Напишите логическую функцию, которая возвращает значение «истина», если переданное ей
простое (делится только на само себя и на единицу).
Пример:
Введите число: 17
Число простое!
Пример:
Введите число: 18
Число составное!

Слайд 121

Конец фильма

ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН

Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163,
Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
Имя файла: Программирование-(C++).pptx
Количество просмотров: 37
Количество скачиваний: 0