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

Фрагменты блок-схем алгоритмов Назначение Соответствующие фрагменты программ на языке Pascal Начало и конец алгоритма. Begin и End Блок обработки (в нем вычисляются новые значения или производится вызов подпрограмм). X := A + B Ввод исходных данных или вывод результатов. Read (x,y) или write (x,y) Ветвление полное. Если значение переменной а больше b, то выполняется x=a, иначе x=b. if a>b then x:=a else x:=b Ветвление неполное. Если значение переменной a больше b, то выполняется x=a. if a>b then x:=a Цикл с предусловием. Пока значение условия i<6 истино выполняется тело цикла, то есть действия К=К+1 и i=i+2. Переменная i определяет количество повторений и называется счетчиком цикла.    i:=1;          while i<6 do          begin                k:=k+1;                i:=i+2;          end    write (k); Цикл с постусловием.Пока значение условия i>6 ложно выполняется тело цикла, то есть действия К=К+1 и i=i+0,1.Переменная i определяет количество повторений в цикле и называется счетчиком цикла.    i:=1;    repeat          k:=k+1;          i:=i+0.1;    until i<6;    write (k); Цикл с постоянным приращением счетчика. В этом цикле изменение счетчика цикла i происходит только на единицу.Пока значение счетчика цикла меньше или равно 6 выполняется тело цикла, то есть дейст-вия K=K+S и I=i+1.    for i:=1 to 6 do       k:=k+s;    write (k);

Алгоритмы и алгоритмизация. Заключение

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

Алгоритмы обработки двумерных массивов

Двумерный массив. Например, в двумерном массиве А, изображенном на рис. 34, элемент со значением 5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет обозначаться как А(3,2). А элемент А(1,4) имеет значение , равное нулю. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.

В дальнейшем будем считать, что для двумерного массива A(N,М) в обозначении элемента А(i,j) первое значение i соответствует номеру строки и изменяется от1 до N, а j - номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элементов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, - для изменения номера столбца j в текущей строке i.

На рис. 35 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов.

Рис. 35. Алгоритм ввода элементов двумерного массива

При рассмотрении в дальнейшем алгоритмов обработки элементов двумерного массива в целях сокращения их размера фрагмент ввода элементов будем заменять отдельным блоком ввода

Алгоритмы обработки одномерных символьных массивов

Одномерные символьные массивы. Основными операциями, выполняемыми над текстами, являются операции по определению слов, выделению слова с максимальной длиной, удаление и перестановка слов, сортировка по алфавиту и др.

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

Рассмотрим алгоритмическое решение распространенной задачи определения в массиве символов слова с максимальной длиной. Пусть исходный массив А содержит N символов. Для определения слова с максимальной длиной будем использовать сравнение длины текущего слова М с длиной предыдущего слова МАХ. Длина слова определяется как содержащееся в нем количество символов. Для того, чтобы вывести слово с максимальной длиной, необходимо запомнить номер элемента S, с которого начинается это слово. Алгоритм поиска в символьном массиве слова с максимальной длиной приведен на рис. 32, а его таблица трассировки для массива (Дул теплый ветер)- в таблице 8.

Рис. 32.Алгоритм поиска в символьном массиве слова с максимальной длиной.

Таблица 8. Таблица трассировки алгоритма поиска слова с максимальной длиной при N= 16 в тексте : "Дул теплый ветер"

K	A(K)	K=N	A(K)=" "	M>MAX	M	MAX	S	Новое S
1	Д	нет	нет		1	0	1	1
2	у	нет	нет		2
3	л	нет	нет		3
4	" "	нет	да	да	0	3	3	4
5	т	нет	нет		1
6	е	нет	нет		2
7	п	нет	нет		3
8	л	нет	нет		4
9	ы	нет	нет		5
10	й	нет	нет		6
11	" "	нет	да	да	0	6	10	11
12	в	нет	нет		1
13	е	нет	нет		2
14	т	нет	нет		3
15	е	нет	нет		4
16	р	да	нет	нет	5

Рассмотрите результат, приведенный в таблице 8, для конкретного входного символьного массива "Дул теплый ветер" без последнего столбца. Однако, после выполнения приведенного на рис. 32 алгоритма для предложения "Дул теплый ветер" будет выведено слово из 7 символов, начинающихся с пробела :" теплый". Значит, формулу определения номера символа S = K-1 , с которого начинается слово с максимальной длиной, следует изменить на S = K. При этом надо будет изменить содержание блока вывода результата: вместо A( S -MАХ), : A(S) следует использовать A( S -MАХ), : A(S-1). Таким образом, таблица трассировки показала наличие ошибок в алгоритме, изображенном на рис. 32. После внесения изменений этот алгоритм будет работать правильно (см. модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной на рис. 33).

Рис. 33. Модернизированный алгоритм поиска в символьном массиве слова с максимальной длиной

Алгоритмы обработки упорядоченных массивов - Поиск элементов в упорядоченном массиве

Задача поиска значения Х в упорядоченном по возрастанию значений массиве A(1)Х, то все элементы, имеющие номера с S по n также больше Х в силу упорядоченности массива по возрастанию значений. Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае - левую, во втором случае - правую половину. Рассмотрим пример. Допустим, что требуется определить совпадает ли значение Х=12 с каким-либо элементом в упорядоченном массиве А и если совпадает, то определить порядковый номер S этого элемента. Иллюстрация применения метода бинарного поиска для поиска элемента Х=12 в массиве (2,3,4,6,10,12,20,30,35,45) приведена на рис. 30.

Элементы массива А (2,3,4,6,10,12,20,30,35,45). Номера элементов 1 2 3 4 5 6 7 8 9 10. Первое деление S=5, А(5)=10 А(5)<Х), исключаем левую половину. Элементы массива А (2,3,4,6,10,12,20,30,35,45). Номера элементов 1 2 3 4 5 6 7 8 9 10. Второе деление S=8, А(8)=30 А(8)>Х), исключаем правую половину. Элементы массива А (2,3,4,6,10,12,20,30,35,45). Номера элементов 1 2 3 4 5 6 7 8 9 10. Третье деление S=6, А(6)=12 А(6)=Х), элемент Х=12 найден.

Рис.30. Иллюстрация применения метода бинарного поиска.

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

Рис.31.Алгоритм поиска методом бинарного поиска.

Алгоритмы обработки упорядоченных массивов

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

Алгоритмы сортировки одномерных массивов - Сортировка методом парных перестановок

Самый простой вариант этого метода сортировки массива основан на принципе сравнения и обмена пары соседних элементов. Процесс перестановок пар повторяется просмотром массива с начала до тех пор , пока не будут отсортированы все элементы , т.е. во время очередного просмотра не произойдет ни одной перестановки. Для подсчета количества перестановок целесообразно использовать счетчик - специальную переменную В. Если при просмотре элементов массива значение счетчика перестановок осталось равным нулю, то это означает, что все элементы отсортированы (см.рис.29).

Рис.29. Алгоритм сортировки методом парных перестановок содержит два цикла, внутренний цикл выделен цветом