1 Программирование на языке Паскаль Часть II 1.МассивыМассивы 2.Максимальный элемент массиваМаксимальный элемент массива 3.Обработка массивовОбработка.

Презентация:



Advertisements
Похожие презентации
1 Программирование на языке Паскаль Файлы с последовательным доступом. Кулебякин В.В.
Advertisements

1 Программирование на языке Паскаль Часть II Символьные строки.
1 Программирование на языке Паскаль Тема: Файлы. Integer, Real, Boolean, Character, String, Text.
1 Программирование на языке Паскаль Тема 4. Сортировка массивов.
Алгоритмы сортировки. 2 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме.
Программирование на языке Паскаль Часть II Тема 1. Массивы.
Программирование на языке Паскаль Символьные строки.
1 Программирование на языке Паскаль Часть II © К.Ю. Поляков, МассивыМассивы 2.Максимальный элемент массиваМаксимальный элемент массива 3.Обработка.
Программирование на языке Паскаль Массивы.
Программирование на языке Паскаль Часть II Матрицы.
К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 4. Символьные строки.
К.Ю. Поляков, Е.А. Ерёмин, 2013 Программирование на языке Паскаль § 64. Сортировка 1.
ОДНОМЕРНЫЕ МАССИВЫ. РАБОТА С ЭЛЕМЕНТАМИ СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ.
Программирование на языке Паскаль Текстовые файлы.
1 Программирование на языке Паскаль Матрицы. 2 Задача: запомнить положение фигур на шахматной доске abcdefgh
Язык программирования Pascal Массивы А. Жидков. Массивы Массив – поименованный набор однотипных элементов, каждый из которых имеет свой номер, (индекс).
1 Программирование на языке Паскаль Часть II Тема 4. Сортировка массивов © К.Ю. Поляков,
1 Программирование на языке Паскаль Тема 1. Массивы.
Матрицы 1. 2 Задача: запомнить положение фигур на шахматной доске abcdefgh
Программирование на языке Паскаль Урок Сортировка массивов Рыжикова С. В. Учитель информатики МОУ СОШ 2 г. Волжского Волгоградской обл.
Транксрипт:

1 Программирование на языке Паскаль Часть II 1.МассивыМассивы 2.Максимальный элемент массиваМаксимальный элемент массива 3.Обработка массивовОбработка массивов 4.Сортировка массивовСортировка массивов 5.Поиск в массивеПоиск в массиве 6.Символьные строкиСимвольные строки 7.Рекурсивный переборРекурсивный перебор 8.МатрицыМатрицы 9.ФайлыФайлы

2 Программирование на языке Паскаль Часть II Тема 1. Массивы

3 Массивы Массив – это группа однотипных элементов, имеющих общее имя и расположенных в памяти рядом. Особенности: все элементы имеют один тип весь массив имеет одно имя все элементы расположены в памяти рядом Примеры: список учеников в классе квартиры в доме школы в городе данные о температуре воздуха за год

4 Массивы A массив 3 15 НОМЕР элемента массива (ИНДЕКС) НОМЕР элемента массива (ИНДЕКС) A[1] A[2] A[3] A[4] A[5] ЗНАЧЕНИЕ элемента массива A[2] НОМЕР (ИНДЕКС) элемента массива: 2 ЗНАЧЕНИЕ элемента массива: 10

5 Объявление массивов Зачем объявлять? определить имя массива определить тип массива определить число элементов выделить место в памяти Массив целых чисел: Размер через константу: имя начальный индекс конечный индекс тип элементов тип элементов var A: array[1.. ] of integer; const N=5; N var A : array[ ] of integer ;

6 Объявление массивов Массивы других типов: Другой диапазон индексов: Индексы других типов: var X, Y: array [1..10] of real; C: array [1..20] of char; var X, Y: array [1..10] of real; C: array [1..20] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var Q: array [0..9] of real; C: array [-5..13] of char; var A: array ['A'..'Z'] of real; B: array [False..True] of integer;... A['C'] := *A['B']; B[False] := B[False] + 1; var A: array ['A'..'Z'] of real; B: array [False..True] of integer;... A['C'] := *A['B']; B[False] := B[False] + 1;

7 Что неправильно? var a: array[10..1] of integer;... A[5] := 4.5; var a: array[10..1] of integer;... A[5] := 4.5; [1..10] var a: array ['z'..'a'] of integer;... A['B'] := 15; var a: array ['z'..'a'] of integer;... A['B'] := 15; A['b'] ['a'..'z'] var a: array [0..9] of integer;... A[10] := 'X'; var a: array [0..9] of integer;... A[10] := 'X';

8 Массивы Объявление: Ввод с клавиатуры: Поэлементные операции: Вывод на экран: const N = 5; var a: array[1..N] of integer; i: integer; const N = 5; var a: array[1..N] of integer; i: integer; for i:=1 to N do begin write('a[', i, ']='); read ( a[i] ); end; for i:=1 to N do begin write('a[', i, ']='); read ( a[i] ); end; a[1] = a[2] = a[3] = a[4] = a[5] = Почему write ? ? for i:=1 to N do a[i]:=a[i]*2; writeln('Массив A:'); for i:=1 to N do write(a[i]:4); writeln('Массив A:'); for i:=1 to N do write(a[i]:4); Массив A:

9 Задания «4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива. Пример: Введите пять чисел: среднее арифметическое «5»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них. Пример: Введите пять чисел: минимальный элемент 3 При изменении N остальная программа не должна изменяться! !

10 Программирование на языке Паскаль Часть II Тема 2. Максимальный элемент массива

11 Максимальный элемент Задача: найти в массиве максимальный элемент. Алгоритм: Псевдокод: { считаем, что первый элемент – максимальный } for i:=2 to N do if a[i] > { максимального } then { запомнить новый максимальный элемент a[i] } { считаем, что первый элемент – максимальный } for i:=2 to N do if a[i] > { максимального } then { запомнить новый максимальный элемент a[i] } Почему цикл от i=2 ? ?

12 Максимальный элемент max := a[1]; { считаем, что первый – максимальный } iMax := 1; for i:=2 to N do { проверяем все остальные } if a[i] > max then { нашли новый максимальный } begin max := a[i]; { запомнить a[i] } iMax := i; { запомнить i } end; max := a[1]; { считаем, что первый – максимальный } iMax := 1; for i:=2 to N do { проверяем все остальные } if a[i] > max then { нашли новый максимальный } begin max := a[i]; { запомнить a[i] } iMax := i; { запомнить i } end; Дополнение: как найти номер максимального элемента? Как упростить? ? По номеру элемента iMax всегда можно найти его значение a[iMax]. Поэтому везде меняем max на a[iMax] и убираем переменную max. a[iMax]

13 Программа program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin writeln('Исходный массив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end. program qq; const N = 5; var a: array [1..N] of integer; i, iMax: integer; begin writeln('Исходный массив:'); for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } writeln; {перейти на новую строку} writeln('Максимальный элемент a[', iMax, ']=', a[iMax]); end. for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; for i:=1 to N do begin a[i] := random(100) + 50; write(a[i]:4); end; iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } iMax := 1; { считаем, что первый – максимальный } for i:=2 to N do { проверяем все остальные } if a[i] > a[iMax] then { новый максимальный } iMax := i; { запомнить i } случайные числа в интервале [50,150) поиск максимального

14 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и найти в нем максимальный и минимальный элементы и их номера. Пример: Исходный массив: максимальный a[4]=10 минимальный a[8]=-10 «5»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и найти в нем два максимальных элемента и их номера. Пример: Исходный массив: максимальные a[4]=10, a[7]=8

15 Программирование на языке Паскаль Часть II Тема 3. Обработка массивов

16 Реверс массива Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять местами A[1] и A[N], A[2] и A[N-1], … Псевдокод: 35…97 79…53 12…N-1N 12… N for i:=1 to N do { поменять местами A[i] и A[N+1-i] } for i:=1 to N do { поменять местами A[i] и A[N+1-i] } сумма индексов N+1 Что неверно? ? N div 2 do

17 Как переставить элементы? Задача: поменять местами содержимое двух чашек. Задача: поменять местами содержимое двух ячеек памяти ? ? x y c c := x; x := y; y := c; c := x; x := y; y := c; x := y; y := x; x := y; y := x; Можно ли обойтись без c ? ?

18 Программа program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end; for i:=1 to N div 2 do begin c:=A[i]; A[i]:=A[N+1-i]; A[N+1-i]:=c; end;

19 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить инверсию отдельно для 1-ой и 2-ой половин массива. Пример: Исходный массив: Результат: «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить инверсию для каждой трети массива. Пример: Исходный массив: Результат:

20 Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент становится на место последнего. Алгоритм: A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N]; Цикл: 3581… …N-1N 581…973 for i:=1 to N-1 do A[i]:=A[i+1]; for i:=1 to N-1 do A[i]:=A[i+1]; Что неверно? ? почему не N ?

21 Программа program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. program qq; const N = 10; var A: array[1..N] of integer; i, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c; c := A[1]; for i:=1 to N-1 do A[i]:=A[i+1]; A[N] := c;

22 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО. Пример: Исходный массив: Результат: «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить циклический сдвиг ВПРАВО на 4 элемента. Пример: Исходный массив: Результат:

23 Программирование на языке Паскаль Часть II Тема 4. Сортировка массивов

24 Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» (Quick Sort) сортировка «кучей» (Heap Sort) сортировка слиянием пирамидальная сортировка сложность O(N 2 ) сложность O(N·logN) время N O(N 2 ) O(N·logN)

25 Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает») начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место ый проход 2-ой проход 3-ий проход Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

26 Программа 1-ый проход: 5 2 … … N-1 N сравниваются пары A[N-1] и A[N], A[N-2] и A[N-1] … A[1] и A[2] A[j] и A[j+1] 2-ой проход A[1] уже на своем месте! ! for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; for j:=N-1 downto 2 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 2 for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; for j:=N-1 downto 1 do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; 1 i -ый проход for j:=N-1 downto i do... for j:=N-1 downto i do... i 1 5 … … N-1 N

27 Программа program qq; const N = 10; var A: array[1..N] of integer; i, j, c: integer; begin { заполнить массив } { вывести исходный массив } { вывести полученный массив } end. for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; for i:=1 to N-1 do begin for j:=N-1 downto i do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; end; Почему цикл по i до N-1 ? ? i элементы выше A[i] уже поставлены

28 Метод пузырька с флажком Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны. Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход. repeat flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } repeat flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } flag := False; flag := True; not flag; var flag: boolean; Как улучшить? ?

29 Метод пузырька с флажком i := 0; repeat i := i + 1; flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; repeat i := i + 1; flag := False; { сбросить флаг } for j:=N-1 downto 1 do if A[j] > A[j+1] then begin с := A[j]; A[j] := A[j+1]; A[j+1] := с; flag := True; { поднять флаг } end; until not flag; { выход при flag=False } i := 0; i i := i + 1;

30 Метод выбора Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2] ), и т.д

31 Метод выбора for i := 1 to N-1 do begin nMin = i ; for j:= i+1 to N do if A[j] < A[nMin] then nMin:=j; if nMin i then begin c:=A[i]; A[i]:=A[nMin]; A[nMin]:=c; end; N-1 N нужно N-1 проходов поиск минимального от A[i] до A[N] если нужно, переставляем Можно ли убрать if ? ? i+1 i

32 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре. Пример: Исходный массив: Результат: «5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию. Пример: Исходный массив: Результат:

33 «Быстрая сортировка» (Quick Sort) Идея – более эффективно переставлять элементы, расположенные дальше друг от друга. Сколько перестановок нужно, если массив отсортирован по убыванию, а надо – по возрастанию? ? N div 2 2 шаг: переставить элементы так: при сортировке элементы не покидают « свою область»! 1 шаг: выбрать некоторый элемент массива X A[i] = X 3 шаг: так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer)

34 «Быстрая сортировка» (Quick Sort) Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…). Разделение: 1)выбрать средний элемент массива ( X=67 ) 2)установить L:=1, R:=N 3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа) 4)уменьшая R, найти первый элемент A[R], который

35 «Быстрая сортировка» (Quick Sort) LR LR LR RL L > R : разделение закончено !

36 «Быстрая сортировка» (Quick Sort) procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; QSort(first, R); QSort(L, last); end; end. procedure QSort ( first, last: integer); var L, R, c, X: integer; begin if first < last then begin X:= A[(first + last) div 2]; L:= first; R:= last; QSort(first, R); QSort(L, last); end; end. ограничение рекурсии while L X do R:= R - 1; if L

37 «Быстрая сортировка» (Quick Sort) program qq; const N = 10; var A: array[1..N] of integer; begin { заполнить массив } { вывести исходный массив на экран } Qsort ( 1, N ); { сортировка } { вывести результат } end. program qq; const N = 10; var A: array[1..N] of integer; begin { заполнить массив } { вывести исходный массив на экран } Qsort ( 1, N ); { сортировка } { вывести результат } end. procedure QSort ( first, last: integer);... Сложность (в среднем) ! !

NQuickSort«пузырек» Количество перестановок (случайные данные) От чего зависит скорость? ? Как хуже всего выбирать X? ?

39 Задания «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и отсортировать его по убыванию с помощью алгоритма быстрой сортировки. «5»: Заполнить массив из 500 элементов случайными числами в интервале [0..100]. Отсортировать его по возрастанию двумя способами – методом «пузырька» и методом «быстрой сортировки». Вывести на экран число перестановок элементов массива в том и в другом случае. Массив выводить на экран не нужно.

40 Программирование на языке Паскаль Часть II Тема 5. Поиск в массиве

41 Поиск в массиве Задача – найти в массиве элемент, равный X, или установить, что его нет. Решение: для произвольного массива: линейный поиск (перебор) недостаток: низкая скорость Как ускорить? – заранее подготовить массив для поиска как именно подготовить? как использовать «подготовленный массив»?

42 Линейный поиск nX := 0; for i:=1 to N do if A[i] = X then begin nX := i; break; {выход из цикла} end; nX := 0; for i:=1 to N do if A[i] = X then begin nX := i; break; {выход из цикла} end; nX := 0; { пока не нашли...} if nX < 1 then writeln('Не нашли...') else writeln('A[', nX, ']=', X); nX := 0; { пока не нашли...} if nX < 1 then writeln('Не нашли...') else writeln('A[', nX, ']=', X); nX – номер нужного элемента в массиве Что плохо? ? Улучшение: после того, как нашли X, выходим из цикла. for i:=1 to N do { цикл по всем элементам } if A[i] = X then { если нашли, то... } nX := i; {... запомнили номер} for i:=1 to N do { цикл по всем элементам } if A[i] = X then { если нашли, то... } nX := i; {... запомнили номер} nX := 0; i := 1; while i

43 Двоичный поиск X = 7X = 7 X < 8X < X > 4X > X > 6 1.Выбрать средний элемент A[c] и сравнить с X. 2.Если X = A[c], нашли (выход). 3.Если X < A[c], искать дальше в первой половине. 4.Если X > A[c], искать дальше во второй половине.

44 Двоичный поиск nX := 0; L := 1; R := N; {границы: ищем от A[1] до A[N] } if nX < 1 then writeln('Не нашли...') else writeln('A[', nX, ']=', X); while R >= L do begin c := (R + L) div 2; if X < A[c] then R := c - 1; if X > A[c] then L := c + 1; end; номер среднего элемента if X = A[c] then begin nX := c; R := L - 1; { break; } end; if X = A[c] then begin nX := c; R := L - 1; { break; } end; нашли Почему нельзя while R > L do begin … end; ? ? выйти из цикла сдвигаем границы 1LcRN

45 Сравнение методов поиска ЛинейныйДвоичный подготовканетотсортировать число шагов N = 222 N = N = N= N N log 2 N+1

46 Задания «4»: Написать программу, которая сортирует массив ПО УБЫВАНИЮ и ищет в нем элемент, равный X (это число вводится с клавиатуры). Использовать двоичный поиск. «5»: Написать программу, которая считает среднее число шагов в двоичном поиске для массива из 32 элементов в интервале [0,100]. Для поиска использовать 1000 случайных чисел в этом же интервале.

47 Программирование на языке Паскаль Часть II Тема 6. Символьные строки

48 Чем плох массив символов? var B: array[1..N] of char; Это массив символов: каждый символ – отдельный объект; массив имеет длину N, которая задана при объявлении Что нужно: обрабатывать последовательность символов как единое целое строка должна иметь переменную длину

49 Символьные строки Привет!¤¤¤…¤¤¤ длина строки рабочая часть s[1] s[2] s[3] s[4] var s: string; var s: string[20]; 20 1 Длина строки: n := length ( s ); var n: integer; В Delphi это ограничение снято! !

50 Символьные строки Задача: ввести строку с клавиатуры и заменить все буквы «а» на буквы «б». program qq; var s: string; i: integer; begin writeln('Введите строку'); readln(s); for i:=1 to Length(s) do if s[i] = 'а' then s[i] := 'б'; writeln(s); end. program qq; var s: string; i: integer; begin writeln('Введите строку'); readln(s); for i:=1 to Length(s) do if s[i] = 'а' then s[i] := 'б'; writeln(s); end. readln(s); writeln(s); Length(s) ввод строки длина строки вывод строки

51 Задания «4»: Ввести символьную строку и заменить все буквы «а» на буквы «б» и наоборот, как заглавные, так и строчные. Пример: Введите строку: ааббссААББСС Результат: ббаассББААСС «5»: Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях). Пример: Пример: Введите строку: Введите строку: АБВГДЕ КАЗАК Результат: Результат: Не палиндром. Палиндром.

52 Операции со строками Объединение: добавить одну строку в конец другой. Запись нового значения: var s, s1, s2: string; s := 'Вася'; s1 := 'Привет'; s2 := 'Вася'; s := s1 + ', ' + s2 + '!'; s1 := 'Привет'; s2 := 'Вася'; s := s1 + ', ' + s2 + '!'; 'Привет, Вася!' Подстрока: выделить часть строки в другую строку. s := ' '; s1 := Copy ( s, 3, 6 ); s2 := Copy ( s1, 2, 3 ); s := ' '; s1 := Copy ( s, 3, 6 ); s2 := Copy ( s1, 2, 3 ); '345678' '456' с 3-его символа 6 штук

53 Удаление и вставка Удаление части строки: Вставка в строку: s := ' '; Delete ( s, 3, 6 ); s := ' '; Delete ( s, 3, 6 ); с 3-его символа 6 штук строка меняется! строка меняется! ' ' '129' s := ' '; Insert ( 'ABC', s, 3 ); Insert ( 'Q', s, 5 ); s := ' '; Insert ( 'ABC', s, 3 ); Insert ( 'Q', s, 5 ); куда вставляем что вставляем начиная с 3-его символа '12ABC ' '12ABQC '

54 Поиск в строке Поиск в строке: s := 'Здесь был Вася.'; n := Pos ( 'е', s ); if n > 0 then writeln('Буква е – это s[', n, ']') else writeln('Не нашли'); n := Pos ( 'Вася', s ); s1 := Copy ( s, n, 4 ); s := 'Здесь был Вася.'; n := Pos ( 'е', s ); if n > 0 then writeln('Буква е – это s[', n, ']') else writeln('Не нашли'); n := Pos ( 'Вася', s ); s1 := Copy ( s, n, 4 ); s[3] 3 3 n = 11 Особенности: функция возвращает номер символа, с которого начинается образец в строке если слова нет, возвращается 0 поиск с начала (находится первое слово) var n: integer;

55 Примеры s := 'Вася Петя Митя'; n := Pos ( 'Петя', s ); Delete ( s, n, 4 ); Insert ( 'Лена', s, n ); s := 'Вася Петя Митя'; n := Pos ( 'Петя', s ); Delete ( s, n, 4 ); Insert ( 'Лена', s, n ); 'Вася Лена Митя' s := 'Вася Петя Митя'; n := length ( s ); s1 := Copy ( s, 1, 4 ); s2 := Copy ( s, 11, 4 ); s3 := Copy ( s, 6, 4 ); s := s3 + s1 + s2; n := length ( s ); s := 'Вася Петя Митя'; n := length ( s ); s1 := Copy ( s, 1, 4 ); s2 := Copy ( s, 11, 4 ); s3 := Copy ( s, 6, 4 ); s := s3 + s1 + s2; n := length ( s ); 'Вася Митя' 14 'Вася' 'Митя' 'Петя' 'ПетяВасяМитя'

56 Преобразования «строка»-«число» Из строки в число: s := '123'; Val ( s, N, r ); { N = 123 } { r = 0, если ошибки не было r – номер ошибочного символа} s := ' '; Val ( s, X, r ); { X = } s := '123'; Val ( s, N, r ); { N = 123 } { r = 0, если ошибки не было r – номер ошибочного символа} s := ' '; Val ( s, X, r ); { X = } Из числа в строку: N := 123; Str ( N, s ); { '123' } X := ; Str ( X, s ); { ' E+002' } Str ( X:10:3, s ); { ' ' } N := 123; Str ( N, s ); { '123' } X := ; Str ( X, s ); { ' E+002' } Str ( X:10:3, s ); { ' ' } var N: integer; X: real; s: string; var N: integer; X: real; s: string;

57 Пример решения задачи Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы». Пример: Введите имя, фамилию и отчество: Василий Алибабаевич Хрюндиков Результат: Хрюндиков В.А. Алгоритм: найти первый пробел и выделить имя удалить имя с пробелом из основной строки найти первый пробел и выделить отчество удалить отчество с пробелом из основной строки «сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…

58 Программа program qq; var s, name, otch: string; n: integer; begin writeln('Введите имя, отчество и фамилию'); readln(s); n := Pos(' ', s); name := Copy(s, 1, n-1); { вырезать имя } Delete(s, 1, n); n := Pos(' ', s); otch := Copy(s, 1, n-1); { вырезать отчество } Delete(s, 1, n); { осталась фамилия } s := s + ' ' + name[1] + '.' + otch[1] + '.'; writeln(s); end. program qq; var s, name, otch: string; n: integer; begin writeln('Введите имя, отчество и фамилию'); readln(s); n := Pos(' ', s); name := Copy(s, 1, n-1); { вырезать имя } Delete(s, 1, n); n := Pos(' ', s); otch := Copy(s, 1, n-1); { вырезать отчество } Delete(s, 1, n); { осталась фамилия } s := s + ' ' + name[1] + '.' + otch[1] + '.'; writeln(s); end.

59 Задания «4»: Ввести имя файла (возможно, без расширения) и изменить его расширение на «.exe ». Пример: Введите имя файла: Введите имя файла: qqq qqq.com Результат: Результат: qqq.exe qqq.exe «5»: Ввести путь к файлу и «разобрать» его, выводя каждую вложенную папку с новой строки Пример: Введите путь к файлу: C:\Мои документы\10-Б\Вася\qq.exe Результат: C: Мои документы 10-Б Вася qq.exe

60 Посимвольный ввод Задача: с клавиатуры вводится число N, обозначающее количество футболистов команды «Шайба», а затем – N строк, в каждой из которых – информация об одном футболисте таком формате: Все данные разделяются одним пробелом. Нужно подсчитать, сколько футболистов, родившихся в период с 1988 по1990 год, не забили мячей вообще. Алгоритм: for i:=1 to N do begin { пропускаем фамилию и имя } { читаем год рождения Year и число голов Gol } if (1988

61 Посимвольный ввод Пропуск фамилии: repeat read(c); until c = ' '; { пока не встретим пробел } repeat read(c); until c = ' '; { пока не встретим пробел } var c: char; Пропуск имени: repeat read(c); until c = ' '; Ввод года рождения: read(Year); { из той же введенной строки } var Year: integer; Ввод числа голов и переход к следующей строке: readln(Gol); { читать все до конца строки } var Gol: integer;

62 Программа program qq; var c: char; i, N, count, Year, Gol: integer; begin writeln('Количество футболистов'); readln(N); count := 0; for i:=1 to N do begin repeat read(c); until c = ' '; read(Year); readln(Gol); if (1988

63 Посимвольный ввод Если фамилия нужна: fam := ''; { пустая строка } repeat read(c); { прочитать символ } fam := fam + c; { прицепить к фамилии } until c = ' '; fam := ''; { пустая строка } repeat read(c); { прочитать символ } fam := fam + c; { прицепить к фамилии } until c = ' '; Вместо read(Year) : s := ''; { пустая строка } repeat read(c); { прочитать символ } s := s + c; { прицепить к фамилии } until c = ' '; Val(s, Year, r); { строку – в число } s := ''; { пустая строка } repeat read(c); { прочитать символ } s := s + c; { прицепить к фамилии } until c = ' '; Val(s, Year, r); { строку – в число } var fam: string; var s: string;

64 Посимвольный ввод Если нужно хранить все фамилии: const MAX = 100; var fam: array[1..MAX] of string;... fam[i] := ''; { пустая строка } repeat read(c); { прочитать символ } fam[i] := fam[i] + c; until c = ' '; const MAX = 100; var fam: array[1..MAX] of string;... fam[i] := ''; { пустая строка } repeat read(c); { прочитать символ } fam[i] := fam[i] + c; until c = ' '; массив символьных строк

65 Задания «4»: Вывести фамилию и имя футболиста, забившего наибольшее число голов, и количество забитых им голов. Пример: Иванов Василий 25 «5»: Вывести в алфавитном порядке фамилии и имена всех футболистов, которые забили хотя бы один гол. В списке не более 100 футболистов. Пример: Васильев Иван Иванов Василий Кутузов Михаил Пупкин Василий Информация о футболистах вводится так же, как и для приведенной задачи (сначала N, потом N строк с данными).

66 Программирование на языке Паскаль Часть II Тема 7. Рекурсивный перебор

67 Рекурсивный перебор Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры. 1K в каждой ячейке может быть любая из 4-х букв 4 варианта Количество вариантов:

68 Рекурсивный перебор Ы 1K Рекурсия: Решения задачи для слов из К букв сводится к 4-м задачам для слов из K-1 букв. Щ 1K О 1K Ц 1K перебрать все варианты

69 Процедура procedure Rec(p: integer); begin if p > K then begin writeln(s); count := count+1; end else begin s[p]:='Ы'; Rec ( p+1 ); s[p]:='Ц'; Rec ( p+1 ); s[p]:='Щ'; Rec ( p+1 ); s[p]:='О'; Rec ( p+1 ); end; ???? 1K p s p+1 рекурсивные вызовы А если букв много? ? окончание рекурсии Глобальные переменные: var s: string; count, K: integer;

70 Процедура procedure Rec(p: integer); const letters = 'ЫЦЩО'; var i: integer; begin if p > k then begin writeln(s); count := count+1; end else begin for i:=1 to length(letters) do begin s[p] := letters[i]; Rec(p+1); end; procedure Rec(p: integer); const letters = 'ЫЦЩО'; var i: integer; begin if p > k then begin writeln(s); count := count+1; end else begin for i:=1 to length(letters) do begin s[p] := letters[i]; Rec(p+1); end; const letters = 'ЫЦЩО'; for i:=1 to length(letters) do begin s[p] := letters[i]; Rec(p+1); end; все буквы цикл по всем буквам локальная переменная

71 Программа program qq; var s: string; K, i, count: integer; begin writeln('Введите длину слов:'); read ( K ); s := ''; for i:=1 to K do s := s + ' '; count := 0; Rec ( 1 ); writeln('Всего ', count, ' слов'); end. program qq; var s: string; K, i, count: integer; begin writeln('Введите длину слов:'); read ( K ); s := ''; for i:=1 to K do s := s + ' '; count := 0; Rec ( 1 ); writeln('Всего ', count, ' слов'); end. procedure Rec(p: integer);... end; процедура s := ''; for i:=1 to K do s := s + ' '; строка из K пробелов глобальные переменные

72 Задания Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и О. Число K вводится с клавиатуры. «4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество. «5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество.

73 Программирование на языке Паскаль Часть II Тема 8. Матрицы

74 Матрицы Задача: запомнить положение фигур на шахматной доске abcdefgh c6 A[6,3]

75 Матрицы Матрица – это прямоугольная таблица чисел (или других элементов одного типа). Матрица – это массив, в котором каждый элемент имеет два индекса (номер строки и номер столбца) A строка 2 столбец 3 ячейка A[3,4]

76 Матрицы Объявление: const N = 3; M = 4; var A: array[1..N,1..M] of integer; B: array[-3..0,-8..M] of integer; Q: array['a'..'d',False..True] of real; const N = 3; M = 4; var A: array[1..N,1..M] of integer; B: array[-3..0,-8..M] of integer; Q: array['a'..'d',False..True] of real; Ввод с клавиатуры: for i:=1 to N do for j:=1 to M do begin write('A[',i,',',j,']='); read ( A[i,j] ); end; for i:=1 to N do for j:=1 to M do begin write('A[',i,',',j,']='); read ( A[i,j] ); end; Если переставить циклы? ? A[1,1]=25 A[1,2]=14 A[1,3]=14... A[3,4]=54 i i j j for j:=1 to M do for i:=1 to N do begin

77 Матрицы Заполнение случайными числами for i:=1 to N do for j:=1 to M do A[i,j] := random(25) - 10; for i:=1 to N do for j:=1 to M do A[i,j] := random(25) - 10; Какой интервал? ? цикл по строкам цикл по столбцам Вывод на экран for i:=1 to N do begin writeln; end; for i:=1 to N do begin writeln; end; перейти на новую строку for j:=1 to M do write ( A[i,j]:5 ); for j:=1 to M do write ( A[i,j]:5 ); вывод строки Если переставить циклы? ? в той же строке

78 Обработка всех элементов матрицы Задача: заполнить матрицу из 3 строк и 4 столбцов случайными числами и вывести ее на экран. Найти сумму элементов матрицы. program qq; const N = 3; M = 4; var A: array[1..N,1..M] of integer; i, j, S: integer; begin { заполнение матрицы и вывод на экран} S := 0; writeln('Сумма элементов матрицы ', S); end. program qq; const N = 3; M = 4; var A: array[1..N,1..M] of integer; i, j, S: integer; begin { заполнение матрицы и вывод на экран} S := 0; writeln('Сумма элементов матрицы ', S); end. for i:=1 to N do for j:=1 to M do S := S + A[i,j]; for i:=1 to N do for j:=1 to M do S := S + A[i,j];

79 Задания Заполнить матрицу из 8 строк и 5 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. «4»: Найти минимальный и максимальный элементы в матрице их номера. Формат вывода: Минимальный элемент A[3,4]=-6 Максимальный элемент A[2,2]=10 «5»: Вывести на экран строку, сумма элементов которой максимальна. Формат вывода: Строка 2:

80 Операции с матрицами Задача 1. Вывести на экран главную диагональ квадратной матрицы из N строк и N столбцов. A[1,N] A[2,2] A[3,3] A[N,N] for i:=1 to N do write ( A[i,i]:5 ); for i:=1 to N do write ( A[i,i]:5 ); Задача 2. Вывести на экран вторую диагональ. A[N,1] A[N-1,2] A[2,N-1] for i:=1 to N do write ( A[i, ]:5 ); for i:=1 to N do write ( A[i, ]:5 ); N+1-i сумма номеров строки и столбца N+1 A[1,1]

81 Операции с матрицами Задача 3. Найти сумму элементов, стоящих на главной диагонали и ниже ее. Одиночный цикл или вложенный? ? строка 1: A[1,1] строка 2: A[2,1]+A[2,2]... строка N: A[N,1]+A[N,2]+...+A[N,N] S := 0; for i:= 1 to N do S := 0; for i:= 1 to N do цикл по всем строкам for j:= 1 to i do S := S + A[i,j]; for j:= 1 to i do S := S + A[i,j]; складываем нужные элементы строки i

82 Операции с матрицами Задача 4. Перестановка строк или столбцов. В матрице из N строк и M столбцов переставить 2-ую и 4-ую строки j A[2,j] A[4,j] for j:=1 to M do begin c := A[2,j]; A[2,j] := A[4,j]; A[4,j] := c; end; for j:=1 to M do begin c := A[2,j]; A[2,j] := A[4,j]; A[4,j] := c; end; Задача 5. К третьему столбцу добавить шестой. for i:=1 to N do A[i,3] := A[i,3] + A[i,6]; for i:=1 to N do A[i,3] := A[i,3] + A[i,6];

83 Задания Заполнить матрицу из 7 строк и 7 столбцов случайными числами в интервале [-10,10] и вывести ее на экран. Обнулить элементы, отмеченные зеленым фоном, и вывести полученную матрицу на экран. «4»: «5»:

84 Программирование на языке Паскаль Часть II Тема 9. Файлы

85 Файлы Файл – это область на диске, имеющая имя. Файлы только текст без оформления, не содержат управляющих символов (с кодами < 32) ACSII (1 байт на символ) UNICODE (2 байта на символ) *.txt, *.log, *.htm, *.html могут содержать любые символы кодовой таблицы *.doc, *.exe, *.bmp, *.jpg, *.wav, *.mp3, *.avi, *.mpg ТекстовыеДвоичные Папки (каталоги)

86 Принцип сэндвича I этап. открыть файл : связать переменную f с файлом открыть файл (сделать его активным, приготовить к работе) assign(f, 'qq.txt'); reset(f); {для чтения} rewrite(f); {для записи} II этап: работа с файлом Переменная типа «текстовый файл»: var f: text; III этап: закрыть файл close(f); read ( f, n ); { ввести значение n } write ( f, n ); { записать значение n } writeln ( f, n );{c переходом на нов.строку } write ( f, n ); { записать значение n } writeln ( f, n );{c переходом на нов.строку }

87 Работа с файлами Особенности: имя файла упоминается только в команде assign, обращение к файлу идет через файловую переменную файл, который открывается на чтение, должен существовать если файл, который открывается на запись, существует, старое содержимое уничтожается данные записываются в файл в текстовом виде при завершении программы все файлы закрываются автоматически после закрытия файла переменную f можно использовать еще раз для работы с другим файлом

88 Последовательный доступ при открытии файла курсор устанавливается в начало чтение выполняется с той позиции, где стоит курсор после чтения курсор сдвигается на первый непрочитанный символ конец файла (end of file, EOF) конец файла (end of file, EOF) assign ( f, 'qq.txt' ); reset ( f ); assign ( f, 'qq.txt' ); reset ( f ); read ( f, x );

89 чтение до конца строки как вернуться назад? Последовательный доступ close ( f ); reset ( f ); { начать с начала } close ( f ); reset ( f ); { начать с начала } readln ( f, x ); ¤ 36 67¤ 56 конец строки (end of line, EOL) конец строки (end of line, EOL)

90 Пример Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно. Записать в файл output.txt их сумму. Алгоритм: 1.Открыть файл input.txt для чтения. 2.S := 0; 3.Если чисел не осталось, перейти к шагу 7. 4.Прочитать очередное число в переменную x. 5.S := S + x; 6.Перейти к шагу 3. 7.Закрыть файл input.txt. 8.Открыть файл output.txt для записи. 9.Записать в файл значение S. 10.Закрыть файл output.txt. Можно ли обойтись без массива? ? цикл с условием «пока есть данные»

91 Программа program qq; var s, x: integer; f: text; begin assign(f, 'input.txt'); reset(f); s := 0; close(f); end. program qq; var s, x: integer; f: text; begin assign(f, 'input.txt'); reset(f); s := 0; close(f); end. while not eof(f) do begin readln(f, x); s := s + x; end; while not eof(f) do begin readln(f, x); s := s + x; end; f: text; eof(f) логическая функция, возвращает True, если достигнут конец файла assign(f, 'output.txt'); rewrite(f); writeln(f, 'Сумма чисел ', s); close(f); assign(f, 'output.txt'); rewrite(f); writeln(f, 'Сумма чисел ', s); close(f); запись результата в файл output.txt

92 Задания В файле input.txt записаны числа, сколько их – неизвестно. «4»: Найти среднее арифметическое всех чисел и записать его в файл output.txt. «5»: Найти минимальное и максимальное числа и записать их в файл output.txt.

93 Обработка массивов Задача: в файле input.txt записаны числа (в столбик), сколько их – неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt. Проблемы: 1.для сортировки надо удерживать в памяти все числа сразу (массив); 2.сколько чисел – неизвестно. Решение: 1.выделяем в памяти массив из 100 элементов; 2.записываем прочитанные числа в массив и считаем их в переменной N ; 3.сортируем первые N элементов массива; 4.записываем их в файл. Можно ли обойтись без массива? ?

94 Чтение данных в массив var A: array[1..100] of integer; f: text; var A: array[1..100] of integer; f: text; function ReadArray: integer; var i: integer; begin assign(f, 'input.txt'); reset(f); i := 0; close(f); ReadArray := i; end; function ReadArray: integer; var i: integer; begin assign(f, 'input.txt'); reset(f); i := 0; close(f); ReadArray := i; end; Глобальные переменные: Функция: ввод массива, возвращает число элементов while (not eof(f)) and (i < 100) do begin i := i + 1; readln(f, A[i]); end; while (not eof(f)) and (i < 100) do begin i := i + 1; readln(f, A[i]); end; ReadArray := i; цикл заканчивается, если достигнут конец файла или прочитали 100 чисел

95 Программа program qq; var A: array[1..100] of integer; f: text; N, i: integer; Begin N := ReadArray; { сортировка первых N элементов } end. program qq; var A: array[1..100] of integer; f: text; N, i: integer; Begin N := ReadArray; { сортировка первых N элементов } end. function ReadArray: integer;... end; assign(f, 'output.txt'); rewrite(f); for i:=1 to N do writeln(f, A[i]); close(f); assign(f, 'output.txt'); rewrite(f); for i:=1 to N do writeln(f, A[i]); close(f); вывод отсортированного массива в файл

96 Задания В файле input.txt записаны числа (в столбик), известно, что их не более 100. «4»: Отсортировать массив по убыванию последней цифры и записать его в файл output.txt. «5»: Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.

97 Обработка текстовых данных Задача: в файле input.txt записаны строки, в которых есть слово-паразит «короче». Очистить текст от мусора и записать в файл output.txt. Файл input.txt : Мама, короче, мыла, короче, раму. Декан, короче, пропил, короче, бутан. А роза, короче, упала на лапу, короче, Азора. Каждый, короче, охотник желает, короче, знать, где... Результат - файл output.txt : Мама мыла раму. Декан пропил бутан. А роза упала на лапу Азора. Каждый охотник желает знать, где сидит фазан.

98 Обработка текстовых данных Алгоритм: 1. Прочитать строку из файла ( readln ). 2. Удалить все сочетания ", короче," ( Pos, Delete ). 3. Записать строку в другой файл. 4. Перейти к шагу 1. Обработка строки s : Особенность: надо одновременно держать открытыми два файла (один в режиме чтения, второй – в режиме записи). пока не кончились данные repeat i := Pos(', короче,', s); if i 0 then Delete(s, i, 9); until i = 0; repeat i := Pos(', короче,', s); if i 0 then Delete(s, i, 9); until i = 0; искать «, короче,» удалить 9 символов

99 Работа с двумя файлами одновременно program qq; var s: string; i: integer; fIn, fOut: text; begin assign(fIn, 'input.txt'); reset(fIn); assign(fOut, 'output.txt'); rewrite(fOut); { обработать файл } close(fIn); close(fOut); end. fIn, fOut: text; файловые переменные открыть файл для чтения открыть файл для записи

100 Полный цикл обработки файла while not eof(fIn) do begin readln(fIn, s); writeln(fOut, s); end; while not eof(fIn) do begin readln(fIn, s); writeln(fOut, s); end; repeat i := Pos(', короче,', s); if i 0 then Delete(s, i, 9); until i = 0; пока не достигнут конец файла обработка строки запись «очищенной» строки

101 Задания В файле input.txt записаны строки, сколько их – неизвестно. «4»: Заменить все слова «короче» на «в общем» и записать результат в файл output.txt. «5»: Вывести в файл output.txt только те строки, в которых больше 5 слов (слова могут быть разделены несколькими пробелами).

102 Конец фильма