Типовые алгоритмы (работа с массивами, рекурсивные алгоритмы и т.д.)

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

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

Задача 1. С клавиатуры вводится натуральное число. Определить четное оно или нечетное.

Рассуждение. Четным числом называется такое число, которое при определении остатка от целочисленном деления на 2 дает 0.

В алгоритмическом языке операция ОСТАТОК ОТ ЦЕЛОЧИСЛЕННОГО ДЕЛЕНИЯ

имеет имя MOD.

Проверка результата деления выполняется условным оператором ЕСЛИ.

Алгоритм решения задачи:

АЛГ Четность (НАТ: N )

НАЧ

ВЫВОД: 'Введите натуральное число: '

ВВОД: N

ЕСЛИ N MOD 2 = 0

TO ВЫВОД: 'Введенное число четное.'

ИНАЧЕ ВЫВОД: 'Введенное число нечетное.'

ВСЕ

КОН

Задача 2. С клавиатуры вводится натуральное число. Определить на какую цифру оно оканчивается.

Рассуждение. Чтобы ответить на вопрос задачи нужно из введенного числа выделить последнюю цифру. Операция остаток от целочисленного деления на 10 всегда дает последнюю цифру числа.

Алгоритм решения задачи:

АЛГ ПоследняяЦифра (НАТ: N )

НАЧ

ВЫВОД: 'Введите натуральное число: '

ВВОД: N

ВЫВОД: 'Введенное число оканчивается на цифру:', N MOD 10

КОН

Задача 3. С клавиатуры вводится натуральное число. Определить количество цифр в его записи.

Рассуждение. Если у числа последовательно отбрасывать последнюю цифру, то количество таких действий и даст количество цифр, а исходное число превратится в 0. Операция, позволяющая выполнять такую процедуру, называется ПОЛУЧЕНИЕ ЦЕЛОЙ ЧАСТИ ЧИСЛА и имеет имя DIV. Результат этой операции нужно помещать в ячейку памяти исходной переменной.

Т.к. заранее неизвестно сколько раз нужно выполнять операцию DIV, то нужно применить цикл, пока число не превратится в 0. В этом же цикле нужно счетчик цифр увеличивать на 1 в каждом шаге. Перед циклом счетчику цифр нужно присвоить 0.

Алгоритм решения задачи:

АЛГ КоличествоЦифр (НАТ: N, Schetchik )

НАЧ

ВЫВОД: 'Введите натуральное число: '

ВВОД: N

Schetchik:=0

ПОКА N>0

НЦ

N:= N DIV 10

Schetchik:= Schetchik + 1

КЦ

ВЫВОД: 'Количество цифр в числе = ', Schetchik

КОН

Задача 4. С клавиатуры вводится натуральное число. Определить сумму цифр в его записи.

Рассуждение. Для достижения цели, нужно в цикле последовательно применять операции MOD и DIV с параметром 10.

Алгоритм решения задачи:

АЛГ СуммаЦифр (НАТ: N, Summa )

НАЧ

ВЫВОД: 'Введите натуральное число: '

ВВОД: N

Summa:=0

ПОКА N>0

НЦ

Summa:=Summa+ N MOD 10

N:= N DIV 10

КЦ

ВЫВОД: 'Сумма цифр в числе = '; Summa

КОН

Задача 5. С клавиатуры вводится натуральное число. Определить сумму четных цифр в его записи.

Рассуждение. Для достижения цели, нужно в цикле последовательно применять операции MOD и DIV с параметром 10. В сумму нужно заносить только цифры, удовлетворяющие условию четности.

Алгоритм решения задачи:

АЛГ СуммаЧетныхЦифр (НАТ: N, Summa)

НАЧ

НАТ x

ВЫВОД: 'Введите натуральное число: '

ВВОД: N

Summa:=0

ПОКА N>0

НЦ

x:= N MOD 10

ЕСЛИ x MOD 2 = 0

ТО Summa:=Summa + х

ВСЕ

N:= N DIV 10

КЦ

ВЫВОД: 'Сумма четных цифр в числе = ', Summa

КОН

Задача 6. С клавиатуры вводится натуральное число. Определить количество четных цифр в его записи.

Рассуждение. Особенность задачи заключается в том, что число в своей записи может иметь 0. Операция MOD 2, примененная к нему даст в результате 0, как и четная цифра, но 0 не относится к четным цифрам, и его нужно пропускать. Поэтому в условии ЕСЛИ нужно дополнительно проверять отличие очередной цифры от 0.

Алгоритм решения задачи:

АЛГ СуммаЧетныхЦифр ()

НАЧ

НАТ: N, Kolich, x

ВЫВОД: 'Введите натуральное число:'

ВВОД: N

Kolich := 0

НЦ ПОКА N>0

x:= N MOD 10 | очередная последняя цифра числа

ЕСЛИ (x MOD 2 = 0) AND (x <> 0)

ТО Kolich := Kolich + 1

ВСЕ

N:= N DIV 10 | удалить последнюю цифру числа

КЦ

ВЫВОД: 'Количество четных цифр в числе = ', Kolich

КОН

Задача 7. С клавиатуры вводится натуральное число. Определить все его делители.

Рассуждение. Для определения делителей числа нужно поочередно проверять все числа от 2 до максимального для данного числа. Само число и 1, как делители, рассматривать не нужно.

Максимальным возможным делителем числа является целая часть квадратного корня из введенного числа. Если число х является делителем числа N, то операция N MOD x даст результат 0.

Если делителей не обнаружено, то число считается простым. Для контроля за наличием делителей (кроме 1 и самого числа) вводится дополнительная переменная, которой изначально присваивается 0, а при обнаружении

делителя ей присваивается 1.

Алгоритм решения задачи:

АЛГ ДелителиЧисла (НАТ: N, х, flag)

НАЧ

ВЫВОД: 'Введите натуральное число:'

ВВОД: N

ВЫВОД: 'Делители числа: '

flag:=0

НЦ ДЛЯ х ОТ 2 ДО SQR(N)

ЕСЛИ N MOD x = 0

ТО ВЫВОД: х

flag:=1

ВСЕ

КЦ

ЕСЛИ flag=0

ТО ВЫВОД: 'Делителей, кроме 1 и ',N,' нет. Данное число простое.'

ВСЕ

КОН

Задача 8. С клавиатуры вводится натуральное число. Определить, является ли сумма цифр, введенного числа, делителем этого числа.

Рассуждение. Для определения суммы цифр числа применяем последовательно операции MOD 10 и DIV 10, но нужно иметь ввиду, что исследуемое число в конце цикла превращается в 0. Но после получения суммы нужно введенное число исследовать на делимость. Чтобы сохранить исходное число нужно ввести дополнительную переменную такого же типа, присвоить ей введенное значение и сумму цифр находить, используя дополнительную переменную.

Алгоритм решения задачи:

АЛГ СуммаДелитель (НАТ: N, Summa)

НАЧ

НАТ х

ВЫВОД: 'Введите натуральное число: '

ВВОД: N

Summa:=0

х:=N

ПОКА x>0

НЦ

Summa:=Summa + x MOD 10

x:= x DIV 10

КЦ

ЕСЛИ N MOD Summa=0

ТО ВЫВОД: 'Число делится на сумму своих цифр.'

ИНАЧЕ ВЫВОД: 'Число не делится на сумму своих цифр.'

ВСЕ

КОН

Задача 9. С клавиатуры вводится натуральное число. Определить, есть ли в его записи одинаковые цифры.

Рассуждение. Возьмем 3 простых примера: числа 112, 121, 211. Каждое из этих чисел содержит повторяющуюся цифру 1. Т.к. заранее не известно как расположены повторяющиеся цифры, то нужно каждую, кроме самой левой, сравнить со всеми остальными, расположенными слева от проверяемой цифры.

Далее см. комментарий к строкам алгоритма.

Алгоритм решения задачи:

АЛГ ОдинаковыеЦифры (НАТ: N, х1, х2)

НАЧ

НАТ х, y, flag

ВЫВОД: 'Введите натуральное число:'

ВВОД: N

х:=N

flag:=0

ПОКА x>9 И flag=0 | пока в числе больше одной цифры

НЦ | и не обнаружены одинаковые цифры

x1:= x MOD 10| определить последнюю цифру основной части числа

y:= x DIV 10 | получить целую часть (без последней цифры)

ПОКА y>0 И flag=0 | пока в числе есть цифры

НЦ | и не обнаружены одинаковые цифры

х2:= у MOD 10 | определить последнюю цифру остатка

ЕСЛИ х1=х2

ТО flag:=1 | обнаружены одинаковые цифры

ВСЕ

y:= y DIV 10 | отбросить последнюю цифру остатка

КЦ

x:= x DIV 10 | отбросить последнюю цифру основной части

КЦ

ЕСЛИ flag=1

ТО ВЫВОД: | В числе есть одинаковые цифры.'

ИНАЧЕ ВЫВОД: |В числе нет одинаковых цифр.'

ВСЕ

КОН

Примеры решения задач

Задача: Выполнить циклический сдвиг по часовой стрелке элементов одномерного массива размером N на, указанное, количество элементов.

Фрагмент алгоритма решения задачи:

. . . . . . .

k := 2 | количество элементов сдвига

нц для i от 1 до k

t := M[N]| запомнить последний элемент массива

нц для j от 1 до N-1 | цикл сдвига вправо

M[N-j+1] := M[N-j]

кц

M[1] := t | последний элемент вставить на первое место

кц

Трассировочная таблица проверки алгоритма

Задача . Имеется массив целых неотрицательных случайных чисел, содержащий N элементов.

Определить количество и сумму элементов массива, находящихся слева от первого максимального значения.

Фрагмент алгоритма решения задачи:

. . .

nMax := m[1], i := 2

нц пока i<=N | цикл поиска первого максимального числа

если nMax < m[i]

то nMax := m[i]

t := i

все

i := i + 1

кц

Summ := 0, k := 0

| цикл суммирования всех чисел, слева от первого максимального числа

нц для i от 1 до t-1

Summ := Summ + m[i]

k := k +1

кц

Вывод: 'Summ = ', Summ

Вывод: 'k = ',k

Тест:

1, 5, 3, 7, 6 (пример элементов массива)

Задача . Имеется массив целых неотрицательных случайных чисел, содержащий четное количество элементов N.

Определить индексы пар элементов с максимальной суммой. Пары формируются по правилу: первая пара m[1] и m[N], вторая пара m[2] и m[N-1] и т.д.

. . .

MaxSumm := 0, i := 1

нц пока i < N/2

если m[i]+m[N-i+1]>MaxSumm

то MaxSumm := m[i]+m[N-i+1]

n := i

k := N-i+1

все

i := i + 1

кц

Вывод: 'MaxSumm = ', MaxSumm

Вывод: 'Индексы: ', n, k

Проверка на тесте: 1 5 4 7

Задача. Имеется массив целых неотрицательных случайных чисел, содержащий количество элементов N.

Подсчитать количество и сумму элементов, расположенных между первым минимальным и последним максимальным элементами.

Фрагмент алгоритма решения

. . .

nMin := m[1]

nMax := m[1]

i := 2

| цикл поиска первого минимального и последнего максимального значения

| и соответствующих им индексов

| Для поиска первого минимального значения используется строгое

| неравенство m[i] < nMin

| Для поиска последнего максимального значения используется нестрогое

| неравенство m[i]<=nMax

нц пока i <=N

если m[i] < nMin

то nMin := m[i]

iMin := i

все

если m[i]<=nMax

то nMax := m[i]

iMax := i

все

i := i+1

кц

|Для определения начального индекса суммирования нужно выяснить

|какой индекс iMax или iMin имеет меньшее значение и начальному индексу

|присвоить младший индекс, увеличенный на 1, т.к. в сумму не должны

|входить сами nMin и nMax

если iMax > iMin

то i := iMin+1

иначе i := iMax+1

iMax := iMin

все

k := 0, Summ := 0

нц пока i < iMax

k := k +1

Summ := Summ + m[i]

i := i+1

кц

Вывод: 'Summ = ', Summ

Вывод: 'k = ',k

Задача1. Дано число. Определить, является ли оно квадратом четного числа.

Алгоритм на псевдокоде:

алг Квадрат_числа ()

нач

нат N

вещ R

ВВОД: N

R := Sqr(N)|вычисление квадратного корня из N

|если результат деления и целая часть от деления совпадают,

|то R делитель N

Если N/R = N DIV R

ТО Если R MOD 2 = 0 |проверка на четность

ТО

ВЫВОД: 'Введенное число является квадратом четного числа'

ИНАЧЕ

ВЫВОД: 'Введенное число является квадратом нечетного числа'

ВСЕ

ИНАЧЕ ВЫВОД: 'Введенное число не является квадратом целого'

ВСЕ

кон

Блок-схема алгоритма:

начало

ВВОД: N

R := Sqr (N)

N/R = N Div R

Вывод: не квадрат целого

Вывод: квадрат четного

R MOD 2 = 0

Вывод: квадрат нечетного

конец

ДА

ДА

код программы:

Public Sub Квадрат_числа()

Dim N As Integer, R As Single

N = InputBox("Введите число:")

R = Math.Sqr(N)

If N / R = N \ R Then

If R Mod 2 = 0 Then

MsgBox "Введенное число является квадратом четного числа"

Else

MsgBox "Введенное число является квадратом нечетного числа"

End If

Else

MsgBox "Введенное число не является квадратом целого"

End If

End Sub

Задача 2. Дано натуральное число. Выяснить, является ли количество цифр в записи числа делителем суммы цифр, из которых состоит число.

Алгоритм решения задачи:

алг Количество_делитель ()

нач

нат N, K, S

ВВОД: N

S := 0

K := 0

нц пока N <> 0

S := S + N MOD 10 | сумма цифр

K := K + 1 |количество цифр

N := N DIV 10

кц

если S MOD K = 0

то вывод: ' Количество цифр является делителем суммы цифр'

иначе вывод: ' Количество цифр не является делителем суммы цифр'

Все

кон

Блок-схема алгоритма:

начало

ВВОД: N

S := 0 K := 0

Вывод: ДА

N <> 0

S := S + N MOD 10 K := K + 1 N := N DIV 10

S MOD K = 0

Вывод: НЕТ

ДА

ДА

КОНЕЦ

Public Sub Количество_делитель ()

Dim N As Integer, K As Integer, S As Integer

N = InputBox("Введите целое число:")

S = 0: K = 0

Do While N <> 0

S = S + N Mod 10

K = K + 1

N = N \ 10

Loop

If S Mod K = 0 Then

MsgBox "Количество цифр является делителем суммы цифр"

Else

MsgBox "Количество цифр не является делителем суммы цифр"

End If

End Sub