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

массивов

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



нц для

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

div(N,2)

поменять местами содержимое двух ячеек памяти.
4
6
?
4
6
4
x
y
c
c:= x
x:= y
y:= c
x:=

3

2

1

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






| здесь

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

в интервале [-10..10] и сделать реверс всех элементов, кроме

в интервале [-12..12] и выполнить реверс для каждой трети

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

нц

почему не N?

= 10
целтаб A[1:N]
| здесь нужно заполнить массив

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

в интервале [-10..10] и выполнить циклический сдвиг влево без

в интервале [-12..12] и выполнить циклический сдвиг ВПРАВО на

удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в

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

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

A

B

очередной элемент ставится на место B[count].
цел i, N =

A

B

count

для i от 1 до N
вывод B[i], "

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

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

count

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

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

массивов

порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …).

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

поднимается со дна вверх.
Для массивов – самый маленький

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

1-ый проход

2-ой проход

3-ий проход

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

и 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

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] уже поставлены

в интервале [-10..10] и отсортировать его по убыванию.

в интервале [0..100] и отсортировать первую половину по возрастанию,

место (поменять местами с A[1])
из оставшихся найти минимальный элемент

nMin:= i
нц для j от i+1 до

N-1

N

нужно N-1 проходов

поиск минимального от A[i] до A[N]

если нужно, переставляем

i+1

i

в интервале [0..99] и отсортировать его по убыванию последней

в интервале [0..100] и отсортировать первую половину по возрастанию,

элементы, расположенные дальше друг от друга.
div(N,2)
2 шаг: переставить

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

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

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

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

Разделение:
выбрать средний элемент массива (X=67)


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

цел iStart, iEnd)
нач
цел L, R, c, X
если

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

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

нц пока 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
все

разделение

обмен

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

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

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

Вызов:

qSort(N, A, 1, N)

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

в интервале [-50..50] и отсортировать его с помощью алгоритма

поиск

равный X, или установить, что его нет.
Решение: для

i + 1
кц
если i

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

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

> 6
Выбрать средний элемент A[c] и сравнить с X.
Если

nX > 0
то вывод "A[", nX, "]=",

нц пока 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 (это число

строки

N, обозначающее количество футболистов команды «Шайба», а затем –

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

year, goal, count=0
лит s
ввод N
нц для

год

голы

счётчик

года рождения:
p:= найти(" ", s)
year:= лит_в_цел(s[1:p-1],OK)
s:= s[p+1:длин(s)]
Ввод числа голов:
Иванов

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

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]

двух голов.
Пример:
Иванов Василий
Семёнов Кузьма
«4»: Вывести

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

всех футболистов, которые забили хотя бы один гол. В

букв Ы, Ц, Щ и О. Вывести на экран

1

K

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

4 варианта

4 варианта

4 варианта

4 варианта

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

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

1

K

1

K

1

K

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

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

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

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

вывод s, нс
count:= count

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)

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

Рекурсивный перебор
нач
вывод "Введите длину слов: "
ввод

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

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

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

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

K то
вывод s, нс

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

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

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

все буквы

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

Ц, Щ и О. Число K вводится с клавиатуры.
«3»:

диагональ квадратной матрицы из N строк и N столбцов.
A[1,N]
A[2,2]
A[3,3]
A[N,N]
нц

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

на главной диагонали и ниже ее.
строка 1: A[1,1]
строка 2:

S:= 0;
нц для i от 1 до N



кц

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

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

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

i

В матрице из 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
кц

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

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

случайными числами в интервале [10,90] и вывести ее на

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

текст без оформления, не содержат управляющих символов (с кодами

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

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

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

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

Текстовые

Двоичные

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

его активным, приготовить к работе
связать переменную F с

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

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

цел F

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

закрыть(F)

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

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

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

файла, работа с файлом – через файловую переменную
файл, который

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

12 5 45 67 56●

12 5 45 67 56●

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

Фввод F, x

конец файла

открывая файл заново
начать чтение ( F )
закрыть (

сколько их – неизвестно. Записать в файл output.txt их

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

чисел
нач
цел F, S, x
F:= открыть на чтение("input.txt")

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

F, S
закрыть( F )
Особенности:
файл, который открывается на запись, не

неизвестно.
«3»: Найти сумму всех чётных чисел и записать

столбик), сколько их – неизвестно, но не более 100.

цел F, MAX = 100, N = 0, i,

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

для i от 1 до N
Фвывод F, A[i],

зачем?

что их не более 100.
«3»: Отсортировать массив по

в которых есть слово-паразит «короче». Очистить текст от мусора

все сочетания ", короче,".
Записать строку в другой файл.

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

Обработка строк
нач
цел fIn, fOut
fIn:= открыть на чтение("input.txt")

fIn, s
| обработка строки s
Фвывод fOut,

s)
если p < 1 то выход все
s:=

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

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

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

s

p

p+9

1

длин(s)

неизвестно.
«3»: Заменить все слова «короче» на «в общем»

имена пользователей сайта (не более 100). Вывести их в

строк, подсчитать их в переменной N
отсортировать первые N строк

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

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

на чтение("list.txt")
N:= 0
нц пока не конец файла(f)
N:= N

цел f, N

Вывод первых N строк массива в файл:

f:= открыть на запись("sort.txt")
нц для i от 1 до N
Фвывод f, s[i], нс
кц
закрыть(f)

i от 1 до N-1
nMin:= i
нц для

цел i, j, nMin
лит c

код("в")
"х" > "в"
"Пароход" > "Паровоз"

"Пар"

c | вспомогательная строка
нц для i от 1

Никита
2) Иванов Федор
«4»: Выполнить задачу на «3»

фамилии и имена школьников и баллы, полученные ими на

Отметки на экзамене
нач
цел fIn, fOut
fIn:= открыть на

Фввод fIn, s
| обработка строки s

Иван 78
2) Анисимов Никита 90
«4»: Выполнить задачу на «3»