К. Поляков, 2010 -2012 Программирование на алгоритмическом языке. Часть III 1.Обработка массивовОбработка массивов 2.Сортировка. - презентация

1 К. Поляков, Программирование на алгоритмическом языке. Часть III 1. Обработка массивов Обработка массивов 2. Сортировка массивов Сортировка массивов 3. Двоичный поиск Двоичный поиск 4. Символьные строки Символьные строки 5. Матрицы Матрицы 6.Файлы Файлы

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

3 Программирование на алгоритмическом языке. Часть II К. Поляков, Реверс массива Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять местами A[1] и A[N], A[2] и A[N-1], … Псевдокод: 35…97 79…53 12…N-1N 12… N нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц нц для i от 1 до N | поменять местами A[i] и A[N+1-i] кц сумма индексов N+1 Что неверно? ? div(N,2)

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

5 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа алг Реверс нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон алг Реверс нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон нц для i от 1 до div(N,2) c:= A[i] A[i]:= A[N+1-i] A[N+1-i]:= c; кц нц для i от 1 до div(N,2) c:= A[i] A[i]:= A[N+1-i] A[N+1-i]:= c; кц

6 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс всех элементов, кроме первого. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [ ] и сделать реверс отдельно для 1-ой и 2-ой половин массива. Пример: Исходный массив: Результат:

7 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «5»: Заполнить массив из 12 элементов случайными числами в интервале [ ] и выполнить реверс для каждой трети массива. Пример: Исходный массив: Результат:

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

9 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа алг Циклический сдвиг влево нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон алг Циклический сдвиг влево нач цел i, c, N = 10 целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести результат кон c:= A[1] нц для i от 1 до N-1 A[i]:= A[i+1] кц A[N]:= c; c:= A[1] нц для i от 1 до N-1 A[i]:= A[i+1] кц A[N]:= c;

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

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

12 Программирование на алгоритмическом языке. Часть II К. Поляков, Выбор нужных элементов Задача – найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив. Примитивное решение: цел i, N = 5 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i] < 0 то B[i]:= A[i] все кц цел i, N = 5 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i] < 0 то B[i]:= A[i] все кц ? ? ? ? ? A B Что плохо? ?

13 Программирование на алгоритмическом языке. Часть II К. Поляков, Выбор нужных элементов 13 Решение: ввести счетчик найденных элементов count, очередной элемент ставится на место B[count]. цел i, N = 5, count = 0 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i]< 0 то count:= count + 1 B[ ]:= A[i] все кц цел i, N = 5, count = 0 целтаб A[1:N], B[1:N] | здесь заполнить массив A нц для i от 1 до N если A[i]< 0 то count:= count + 1 B[ ]:= A[i] все кц ? ? ? ? ? A B count

14 Программирование на алгоритмическом языке. Часть II К. Поляков, Как вывести массив B? Примитивное решение: вывод "Выбранные элементы:", нс нц для i от 1 до N вывод B[i], " " кц вывод "Выбранные элементы:", нс нц для i от 1 до N вывод B[i], " " кц Что плохо? ? Правильное решение: вывод "Выбранные элементы:", нс нц для i от 1 до вывод B[i], " " кц вывод "Выбранные элементы:", нс нц для i от 1 до вывод B[i], " " кц count

15 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «3»: Заполнить массив случайными числами в интервале [-10,10] и записать в другой массив все положительные числа. Пример: Исходный массив: Положительные числа: 3 7 «4»: Заполнить массив случайными числами в интервале [20,100] и записать в другой массив все числа, которые оканчиваются на 0. Пример: Исходный массив: Заканчиваются на 0: 40 30

16 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания «5»: Заполнить массив случайными числами и выделить в другой массив все числа, которые встречаются более одного раза. Пример: Исходный массив: Результат: 1 2

17 К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 2. Сортировка массивов

18 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …). Задача: переставить элементы массива в порядке возрастания. Алгоритмы сортировки: 1)простые и понятные, но медленно работающие для больших массивов метод пузырька метод выбора 2)сложные, но быстрые («быстрая сортировка» и др.) сложность O(N 2 ) время N 1 2

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

20 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа 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-ой проход нц для j от N-1 до 2 шаг -1 если A[j] > A[j+1] то c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c все кц нц для j от N-1 до 2 шаг -1 если A[j] > A[j+1] то c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c все кц 2 нц для j от N-1 до 1 шаг -1 если A[j] > A[j+1] то c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c все кц нц для j от N-1 до 1 шаг -1 если A[j] > A[j+1] то c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c все кц 1 i -ый проход нц для j от N-1 до i шаг нц для j от N-1 до i шаг i 1 5 … … N-1 N A[1] уже на своем месте! !

21 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа алг Сортировка нач цел N = 5, i, j, c целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести полученный массив кон алг Сортировка нач цел N = 5, i, j, c целтаб A[1:N] | здесь нужно заполнить массив | здесь нужно вывести полученный массив кон нц для i от 1 до N-1 нц для j от N-1 до i шаг -1 если A[j] > A[j+1] то c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c все кц нц для i от 1 до N-1 нц для j от N-1 до i шаг -1 если A[j] > A[j+1] то c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c все кц Почему цикл по i до N-1 ? ? i элементы выше A[i] уже поставлены

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

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

24 Программирование на алгоритмическом языке. Часть II К. Поляков, Метод выбора 24 Идея: найти минимальный элемент и поставить на первое место (поменять местами с A[1] ) из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2] ), и т.д

25 Программирование на алгоритмическом языке. Часть II К. Поляков, Метод выбора нц для i от 1 до N-1 nMin:= i нц для j от i+1 до N если A[j] < A[nMin] то nMin:= j все кц если nMin i то c:= A[i] A[i]:= A[nMin] A[nMin]:= c все кц N-1 N нужно N-1 проходов поиск минимального от A[i] до A[N] если нужно, переставляем Можно ли убрать если ? ? i+1 i

26 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 26 «3»: Заполнить массив из 10 элементов случайными числами в интервале [0..99] и отсортировать его по убыванию последней цифры. Пример: Исходный массив: Результат: «4»: Заполнить массив из 10 элементов случайными числами в интервале [0..99] и отсортировать его по возрастанию суммы цифр ( подсказка: их всего две ). Пример: Исходный массив: Результат:

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

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

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

30 Программирование на алгоритмическом языке. Часть II К. Поляков, «Быстрая сортировка» (Quick Sort) LR LR LR RL L > R : разделение закончено !

31 Программирование на алгоритмическом языке. Часть II К. Поляков, «Быстрая сортировка» (Quick Sort) алг qSort(аргрез целтаб A[1:5], арг цел iStart, iEnd) нач цел L, R, c, X если iStart >= iEnd то выход все L:= iStart; R:= iEnd; X:= A[div(L+R,2)] qSort(A, iStart, R) qSort(A, L, iEnd) кон алг qSort(аргрез целтаб A[1:5], арг цел iStart, iEnd) нач цел L, R, c, X если iStart >= iEnd то выход все L:= iStart; R:= iEnd; X:= A[div(L+R,2)] qSort(A, iStart, R) qSort(A, L, iEnd) кон ограничение рекурсии сортируем две части: рекурсия! сортируем две части: рекурсия! нц пока L X; R:= R-1 кц кц нц пока L X; R:= R-1 кц кц если L

32 Программирование на алгоритмическом языке. Часть II К. Поляков, «Быстрая сортировка» (Quick Sort) 32 алг Сортировка Quick Sort нач цел N = 5, i целтаб A[1:N] | заполнить массив и вывести на экран qSort(A, 1, N) | сортировка | вывести отсортированный массив кон алг Сортировка Quick Sort нач цел N = 5, i целтаб A[1:N] | заполнить массив и вывести на экран qSort(A, 1, N) | сортировка | вывести отсортированный массив кон алг qSort(аргрез целтаб A[1:5], арг цел iStart, iEnd) нач... кон алг qSort(аргрез целтаб A[1:5], арг цел iStart, iEnd) нач... кон цел N, аргрез целтаб A[1:N] Вызов: qSort(N, A, 1, N) для массивов любого размера

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

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

35 К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 3. Двоичный поиск

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

37 Программирование на алгоритмическом языке. Часть II К. Поляков, Линейный поиск 37 i:= 1 нц пока A[i] X i:= i + 1 кц если i

38 Программирование на алгоритмическом языке. Часть II К. Поляков, Двоичный поиск 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], искать дальше во второй половине.

= L c:= div(R+L, 2); если X < A[c]" title="Программирование на алгоритмическом языке. Часть II К. Поляков, 2010-2012 http://kpolyakov.narod.ru Двоичный поиск 39 L:= 1; R:= N; nX:= 0 если nX > 0 то вывод "A[", nX, "]=", X иначе вывод "Не нашли" все нц пока R >= L c:= div(R+L, 2); если X < A[c]" class="link_thumb"> 39 Программирование на алгоритмическом языке. Часть II К. Поляков, Двоичный поиск 39 L:= 1; R:= N; nX:= 0 если nX > 0 то вывод "A[", nX, "]=", X иначе вывод "Не нашли" все нц пока R >= L c:= div(R+L, 2); если X < A[c] то R:= c – 1 все если X > A[c] то L:= c + 1 все кц номер среднего элемента если X = A[c] то nX:= c; выход все если X = A[c] то nX:= c; выход все нашли Почему нельзя нц пока R > L … кц ? ? выйти из цикла сдвигаем границы 1LcRN = L c:= div(R+L, 2); если X < A[c]"> = L c:= div(R+L, 2); если X < A[c] то R:= c – 1 все если X > A[c] то L:= c + 1 все кц номер среднего элемента если X = A[c] то nX:= c; выход все если X = A[c] то nX:= c; выход все нашли Почему нельзя нц пока R > L … кц ? ? выйти из цикла сдвигаем границы 1LcRN"> = L c:= div(R+L, 2); если X < A[c]" title="Программирование на алгоритмическом языке. Часть II К. Поляков, 2010-2012 http://kpolyakov.narod.ru Двоичный поиск 39 L:= 1; R:= N; nX:= 0 если nX > 0 то вывод "A[", nX, "]=", X иначе вывод "Не нашли" все нц пока R >= L c:= div(R+L, 2); если X < A[c]">

40 Программирование на алгоритмическом языке. Часть II К. Поляков, Сравнение методов поиска 40 Линейный Двоичный подготовканетотсортировать число шагов N = 2N = 222 N = N = N = N N log 2 N + 1

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

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

43 Программирование на алгоритмическом языке. Часть II К. Поляков, Задачи на обработку строк 43 Задача: с клавиатуры вводится число N, обозначающее количество футболистов команды «Шайба», а затем – N строк, в каждой из которых – информация об одном футболисте таком формате: Все данные разделяются одним пробелом. Нужно подсчитать, сколько футболистов, родившихся в период с 1988 по 1990 год, не забили мячей вообще. Алгоритм (для каждой строки): 1)выделить год ( year ) и количество голов ( goal ) 2)если 1988

44 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа 44 использовать Строки алг Футболисты нач цел N, i, p, year, goal, count=0 лит s ввод N нц для i от 1 до N ввод s | разобрать строку, выделить год и голы если year >= 1988 и year = 1988 и year

45 Программирование на алгоритмическом языке. Часть II К. Поляков, Разбор строки 45 Пропуск фамилии: p:= найти(" ", s) s:= s[p+1:длин(s)] p:= найти(" ", s) s:= s[p+1:длин(s)] Пропуск имени: Ввод года рождения: p:= найти(" ", s) year:= лит_в_цел(s[1:p-1],OK) s:= s[p+1:длин(s)] p:= найти(" ", s) year:= лит_в_цел(s[1:p-1],OK) s:= s[p+1:длин(s)] Ввод числа голов: Иванов Вася p Вася p:= найти(" ", s) s:= s[p+1:длин(s)] p:= найти(" ", s) s:= s[p+1:длин(s)] Вася p p 5 goal:= лит_в_цел(s,OK) лог OK

46 Программирование на алгоритмическом языке. Часть II К. Поляков, Разбор строки 46 Если фамилия нужна: p:= найти(" ", s) fam:= s[1:p-1] s:= s[p+1:длин(s)] p:= найти(" ", s) fam:= s[1:p-1] s:= s[p+1:длин(s)] лит fam Иванов Вася p Иванов Вася Если нужны ВСЕ фамилии: p:= найти(" ", s) fam[i]:= s[1:p-1] s:= s[p+1:длин(s)] p:= найти(" ", s) fam[i]:= s[1:p-1] s:= s[p+1:длин(s)] литтаб fam[1:N]

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

48 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 48 «5»: Вывести в алфавитном порядке фамилии и имена всех футболистов, которые забили хотя бы один гол. В списке не более 100 футболистов. Пример: Васильев Иван Иванов Василий Кутузов Михаил Пупкин Василий

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

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

51 Программирование на алгоритмическом языке. Часть II К. Поляков, Процедура 51 алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон ???? 1K p s p+1 рекурсивные вызовы А если букв много? ? Глобальные переменные: лит s цел count, K если p > K то вывод s, нс count:= count + 1 выход все если p > K то вывод s, нс count:= count + 1 выход все s[p]:= "Ы"; Рек(p+1) s[p]:= "Ц"; Рек(p+1) s[p]:= "Щ"; Рек(p+1) s[p]:= "О"; Рек(p+1) s[p]:= "Ы"; Рек(p+1) s[p]:= "Ц"; Рек(p+1) s[p]:= "Щ"; Рек(p+1) s[p]:= "О"; Рек(p+1) окончание рекурсии

52 Программирование на алгоритмическом языке. Часть II К. Поляков, Основная программа 52 лит s, цел count = 0, K алг Рекурсивный перебор нач вывод "Введите длину слов: " ввод K s:= "" нц K раз s:= s + " " кц Рек(1) вывод "Всего ", count, " слов" кон лит s, цел count = 0, K алг Рекурсивный перебор нач вывод "Введите длину слов: " ввод K s:= "" нц K раз s:= s + " " кц Рек(1) вывод "Всего ", count, " слов" кон s:= "" нц K раз s:= s + " " кц строка из K пробелов глобальные переменные алг Рек(цел p) нач... кон алг Рек(цел p) нач... кон

53 Программирование на алгоритмическом языке. Часть II К. Поляков, Процедура (много букв) 53 алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон алг Рек(цел p) нач если p > K то вывод s, нс count:= count + 1 выход все кон лит syms="ЫЦЩО", цел i нц для i от 1 до длин(syms) s[p]:= syms[i]; Рек(p+1) кц нц для i от 1 до длин(syms) s[p]:= syms[i]; Рек(p+1) кц локальные переменные все буквы цикл по всем буквам

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

55 К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 5. Матрицы

56 Программирование на алгоритмическом языке. Часть II К. Поляков, Операции с матрицами 56 Задача 1. Вывести на экран главную диагональ квадратной матрицы из N строк и N столбцов. A[1,N] A[2,2] A[3,3] A[N,N] нц для i от 1 до N вывод A[i,i], " " кц нц для i от 1 до N вывод A[i,i], " " кц Задача 2. Вывести на экран вторую диагональ. A[N,1] A[N-1,2] A[2,N-1] нц для i от 1 до N вывод A[i, ], " " кц нц для i от 1 до N вывод A[i, ], " " кц N+1-i сумма номеров строки и столбца N+1 A[1,1] А снизу вверх? ?

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

58 Программирование на алгоритмическом языке. Часть II К. Поляков, Операции с матрицами 58 Задача 4. Перестановка строк или столбцов. В матрице из N строк и M столбцов переставить 2-ую и 4-ую строки j A[2,j] A[4,j] нц для j от 1 до M c:= A[2,j] A[2,j]:= A[4,j] A[4,j]:= c кц нц для j от 1 до M c:= A[2,j] A[2,j]:= A[4,j] A[4,j]:= c кц Задача 5. К третьему столбцу добавить шестой. нц для i от 1 до N A[i,3]:= A[i,3] + A[i,6] кц нц для i от 1 до N A[i,3]:= A[i,3] + A[i,6] кц

59 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания Заполнить матрицу из 7 строк и 7 столбцов случайными числами в интервале [10,90] и вывести ее на экран. Заполнить элементы, отмеченные зеленым фоном, числами 99, и вывести полученную матрицу на экран. «3»: «4»: «5»:

60 К. Поляков, Программирование на алгоритмическом языке. Часть II Тема 6. Файлы

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

62 Программирование на алгоритмическом языке. Часть II К. Поляков, Работа с файлами: принцип сэндвича 62 I этап. открыть файл: сделать его активным, приготовить к работе связать переменную F с файлом F:= открыть на чтение("in.txt") II этап: работа с файлом цел F III этап: закрыть файл закрыть(F) Фввод F, a, b | ввести a и b F:= открыть на запись("out.txt") Фвывод F, a, b, нс | вывести a и b

63 Программирование на алгоритмическом языке. Часть II К. Поляков, Работа с файлами 63 Особенности: имя файла упоминается только при открытии файла, работа с файлом – через файловую переменную файл, который открывается на чтение, должен существовать если файл, который открывается на запись, существует, старое содержимое уничтожается данные записываются в файл в текстовом виде при завершении программы все файлы закрываются автоматически после закрытия файла переменную F можно использовать еще раз для работы с другим файлом

64 Программирование на алгоритмическом языке. Часть II К. Поляков, Последовательный доступ 64 при открытии файла курсор устанавливается в начало чтение выполняется с той позиции, где стоит курсор после чтения курсор сдвигается на первый непрочитанный символ F:= открыть на чтение("qq.txt") Фввод F, x конец файла

65 Программирование на алгоритмическом языке. Часть II К. Поляков, Последовательный доступ 65 как вернуться назад и начать с начала? не открывая файл заново начать чтение ( F ) закрыть ( F ) F:= открыть на чтение ( "qq.txt" ) закрыть ( F ) F:= открыть на чтение ( "qq.txt" )

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

67 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа: чтение данных из файла 67 использовать Файлы П алг Сумма чисел нач цел F, S, x F:= открыть на чтение("input.txt") S:= 0 нц пока не конец файла( F ) Фввод F, x S:= S + x кц закрыть( F ) | здесь нужно записать результат в файл кон использовать Файлы П алг Сумма чисел нач цел F, S, x F:= открыть на чтение("input.txt") S:= 0 нц пока не конец файла( F ) Фввод F, x S:= S + x кц закрыть( F ) | здесь нужно записать результат в файл кон логическая функция, возвращает да, если достигнут конец файла

68 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа: запись результата в файл 68 F:= открыть на запись("output.txt") Фвывод F, S закрыть( F ) F:= открыть на запись("output.txt") Фвывод F, S закрыть( F ) Особенности: файл, который открывается на запись, не обязательно должен существовать старое содержимое файла уничтожается

69 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 69 В файле input.txt записаны числа, сколько их – неизвестно. «3»: Найти сумму всех чётных чисел и записать её в файл output.txt. «4»: Найти минимальное и максимальное из всех чисел и записать их в файл output.txt. «5»: Найти длину самой длинной цепочки одинаковых чисел, идущих подряд, и записать её в файл output.txt.

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

71 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа: чтение данных в массив 71 использовать Файлы П алг Сортировка нач цел F, MAX = 100, N = 0, i, j, c целтаб A[1:MAX] F:= открыть на чтение("input.txt") нц пока не конец файла(F) и N < MAX N:= N + 1 Фввод F, A[N] кц закрыть(F) | отсортировать первые N элементов | вывести полученный массив кон использовать Файлы П алг Сортировка нач цел F, MAX = 100, N = 0, i, j, c целтаб A[1:MAX] F:= открыть на чтение("input.txt") нц пока не конец файла(F) и N < MAX N:= N + 1 Фввод F, A[N] кц закрыть(F) | отсортировать первые N элементов | вывести полученный массив кон цикл заканчивается, если достигнут конец файла или прочитали 100 чисел

72 Программирование на алгоритмическом языке. Часть II К. Поляков, Программа: вывод массива в файл 72 F:= открыть на запись("output.txt") нц для i от 1 до N Фвывод F, A[i], нс кц закрыть(F) F:= открыть на запись("output.txt") нц для i от 1 до N Фвывод F, A[i], нс кц закрыть(F) зачем?

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

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

75 Программирование на алгоритмическом языке. Часть II К. Поляков, Обработка текстовых данных 75 Алгоритм: 1. Прочитать строку из файла. 2. Удалить все сочетания ", короче,". 3. Записать строку в другой файл. 4. Перейти к шагу 1. Особенность: надо одновременно держать открытыми два файла: один в режиме чтения, второй – в режиме записи. пока не кончились данные

76 Программирование на алгоритмическом языке. Часть II К. Поляков, Работа с двумя файлами одновременно 76 использовать Строки использовать Файлы П алг Обработка строк нач цел fIn, fOut fIn:= открыть на чтение("input.txt") fOut:= открыть на запись("output.txt") | обработка файла закрыть(fIn) закрыть(fOut) кон использовать Строки использовать Файлы П алг Обработка строк нач цел fIn, fOut fIn:= открыть на чтение("input.txt") fOut:= открыть на запись("output.txt") | обработка файла закрыть(fIn) закрыть(fOut) кон

77 Программирование на алгоритмическом языке. Часть II К. Поляков, Цикл обработки файла 77 нц пока не конец файла(fIn) Фввод fIn, s | обработка строки s Фвывод fOut, s, нс кц нц пока не конец файла(fIn) Фввод fIn, s | обработка строки s Фвывод fOut, s, нс кц Оба файла открыты одновременно! !

78 Программирование на алгоритмическом языке. Часть II К. Поляков, Обработка одной строки 78 нц пока да p:= найти(", короче,", s) если p < 1 то выход все s:= s[1:p-1] + s[p+9:длин(s)] кц нц пока да p:= найти(", короче,", s) если p < 1 то выход все s:= s[1:p-1] + s[p+9:длин(s)] кц бесконечный цикл выход из цикла удалить 9 символов, короче, s pp+91 длин(s)

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

80 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 80 Задача: в файле list.txt записаны фамилии и имена пользователей сайта (не более 100). Вывести их в алфавитном порядке в файл sort.txt. Файл list.txt : Федоров Иван Иванов Федор Анисимов Никита Никитин Николай Результат – файл sort.txt : Анисимов Никита Иванов Федор Никитин Николай Федоров Иван Нужен ли массив! ? Для сортировки нужен массив! !

81 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 81 Алгоритм: 1)прочитать строки из файла в массив строк, подсчитать их в переменной N 2)отсортировать первые N строк массива по алфавиту 3)вывести первые N строк массива в файл Объявление массива (с запасом): цел MAX = 100 литтаб s[1:MAX] цел MAX = 100 литтаб s[1:MAX]

82 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 82 Ввод массива строк из файла: f:= открыть на чтение("list.txt") N:= 0 нц пока не конец файла(f) N:= N + 1 Фввод f, s[N] кц закрыть(f) f:= открыть на чтение("list.txt") N:= 0 нц пока не конец файла(f) N:= N + 1 Фввод f, s[N] кц закрыть(f) цел f, N Вывод первых N строк массива в файл: f:= открыть на запись("sort.txt") нц для i от 1 до N Фвывод f, s[i], нс кц закрыть(f) f:= открыть на запись("sort.txt") нц для i от 1 до N Фвывод f, s[i], нс кц закрыть(f)

83 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 83 Сортировка первых N элементов массива: нц для i от 1 до N-1 nMin:= i нц для j от i+1 до N если s[j] < s[nMin] то nMin:= j все кц если i nMin то c:= s[i] s[i]:= s[nMin] s[nMin]:= c все кц нц для i от 1 до N-1 nMin:= i нц для j от i+1 до N если s[j] < s[nMin] то nMin:= j все кц если i nMin то c:= s[i] s[i]:= s[nMin] s[nMin]:= c все кц цел i, j, nMin лит c цел i, j, nMin лит c Какой метод? ?

84 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 84 Как сравниваются строки: Парохо д¤ Паровоз ¤ || ? s1 s2s2 Кодовая таблица: АБВ…Яабв…х…я … …245… … …1093…1103 Win UNICODE код("х") > код("в") "х" > "в" "Пароход" > "Паровоз" Что больше? ? код("в") "х" > "в" "Пароход" > "Паровоз" Что больше? ?">

85 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 85 Как сравниваются строки: Парохо д¤ Пар ¤ || ? s1 s2s2 "х" > ¤"х" > ¤ "Пароход" > "Пар" Любой символ больше пустого! ! ¤"х" > ¤ "Пароход" > "Пар" Любой символ больше пустого! !">

86 Программирование на алгоритмическом языке. Часть II К. Поляков, Сортировка списков 86 Работа с отдельной строкой массива: литтаб s[1:MAX] лит c | вспомогательная строка нц для i от 1 до N с:= s[i] | работаем со строкой c, меняем ее s[i]:= c кц литтаб s[1:MAX] лит c | вспомогательная строка нц для i от 1 до N с:= s[i] | работаем со строкой c, меняем ее s[i]:= c кц

87 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 87 «3»: Добавить к списку нумерацию: 1) Анисимов Никита 2) Иванов Федор «4»: Выполнить задачу на «3» и сократить имя до первой буквы: 1) Анисимов Н. 2) Иванов Ф. «5»: Выполнить задачу на «4», но при выводе начинать с имени: 1) Н. Анисимов 2) Ф. Иванов

88 Программирование на алгоритмическом языке. Часть II К. Поляков, Списки с числовыми данными 88 Задача: в файле marks.txt записаны фамилии и имена школьников и баллы, полученные ими на экзамене (0-100). В файле не более 100 строк. Вывести в файл best.txt список тех, кто получил более 75 баллов. Файл marks.txt : Федоров Иван 78 Иванов Федор 63 Анисимов Никита 90 Никитин Николай 55 Результат – файл best.txt : Федоров Иван 78 Анисимов Никита 90 Нужен ли массив! ? Используем два файла одновременно! !

89 Программирование на алгоритмическом языке. Часть II К. Поляков, Работа с двумя файлами одновременно 89 использовать Файлы П использовать Строки алг Отметки на экзамене нач цел fIn, fOut fIn:= открыть на чтение("marks.txt") fOut:= открыть на запись("best.txt") | обработка строк из файла закрыть(fIn) закрыть(fOut) кон использовать Файлы П использовать Строки алг Отметки на экзамене нач цел fIn, fOut fIn:= открыть на чтение("marks.txt") fOut:= открыть на запись("best.txt") | обработка строк из файла закрыть(fIn) закрыть(fOut) кон

90 Программирование на алгоритмическом языке. Часть II К. Поляков, Цикл обработки файла 90 цел ball нц пока не конец файла(fIn) Фввод fIn, s | обработка строки s | ball:= результат на экзамене если ball > 75 то Фвывод fOut, s, нс все кц цел ball нц пока не конец файла(fIn) Фввод fIn, s | обработка строки s | ball:= результат на экзамене если ball > 75 то Фвывод fOut, s, нс все кц Оба файла открыты одновременно! !

91 Программирование на алгоритмическом языке. Часть II К. Поляков, Преобразования «строка»-«число» 91 Из строки в число: s:= "123" N:= лит_в_цел(s, OK) | N = 123 если не OK то вывод "Ошибка!" все s:= " "; X:= лит_в_вещ(s, OK) | X = если не OK то вывод "Ошибка!" все s:= "123" N:= лит_в_цел(s, OK) | N = 123 если не OK то вывод "Ошибка!" все s:= " "; X:= лит_в_вещ(s, OK) | X = если не OK то вывод "Ошибка!" все Из числа в строку: N:= 123 s:= цел_в_лит(N) | "123" X:= s:= вещ_в_лит(X) | " " N:= 123 s:= цел_в_лит(N) | "123" X:= s:= вещ_в_лит(X) | " " цел N, вещ X, лит s, лог OK да или нет

92 Программирование на алгоритмическом языке. Часть II К. Поляков, Обработка строки 92 n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1] | фамилия:= "Пупкин" s:= удалить(s, 1, n) | s:= "Вася 82" n:= найти(" ", s) | n:= 5 имя:= s[1:n-1] | имя:= "Вася" s:= удалить(s, 1, n) | s:= "82" ball:= лит_в_цел(s, OK) | ball:= 82 n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1] | фамилия:= "Пупкин" s:= удалить(s, 1, n) | s:= "Вася 82" n:= найти(" ", s) | n:= 5 имя:= s[1:n-1] | имя:= "Вася" s:= удалить(s, 1, n) | s:= "82" ball:= лит_в_цел(s, OK) | ball:= 82 цел n лит s, фамилия, имя лог ОK цел n лит s, фамилия, имя лог ОK Пупкин Вася 82 s: n 1 n 1

93 Программирование на алгоритмическом языке. Часть II К. Поляков, Обработка строки 93 n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1] | фамилия:= "Пупкин" s:= удалить(s, 1, n) | s:= "Вася 82" n:= найти(" ", s) | n:= 5 имя:= s[1:n-1] | имя:= "Вася" s:= удалить(s, 1, n) | s:= "82" ball:= лит_в_цел(s, OK) | ball:= 82 если ball > 75 то Фвывод fOut, s, нс все n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1] | фамилия:= "Пупкин" s:= удалить(s, 1, n) | s:= "Вася 82" n:= найти(" ", s) | n:= 5 имя:= s[1:n-1] | имя:= "Вася" s:= удалить(s, 1, n) | s:= "82" ball:= лит_в_цел(s, OK) | ball:= 82 если ball > 75 то Фвывод fOut, s, нс все Что плохо? ? 75 то Фвывод fOut, s, нс все n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1] | фамилия:= "Пупкин" s:= удалить(s, 1, n) | s:= "Вася 82" n:= найти(" ", s) | n:= 5 имя:= s[1:n-1] | имя:= "Вася" s:= удалить(s, 1, n) | s:= "82" ball:= лит_в_цел(s, OK) | ball:= 82 если ball > 75 то Фвывод fOut, s, нс все Что плохо? ?">

94 Программирование на алгоритмическом языке. Часть II К. Поляков, Задания 94 «3»: Добавить к списку нумерацию: 1) Федоров Иван 78 2) Анисимов Никита 90 «4»: Выполнить задачу на «3» и сократить имя до первой буквы: 1) Федоров И. 78 2) Анисимов Н. 90 «5»: Выполнить задачу на «4», но отсортировать список по алфавиту. 1) Анисимов Н. 90 2) Федоров И. 78 «6»: Выполнить задачу на «4», но отсортировать список по убыванию отметки (балла).

95 Программирование на алгоритмическом языке. Часть II К. Поляков, Конец фильма 95 ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ 163, г. Санкт-Петербург