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

64. Сортировка
§ 65. Двоичный поиск
§ 66. Символьные строки
§ 67. Матрицы
§

в памяти рядом (в соседних ячейках) и имеющих общее имя.

Надо:

выделять память
записывать данные в нужную ячейку
читать данные из ячейки

N = 10
целтаб A[1:N]
размер через константу

массива: 2
ЗНАЧЕНИЕ элемента массива: 10

A[1]
| обработать A[2]
| обработать A[3]
| обработать A[4]
| обработать A[5]

i + 1
| обработать A[i]
i:= i + 1
| обработать A[i]
i:=

i:= i + 1

Обработка в цикле:

i:= 1
нц пока i <= N
| обработать A[i]
i:= i + 1
кц

Цикл с переменной:

нц для i от 1 до N
| обработать A[i]
кц

нц для i от 1 до N
A[i]:= i*i

экран:
цел N = 5, i
целтаб A[1:N]
нц для i от 1

A[1] =
A[2] =
A[3] =
A[4] =
A[5] =

5
12
34
56
13

вывод 'Массив A', нс
нц для i от 1 до N
вывод A[i], ' '
кц

irand(20,100)
вывод A[i], ' '
кц
Задача. Заполнить массив (псевдо)случайными целыми числами

| сделать что-то с A[i]
кц
Подсчёт нужных элементов:
Задача. В массиве записаны

цел count = 0
нц для i от 1 до N
если 180 < A[i] и A[i] < 190 то
count:= count + 1
все
кц

i от 1 до N
если 180 < A[i] и

среднее арифметическое

среднее арифметическое его значений.
Пример:
Массив:
1 2 3 4 5
Среднее арифметическое

«B»: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50.
Пример:
Массив:
3 2 52 4 60
Ср. арифм. элементов [0,50): 3.000
Ср. арифм. элементов [50,100]: 56.000

[1,N] так, чтобы в массив обязательно вошли все числа от

X
i:= i + 1
кц
вывод 'A[',i,']=',X
i:= 1
нц пока

i <= N

должно быть первым!

если A[i] = X то
nX:= i

Вариант с досрочным выходом:

выход

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

X и найдите все значения, равные X.
Пример:
Массив:
1 2 3

ли в нем элементы с одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1

элементы с одинаковыми значениями, не обязательно стоящие рядом.
Пример:
Массив:
3 2 1

A[i] > M то
M:= A[i]
все
кц
вывод M

элементы массива и их номера.
Пример:
Массив:
1 2 3 4 5
Минимальный

«B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5

количество элементов, имеющих максимальное значение.
Пример:
Массив:
3 4 5 5 3

поменять местами A[i] и A[N+1-i]
кц
div(N,2)
остановиться на середине!

A[i]:= A[N+1-i]
A[N+1-i]:= c
кц

N-1
A[i]:= A[i+1]
кц
A[N]:= c

массива вправо на 1 элемент.
Пример:
Массив:
1 2 3 4 5

«B»: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине.
Пример:
Массив:
1 2 3 4 5 6
Результат:
3 2 1 6 5 4

элементы так, чтобы все положительные элементы стояли в начала массива,

условию, в массив B.
нц для i от 1 до N

A

B

выбрать чётные элементы

от 1 до N
если mod(A[i],2) = 0 то

B[count]:= A[i]

в другой массив все чётные отрицательные числа.
Пример:
Массив А:
-5 6 7

«B»: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым.
Пример:
Массив А:
12 13 85 96 47
Массив B:
13 47

все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли

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

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

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

1-й проход:

-1
если A[j+1]< A[j] то
| поменять местами A[j]

2-й проход:

нц для j от N-1 до шаг -1
если A[j+1]< A[j] то
| поменять местами A[j] и A[j+1]
все
кц

2

единственное отличие!

для j от N-1 до шаг -1
если

i

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

«С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.

на первое место.
нц для i от 1 до N-1

если i nMin то
| поменять местами

nMin:= i
нц для j от i+1 до N
если A[j] < A[nMin] то
nMin:= j
все
кц

первую половину массива по возрастанию, а вторую – по убыванию.

чисел в нем.
Пример:
Массив:
5 3 4 2 1 6 3

«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

от друга.

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

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

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

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

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

массив
qSort(1, N) | сортировка
| вывести результат
кон

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

глобальные данные

если nStart >= nEnd то выход все
L:= nStart; R:=

по возрастанию отдельно элементы первой и второй половин массива. Каждый

чисел в нем. Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2

сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее

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

средний элемент A[c] и сравнить с X.
Если X = A[c],

| начальный диапазон
нц пока L < R-1

X. Используя двоичный поиск, определить, есть ли в массиве число,

X. Используя двоичный поиск, определить, сколько чисел, равных X, находится

его. Ввести число X. Используя двоичный поиск, определить, есть ли

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

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

литерный тип

s
Отдельный символ:
s[4]:= 'a'
Длина строки:
цел n
n:= длин(s)
лит s

вывод 'Введите строку: '
ввод s
цел i

Задача: заменить в строке все буквы 'а' на буквы 'б'.

все буквы «а» на «б» и все буквы «б» на

ней слов. Словом считается последовательности непробельных символов, отделенная с двух

слово и его длину. Словом считается последовательности непробельных символов, отделенная

s1 + ', ' + s2 + '!'
'Привет, Вася!'
Срез:
s:=

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

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

'123456789'
удалить(s, 3, 6) | '129'
с какого символа
сколько символов

0 то
вывод 'Номер символа ', n
иначе
вывод 'Символ

что

где

к формату «фамилия-инициалы».
Пример:
Введите имя, отчество и фамилию:

Алгоритм:
найти первый пробел и выделить имя
удалить имя с пробелом из основной строки
найти первый пробел и выделить отчество
удалить отчество с пробелом из основной строки
«сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…

Алибабаевич Хрюндиков

Хрюндиков

Хрюндиков В.А.

вывод 'Введите имя, отчество и фамилию'

отчество, разделив их пробелом. Вывести фамилию и инициалы.
Пример:
Введите фамилию, имя

знаком '/'. Каждую часть вывести в отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2013/Поход/vasya.jpg
C:
Фото
2013
Поход
vasya.jpg

символов на другую.
Пример:
Введите строку:
(X > 0) and (Y < X)

OK) | N = 123
если не OK то вывод

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

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

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

да или нет

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

и двух знаков (допускаются знаки «+», «–», «*» и «/»).

и двух знаков (допускаются знаки «+», «–», «*» и «/»)

строке s все вхождения слова-образца wOld на слово-замену wNew.
нц пока

wOld: '12'
wNew: 'A12B'

зацикливание

replaceAll(s, '12', 'A12B')
вывод s
кон

wNew)
нач
лит res; цел p, len
len:= длин(wOld)
res:= ''

найти слово wOld

не нашли…

добавить то, что перед ним

добавить wNew

взять «хвост»

'12.12.12'
s:= replaceAll(s, '12', 'A12B')
вывод s
кон
алг лит replaceAll(лит s0,

строки.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды

расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя

числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в

«Ш», «Ч» и «О». Нужно вывести на экран все слова,

перебор K-1 символов

задача для слов длины К сведена к задаче для слов длины К-1!

перебор последних K-1 символов
w[1]:='Ш'
| перебор последних K-1

K символов
TumbaWords('ЫШЧО', word, 0)
кон
алг TumbaWords(лит A, w0, цел N)
нач

уже установлено

когда все символы уже установлены

по всем символам алфавита

алфавит

слово

«Ч» и «О». Нужно вывести на экран все возможные слова,

«B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

«Ч» и «О». Нужно вывести на экран все возможные слова,

литтаб S[1:N]
лит s1
нц для i от 1 до

нц для i от 1 до N-1
нц для j от N-1 до i шаг -1
если S[j+1] < S[j] то
s1:= S[j]
S[j]:= S[j+1]
S[j+1]:= s1
все
кц
кц

массив строк

строки с точкой, а затем – слово. Вывести слова в

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

записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой.

одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет

нет знака

нолик

крестик

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

X[-3:0, -8:M]
логтаб L[1:N, 0:1]
строки
столбцы
строки
столбцы

нц для j от 1 до M
A[i,j]:= irand(20,80)

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

s:= 0
нц для i от 1 до N
нц для j от 1 до M
s:= s + A[i,j]
кц
кц

интервале [10,99], и находит максимальный и минимальный элементы в матрице

в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:
вычислить

числами по спирали и змейкой, как на рисунках:

| работаем с  A[i,i]
кц
Побочная диагональ:
нц для i от 1

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

нц для i от 1 до N
нц для j от 1 до  i 
| работаем с  A[i,j]
кц
кц

M
c:= A[2,j]
A[2,j]:= A[4,j]
A[4,j]:= c
кц

интервале [10,99], а затем записывает нули во все элементы выше

содержащей N строк и M столбцов. Выполните отражение рисунка сверху

«С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

символов только символы перехода на новую строку
любые символы
рисунки, звуки, видео,

| здесь работаем с файлами
закрыть(Fout)
закрыть(Fin)
файловые переменные

Fin, a, b
Переход к началу открытого файла:
если конец файла(Fin)
вывод

Определение конца файла:

Fout
Fout:= открыть на запись('output.txt')

закрыть(Fout)
вывод Fout, a, '+', b, '=', a+b

прочитать число из файла
| добавить его к сумме
кц
Задача. В

цел x, S
файл Fin
Fin:= открыть на чтение('input.txt')
S:= 0
нц пока не конец файла(Fin)
ввод Fin, x
S:= S + x
кц
закрыть(Fin)

в файле в столбик, и выводит результат в другой файл.

«B»:

Вывести в другой текстовый файл те же числа, отсортированные в

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

счётчик прочитанных данных
нц пока не конец файла(Fin) и
N:= N

N < MAX

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

N

по возрастанию последней цифры и записать в другой файл.

«B»: В

строчке кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка

нц пока не конец файла(Fin)
| прочитать строку из файла Fin
| разобрать строку – выделить возраст
если возраст < 5 то
| записать строку в файл Fout
все
кц

с первым пробелом
| найти в строке пробел
| выделить возраст перед

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

лит s, sAge
цел age, p
лог OK
... | s = 'Мухтар 4 овчарка'
p:= позиция(' ', s) | 'Мухтар 4 овчарка'
s:= s[p+1:длин(s)] | s = '4 овчарка'
p:= позиция (' ',s) | '4 овчарка'
sAge:= s[1:p-1] | sAge = '4'
age:= лит_в_цел(sAge, OK) | age = 4

s0
s:= s0
... | обработка строки s
если age

строка содержит фамилию, имя и количество баллов, разделенные пробелами:

строка содержит фамилию, имя и количество баллов, разделенные пробелами:

Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО