Алгоритм. Способы описания, характеристики и основные структуры алгоритма.
Алгоритм – это система правил описывающая последовательность действий, каторые необходима выполнить для решение задачи.
Основные структуры алгоритма:
| конц |
2. Разветвляющейся – однократное выполнение последовательности шагов, однако состав этой последовательности определяется результатами некоторого условия, то есть зависит от обрабатываемой информации
3. Циклическая обеспечивает многократное выполнение одной и той же последовательности шагов тела цикла с изменяемой информацией.
Частный случай разветвляющей структуры
Основные блоки алгоритма блок- начало/окончание
1. Блок – начало/окончание
| КОНЕЦ |
| НАЧАЛО |
2. Блок ввода/ вывода
3. Блок действия
4. Блок ветвления (условия)
| условие |
ДА НЕТ
При решение задач используются встроенные числовые функции. Приведем список наиболее часто встречающихся числовых функций:
ABS
ABS(x)
Х – любое число выражение.
Значение функции равно Х, если Х>=0, и равно – Х, если Х<0
INT
INT(x)
Х – любое число выражение.
|
|
|
Значение функции – целая часть значения аргумента, т.е. наибольшее целое число, не превосходящее Х.
SGN
SGN(x)
Х - любое числовое выражение.
Значение функции равно -1 при Х<0, равно О при Х=0 и равно 1 при Х>0.
SQR
SQR(x)
Х - неотрицательное числовое выражение.
Значение функции - корень квадратный из Х в виде вещественного числа двойной точности.
ATN
ATN(x)
Х - любое числовое выражение.
Значение функции - число с двойной точностью, равное величине (в радианах) угла, тангенс которого равен Х. Значение функции всегда расположено в интервале (-π/?,π/2).
COS
COS(x)
Х - любое числовое выражение; оно представляет угол в радианах.
Значение функции - число двойной точности, равное косинусу угла Х (угол задается в радианах).
SIN
SIN(x)
Х - любое числовое выражение.
Значение функции - число двойной точности, равное синусу угла Х (угол задается в радианах).
TAN
TAN(x)
Х - любое числовое выражение.
Значение функции - число двойной точности, равное тангенсу угла Х (угол задается в радианах).
ЕХР, ЕХР2, ЕХР10
ЕХР(х), ЕХР2(х), ЕХРЮ(х)
Х- любое числовое выражение.
Функции возвращают значения ех,2х,10х соответственно, в виде чисел двойной точности.
|
|
|
LOG, LOG2, LOG10
LOG(x), LOG2(x), LOG1O(x)
Х - любое числовое выражение.
Функции возвращают значения ln х, log 2x, Ig x, соответственно, в виде числа двойной точности. Если Х<-0, то при выполнении программы возникает ошибка.
RND
RND[(x)]
Х - любое числовое выражение.
Функция выполняется следующим образом:
• если Х>0, то функция возвращает псевдослучайное число в диапазоне [0,1), генерируемое встроенным в Турбо Бейсик датчиком равномерно распределенных случайных чисел;
• если Х=0, то датчик сохраняет старое значение;
• если Х<0, то значение -Х преобразуется в целое и используется для установки начального значения в датчике.
Массивы. Ряды. Матрицы
Понятие массивов. Объявление массивов. Обращение к элементам
Массивы представляют собой набор данных одного типа. Следовательно, в простейшем случае массив представляет собой набор переменных одного типа (базового типа). Каждая такая переменная – элемент массива. Эти переменные имеют одно имя – имя массива, но различаются порядковыми номерами. Например массив А, состоящий из 10 элементов:
А={ А1 , А2,…, А10}
В этом массиве элемент имеет один индекс (порядковый номер). Количество элементов – размер массива. Количество индексов - размерность массива. Этот массив одномерный, т.к. каждый элемент имеет только один индекс. Одномерный массив иногда называют рядом или вектором. Эти массивы могут быть разных типов. Например, если массив целочисленный, то его элементы – целые числа.
|
|
|
Массив, каждый элемент которого имеет 2 индекса – двумерный массив (матрица). Этот массив обычно представляют в виде таблицы, размером n строк на m столбцов (n*m):
А1; 1, А1; 2,…, А1; m
А2; 1, А2; 2,…, А2; m
…
Аn; 1, Аn; 2,…, Аn; m
Двумерный массив называют также матрицей. К этому массиву применяют понятия высшей математики, относящиеся к матрицам:
- Строка;
- Столбец;
- квадратная матрица (m = n);
- Главная диагональ от А1; 1 к Аn; n;
- Побочная диагональ от Аn; 1 к А1; n;
Существуют и трёхмерные и многомерные массивы, применяемые довольно редко.
Теперь, используя эту терминологию, перейдём к практике программирования, связанного с массивами и матрицами. Поскольку, массив состоит из достаточно большого числа элементов, иногда каждый элемент занимает большой объём оперативной памяти, поэтому необходимо заранее определить размер массива. Это нужно для того, чтобы компьютер мог выделить область в оперативной памяти для хранения и обработки массивов.
|
|
|
Рассмотрим объявление одномерных массивов:
DIM <имя>(<размер>)
Здесь можно определить размер массива и его имя. Под первым элементом массива можно понимать 0-й или 1-й. В Турбо - Basic можно определить, с какого элемента начинается отсчёт. Для этого нужно до объявления массива вызвать оператор OPTION BASE 0 – если первый элемент имеет номер 0, а элементы массива от 0 до <размер-1>, или OPTION BASE 1 – первый элемент массива имеет номер 1, а элементы массива от 1 до <размер>. По умолчанию отсчёт от 1.
Рассмотрим пример объявления одномерного массива A из 12 целых чисел:
Элементы от 0-го до 11-го:
OPTION BASE 0
DIM $ (12)
Элементы от 1-го до 12-го:
OPTION BASE 1
DIM $ (12)
Объявление массива, имеющие размерность от 2 и более:
DIM <имя и тип>(<размер1>,<размер2>,…,<размер n>)
Кроме того, в Турбо Basic допустимо определить размер массива до его объявления:
INPUT N
DIM A(N)
Теперь, когда массив объявлен, можно работать с его элементами. Их можно использовать как обычные переменные, т.е. присваивать им значения, употреблять в формулах и т.п.
Рассмотрим обращение к элементу массива:
<имя>(<индекс1>,<индекс2>, … , <индекс n>)
Например, для одномерного массива A к элементу A7: A(7)
Например, для одномерного массива A к элементу A7;3: A(7,3)
И несколько пример использования:
B(5)=C(6)
A(7,3)=12
S=A(2,7)+A(7,8)
IF A(7,5)>0 THEN
PRINT “положит.”
Способы заполнения массивов
После объявления массива можно полноценно работать с элементами, применять их в формулах, однако лучшем случае элементы окажутся нулями, а в общем случае их значениями окажется то, что до этого лежало в памяти.
Отсюда задача – присвоить элементам массива нужные значения. Можно решать задачу «в лоб», а именно:
A(1)=<знач.1>
A(1)=<знач.2>
…
A(<N>)=<знач.n>
Однако, если например n=1000, то программист должен вводить 1000 элементов вручную – это не удобно. Есть более простые пути заполнения.
Эти способы пригодны для массивов любой размерности.
1. Заполнение с клавиатуры:
FOR I=1 TO N
INPUT A(I)
NEXT I
Стоит заметить, что все способы будут сводиться к тому, что с помощью счётчика цикла меняются номера элементов массива. Например на 1-м шаге цикла (I=1) обслуживается первый элемент массива. На втором – второй и т.д. Когда можно иметь доступ ко всем элементам массива, можно присвоить им значения.
При заполнении с клавиатуры, каждый элемент вводит пользователь. При этом в теле цикла находится оператор ввода.
2.Заполнение по формуле.
FOR I=1 TO N
A(I)=<f(I)>
NEXT I
Суть этого способа в присваивании элементу массива значения, зависящего от индекса этого элемента (зависимость <f(i)>). В простейшем случае значение элемента равно его порядковому номеру:
FOR I=1 TO N
A(I)=I
NEXT I
3. Заполнение массива случайными значениями.
По сути это один из вариантов заполнения по формуле, однако здесь главным элементом этой формулы является значение некоторой функции – генератора случайных чисел. Суть этой функции в том, что она принимает случайное значение от 0 до 1 (для вещественных чисел) или в диапазоне заданной ширины (для целых чисел). На самом деле эти числа не совсем случайные, а псевдослучайные. Эти числа получаются при некоторой обработке текущего системного времени. Поскольку дата и время всегда разные, то создаётся иллюзия, что числа получаются случайные.
Рассмотрим реализацию генераторов случайных чисел.
Случайное число генерируется с помощью функции RND. Эта функция генерирует число от 0 до 1. Для генерации чисел на заданном интервале используем формулу:
RND*<ширина интервала>+<начало интервала>
Например: RND*12+10 – числа от 10 до 21 включительно (12 чисел).
RND*12-10 – числа от -10 до 1 включительно (12 чисел).
Для того, чтобы каждый раз при запуске программы генератор возвращал произвольные числа, в начале программы необходимо поместить строку
RANDOMIZE TIMER
Это будет означать, что получение случайных чисел основано на некоторой обработке системного времени.
Рассмотрим пример заполнения массива из 5 элементов числами от 5 до 9.
RANDOMIZE TIMER
FOR I=1 TO 5
A(I)=RND*5+5
NEXT I
4. Из файла .
Этот способ наиболее подходящий для заполнения массива конкретными значениями. Например, результаты какого-то физического эксперимента записаны в файл. Для дальнейшей обработки, данные нужно считать из файла.
Здесь мы рассматривали только одномерные массивы. С двумерными массивами всё также. Разница лишь в том, что для их обработки мы используем вложенный цикл. Внешний цикл производит переход по строкам, внутренний - по столбцам. Поскольку, на каждом шаге внешнего цикла выполняются все шаги внутреннего, то удаётся рассмотреть весь массив. Будем считать, что у нас квадратная матрица (N*N):
FOR I=1 TO N
FOR J=1 TO N
A(I,J)=<…>
NEXT J
NEXT I
В этом примере <…> - некоторый закон заполнения (формула, ввод с клавиатуры и.т.п. аналогично одномерным массивам).
Так, на первом шаге внешнего цикла (I=1) Внутренний цикл позволит работать с элементами A1,J, т.е A1,1; A1,2 … Когда цикл по J закончится, I примет новое значение I=2, тогда внутренний цикл обеспечит работу с элементами A2,J, т.е A2,1; A2,2 … В целом, это очень похоже на пример из п. 4.5. с таблицей квадратов.
При запуске этих примеров, видно, что никаких видимых результатов нет. И это понятно, так как не разу не применялся оператор вывода. Но для вывода массивов есть свои правила, отличные от вывода переменных. Очевидно, что будет использоваться цикл.
Рассмотрим способы вывода массивов:
1. В строчку. Здесь используется цикл, на каждом шаге которого используются операторы вывода, не переходящие на другую строку. Кроме того, оставляются пробелы, чтобы элементы не сливались:
FOR I=1 TO N
PRINT A(I);
NEXT I
2. В столбик . Всё также, как в сточку, только операторы вывода должны обеспечивать переход на следующую строку:
FOR I=1 TO N
PRINT A(I)
NEXT I
Эти способы относятся к одномерным массивам. Они конечно применимы для массивов большей размерности, но для двумерных массивов есть другой способ – в виде таблицы. В рамках этого способа таблицу стоит рассматривать как столбец из строк. Вложенный цикл обеспечивает работу с элементами массива построчно. Все элементы строки (внешний цикл) будем выводить в строчку. А внешний цикл обеспечивает переход между строками (в теле внешнего цикла сделаем переход на другую строку с помощью пустого оператора вывода с переходом на другую строку). Программа имеет вид:
FOR I=1 TO N
FOR J=1 TO N
PRINT A(I,J);
NEXT J
NEXT I
Теперь матрица будет выводиться на экран в виде таблицы.
Типовые задачи на массивы
Теперь, когда мы рассмотрели объявление и заполнение массивов, уделим внимание из обработке. Из прошлых пунктов мы установили, что для успешной работы с массивами их нужно:
1. Объявить;
2. Заполнить.
Если это не сделано, не о какой обработке массивов не может быть и речи.
Рассмотрим ряд задач на массивы. Вообще все задачи будут сводится к отбору элементов массива, т.е. проверке того, удовлетворяет ли данный элемент условиям.
1. Задачи на сумму чисел, удовлетворяющих определённым условиям аналогичны задачам на суммы элементов в массиве. Условный оператор, находящийся в цикле, позволит вызвать нужные элементы массива. Для примера рассмотрим суммирование положительных элементов в массиве:
S = 0
FOR I = 1 TO N
IF A(I) > 0 THEN
S = S + A(I)
NEXT I
Аналогичным образом можно решать задачи поиска элементов массива с данным значением. В них будет проверяться равенство элемента данному значению.
2. Поиск максимума и минимума в массиве. Суть этих задач в том, что вначале мы полагаем, что максимум (минимум) – первый элемент. Затем проверяем все оставшиеся элементы. Если текущий элемент больше максимума (меньше минимума), то в переменную максимум (минимум) записывается значение этого элемента. В итоге то значение, которое будет в переменной максимум (минимум) – это и есть значение максимума (минимума в массиве). Рассмотрим для примера поиск максимума. Выведем также его значение:
MAX = A(1)
FOR I = 2 TO N
IF A(I) > MAX
THEN MAX = A(I)
NEXT I
PRINT MAX
Можно также искать порядковые номера максимума (минимума).
3. Перестановка элементов в массиве. Идея перестановки заключается в том, что нужно поменять местами элементы массива (I-й и J-й). Эта задача найдёт широкое применение в сортировке массивов. На рисунке сбоку проиллюстрировано, к чему должна привести перестановка.
Казалось бы, как легко переставить элементы массива. Ну, например в Basic:
A(J)=A(I)
A(I)=A(J)
Но это не даст желаемых результатов. Суть в том, что переменную можно рассматривать как некоторую коробочку, в которой хранится значение. Когда мы присваиваем её другое значение, прежнее значение переменной уничтожается. Таким образом эти действия проиллюстрированы ниже.
Здесь уже первое действие приводит к тому, что значение A(J) теряется. Второе действие уже бессмысленно.
Для того, чтобы перестановка прошла успешно, необходимо, чтобы значение одной переменной, которое пропадает. Временно хранилось бы в третьей переменной (U) того же типа, что и переставляемые элементы массива. Тогда схему перестановки можно будет проиллюстрировать рисунком, приведённым ниже. Здесь первым шагом значение A(J) записывается в переменную U. Когда значение A(J) сохранено, можно смело записывать в неё новое значение. На втором шаге A(J)=A(I). Теперь, когда значение A(I) сохранено в A(J), можно записать значение из U в A(I).
Теперь рассмотрим программную реализацию перестановки:
U=A(J)
A(J)=A(I)
A(I)=U
Эту задачу можно расширить для случая, когда переставляются строки или столбцы двумерного массива. Для примера рассмотрим перестановку строк (I-й и J-й) в матрице (N*N):
FOR K = 1 TO N
U = A(J,K)
A(J,K) = A(I,K)
A(I,K) = U
NEXT K
4. Сортировка массивов . Сортировка – такой вид перестановки элементов массива, при котором элементы располагаются в порядке возрастания (убывания). Для примера: список студентов группы (фамилии) – массив из строковых данных (об этом в разделе 6.). Упорядочивание списка в алфавитном порядке – сортировка. Сортировка применима в основном к одномерным массивам, но возможна и для двумерных (сортировка элементов строки, сортировка строк по возрастанию максимального элемента в строке).
Мы ограничимся рассмотрением общей идеи сортировки на примере одномерных массивов. Здесь всё-таки будут написаны программы, но не надейтесь, что вы их отсюда сдерёте, сдадите в качестве лабораторной и на халяву проскочите.
Здесь мы рассмотрим два алгоритма сортировки – линейную сортировку и пузырьковую сортировку.
1. Линейная сортировка. Всё очень просто. Мы находим максимум среди элементов массива. Затем этот максимум меняем местами с первым элементов (делаем перестановку). Но, чтобы поменять местами два элемента массива, нам необходимо отслеживать индекс максимального элемента массива maxind. Затем мы ищем максимум среди остальных элементов (от 2-го до последнего) и меняем его местами со вторым элементов. Так проделываем до конца массива, т.е. пока среди остальных элементов не останется всего один.
| ДА |
| max := a[J] |
| maxind := J |
| КОНЕЦ СОРТИРОВКИ |
| Перестановка a[maxind] и a[I] |
| НЕТ |
| I = 1; <размер массива>; 1 |
| maxind := I |
| max := a[I] |
| J = I; <размер массива>; 1 |
| a(J) > max |
Пунктиром обведён фрагмент программы, направленный на поиск максимума. Остальные части были подробно рассмотрены выше.
Теперь напишем программу сортировки одномерного массива по данной блок-схеме. Стоит только пояснить, что перестановка A(I) и A(MAXIND) – перестановка I-го элемента и максимального элемента массива.
FOR J = I TO N
IF A(J) > MAX
THEN
MAX = A(J)
MAXIND = J
END IF
NEXT J
U = A(I)
A(I) = A(MAXIND)
A(MAXIND) = U
NEXT I
Однако, хочется сказать, что этот алгоритм неэффективен. Представим, что массив уже отсортирован. При этом поиск максимума окажется бесполезной работой, как и перестановка элемента с самим собой. В этом случае нужно найти другой алгоритм, который не будет работать впустую.
2.Пузырьковая сортировка. А что, если нам не искать максимум, а просто переставлять соседние элементы. Если пройти весь массив N раз, где N – размер массива, то он окажется отсортирован. Это выход, но не эффективный. Когда переставлять элементы незачем (массив отсортирован), программа совершает бесполезную работу. А что если нам при каждом прохождении массива считать, сколько было сделано перестановок, и если их не было, значит массив отсортирован и на этом можно закончить работу программы. Рассмотрим это на конкретном примере, изображённом в этой таблице. Здесь видно, что самый большой элемент постепенно поднимается вверх (к 1-му элементу). Это можно сравнить с пузырьком воздуха, поднимающимся вверх, в стакане воды.
Здесь важная величина – количество перестановок элементов массива. Суть алгоритма в следующем. Пока количество перестановок не равно 0, просматриваем все элементы со 2-го до последнего и если I-1-й (предыдущий) элемент меньше I-го (текущего), переставляем из (меняем местами). Нам не важно количество перестановок, а важно только их наличие. Индикатором наличия перестановок может служить логическая переменная. Если эта переменная равна имеет значение «ложь», значит перестановок не было, но если появится хотя бы одна перестановка, эта переменная примет значение «истина». Назовём эту переменную FLAG. Исходя из этого, составим краткую блок-схему алгоритма пузырьковой сортировки:
| НЕТ |
| ДА |
| КОНЕЦ СОРТИРОВКИ |
| ДА |
| НЕТ |
| FLAG = ложь |
| I = 2; <размер массива>; 1 |
| FLAG = ложь |
| Перестановка A(I) и A(I-1) |
| FLAG = истина |
| A(I) > A(I-1) |
Теперь напишем программу пузырьковой сортировки:
DO
FLAG = 0
FOR I = 2 TO N
IF A(I) > A(I-1) THEN
U = A(I)
A(I) = A(I-1)
A(I-1) = U
FLAG = 1
END IF
NEXT I
LOOP UNTIL FLAG=0
Напомним, что в С++ нужно писать TRUE и FALSE большими буквами, иначе это приведёт к ошибке. Здесь «==» означает равенство. В Pascal not flag означает, что flag = ложь (flag не истинно).
Напоследок рассмотрим ещё один тип задач, относящийся к двумерным массивам. Эти задачи заключаются в поиске суммы элементов, максимума и т.п. не во всём массиве, а в определённой области. Здесь обычно идёт речь о некоторой области, ограниченной некоторыми линиями. Рассмотрим самые простые примеры – область, ограниченная диагоналями матрицы.
Справа изображена картинка. На ней изображено несколько областей, главная диагональ и области сверху и снизу от главной диагонали. Вспомнив, что эта диагональ определяется условием i = j, где i-номер строки, j-номер столбца. Тогда если i > j – область находится ниже главной диагонали, если i < j – область находится сверху от главной диагонали. Если эти неравенства сделать нестрогими, тогда в эту область включается и главная диагональ (i = j). Аналогично можно нарисовать картинку для побочной диагонали (картинка слева). Этот класс задач напоминает задачи на попадание точки в заданную область. Для примера рассмотрим задачу на сумму элементов в области выше главной диагонали:
S = 0
FOR I = 1 TO N
FOR J = 1 TO N
IF I < J
THEN S = S + A(I,J)
NEXT J
NEXT I
Конечно, возможно, что заданная область будет более сложной. В этом случае условие будет составным. Но и в этом случае будет полная аналогия с задачами на попадание точки в заданную область. Ещё один тип задач на матрицы связан с их выводом на экран. Обычно на схеме матрицы показано стрелками, в какую сторону выводить столбец. Пример такой схемы показан ниже.
Сверху изображено графически условие задачи. Подразумевается, что чётные столбцы выводятся снизу вверх (в обратном порядке), чётные – сверху вниз (в прямом порядке).
FOR I = 1 TO N
FOR J = 1 TO N
IF J MOD 2=0 THEN
PRINT A(I,J);
ELSE
PRINT A(N+1-I,J);
END IF
NEXT J
NEXT I
В этой главе мы рассмотрели самые разные задачи на массивы, многие из которых включают в себя друг друга. Эти задачи имеют большое практическое применение.
Дата добавления: 2021-11-30; просмотров: 54; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!