Как составить алгоритм для массивов

В современной школе информатика –
достаточно сложный предмет для усвоения
учащимися. Основное препятствие для
полноценного изучения информатики – нехватка
времени. Мною проанализировано много учебных
планов и методик преподавания информатики и для
общеобразовательных классов, и для профильных с
углубленным изучением информатики. Вывод
неутешителен. Предлагаемые материалы
основываются на гораздо большем годовом
количестве учебных часов, чем то, которым мы
реально располагаем. Следствием расхождения
между рекомендуемым и реальным объемом учебных
часов является невозможность использовать в
процессе обучения какой-то один учебник
информатики. Это неудобно как ученикам, так и
преподавателю. Выходом из этой ситуации является
разработка собственной методики преподавания
информатики с ориентацией на творческую
деятельность учащихся и тестовый контроль,
которая, не уменьшая объем материала, позволяла
бы сократить время на его усвоение учениками и
уложиться в отведенное количество часов.

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

Секрет могущества ЭВМ – высокая
скорость и большая память. Для записи алгоритмов,
работающих с большими объемами информации, в
алгоритмическом языке существуют специальные
табличные величины (или просто таблицы).
Исполнение многих алгоритмов было бы просто
невозможно, если бы соответствующие объекты не
были каким-либо образом организованы:
упорядочены, классифицированы, занумерованы и
так далее. Итак, нужно уметь организовать не
только действия, но и те объекты, над которыми эти
действия производятся.

Необходимо отметить, что таблицы
(массивы) как основное средство представления
однородной информации неизбежно используются во
всех реальных компьютерных программах. На
табличном принципе основана и архитектура
современных ЭВМ: память машины можно
рассматривать как большой массив байтов, адреса
которых располагаются по возрастанию.

Следовательно, без понимания
информационной сущности таблиц и основных
алгоритмов их обработки невозможно формирование
полноценных представлений о возможностях ЭВМ и
принципах их работы. Для построения сколь-нибудь
сложных и содержательных программ необходимо
уверенное владение общими принципами применения
таблиц и базовыми приемами их
обработки. В данной работе будет рассмотрен ряд
простых алгоритмов, которые используются при
построении более сложных.

Алгоритм вычисления суммы

1. Пусть дан массив A,
состоящий из n элементов: a₁,
a₂, a₃, …, a_n. Нужно
найти их сумму, т.е. S=a₁+a₂+a₃+…+a_n.

Нахождение суммы есть
последовательное нахождение суммы по формулам:

S=0 S=S+a₂ … S=S+a_i S=S+a_n

S=S+a₁ S=S+a₃ …

Алгоритм вычисления суммы удобно
организовать циклом, взяв за параметр цикла
переменную i, которая
меняется от 1 до n с шагом 1, и
записав в цикле формулу S=S+a_i один раз. Схема алгоритма приведена
на рис. 1а.

В схеме блок 4 присваивает S нулевое значение, блок 5 счетчику i
присваивает начальное значение,
блок 6 выполняет накопление суммы, блок 7 изменяет
значение i на 1, блок 8
осуществляет проверку условия повторения цикла.
При выполнении этого условия управление
передается в начало цикла, а при невыполнении –
осуществляется выход из цикла, т.к. при i=n+1 суммировать не нужно. n – в схеме предполагается число, но n может быть и переменной, значение
которой равно числу элементов массива A, которое нужно вводить перед
описанием массива.

При разработке этого алгоритма
учащимся можно предложить изменить схему на
случай, если нужно найти сумму элементов,
расположенных на четных местах в массиве A (Ответ: Блок 5 надо изменить на i=2 и блок 7 на i=i+2)
или задать вопрос – что изменится в схеме на
рис.1а, если суммировать только положительные
элементы массива A? (Ответ:
Перед блоком суммирования 6 нужно поставить блок
проверки элемента массива a_i на положительность и, если он
положителен, то его суммировать, а если нет, то
обходить блок суммирования.) Схема алгоритма
будет иметь вид:

При таком тщательном исследовании
схемы алгоритма учащиеся без особых затруднений
ответят на вопрос – что добавить в схеме на
рис.2, чтобы в ней подсчитывалось еще количество
положительных элементов массива?

(Ответ: Надо ввести
переменную k для получения
количества положительных элементов и перед
циклом присвоить ей значение 0. После блока
проверки 7 по пути “+” нужно поставить блок,
содержащий k=k+1, который ведет
счет количества положительных элементов массива
A.) Схема алгоритма приведена
на рис.3а.

Алгоритм вычисления произведения

Этот алгоритм предлагается учащимся
разработать самостоятельно, взяв за основу
алгоритм определения суммы элементов массива
(Рис. 1а). Учащиеся должны не только указать на
изменения блока 6 на S=S*a_i
(в S будет направляться
произведение элементов), но и дать четкое
объяснение изменению блока 4 на S=1. Схема алгоритма представлена на
рис.1б.

Алгоритм формирования нового массива

Как положительные элементы массива A сформировать в массив? Обозначим
массив положительных элементов B и по пути “+” после блока 7 поставим
присвоение соответствующему элементу массива B элемент массива A,
т.е. блок, содержимое которого b_k=a_i.

k будем использовать
как меняющийся индекс нового массива. Необходимо
обратить внимание учащихся на блок 2, в котором
требуется описать массив B,
указав количество его элементов равное
количеству элементов массива A. Схема алгоритма на рис.3б.

Алгоритм определения максимального элемента

Для получения максимального числа
введем переменную M и ей
присвоим значение первого элемента массива a₁, а затем необходимо сравнить M с текущим элементом массива a_i и если текущий элемент будет больше M, то значение M
заменить на значение этого элемента. Схема
алгоритма на Рис. 4. Очень важно обратить внимание
учащихся на начальное значение переменной M.
Почему, например нельзя
переменной M присвоить
значение равное нулю? (Ответ: Для массива с
отрицательными значениями элементов максимум не
будет найден.)

Алгоритм упорядочения массива методом
“Пузырька”

Действия по упорядочению некоторых
данных по ключу называются процессом сортировки.
Очевидно, что с отсортированными данными
работать легче и быстрее, чем с произвольно
расположенными. Все применения ЭВМ основаны на
их способности к быстрой и точной обработке
больших объемов информации, а это возможно
только тогда, когда информация однородна и отсортирована.
Существует довольно много различных методов
сортировки, отличающихся друг от друга степенью
эффективности, под которой понимается
количество сравнений и количество обменов,
произведенных в процессе сортировки, время
выполнения и объем
занимаемой ОП. Рассмотрим сортировку методом
“Пузырька”, которая легко описывается в форме
четких алгоритмов и приводит к простой
программной реализации.

Одномерный массив A
из n элементов упорядочим по
возрастанию. При
пузырьковой сортировке элементы массива попарно
сравниваются и более “легкие” элементы как бы
всплывают на поверхность. При реализации
алгоритма возникает проблема в определении
количества шагов сортировки. Для решения этой
задачи воспользуемся известным методом
“расстановки флажков”, благодаря
которому однозначно будет определен момент
завершения сортировки и выхода из цикла (блок 5).

В качестве “флажка” возьмем числовую
переменную F и присвоим ей
произвольное начальное значение отличное от
нуля (блок 4). Схема алгоритма на рис. 5. По парное
сравнивание элементов и их обмен местами
происходит в блоках 9-12, здесь же изменяется
значение флажка (блок 13). В случае, когда все
элементы массива будут упорядочены, значение F останется равным нулю (блок 6). Блоки
3 и 15 являются укрупненными, т.к. алгоритмы ввода и
вывода элементов массива подробно не описаны на
схеме (Рис. 5).

В помощь учащимся общеобразовательной
школы мною разработано методическое пособие по
алгоритмам обработки массивов данных, в котором
подробно рассматриваются элементарные
алгоритмы, используемые при составлении более
сложных алгоритмов, и прилагается большая
подборка задач.

Задачи “Первые шаги”

1. В массиве а₁, а₂, …, а₅₀
   определить количество нулей.
2. В массиве d₁, d₂, …, d₃₅
   найти сумму чисел, расположенных на нечетных
   местах.
3. В массиве с₁, с₂
   , …, с₄₀
   найти произведение отрицательных чисел.
4. В массиве b₁, b₂, …, b₄₅
   найти сумму отрицательных чисел.
5. В массиве b₁, b₂, …, b₂₀
   найдите количество «единиц».
6. Из массива а₁, а₂
   , …, а₃₀
   найти произведение чисел, расположенных на
   нечетных местах.
7. В массиве с₁, с₂
   , …, с₄₀
   найти сумму чисел больших единицы.
8. В массиве чисел а₁, а₂
   , …, а₅₀
   найти количество чисел меньших единицы.
9. В массиве с₁, с₂
   , …, с₃₇
   найти произведение чисел больших 2.
10. В массиве а₁, а₂
    , …, а₄₀
    найти сумму чисел, расположенных на местах
    кратных 3.
11. В массиве а₁, а₂
    , …, а₅₀
    найти произведение чисел меньших или равных 2.
12. В массиве b₁, b₂, …, b₄₅
    найти количество чисел равных 3,5.
13. В массиве d₁, d₂, …, d₅₀
    найти сумму чисел равных 4,7.
14. В массиве b₁, b₂, …, b₃₀
    найти произведение чисел больших
    или равных 5.
15. В массиве с₁, с₂
    , …, с₇₀
    найти количество «нулей», стоящих на
    нечетных местах.
16. В массиве b₁, b₂, …, b₆₅
    найти сумму чисел больших или
    равных 5.
17. В массиве d₁, d₂, …, d₃₀
    найти произведение чисел, исключая
    первый и последний элемент.
18. В массиве а₁, а₂
    , …, а₃₅
    найти количество «единиц», стоящих на четных
    местах.
19. В массиве чисел а₁, а₂
    , …, а₃₀
    найти сумму отрицательных чисел, стоящих на
    нечетных местах.
20. В массиве чисел в₁, в₂, …, в₃₅
    найти произведение чисел больших или равных 2.
21. В массиве чисел с₁, с₂, …, с₄₀
    найти количество чисел, попавших в интервал [а,
    в]
22. В массиве чисел с₁, с₂, …, с₄₀
    найти сумму чисел, не попавших в
    интервал [с, d].
23. В массиве чисел в₁, в₂, …, в₄₅
    найти произведение всех ненулевых чисел.
24. В массиве чисел с₁, с₂, …, с₆₀ найти
    количество нулей стоящих на местах, кратных 4 т.е.
    среди чисел с₄, с₈, …, с₆₀.
25. В массиве чисел z₁, z₂, …, z₂₀₀
    найти сумму чисел z₅, z₁₀,
    …, z₂₀₀.

Задачи “Джентльменский
набор”.

1. Даны три последовательности
   чисел а₁, а₂, …,
   a₉, b₁, b₂ …, b₉,
   с₁, с₂, …, с₉.
   Составьте новую последовательность d₁, d₂,
   …, d₉, каждый элемент
   которой определяется по правилу d_i =
   max (а_i, b_i, с_i), где i=
   1,2, …,9.
2. Найти номер первого нулевого
   элемента массива х₁, х₂, …, х₂₀ и
   сумму элементов предшествующих ему.
3. Даны три последовательности
   чисел: а₁, а₂, …, а₈; b_1, b₂, …, b₈; с₁, с₂
   , …, с₈.
   Составить новую последовательность, в которой
   чередовались бы числа всех трех
   последовательностей, т.е. d₁ = a₁; d₂=b₁;
   d₃ = c₁; d₄ = a₂; d₅ = b₂;
   d₆ = c₂.
4. Известно, что в массиве а₁, а₂, …, а₁₆
   количество отрицательных чисел
   равно количеству положительных. Составить новый
   массив так, чтобы чередовались положительные и
   отрицательные числа.
5. Найти сумму элементов
   последовательности b₁, b₂, …, b₁₅
   , расположенных правее последнего
   отрицательного элемента и номер этого элемента.
6. Дана последовательность чисел с₁
   , с₂, …, с₁₆
   . Найти произведение элементов этой
   последовательности до первого нулевого и сумму
   элементов, расположенных после него.
7. Из массива с₁
   , с₂, …, с₁₈
   получить массив х₁
   , х₂, …, х₁₈
   по правилу; х₁
   = с₁, х₂
   =с₃, …, х₉
   =с₁₇, x₁₀=с₁₈
   , х₁₁=с₁₆,
   …, x₁₈=с₂.
8. Из данного массива чисел х₁
   , х₂, …, х₂₅
   исключить последнее положительное
   число. Оставшиеся числа переписать в новый
   массив z₁, z₂, …, z₂₄.
9. Найти номер первого
   положительного элемента массива b₁, b₂,
   …, b₁₅ и сумму элементов,
   расположенных правее него.
10. Все положительные элементы
    массива а₁, а₂
    , …, а₂₀,
    расположенные правее первого нулевого элемента,
    увеличить в два раза.
11. В массиве х₁
    , х₂, …, х₂₅
    поменять местами элементы х₁
    , х₄, х₇
    , х₁₀, …, х₂₂
    с наименьшим из следующий за
    ними соответствующей пары элементов.
12. Из заданного массива а₁
    , а₂, …, а₁₂
    , не содержащего нулей, получить
    массив b₁, b₂, …, b₁₂
    , приняв в качестве первых его
    элементов все положительные элементы массива A
    с сохранением порядка их
    следования, а в качестве остальных элементов все
    отрицательные элементы также с сохранением
    порядка их следования.
13. Дан массив с₁
    , с₂, …, с₁₅, состоящий из нулей и единиц.
    Подсчитать количество 0, количество 1 и
    количество нулей до первой единицы.
14. Дан массив чисел х₁, х₂, …, х₂₂
    . Переписать в другой массив из
    данного все элементы, расположенные правее
    последнего отрицательного элемента, сохраняя
    порядок их следования.
15. По данным числам х, у, z получить массив а₁, а₂, …, а₁₇
    , где а₁ = х,
    а₂ = у, а₃ = z,
    а каждый следующий элемент
    массива определяется как среднее арифметическое
    трех предшествующих.
16. Из заданных массивов а₁
    , а₂, …а₈;
    b₁, b₂, …, b₁₂; с₁
    , с₂, …, с₆
    получить массив d₁, d₂,
    …, d₂₆ в котором
    разместить сначала все элементы массива A, затем элементы массива B
    и в конце элементы массива C.
17. В массиве а₁
    , а₂, …, а₁₈ вычислить сумму отрицательных до
    последнего нулевого и произведение элементов
    расположенных правее него.
18. В массиве у₁, у₂, …, у₁₈
    элементы с номерами, кратными 4,
    заменить среднем арифметическим из трех
    предшествующих элементов.
19. Массивы х₁, х₂, …, х₁₀
    и у₁, у₂, …, у₁₀
    преобразовать по правилу: большее из х_i
    и у_i
    принять в качестве нового значения х_i
    , а меньшее – в качестве нового
    значения у_i (i = 1,2, …,10).
20. Все элементы массива а₁
    , а₂, …, а₄₅, начиная с первого по порядку
    положительного элемента, уменьшить на 0,5, если
    значение элемента превышает 1 и увеличивать на 0,5
    в противном случае.
21. В массиве а₁, а₂, …, а₂₅
    найти произведение первых трех
    положительных элементов.
22. Из десяти последних
    отрицательных чисел последовательности t₁,
    t₂, t₃, …, t₃₀₀
    сформировать последовательность у₁, у₂, …, у₁₀.
23. Если наименьший элемент данной
    последовательности х₁,
    х₂, …, х₂₇ больше 0,1 то все отрицательные
    элементы последовательности заменить единицей.
24. Дана последовательность а₁, а₂, …, а₅₀
    . Сформировать последовательность в₁, в₂, …, в₅₀
    следующим образом: в начале
    расположить все отрицательные элементы
    последовательности, а затем все остальные.

Задачи “Уже
проблемы”

1. Дан массив а₁, а₂,
   …, a₂₀. Получить массив
   х₁+у₁
   , х₂+у₂, …, х_r+у_r
   , где элементами массива х₁, х₂, …, х_p
   являются отрицательные, а
   элементами массива у₁, у₂
   , …, у_t
   положительные элементы массива A, r = min
   (р, t).
2. Найти номер первого нулевого элемента массива а₁, а₂, …, а₂₅
   и произведение элементов,
   расположенных до него, а среди элементов,
   расположенных правее первого нулевого, найти
   максимальный элемент.
3. В данном массиве чисел с₁, с₂, …, с₂₅
   поменять местами максимальный элемент с
   последним отрицательным элементом.
4. Из массива х₁, х₂, …, х₂₅
   сформировать два массива; в одном написать числа,
   расположенные до минимального элемента массива
   х, в другой расположенный правее минимального.
5. Пять последних элементов последовательности у₁,
   у₂, …, у₄₀ помножить на номер
   максимального элемента данной
   последовательности.
6. Из массива а₁, а₂, …, а₃₀
   исключить максимальный элемент.
7. Среди отрицательных элементов массива х₁,
   х₂, …, х₅₀ найти минимальный и
   помножить на него все отрицательные элементы,
   стоящие левее этого минимального.
8. Дана последовательность чисел d₁, d₂,
   …, d₅₀. Найти сумму S₁ элементов до
   максимального элемента и сумму S₂
   элементов, расположенных правее него.
9. В данном массиве чисел а₁, а₂, …, а₂₅
   поменять местами минимальный и максимальный
   элементы.
10. Найти сумму положительных элементов
    последовательности d₁, d₂, …, d₄₀,
    расположенных до первого нулевого элемента,
    заменить этой суммой минимальный элемент
    массива.
11. Из отрицательных элементов массива х₁, х₂
    …, x₃₀, расположенных левее минимального
    элемента, сформировать новый массив.
12. Из элементов последовательности у₁, у₂,
    …, у₂₅, расположенных между первым нулевым и
    максимальным (в предположении, что в массиве есть
    положительные числа) (или максимальным и первым
    нулевым), сформировать новый массив.
13. Дан массив чисел а₁, а₂, …, а₅₀.
    Найти сумму элементов массива, стоящих правее
    первого положительного элемента, и максимальный
    элемент, его номер среди чисел предшествующих
    первому положительному.
14. В массиве у₁, у₂, …, у₂₅ поменять
    местами минимальный элемент с первым
    положительным элементом.
15. Среди элементов последовательности а₁, а₂,
    …, а₂₅ расположенных до первого
    отрицательного элемента, найти минимальный
    элемент. Из положительных элементов массива,
    расположенных правее минимального, сформировать
    новый массив.
16. Три отрицательных элемента массива b₁, b₂,
    …, b₂₅, расположенных правее максимального
    помножить на номер максимального элемента.
17. Дан массив х₁, х₂, …, х₃₀.
    Помножить элементы массива на квадрат его
    наименьшего элемента, если х_i больше или
    равно 0, и на квадрат его наибольшего элемента,
    если х_i меньше 0.
18. Дана последовательность t₁, t₂, …, t₂₀.
    Среди положительных элементов найти
    максимальный и помножить на него все
    положительные элементы последовательности.
19. Из элементов последовательности с₁, с₂,
    с₃ …, с₄₅, стоящих на нечетных местах и
    расположенных правее минимального элемента
    данной последовательности, сформировать новый
    массив d₁, d₂, …
20. В массиве чисел х₁, х₂, …, х₁₇
    заменить нулем все отрицательные элементы,
    предшествующие его максимальному элементу.
21. Дана последовательность чисел а₁, а₂,
    …, а₂₅; из положительных элементов данной
    последовательности, расположенных до
    минимального элемента, сформировать
    последовательность р₁, p₂, p₃…
22. Из массива у₁, у₂, …, у₅₀
    сформировать новый массив в₁, в₂, в₃,
    …, в который записать все числа, находящиеся в
    массиве у между его максимальным и минимальным
    (или минимальным и максимальным) элементами.
23. Из массива х₁, х₂, …, х₃₀
    получить массив у₁, у₂, …, у_n
    состоящий из элементов массива х, расположенных
    правее его максимального элемента.
24. Если наименьший элемент данной
    последовательности х₁, х₂, …, х₂₇
    больше 0,1 то все отрицательные элементы
    последовательности заменить единицей.
25. Найти наименьший элемент из элементов
    последовательности x₁, x₂, …, x₂₅,
    расположенных до первого отрицательного числа.
    Все отрицательные числа, расположенные правее
    первого отрицательного, помножить на этот
    наименьший.
26. В последовательности у₁, у₂, …, у₂₅
    найти максимальный элемент из элементов, стоящих
    на четных местах. Помножить на него все элементы
    данной последовательности, стоящие на нечетных
    местах и расположенные правее найденного
    максимального.

Используя
команды повторения можно коротким
алгоритмом описать большой объем
действий, необходимых для решения
поставленной задачи. Массивы играют
аналогичную роль по отношению к данным
и позволяют коротким алгоритмом описать
действия с огромным объемом информации.

Применение массивов
при описании алгоритмов решения
практических задач позволяет:

1. записать коротким
   алгоритмом работу с большим объемом
   информации;

2. расширить область
   применимости алгоритма.

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

Массив
– это
упорядоченная по индексам, конечная
совокупность однотипных объектов,
образованных по одному и тому же правилу.
Отношение порядка в массиве задается
с помощью индексирования элементов
массива. Если для индексирования массива
используется один индекс, то массив
называется одномерным, если два или
больше, то многомерным. Для индексации
элементов двумерного массива указываются
два индекса, первый индекс, как правило,
номер строки, второй – номер столбца.
Одномерный массив часто называют
вектором, двумерный – матрицей.

При работе с
массивами, каждому массиву дается имя.
Работа с массивом – это работа с
элементами массива. Элементу массива
дается имя, соответствующее имени
массива, и указывается в квадратных или
круглых скобках порядковый номер этого
элемента в массиве.

Очевидно, чтобы
задать массив (таблицу), необходимо:

1. указать, что
   однотипные объекты объединены в массив
   (таблицу);

2. указать имя
   массива (таблицы), начальный и конечный
   порядковые номера индексов его (её)
   элементов;

3. указать тип
   значений элементов массива (таблицы).

При описании
массива после имени массива будем в
круглых (квадратных) скобках указывать
начальный и конечный номера каждого
индекса элементов массива через
двоеточие. Если массив многомерный, то
описание начального и конечного номеров
каждого индекса элементов массива
разделим запятой. Например, А(1:50) –
массив, элементы которого: А(1), А(2), … ,
А(50); В(1:2,1:3) – массив, элементы которого:

.

Пример 1.
Одномерный массив Осадки (1:365) –
количество осадков в течение года.

Пример 2.
Двумерный массив Расписание (1:4,1:2) –
расписание уроков на 2 дня в 4 классе
общеобразовательной школы.

Массивы
имеют размер и размерность. Размер
массива –
это количество
элементов
в данном массиве, размерность
– количество
индексов,
необходимых для однозначного определения
места фиксированного элемента массива.
Массив примера 1 имеет размерность,
равную 1 (одномерный), размер – 365. Массив
примера 2 имеет размерность равную 2
(двумерный), размер 2∙4=8. Элемент массива
называется переменной с индексом,
переменная без индекса – простой
переменной. Над элементами массива
можно производить те операции, которые
допустимы для базового типа.

В
качестве типов индексов элементов
массива можно использовать целый тип.
Индексы могут задаваться константами,
переменными и выражениями. Значения
переменных и выражений задают номер
элемента массива, поэтому их значения
должны быть определены при обращении
к этому элементу. Элементами массива
могут быть значения любого типа данной
реализации языка.

Пример 3.
Пусть массив A
– одномерный массив, имеющий 4 элемента
целого типа – integer:
-12, 0, 41, -131.

направление изменения
индекса

1
2 3 4

A[1]=-12;
если
i=2,
то
A[i]=0;
если
i=1,
j=3,
то
A[i+j]=-131

Пример 4.
Массив Q
– двумерный массив, имеющий 3 строки и
4 столбца – 12 элементов вещественного
типа – real:

.

направление изменения второго индекса

1 2 3 4

н

аправление

изменения

первого

и
ндекса

Q[3,3]=-28;
если
i=1,
j=2,
s=2,
то
Q[i∙s,j+2]=Q[2,4]=5,121

З
адача
21. Произведение
элементов массива. Составьте блок-схему
алгоритма нахождения произведения
вещественных чисел

П =
a(1)a(2)…a(n).

Решение.
Смотри
блок-схему алгоритма (задача 21),
использована циклическая структура
«while
P
do
S».

Произведение можно
находить так:

П:=а(1); П:=Па(2);
… ; П:=Па(n).

В блок-схеме вместо
этой цепочки операторов запишем оператор
П:=Па(k),
где k
изменяется от 1 до n;
k
– параметр цикла. Чтобы значение первого
произведения было равно a₁,
следует положить начальное значение П
равным 1. Операторы 5-6 составляют тело
цикла.

Задача 22.
Произведение матриц. Составьте блок-схему
нахождения произведения матрицы А
на матрицу В:

,

.

Решение.
Смотри блок-схемы 1-3 алгоритма (задача
22).

Смотри блок-схему
1 (задача 22). Произведение матрицы А
на матрицу
В
есть матрица-столбец; обозначим ее С.

,
где

,
i=1,2,…,m.

Функциональный
блок, вычисляющий величину c(i),
обозначим S₁.
Смотри блок-схему 2 (задача 22).

П


олучать
элементы c(i)
при фиксированном i
можно так: c(i) = c(i)+a(i,j)∙b(j),
где 1jn,
а начальное значение c(i)
равно 0.

Очевидно, что
функциональный блок S₁
будет содержать циклическую структуру,
например, структуру «repeat
S
until
P».

Подставив
детализацию блока S₁
(блок-схема 2 (задача 22)) в блок-схему 1
(задача 22), получим одну циклическую
структуру внутри другой, вложенные
циклы – блок-схема 3(задача 22).

Задача
23.
Положительные числа. Дана числовая
последователь­ность a₁,
a₂,
… , a_n.
Определите, есть ли среди a_i,
1in
положительные числа, если да, то
переменной K
присвойте значение 1, в противном случае
– значение 0. Составьте блок-схему
алгоритма решения поставленной задачи.

Решение.
Смотри блок-схему алгоритма (задача
23).

Б

лок-схема
алгоритма
(задача
23):
Блок-схема
алгоритма (задача
24):

Поскольку
положительный элемент может оказаться
на i-ом
месте, где i<n,
то нужно иметь возможность выйти из
цикла при i<n.
С этой целью перед началом цикла
переменной K
присвоено значение 0, а если a_i>0
– истинно, K
получит значение 1. Проверка окончания
организована так, что выход из цикла
произойдёт или при i>n
(положительного элемента нет), K
= 0, или при
i>n
и K = 1
(этот элемент – последний в массиве),
или при i<n
и K
= 1 (положительный
элемент – a_i,
где 1in—1).

Задача 24.
Поиск
буквы. Пусть w
– слово, состоящее из n
букв русского алфавита: w(1),
w(2),
… , w(n);
v
– буква, относительно которой требуется
установить, входит ли она в слово. Если
входит, то укажите номер позиции первого
вхождения буквы в слово. Составьте
блок-схему алгоритма решения поставленной
задачи.

Решение.
Смотри блок-схему алгоритма (задача
24).

Будем просматривать
последовательно все буквы данного
слова. Для реализации этого используем
цикл с постусловием. Если буква v
не входит в слово, то выход из цикла
осуществляется при i>n,
где i
– номер рассматриваемой буквы. Значение
переменной K
в этом случае равно 0. Если буква v
входит в слово, выход из цикла может
быть осуществлен раньше, чем i
станет больше n,
при K<>
0, где K
– номер позиции первого вхождения
буквы v
в слово w.

Задача 25.
Количество
положительных элементов. Дана
последовательность чисел a₁,
a₂,
… , a_n.
Присвойте переменной m
номер K-го
положительного элемента этой
последовательности. Если в последовательности
положительных элементов меньше K,
то переменной m
присвойте значение 0. Составьте блок-схему
алгоритма решения поставленной задачи.

Решение.
Смотри блок-схему алгоритма (задача
25).

Подсчет
количества положительных элементов
массива организуем с помощью цикла с
постусловием. Если положительных
элементов нет или их меньше, чем K,
выход из
цикла осуществим при i>n,
m
присвоим значение 0. При l
= K,
где l
– число положительных элементов, также
реализуем выход из цикла. При этом i
получит уже следующее значение. Значит,
номер K-го
положительного элемента на единицу
меньше i.

Задача 26.
Сдвиг в
массиве.
Переставьте вещественные элементы
массива A(1:n)
таким образом, чтобы они шли в следующем
порядке: А(n),
А(1), А(2), … , A(n-2),
A(n-1),
т.е. в массиве произведите сдвиг элементов
на одну позицию вправо. Составьте
блок-схему алгоритма решения поставленной
задачи.

Решение.
Смотри блок-схему алгоритма (задача
26).

Б
лок-схема
алгоритма (задача
25):
Блок-схема
алгоритма (задача
26):

Задача 27.
Максимальные
элементы массива. Дана последовательность
чисел a₁,
a₂,
… , a_n.
Найдите количество максимальных
элемен­тов последовательности и их
номера. Составьте блок-схему решения
поставленной задачи.

Решение.
Смотри блок-схемы 1-2 алгоритма (задача
27).

В
блок-схеме1 алгоритма (задача 27) первый
цикл организуем для определения
максимального элемента, значение
которого присваивается переменной b.
Начальное значение b
положим равным a₁.
Второй
цикл считает K
– количество одинаковых максимальных
элементов. Переменная M(K)
принимает значение индекса встретившегося
максимального элемента. M(K)
– числовая последовательность, членами
которой являются эти индексы.

Б

лок-схема1
алгоритма (задача
27):
Блок-схема2
алгоритма (задача
27):

Блок-схема2
алгоритма (задача 27) предполагает в
одном цикле на i-ом
шаге определение максимального элемента
из i
рассмотренных, подсчет количества
таких элементов и фиксирование их
номеров. Если на (i+1)-ом
шаге встречается больший элемент, то
операторы b:=a_i,
K:=1,
m_K:=i
зададут новые начальные значения
переменных b,
K,
m_K,
и все вычисления будут проведены
относительно нового большего элемента.

Задача 28.
Дружественные числа.
Дружественными
числами называются два натуральных
числа, таких, что каждое из них равно
сумме всех натуральных делителей
другого, исключая само это другое число.
Числа 220 и 284 являются дружественными
числами, так как сумма делителей числа
220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 =
284, а сумма делителей числа 284 – это 1 +
2 + 4 + 71 + 142 = 220. Составьте блок-схему
алгоритма нахождения дружественных
чисел на отрезке [2;n].

Решение.
Смотри блок-схему алгоритма (задача
28).

Блок-схема
алгоритма (задача
28):

С
уммы
делителей чисел от 2 до n
организуем в виде массива Делитель(2:n),
где Делитель(k)
– текущая сумма делителей числа k.
Вычислим суммы делителей всех чисел
от 2 до n,
затем попарно сравним эти суммы, если
суммы делителей чисел k
и s,
принадлежащих [2;n],
равны, то числа k
и s
– дружественные, их необходимо вывести.

Н
екоторые
пары дружественных чисел:
220 и 284,
1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368 и т.д.

Задача 29.
Группировка.
Дан массив A(1:n),
элементы которого отличны от нуля.
Расположите их в таком порядке, чтобы
первыми были все положительные элементы,
а затем – все отрицательные, причем
порядок следования как положительных,
так и отрицательных элементов должен
сохраняться. При решении задачи нельзя
заводить новую таблицу. Составьте
блок-схему алгоритма решения поставленной
задачи.

Решение.
Смотри блок-схемы 1-2 алгоритма (задача
29).

Для решения
поставленной задачи будем перебирать
элементы массива с первого по n-ый.
Если A(i)>0,
никаких изменений в массиве не производим,
увеличиваем i
на единицу и переходим к исследованию
следующего элемента. Если же A(i)<0,
поставим его на n-ое
место (в конец таблицы), предварительно
освободив это n-ое
место, произведя сдвиг элементов массива
от A(i+1)
до A(n)
на один номер влево. Количество
просмотренных элементов массива будем
запоминать в переменной k.

Д
етализируем
блок «сдвиг влево на одну позицию и
перестановку A(i)
на n-ое
место»: скопируем A(i)
в переменную C,
произведем сдвиг и A(n)
присвоим значение C.
Смотри блок-схему2 алгоритма (задача
29).

Теперь детализированный
блок можно подставить в блок-схему1
алгоритма (задача 29).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Здесь приведены примеры программ и алгоритмов, используемых в курсе Основы программирования для студентов 1 курса ФИИТ мехмата ЮФУ

Редактировать

Методы и операции для работы с массивами

Объявление и выделение памяти

  var n := ReadInteger;
  var a: array of integer;
  a := new integer[n];

или

  var n := ReadInteger;
  var a := new integer[n];

Ввод-вывод

  var a := ReadArrInteger(n);
  var r := ReadArrReal(n);
  Print(a);
  a.Println;
  a.Println(', ');

Заполнение

  a := |1,3,7|;
  a := Arr(1..10);
  a := ArrFill(10,666);
  a := ArrGen(n,i->elem(i)[,from:=0])
  a := ArrGen(n,first,x->next(x))
  a := ArrGen(n,first,second,(x,y)->next(x,y))

Примеры:

a := ArrGen(10,1,x -> x + 2); // 1 3 5 7 9 11 13 15 17 19
a := ArrGen(10,1,x -> x * 2); // 1 2 4 8 16 32 64 128 256 512 
a := ArrGen(10,1,1,(x,y) -> x + y); // 1 1 2 3 5 8 13 21 34 55 

Заполнение случайными числами

  a := ArrRandomInteger(n[,from,to]);
  r := ArrRandomReal(n[,from,to]);

Срезы

  var a := Arr(0..9);
  a[2:5]    // 2 3 4 
  a[:2]     // 0 1
  a[5:]     // 5 6 7 8 9 
  a[:]      // копия массива a
  a[::2]    // 0 2 4 6 8
  a[1::2]   // 1 3 5 7 9
  a[5:2:-1] // 5 4 3
  a[::-1]   // 9 8 7 6 5 4 3 2 1 0

Операции + и *

  var a := |1,2,3|;
  var b := |4,5,6|;
  a + b // 1 2 3 4 5 6
  a * 2 // 1 2 3 1 2 3
  |0|*3 + |1|*3 // 0 0 0 1 1 1 
  (|0| + |1|)*3 // 0 1 0 1 0 1

Циклы по массиву

For

for var i:=0 to a.Length-1 do
  a[i] += 1;

Foreach

foreach var x in a do
  Print(x);

Foreach по индексам

foreach var i in a.Indices do
  a[i] *= 2;

Foreach по определённым индексам

foreach var i in a.Indices(x -> x in 10..20) do
  a[i] += 1;

foreach var i in a.Indices((x,i) -> i.IsEven and (x > 0)) do
  a[i] += 1;

Инвертирование

Задача. Инвертировать массив

Решение 1. Алгоритм

procedure Reverse<T>(a: array of T);
begin
  var n := a.Length;
  for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
end;

Решение 2. С помощью срезов

Решение 3. С помощью стандартной процедуры

Поиск

Задача. Есть ли в массиве a элемент x

Решение. С помощью операции in или метода Contains:

Задача. Найти индекс первого вхождения элемента x

Решение 1. С использованием break

function IndexOf<T>(a: array of T; x: T): integer;
begin
  Result := -1;
  for var i := 0 to a.High do // a.High = a.Length - 1
    if a[i] = x then
    begin
      Result := i;
      break;
    end;
end;

Решение 2. Без использования break

function IndexOfW<T>(a: array of T; x: T): integer;
begin
  var n := a.Length;
  var i := 0;
  while (i<n) and (a[i]<>x) do
    i += 1;
  Result := i=n ? -1 : i;
end;

Решение 3. Поиск с барьером

Добавим в конец массива барьер, равный x. В массиве должно быть место под этот элемент

function IndexOfWithBarrier<T>
  (a: array of T; n: integer; x: T): integer;
begin
  Assert((0 < n) and (n < a.Length));
  a[n] := x; // барьер
  var i := 0;
  while a[i]<>x do
    i += 1;
  Result := i=n ? -1 : i;
end;

За счет использования барьера экономится одна операция сравнения

Решение 4. Стандартные методы

a.IndexOf(x)
a.LastIndexOf(x)

Поиск по условию

Задача. Поиск по условию

Решение 1. Алгоритм

function FindIndex<T>(a: array of T; cond: T->boolean): integer;
begin
  Result := -1;
  for var i := 0 to a.High do
    if cond(a[i]) then
    begin
      Result := i;
      break;
    end;
end;

Решение 2. С помощью стандартного метода

Количество по условию

Задача. Количество элементов, удовлетворяющих заданному условию

Решение 1. Алгоритм

function Count<T>(a: array of T; cond: T->boolean): integer;
begin
  Result := 0;
  foreach var x in a do
    if cond(x) then
      Result += 1;
end;

Решение 2. С помощью стандартного метода

Минимумы-максимумы

Задача. Найти минимальный элемент и его индекс

Решение 1. Алгоритм

function MinElemAndIndex(a: array of real): (real,integer); 
begin
  var (min, minind) := (real.MaxValue, -1);  
  for var i:=0 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);
  Result := (min, minind)
end;

Решение 2. С помощью стандартной функции

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

Решение. Алгоритм

function MinElemAndIndexCond(a: array of real: cond: real -> boolean): 
  (real,integer); 
begin
  var (min, minind) := (real.MaxValue, -1);  
  for var i:=0 to a.Length-1 do
    if (a[i]<min) and cond(a[i]) then
      (min, minind) := (a[i], i);
  Result := (min, minind)
end;

Сдвиги

Задача. Сдвиг влево на 1

Решение 1. Алгоритм

procedure ShiftLeft<T>(a: array of T);
begin
  for var i:=0 to a.Length-2 do
    a[i] := a[i+1];
  a[a.Length-1] := default(T);
end;

Решение 2. С помощью срезов

Задача. Сдвиг вправо

Решение 1. Алгоритм

procedure ShiftRight<T>(a: array of T);
begin
  for var i:=a.Length-1 downto 1 do
    a[i] := a[i-1];
  a[0] := default(T);
end;

Решение 2. С помощью срезов

a := |0| + a[:a.Length-1];

Задача. Циклический сдвиг вправо

Решение 1. Алгоритм

procedure CycleShiftRight<T>(a: array of T);
begin
  var v := a.Last;
  for var i:=a.Length-1 downto 1 do
    a[i] := a[i-1];
  a[0] := v;  
end;

Решение 2. С помощью срезов

var m := a.Length-1;
a := a[m:] + a[:m];

Задача. Циклический сдвиг влево на k

Решение 1. С помощью срезов

Решение 2. С помощью частичного Reverse

Reverse(a,0,k);
Reverse(a,k,a.Length-k);
Reverse(a);

Преобразование элементов

Задача. Требуется преобразовать элементы массива по правилу $$x -> f(x)$$

Решение 1. Алгоритм

procedure Transform<T>(a: array of T; f: T -> T);
begin
  for var i:=0 to a.Length-1 do
    a[i] := f(a[i]);
end;

Решение 2. С помощью стандартного метода

Для преобразования части элементов:

a.Transform(x -> if x mod 2 = 0 then x*x else x)

Слияние

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

В массивах должно быть место под один барьерный элмент

function Merge(a,b: array of real; n,m: integer): 
  array of real;
begin
  Assert((0 < n) and (n < a.Length));
  Assert((0 < m) and (m < b.Length));
  a[n] := real.MaxValue; // барьер
  b[m] := real.MaxValue; // барьер
  SetLength(Result,m+n);
  var (ia,ib) := (0,0);
  for var ir:=0 to n+m-1 do
    if a[ia]<b[ib] then
    begin
      Result[ir] := a[ia]; 
      ia += 1;
    end
    else
    begin
      Result[ir] := b[ib]; 
      ib += 1;
    end;
end;

Бинарный поиск

Задача. Поиск в упорядоченном массиве

Решение 1. Алгоритм

function BinarySearch(a: array of integer; x: integer): integer;
begin
  var k: integer;
  var (l,r) := (0, a.Length-1); 
  repeat
    k := (l+r) div 2;
    if x>a[k] then
      l := k+1
    else r := k-1;
  until (a[k]=x) or (l>r);
  Result := a[k]=x ? k : -1;
end;

Асимптотическая сложность $$Theta(log n)$$

Решение 2. С помощью стандартного метода

Алгоритмы сортировки

Сортировка выбором

procedure SortByChoice(a: array of integer);
begin
  for var i := 0 to a.High-1 do
  begin
    var min := a[i];
    var imin := i;
    for var j := i + 1 to a.High do
      if a[j] < min then
      begin        
        min := a[j];
        imin := j;
      end;  
    Swap(a[imin],a[i]);
  end;
end;

С использованием срезов:

procedure SortByChoice(a: array of integer);
begin
  for var i := 0 to a.High-1 do
    Swap(a[a[i:].IndexMin + i],a[i]);
end;

Асимптотическая сложность $$Theta(n^2)$$

Пузырьковая сортировка

procedure BubbleSort(a: array of integer);
begin
  for var i := 0 to a.High-1 do
    for var j := a.High downto i+1 do
      if a[j] < a[j-1] then
        Swap(a[j], a[j-1]);
end;

Асимптотическая сложность $$Theta(n^2)$$

С флагом (эффективнее в ситуациях, когда массив частично отсортирован):

procedure BubbleSort2(a: array of integer);
begin
  var i := a.High;
  var q: boolean;
  repeat
    q := true;
    for var j := 0 to i - 1 do
      if a[j+1] < a[j] then
      begin
        Swap(a[j+1], a[j]);
        q := false;
      end;
    i -= 1;
  until q;
end;

Асимптотическая сложность $$Theta(n^2)$$ в среднем и $$Theta(n)$$) в лучшем случае (когда массив отсортирован).

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

procedure SortByInsert(a: array of integer);
begin
  for var i:=1 to a.High do
  begin
    var x := a[i];
    var j := i - 1;
    while (j >= 0) and (x < a[j]) do
    begin
      a[j+1] := a[j];
      j -= 1;
    end;
    a[j+1] := x;
  end;
end;

Асимптотическая сложность $$Theta(n^2)$$

Стандартная сортировка

Асимптотическая сложность $$Theta(n cdot log n)$$

Методы и операции для работы cо списками List

Список List<T> – это динамический массив с возможностью динамического изменения размеров по ходу работы программы.

Объявление списка:

var l := new List<integer>;

Добавление элементов в конец списка:

l.Add(5); // список расширяется, выделяя память под новые элементы
l.Add(3);
l.Add(4);
l += 8; // синоним l.Add(8)

Цикл по списку:

for var i:=0 to l.Count-1 do
  Print(l[i]);
foreach var x in l do
  Print(x);

Заполнение списка:

var l := Lst(5,2,3); 
var l1 := Lst(1..10); 

Операции со списками:

var l := Lst(5,2,3); 
Print(2 in l); // True
Print(2 * l); // [5,2,3,5,2,3]
l.Print; // 5 2 3
Print(l + Lst(7,6,8)); // 5 2 3 7 6 8

Методы списков:

l.Insert(ind,x); // вставка x по индексу ind
l.RemoveAt(ind); // удаление элемента по индексу ind
l.RemoveRange(ind,count) // удаление диапазона элементов
l.RemoveAll(x -> x.IsOdd); // возвращает число удалённых элементов
l.IndexOf(3); // индекс первого вхождения или -1
l.FindIndex(x -> x > 4); // индекс первого вхождения или -1
l.Clear; // очищает список
l.Reverse; // инвертирует список
l.Sort; // сортирует список

Реализация функции Distinct

Задача. Реализовать функцию Distinct, по заданному массиву возвращающая список только различных элементов массива

Решение. Алгоритм

function Distinct(a: array of T): List<T>;
begin
  Result := new List<T>;
  foreach var x in a do
    if not (x in Result) then
      Result += x;
end;

Вставка и удаление элементов в массиве и списке

Задача. Дан массив (список) $$N$$ вещественных. Требуется вставить элемент $$x$$ на $$k$$-тое место (начиная с 0), $$k leq N$$.

Решение. В массиве — с помощью срезов:

var N := ReadInteger;
var a := ReadArrInteger(N);
var l := Lst(a);
var k := ReadInteger;
a := a[:k] + |x| + a?[k:]; 

Решение. В списке — с помощью стандартного метода:

Задача. Дан массив (список) $$N$$ вещественных. Требуется удалить элемент с индексом $$k$$, $$k<N$$.

Решение. В массиве — с помощью срезов:

var N := ReadInteger;
var a := ReadArrInteger(N);
var l := Lst(a);
var k := ReadInteger;
a := a[:k] + a?[k+1:]; 

Решение. В списке — с помощью стандартного метода:

Вопросы:

·     Поиск
элемента массива с заданным значением.

·     Сортировка
элементов массива.

Часто при решении
некоторых задач требуется найти элемент массива со значением, равным чему-либо.

Задача: Написать
программу, которая определяет, есть ли в массиве из 100 случайных целых чисел,
на промежутке от 1 до 200, число, введённое пользователем.

Начнём написание
программы для решения задачи. Назовём нашу программу zadannoe_chislo.
Для работы программы нам потребуется массив из 100 элементов. Назовём его a.
Так как элементами массива будут целые числа на промежутке от 1 до 200, укажем
тип элементов массива byte.
Также нам понадобятся переменные для хранения номера текущего элемента — i
и для хранения числа, введённого пользователем — num.
Объявим принадлежащими к целочисленному типу byte.

Напишем логические
скобки. Тело программы будет начинаться с оператора writeln,
который будет выводить на экран сообщение о том, что это программа,
определяющая, есть ли в массиве случайных чисел число, введённое пользователем.
Теперь запишем цикл для заполнения массива случайными числами. Это будет цикл для
i, изменяющегося от 1 до 100. В нём
будет оператор присваивания i-тому
элементу массива a, суммы случайного
целого числа на промежутке от 0 до 199 и 1. После того как мы заполнили массив
случайными числами, напишем оператор write,
выводящий на экран запрос на ввод числа на промежутке от 1 до 200, а также
оператор readln для считывания
значения переменной num.

Для того чтобы
определить, есть ли введённое число в массиве a,
мы позже опишем логическую функцию, которую назовём poisk,
поэтому сейчас напишем условный оператор if,
условием которого будет значение функции poisk,
с введённым числом num
в качестве аргумента. После служебного слова then
в этом условном операторе, напишем оператор writeln,
выводящий на экран сообщение о том, что число num
есть в массиве. После слова else
также напишем оператор writeln,
который будет выводить на экран сообщение о том, что числа num нет в
массиве.

Для того чтобы
пользователь могу убедиться в том, что программа работает правильно, напишем
оператор write, выводящий
сообщение о том, что это массив, а также цикл с для i
для вывода элементов массива через пробел. На этом описание основной программы
завершено.

program zadannoe_chislo;

var

 a: array [1..100] of
byte;

 i, num: byte;

begin

 writeln (‘Программа, определяющая, есть ли в массиве случайных чисел число,
введённое пользователем.’);

 for i:=1 to 100
do

  a[i]:=random (200)+1;

 write (‘Введите число на промежутке [1;
200]>>> ‘);

 readln (num);

 if poisk (num)

 then write (‘Число ‘, num, ‘ есть в
массиве.’)

 else write (‘Числа ‘, num, ‘ нет в массиве.’);

end.

Заголовок,
переменные и операторный блок основной программы

Теперь рассмотрим, как же
проверить, есть ли в массиве Элемент с указанным значением. Для этого будем
проверять последовательно все элементы массива от первого к последнему, пока не
найдём нужный или же пока они не закончатся. Такой поиск элемента в массиве
называется линейным.

Напишем для нашей
программы логическую функцию, определяющую, есть ли в массиве a
заданное число. Как мы помним, она должна называться poisk.
Эта функция должна иметь один аргумент целочисленного типа byte,
назовём его t. Также функция
должна возвращать значение логического типа boolean.
Для работы функции нам потребуется дополнительная переменная, которая будет
хранить номер текущего элемента массива. Назовём её i
и укажем принадлежащей к целочисленному типу byte.
В логических скобках опишем операторный блок функции. В его начале присвоим
переменной i начальное значение – 0.
Дальше напишем цикл с постусловием. Условием окончания работы цикла будет то,
что i-тый Элемент массива a
равен t или что достигнут конец
массива и i равно 100. Тело цикла
будет содержать единственный оператор, увеличивающий значение переменной i
на 1. После завершения работы цикла нам будет достаточно проверить равен ли i-тый
элемент массива a t
и присвоить значение истинности этого высказывания переменной функции poisk.
На этом описание функции закончено.

function poisk (t: byte): boolean;

var

 i: byte;

begin

 i:=0;

 repeat

  i:=i+1;

 until (a[i]=t) or (i = 100);

 poisk:=a[i]=t;

end;

Функция poisk

Запустим программу на
выполнение. Введём число 75.
Программа вывела сообщение о том, что такое число есть в массиве. Просмотрев
элементы массива, мы можем убедиться, что такое число действительно в нём есть.

Снова запустим программу
и введём число 120. Программа вывела сообщение о том, что такого числа нет в
массиве. Программа работает правильно. Задача решена.

Рассмотрим функцию poisk.
Очевидно, что в лучшем случае при её выполнении будет выполнена 1 проверка, а в
худшем – 100. Это не очень много, но предположим, что у нас есть программа,
которая будет выполнять поиск тысячи или даже миллионы раз. Тогда для этого
может потребоваться много времени, но поиск в массиве можно организовать проще,
если элементы массива расположены в соответствии с некоторыми правилами,
например, по возрастанию или по убыванию своих значений.

Мы можем изменить порядок
следования элементов массива, отсортировав их. Сортировкой элементов массива
называется изменение порядка их следования в соответствии с некоторыми
правилами. По значениям элементы массива можно отсортировать разными способами.
Рассмотрим наиболее распространённые. Если в массиве не может быть равных
элементов, то его можно отсортировать по возрастанию или по убыванию.
Если же в массиве могут быть равные элементы, то его можно отсортировать по
неубыванию или по невозрастанию.

Варианты
сортировки элементов массива

Как же можно
отсортировать элементы массива, например, по возрастанию. Мы можем
последовательно проверять все пары элементов массива, расположенных рядом, то
есть первый и второй, второй и третий и так далее. Если в паре элементы
расположены не по возрастанию, то их нужно менять местами. Таким образом,
постепенно все элементы массива станут расположены по возрастанию. Такой способ
сортировки называется методом пузырька. Он был назван так потому, что
подобно пузырькам воздуха в стакане воды, элементы массива с наименьшими
значениями перемещаются в начало массива.

Итак, что же нужно
сделать чтобы отсортировать массив по возрастанию методом пузырька… Вначале предположим,
что элементы массива уже расположены по возрастанию. Дальше будем
последовательно проверять пары элементов массива. Если найдём пару, в которой
элементы расположены не по возрастанию, то мы опровергнем начальное
предположение о том, что элементы уже расположены по возрастанию. Мы поменяем
местами элементы массива в паре, и продолжим проверять его дальше. После того,
как мы проверили все пары элементов массива мы должны проверить, осталось ли
наше начальное предположение о том, что элементы массива расположены по
возрастанию не опровергнутым. Если предположение было опровергнуто – мы начнём
выполнять алгоритм сначала, в противном случае – алгоритм завершит свою работу.
Когда после завершения работы алгоритма начальное положение останется не опровергнуто
алгоритм завершит свою работу.

Для написанной нами
программы для поиска элементов массива напишем процедуру сортировки элементов
массива a но не убыванию. Назовём
её sort. Для работы
процедуры нам нужна переменная для хранения, номера текущего элемента массива –
i и переменная для хранения одного из
элементов массива, когда мы будем менять их местами – k,
а также логическая переменная – p.
Напишем программный блок процедуры. В нём будет цикл с постусловием, в качестве
условия завершения работы которого будет значение логической переменной p.
Тело цикла будет начинаться с того что мы предположим, что элементы массива уже
расположены по возрастанию. Для этого переменной p
мы присвоим значение true.
Дальше будет следовать цикл с параметром i,
изменяющимся от 1 до 99. Это будет цикл для проверки пар элементов массива. В
нём будет условный оператор, который проверяет расположены ли элементы массива
с индексами i и i
+ 1
не по неубыванию. То есть что a[i]
> a[i
+ 1].
Если это условие выполняется, мы должны поменять эти два элемента массива
местами. Для этого после слова then
в логических скобках запишем четыре оператора присваивания: переменной p
– значения false, так как мы
опровергли начальное предположение, переменной k
– значения a[i],
a[i]
– значение a[i
+ 1],
a[i
+ 1]
– значение переменной k.
Таким образом, мы опровергли начальное предположение и поменяли местами
элементы массива с индексами i
и i + 1.
На этом описание процедуры завершено.

procedure sort ();

var

 p: boolean;

 i, k: byte;

begin

 repeat

  p:=true;

  for i:=1 to 99
do

   if a[i]>a[i+1]

   then begin

    p:=false;

    k:=a[i];

    a[i]:=a[i+1];

    a[i+1]:=k;

   end;

 until p;

end;

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

В программном блоке
основной программы перед запросом на ввод числа запишем вызов процедуры sort.
Запустим программу на выполнение. Зададим число 28.
Программа вывела сообщение о том, что это число есть в массиве. Просмотрев
элементы массива, мы можем убедиться в том, что они действительно отсортированы
по невозрастанию.

Программа работает
правильно. Обратим внимание, что для того, чтобы отсортировать элементы массива
по невозрастанию достаточно изменить знак больше в условном операторе в
процедуре сортировки на противоположный знак меньше.

Теперь рассмотрим, как мы
можем организовать поиск элемента с заданным значением в массиве,
отсортированном по неубыванию. Очевидно, что элементы с наименьшим и наибольшим
значениями располагаются по краям. Для поиска элемента с заданным значением
можно использовать метод деления отрезка пополам (метод двоичной
дихотомии). Если элементы массива расположены по возрастанию, то мы можем проверить
его средний элемент. Так мы можем точно сказать где нужно искать элемент с
искомым значением. Если средний элемент массива будет меньше искомого, то
искомый элемент нужно искать после среднего, а в противном случае от первого до
среднего. Таким образом мы сократим область поиска сразу в два раза. Точно
также мы найдём средний элемент на новом промежутке поиска, сравним его с
искомым и так далее. Так будет продолжаться до тех пор, пока начальный или
конечный элемент промежутка поиска не будет равен искомому или пока промежуток
поиска не станет равен одному элементу.

В написанной нами
программе изменим функцию poisk.
В ней нам понадобится дополнительные переменные для хранения номеров первого и
последнего элемента массива на промежутке поиска, назовём их соответственно f
и l, объявим их
целочисленного типа byte.
Запишем логические скобки. Операторный блок процедуры будет начинаться с того,
что мы присвоим переменным f
и l их начальные значения,
то есть соответственно 1 и 100. Дальше мы запишем цикл с постусловием. Условием
завершения его работы будет, то что один из элементов массива с индексами f
и l равен искомому элементу t
или что промежуток поиска сузился до одного элемента, то есть f
= l.
В теле цикла будет условный оператор, который будет проверять меньше ли средний
элемент массива, с индексом равным (f
+ l) div
2,
искомого t. Если это условие
выполняется, то мы должны сократить промежуток поиска элемента. Поэтому после слова
then присвоим переменной f
значение (f
+ l) div
2 + 1. В противном случае – сократим промежуток поиска в
другом направлении и присвоим переменной l
значение (f
+ l) div
2.
После завершения работы цикла проверим, равен ли один из элементов с индексами f
и l искомому t.
И присвоим значение истинности этого высказывания переменной функции – poisk.

function poisk (t: byte): boolean;

var

 f, l: byte;

begin

 f:=1;

 l:=100;

 repeat

  if a[(f+l) div 2]<t

  then f:=(f+l) div 2
+ 1

  else l:=(f+l)
div 2;

 until (a[f]=t) or (a[l]=t)
or (f=l);

 poisk:=(a[f]=t) or (a[l]=t);

end;

Функция поиска элемента с
заданным значением методом деления отрезка пополам

Запустим программу на
выполнение. Введём число 45. Программа вывела сообщение о том, что такого числа
нет в массиве.

Снова запустим программу
и введём число 190. Программа вывела сообщение о том, что это число есть в
массиве.

Программа работает
правильно задача решена.