Программирование на алгоритмическом языке. Часть III (9 класс)

Содержание

Слайд 2

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

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

Тема 1. Обработка массивов

Слайд 3

Реверс массива Задача: переставить элементы массива в обратном порядке. Алгоритм: поменять

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

Задача: переставить элементы массива в обратном порядке.
Алгоритм:
поменять местами A[1] и

A[N], A[2] и A[N-1], …
Псевдокод:

нц для i от 1 до N
| поменять местами A[i] и A[N+1-i]
кц

сумма индексов N+1

div(N,2)

Слайд 4

Как переставить элементы? 2 3 1 Задача: поменять местами содержимое двух

Как переставить элементы?

2

3

1

Задача: поменять местами содержимое двух чашек.

Задача: поменять местами содержимое

двух ячеек памяти.

4

6

?

4

6

4

x

y

c

c:= x
x:= y
y:= c

x:= y
y:= x

3

2

1

Слайд 5

Программа алг Реверс нач цел i, c, N = 10 целтаб

Программа

алг Реверс
нач
цел 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;
кц

Слайд 6

Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«3»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10]

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

Задания «5»: Заполнить массив из 12 элементов случайными числами в интервале

Задания

«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12]

и выполнить реверс для каждой трети массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
10 3 -5 4 -10 8 -6 -4 7 5 0 1
Слайд 8

Циклический сдвиг Задача: сдвинуть элементы массива влево на 1 ячейку, первый

Циклический сдвиг

Задача: сдвинуть элементы массива влево на 1 ячейку, первый элемент

становится на место последнего.
Алгоритм:
A[1]:=A[2]; A[2]:=A[3];… A[N-1]:=A[N];

нц для i от 1 до N-1
A[i]:= A[i+1]
кц

почему не N?

Слайд 9

Программа алг Циклический сдвиг влево нач цел i, c, N =

Программа

алг Циклический сдвиг влево
нач
цел i, c, N = 10
целтаб

A[1:N]
| здесь нужно заполнить массив
| здесь нужно вывести результат
кон

c:= A[1]
нц для i от 1 до N-1
A[i]:= A[i+1]
кц
A[N]:= c;

Слайд 10

Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«3»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10]

и выполнить циклический сдвиг влево без первого элемента.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
4 0 -5 3 10 -4 -6 8 -10 1
«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг ВПРАВО.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
0 4 -5 3 10 -4 -6 8 -10 1
Слайд 11

Задания «5»: Заполнить массив из 12 элементов случайными числами в интервале

Задания

«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12]

и выполнить циклический сдвиг ВПРАВО на 4 элемента.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
1 0 5 7 4 -5 3 10 -4 -6 8 -10
Слайд 12

Выбор нужных элементов Задача – найти в массиве элементы, удовлетворяющие некоторому

Выбор нужных элементов

Задача – найти в массиве элементы, удовлетворяющие некоторому условию

(например, отрицательные), и скопировать их в другой массив.

Примитивное решение:

цел i, N = 5
целтаб A[1:N], B[1:N]
| здесь заполнить массив A
нц для i от 1 до N
если A[i] < 0 то
B[i]:= A[i]
все
кц

A

B

Слайд 13

Выбор нужных элементов Решение: ввести счетчик найденных элементов count, очередной элемент

Выбор нужных элементов

Решение: ввести счетчик найденных элементов 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]
все
кц

A

B

count

Слайд 14

Как вывести массив B? Примитивное решение: вывод "Выбранные элементы:", нс нц

Как вывести массив B?

Примитивное решение:

вывод "Выбранные элементы:", нс
нц для i от

1 до N
вывод B[i], " "
кц

Правильное решение:

вывод "Выбранные элементы:", нс
нц для i от 1 до
вывод B[i], " "
кц

count

Слайд 15

Задания «3»: Заполнить массив случайными числами в интервале [-10,10] и записать

Задания

«3»: Заполнить массив случайными числами в интервале [-10,10] и записать в

другой массив все положительные числа.
Пример:
Исходный массив:
0 -5 3 7 -8
Положительные числа:
3 7
«4»: Заполнить массив случайными числами в интервале [20,100] и записать в другой массив все числа, которые оканчиваются на 0.
Пример:
Исходный массив:
40 57 30 71 84
Заканчиваются на 0:
40 30
Слайд 16

Задания «5»: Заполнить массив случайными числами и выделить в другой массив

Задания

«5»: Заполнить массив случайными числами и выделить в другой массив все

числа, которые встречаются более одного раза.
Пример:
Исходный массив:
4 1 2 1 11 2 34
Результат:
1 2
Слайд 17

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

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

Тема 2. Сортировка массивов

Слайд 18

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

Сортировка

Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию,

убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы массива в порядке возрастания.
Алгоритмы сортировки:
простые и понятные, но медленно работающие для больших массивов
метод пузырька
метод выбора
сложные, но быстрые («быстрая сортировка» и др.)

сложность O(N2)

Слайд 19

Метод пузырька Идея – пузырек воздуха в стакане воды поднимается со

Метод пузырька

Идея – пузырек воздуха в стакане воды поднимается со дна

вверх.
Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

Слайд 20

Программа 1-ый проход: сравниваются пары A[N-1] и A[N], A[N-2] и A[N-1],

Программа

1-ый проход:

сравниваются пары
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
все
кц

2

нц для 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 шаг -1
...

i

Слайд 21

Программа алг Сортировка нач цел N = 5, i, j, c

Программа

алг Сортировка
нач
цел 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

элементы выше A[i] уже поставлены

Слайд 22

Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«3»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10]

и отсортировать его по убыванию.
Пример:
Исходный массив:
4 5 -8 3 -7 -5 3 1 0 9
Результат:
9 5 4 3 3 1 0 -5 -7 -8
«4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
30 11 41 32 13 14 25 76 97 58
Слайд 23

Задания «5»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100]

и отсортировать первую половину по возрастанию, а вторую – по убыванию.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
13 14 25 30 76 97 58 41 32 11
Слайд 24

Метод выбора Идея: найти минимальный элемент и поставить на первое место

Метод выбора

Идея:
найти минимальный элемент и поставить на первое место (поменять местами

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

Метод выбора нц для i от 1 до N-1 nMin:= i

Метод выбора

нц для 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

Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«3»: Заполнить массив из 10 элементов случайными числами в интервале [0..99]

и отсортировать его по убыванию последней цифры.
Пример:
Исходный массив:
14 25 13 12 76 58 21 87 10 98
Результат:
98 58 87 76 25 14 13 12 21 10
«4»: Заполнить массив из 10 элементов случайными числами в интервале [0..99] и отсортировать его по возрастанию суммы цифр (подсказка: их всего две).
Пример:
Исходный массив:
14 25 13 12 76 58 21 87 10 98
Результат:
10 21 12 13 14 25 76 58 87 98
Слайд 27

Задания «5»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100]

и отсортировать первую половину по возрастанию, а вторую – по убыванию.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
13 14 25 30 76 97 58 41 32 11
Слайд 28

«Быстрая сортировка» (Quick Sort) Идея – более эффективно переставлять элементы, расположенные

«Быстрая сортировка» (Quick Sort)

Идея – более эффективно переставлять элементы, расположенные дальше

друг от друга.

div(N,2)

2 шаг: переставить элементы так:
при сортировке элементы не покидают « свою область»!

1 шаг: выбрать некоторый элемент массива X

3 шаг: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Слайд 29

«Быстрая сортировка» (Quick Sort) Медиана – такое значение X, что слева

«Быстрая сортировка» (Quick Sort)

Медиана – такое значение X, что слева и

справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

Разделение:
выбрать средний элемент массива (X=67)
установить L:= 1, R:= N
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L <= R, поменять местами A[L] и A[R] и перейти к п. 3

Слайд 30

«Быстрая сортировка» (Quick Sort)

«Быстрая сортировка» (Quick Sort)

Слайд 31

«Быстрая сортировка» (Quick Sort) алг qSort(аргрез целтаб A[1:5], арг цел iStart,

«Быстрая сортировка» (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)
кон

ограничение рекурсии

сортируем две части:
рекурсия!

нц пока L <= R
нц пока A[L] < X; L:= L+1 кц
нц пока A[R] > X; R:= R-1 кц
кц

если L <= R то
c:= A[L]; A[L]:= A[R]; A[R]:= c
L:= L+1; R:= R-1
все

разделение

обмен

двигаемся дальше

Слайд 32

«Быстрая сортировка» (Quick Sort) алг Сортировка Quick Sort нач цел N

«Быстрая сортировка» (Quick Sort)

алг Сортировка Quick Sort
нач
цел N = 5,

i
целтаб A[1:N]
| заполнить массив и вывести на экран
qSort(A, 1, N) | сортировка
| вывести отсортированный массив
кон

алг qSort(аргрез целтаб A[1:5], арг цел iStart, iEnd)
нач
...
кон

Вызов:

qSort(N, A, 1, N)

для массивов любого размера

Слайд 33

Количество перестановок (случайные данные)

Количество перестановок

(случайные данные)

Слайд 34

Задания «3»: Заполнить массив из 10 элементов случайными числами в интервале

Задания

«3»: Заполнить массив из 10 элементов случайными числами в интервале [-50..50]

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

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

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

Тема 3. Двоичный поиск

Слайд 36

Поиск в массиве Задача – найти в массиве элемент, равный X,

Поиск в массиве

Задача – найти в массиве элемент, равный X, или

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

Линейный поиск i:= 1 нц пока A[i] X i:= i +

Линейный поиск

i:= 1
нц пока A[i] <> X
i:= i + 1
кц
если

i <= N
то вывод "A[", i, "]=", X
иначе вывод "Нет такого"
все

i – номер нужного элемента в массиве

i<=N и A[i]<>X

Слайд 38

Двоичный поиск X = 7 X 8 4 X > 4

Двоичный поиск

X = 7

X < 8

8

4

X > 4

6

X > 6

Выбрать средний

элемент A[c] и сравнить с X.
Если X = A[c], нашли (выход).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.
Слайд 39

Двоичный поиск L:= 1; R:= N; nX:= 0 если nX >

Двоичный поиск

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; выход
все

нашли

выйти из цикла

сдвигаем границы

Слайд 40

Сравнение методов поиска

Сравнение методов поиска

Слайд 41

Задания «3»: Написать программу, которая сортирует массив по возрастанию и ищет

Задания

«3»: Написать программу, которая сортирует массив по возрастанию и ищет в

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

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

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

Тема 4. Символьные строки

Слайд 43

Задачи на обработку строк Задача: с клавиатуры вводится число N, обозначающее

Задачи на обработку строк

Задача: с клавиатуры вводится число N, обозначающее количество

футболистов команды «Шайба», а затем – N строк, в каждой из которых – информация об одном футболисте таком формате:
<Фамилия> <Имя> <год рождения> <голы>
Все данные разделяются одним пробелом. Нужно подсчитать, сколько футболистов, родившихся в период с 1988 по1990 год, не забили мячей вообще.

Алгоритм (для каждой строки):
выделить год (year) и количество голов (goal)
если 1988 <= year <=1990 и goal = 0,
то увеличить счётчик

Слайд 44

Программа использовать Строки алг Футболисты нач цел N, i, p, year,

Программа

использовать Строки
алг Футболисты
нач
цел N, i, p, year, goal, count=0

лит s
ввод N
нц для i от 1 до N
ввод s
| разобрать строку, выделить год и голы
если year >= 1988 и year <= 1990 и goal = 0
то count:=count+1
все
кц
вывод count
кон

год

голы

счётчик

Слайд 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)]

Ввод числа голов:

Иванов Вася 1998 5

p

Вася 1998 5

p:= найти(" ", s)
s:= s[p+1:длин(s)]

Вася 1998 5

p

1998 5

p

1998 5

5

goal:= лит_в_цел(s,OK)

лог OK

1998 5

Слайд 46

Разбор строки Если фамилия нужна: p:= найти(" ", s) fam:= s[1:p-1]

Разбор строки

Если фамилия нужна:

p:= найти(" ", s)
fam:= s[1:p-1]
s:= s[p+1:длин(s)]

лит fam

Иванов Вася

1998 5

p

Иванов

Вася 1998 5

Если нужны ВСЕ фамилии:

p:= найти(" ", s)
fam[i]:= s[1:p-1]
s:= s[p+1:длин(s)]

литтаб fam[1:N]

Слайд 47

Задания «3»: Вывести фамилии всех футболистов, которые забили больше двух голов.

Задания

«3»: Вывести фамилии всех футболистов, которые забили больше двух голов.
Пример:

Иванов Василий
Семёнов Кузьма
«4»: Вывести фамилию и имя футболиста, забившего наибольшее число голов, и количество забитых им голов.
Пример:
Иванов Василий 25

Информация о футболистах вводится так же, как и для приведенной задачи (сначала N, потом N строк с данными).

Слайд 48

Задания «5»: Вывести в алфавитном порядке фамилии и имена всех футболистов,

Задания

«5»: Вывести в алфавитном порядке фамилии и имена всех футболистов, которые

забили хотя бы один гол. В списке не более 100 футболистов.
Пример:
Васильев Иван
Иванов Василий
Кутузов Михаил
Пупкин Василий
Слайд 49

Рекурсивный перебор Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы,

Рекурсивный перебор

Задача: Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц,

Щ и О. Вывести на экран все слова из К букв, которые можно составить в этом языке, и подсчитать их количество. Число K вводится с клавиатуры.

1

K

в каждой ячейке может быть любая из 4-х букв

4 варианта

4 варианта

4 варианта

4 варианта

Количество вариантов:

Слайд 50

Рекурсивный перебор 1 K Рекурсия: Решения задачи для слов из К

Рекурсивный перебор

1

K

Рекурсия: Решения задачи для слов из К букв сводится к

4-м задачам для слов из K-1 букв.

1

K

1

K

1

K

перебрать все варианты

перебрать все варианты

перебрать все варианты

перебрать все варианты

Слайд 51

Процедура алг Рек(цел p) нач если p > K то вывод

Процедура

алг Рек(цел p)
нач
если p > K то
вывод s,

нс
count:= count + 1
выход
все
кон

1

K

p

s

p+1

рекурсивные вызовы

Глобальные переменные:
лит s
цел count, K

если p > K то
вывод s, нс
count:= count + 1
выход
все

s[p]:= "Ы"; Рек(p+1)
s[p]:= "Ц"; Рек(p+1)
s[p]:= "Щ"; Рек(p+1)
s[p]:= "О"; Рек(p+1)

окончание рекурсии

Слайд 52

Основная программа лит s, цел count = 0, K алг Рекурсивный

Основная программа

лит s, цел count = 0, K
алг Рекурсивный перебор
нач

вывод "Введите длину слов: "
ввод K
s:= ""
нц K раз s:= s + " " кц
Рек(1)
вывод "Всего ", count, " слов"
кон

s:= ""
нц K раз s:= s + " " кц

строка из K пробелов

глобальные переменные

алг Рек(цел p)
нач
...
кон

Слайд 53

Процедура (много букв) алг Рек(цел p) нач если p > K

Процедура (много букв)

алг Рек(цел p)
нач
если p > K то

вывод s, нс
count:= count + 1
выход
все
кон

лит syms="ЫЦЩО", цел i

нц для i от 1 до длин(syms)
s[p]:= syms[i]; Рек(p+1)
кц

локальные переменные

все буквы

цикл по всем буквам

Слайд 54

Задания Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ

Задания

Алфавит языка племени «тумба-юмба» состоит из букв Ы, Ц, Щ и

О. Число K вводится с клавиатуры.

«3»: Вывести на экран все слова из К букв, в которых первая буква – Ы, и подсчитать их количество.
«4»: Вывести на экран все слова из К букв, в которых буква Ы встречается более 1 раза, и подсчитать их количество.
«5»: Вывести на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, ЫЩЩО), и подсчитать их количество.

Слайд 55

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

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

Тема 5. Матрицы

Слайд 56

Операции с матрицами Задача 1. Вывести на экран главную диагональ квадратной

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

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

из N строк и N столбцов.

A[1,N]

A[2,2]

A[3,3]

A[N,N]

нц для i от 1 до N
вывод A[i,i], " "
кц

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

A[N,1]

A[N-1,2]

A[2,N-1]

нц для i от 1 до N
вывод A[i, ], " "
кц

N+1-i

сумма номеров строки и столбца N+1

A[1,1]

Слайд 57

Операции с матрицами Задача 3. Найти сумму элементов, стоящих на главной

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

Задача 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
кц

нц для j от 1 до i
S:= S + A[i,j]
кц

складываем нужные элементы строки i

цикл по всем строкам

i

Слайд 58

Операции с матрицами Задача 4. Перестановка строк или столбцов. В матрице

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

Задача 4. Перестановка строк или столбцов. В матрице из

N строк и M столбцов переставить 2-ую и 4-ую строки.

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
кц

Задача 5. К третьему столбцу добавить шестой.

нц для i от 1 до N
A[i,3]:= A[i,3] + A[i,6]
кц

Слайд 59

Задания Заполнить матрицу из 7 строк и 7 столбцов случайными числами

Задания

Заполнить матрицу из 7 строк и 7 столбцов случайными числами в

интервале [10,90] и вывести ее на экран. Заполнить элементы, отмеченные зеленым фоном, числами 99, и вывести полученную матрицу на экран.

«3»: «4»: «5»:

Слайд 60

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

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

Тема 6. Файлы

Слайд 61

Файлы Файл – это данные на диске, имеющие имя. Файлы только

Файлы

Файл – это данные на диске, имеющие имя.

Файлы

только текст без оформления, не

содержат управляющих символов (с кодами < 32)

ACSII (1 байт на символ)
UNICODE (>1 байта на символ)

*.txt, *.log,
*.htm, *.html

могут содержать любые символы кодовой таблицы

*.doc, *.exe,
*.bmp, *.jpg,
*.wav, *.mp3,
*.avi, *.mpg

Текстовые

Двоичные

Каталоги (папки)

Слайд 62

Работа с файлами: принцип сэндвича I этап. открыть файл: сделать его

Работа с файлами: принцип сэндвича

I этап. открыть файл:
сделать его активным, приготовить

к работе
связать переменную F с файлом

F:= открыть на чтение("in.txt")

II этап: работа с файлом

цел F

III этап: закрыть файл

закрыть(F)

Фввод F, a, b | ввести a и b

F:= открыть на запись("out.txt")

Фвывод F, a, b, нс | вывести a и b

Слайд 63

Работа с файлами Особенности: имя файла упоминается только при открытии файла,

Работа с файлами

Особенности:
имя файла упоминается только при открытии файла, работа с

файлом – через файловую переменную
файл, который открывается на чтение, должен существовать
если файл, который открывается на запись, существует, старое содержимое уничтожается
данные записываются в файл в текстовом виде
при завершении программы все файлы закрываются автоматически
после закрытия файла переменную F можно использовать еще раз для работы с другим файлом
Слайд 64

Последовательный доступ при открытии файла курсор устанавливается в начало чтение выполняется

Последовательный доступ

при открытии файла курсор устанавливается в начало
чтение выполняется с той

позиции, где стоит курсор
после чтения курсор сдвигается на первый непрочитанный символ

12 5 45 67 56●

12 5 45 67 56●

F:= открыть на чтение("qq.txt")

Фввод F, x

конец файла

Слайд 65

Последовательный доступ как вернуться назад и начать с начала? не открывая

Последовательный доступ

как вернуться назад и начать с начала?
не открывая файл заново

начать

чтение ( F )

закрыть ( F )
F:= открыть на чтение ( "qq.txt" )

Слайд 66

Пример Задача: в файле input.txt записаны числа (в столбик), сколько их

Пример

Задача: в файле input.txt записаны числа (в столбик), сколько их –

неизвестно. Записать в файл output.txt их сумму.
Алгоритм:
Открыть файл input.txt для чтения.
S := 0
Если чисел не осталось, перейти к шагу 7.
Прочитать очередное число в переменную x.
S := S + x
Перейти к шагу 3.
Закрыть файл input.txt.
Открыть файл output.txt для записи.
Записать в файл значение S.
Закрыть файл output.txt.

цикл «пока есть данные»

Слайд 67

Программа: чтение данных из файла использовать Файлы П алг Сумма чисел

Программа: чтение данных из файла

использовать Файлы П
алг Сумма чисел
нач
цел F,

S, x
F:= открыть на чтение("input.txt")
S:= 0
нц пока не конец файла( F )
Фввод F, x
S:= S + x
кц
закрыть( F )
| здесь нужно записать результат в файл
кон

логическая функция, возвращает да, если достигнут конец файла

Слайд 68

Программа: запись результата в файл F:= открыть на запись("output.txt") Фвывод F,

Программа: запись результата в файл

F:= открыть на запись("output.txt")
Фвывод F, S
закрыть( F

)

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

Слайд 69

Задания В файле input.txt записаны числа, сколько их – неизвестно. «3»:

Задания

В файле input.txt записаны числа, сколько их – неизвестно.

«3»: Найти

сумму всех чётных чисел и записать её в файл output.txt.
«4»: Найти минимальное и максимальное из всех чисел и записать их в файл output.txt.
«5»: Найти длину самой длинной цепочки одинаковых чисел, идущих подряд, и записать её в файл output.txt.
Слайд 70

Обработка массивов Задача: в файле input.txt записаны числа (в столбик), сколько

Обработка массивов

Задача: в файле input.txt записаны числа (в столбик), сколько их

– неизвестно, но не более 100. Переставить их в порядке возрастания и записать в файл output.txt.
Проблемы:
для сортировки надо удерживать в памяти все числа сразу (нужен массив!);
сколько чисел – неизвестно.
Решение:
выделяем в памяти массив из 100 элементов;
записываем прочитанные числа в массив и считаем их с помощью переменной N;
сортируем первые N элементов массива;
записываем их в файл.
Слайд 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 элементов
| вывести полученный массив
кон

цикл заканчивается, если достигнут конец файла или прочитали 100 чисел

Слайд 72

Программа: вывод массива в файл F:= открыть на запись("output.txt") нц для

Программа: вывод массива в файл

F:= открыть на запись("output.txt")
нц для i от

1 до N
Фвывод F, A[i], нс
кц
закрыть(F)

зачем?

Слайд 73

Задания В файле input.txt записаны числа (в столбик), известно, что их

Задания

В файле input.txt записаны числа (в столбик), известно, что их не

более 100.

«3»: Отсортировать массив по убыванию и записать его в файл output.txt.
«4»: Отсортировать массив по убыванию последней цифры и записать его в файл output.txt.
«5»: Отсортировать массив по возрастанию суммы цифр и записать его в файл output.txt.

Слайд 74

Обработка текстовых данных Задача: в файле input.txt записаны строки, в которых

Обработка текстовых данных

Задача: в файле input.txt записаны строки, в которых есть

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

Обработка текстовых данных Алгоритм: Прочитать строку из файла. Удалить все сочетания

Обработка текстовых данных

Алгоритм:
Прочитать строку из файла.
Удалить все сочетания ",

короче,".
Записать строку в другой файл.
Перейти к шагу 1.
Особенность:
надо одновременно держать открытыми два файла: один в режиме чтения, второй – в режиме записи.

пока не кончились данные

Слайд 76

Работа с двумя файлами одновременно использовать Строки использовать Файлы П алг

Работа с двумя файлами одновременно

использовать Строки
использовать Файлы П
алг Обработка строк
нач
цел

fIn, fOut
fIn:= открыть на чтение("input.txt")
fOut:= открыть на запись("output.txt")
| обработка файла
закрыть(fIn)
закрыть(fOut)
кон
Слайд 77

Цикл обработки файла нц пока не конец файла(fIn) Фввод fIn, s

Цикл обработки файла

нц пока не конец файла(fIn)
Фввод fIn, s
|

обработка строки s
Фвывод fOut, s, нс
кц
Слайд 78

Обработка одной строки нц пока да p:= найти(", короче,", s) если

Обработка одной строки

нц пока да
p:= найти(", короче,", s)
если p

< 1 то выход все
s:= s[1:p-1] + s[p+9:длин(s)]
кц

бесконечный цикл

выход из цикла

удалить 9 символов

s

p

p+9

1

длин(s)

Слайд 79

Задания В файле input.txt записаны строки, сколько их – неизвестно. «3»:

Задания

В файле input.txt записаны строки, сколько их – неизвестно.

«3»: Заменить

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

Сортировка списков Задача: в файле list.txt записаны фамилии и имена пользователей

Сортировка списков

Задача: в файле list.txt записаны фамилии и имена пользователей сайта

(не более 100). Вывести их в алфавитном порядке в файл sort.txt.
Файл list.txt :
Федоров Иван
Иванов Федор
Анисимов Никита
Никитин Николай
Результат – файл sort.txt :
Анисимов Никита
Иванов Федор
Никитин Николай
Федоров Иван
Слайд 81

Сортировка списков Алгоритм: прочитать строки из файла в массив строк, подсчитать

Сортировка списков

Алгоритм:
прочитать строки из файла в массив строк, подсчитать их

в переменной N
отсортировать первые N строк массива по алфавиту
вывести первые N строк массива в файл

Объявление массива (с запасом):

цел MAX = 100
литтаб s[1:MAX]

Слайд 82

Сортировка списков Ввод массива строк из файла: f:= открыть на чтение("list.txt")

Сортировка списков

Ввод массива строк из файла:

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)

Слайд 83

Сортировка списков Сортировка первых N элементов массива: нц для i от

Сортировка списков

Сортировка первых 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, j, nMin
лит c

Слайд 84

Сортировка списков Как сравниваются строки: || || || || ? s1

Сортировка списков

Как сравниваются строки:

||

||

||

||

?

s1

s2

Кодовая таблица:

Win

UNICODE

245

226

код("х") > код("в")

"х" > "в"

"Пароход"

> "Паровоз"
Слайд 85

Сортировка списков Как сравниваются строки: || || || ? s1 s2

Сортировка списков

Как сравниваются строки:

||

||

||

?

s1

s2

"х" > ¤

"Пароход" > "Пар"

Слайд 86

Сортировка списков Работа с отдельной строкой массива: литтаб s[1:MAX] лит c

Сортировка списков

Работа с отдельной строкой массива:

литтаб s[1:MAX]
лит c | вспомогательная

строка
нц для i от 1 до N
с:= s[i]
| работаем со строкой c, меняем ее
s[i]:= c
кц
Слайд 87

Задания «3»: Добавить к списку нумерацию: 1) Анисимов Никита 2) Иванов

Задания

«3»: Добавить к списку нумерацию:
1) Анисимов Никита
2) Иванов Федор
«4»:

Выполнить задачу на «3» и сократить имя до первой буквы:
1) Анисимов Н.
2) Иванов Ф.
«5»: Выполнить задачу на «4», но при выводе начинать с имени:
1) Н. Анисимов
2) Ф. Иванов
Слайд 88

Списки с числовыми данными Задача: в файле marks.txt записаны фамилии и

Списки с числовыми данными

Задача: в файле marks.txt записаны фамилии и имена

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

Работа с двумя файлами одновременно использовать Файлы П использовать Строки алг

Работа с двумя файлами одновременно

использовать Файлы П
использовать Строки
алг Отметки на экзамене
нач

цел fIn, fOut
fIn:= открыть на чтение("marks.txt")
fOut:= открыть на запись("best.txt")
| обработка строк из файла
закрыть(fIn)
закрыть(fOut)
кон
Слайд 90

Цикл обработки файла цел ball нц пока не конец файла(fIn) Фввод

Цикл обработки файла

цел ball
нц пока не конец файла(fIn)
Фввод fIn, s

| обработка строки s
| ball:= результат на экзамене
если ball > 75 то
Фвывод fOut, s, нс
все
кц
Слайд 91

Преобразования «строка»-«число» Из строки в число: s:= "123" N:= лит_в_цел(s, OK)

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

Из строки в число:

s:= "123"
N:= лит_в_цел(s, OK) | N =

123
если не OK то вывод "Ошибка!" все
s:= "123.456";
X:= лит_в_вещ(s, OK) | X = 123.456
если не OK то вывод "Ошибка!" все

Из числа в строку:

N:= 123
s:= цел_в_лит(N) | "123"
X:= 123.456
s:= вещ_в_лит(X) | "123.456"

цел N, вещ X, лит s, лог OK

да или нет

Слайд 92

Обработка строки n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1]

Обработка строки

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

s:

n

1

n

1

Слайд 93

Обработка строки n:= найти(" ", s) | n:= 7 фамилия:= s[1:n-1]

Обработка строки

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

Задания «3»: Добавить к списку нумерацию: 1) Федоров Иван 78 2)

Задания

«3»: Добавить к списку нумерацию:
1) Федоров Иван 78
2) Анисимов Никита

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

Похожие презентации

Публикация и продвижение Интернет-систем
Интернет культура 90-х
Реляционная модель базы данных
Информационные агентства, как особый тип СМИ
Звуковые карты.
Интернет-исследование. Рынок handmade подарков сегодня
Графика в Бейсике Автор: Бауэр Наталья Ивановна, преподаватель информатики и специальных дисциплин ГОУ СПО «Белгородский педаг
Архитектуры ИС на основе технологии Intranet и распределенные ИС. (Лекция 10)
Застосування медичної статистики у практичній діяльності медичних працівників
Основи роботи з растровою графікою. Графічний редактор ADOBE Photoshop
Алгоритм работы заказчиков в модуле Малые закупки
Инструкция загрузки и сдачи готовых заданий по МДК
Реализация процедур в среде графического исполнителя стрелочка
Презентация "Носители информации" - скачать презентации по Информатике
Neural Networks for Information Retrieval
Общение в Интернете
Базовая настройка коммутаторов 3028, 3526, 1210-28P
Лекція 8. База даних Access
Правовые основы защиты информации
Обеспечение безопасности информационных систем
Дети в интернете
QoS: качество обслуживания. Вычислительные сети и коммуникации
Программы Microsoft Office
Я выбираю - будущее! Мехатроника и мобильная робототехника
Базы данных 04.11.14
Викторина. Безопасный интернет
Основные этапы решения задач на компьютере
Сергей Брин Создатель Google Выполнил(а): Power-P.ru
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть