Алгоритмизация решения типовых задач и основы программирования на языке высокого уровня. Методические указания к самостоятельной работе студентов (стр. 2 )

Решение: Исходные данные: А, В. Вспомогательная переменная Dор. Результат: А, В.

Модель: Даны переменные А и В. Требуется обменять их значения, т. е. переменная А должна получить значение В, а В — значение А.

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

Решение задачи распадается на три этапа. Соответствующие им блоки и порядок их выполнения описаны ниже двумя способами.

Блок-схема

Рис. 2. Блок-схема алгоритма замены

Псевдокод

Алгоритм Замена; {заголовок

алгоритма}

Переменные А, В, Dop: строковый тип; {описательный блок}

Начало

Ввод (А, В);

Dop:=A; А:=В; B:=Dop;

Вывод (А, В);

Конец

Проверим составленный алгоритм. Для того, чтобы было легче контролировать значения переменных, исполняя алгоритм, будем составлять трассировочную (тестирующую) табл. 4.

Пусть переменным А и В задаются значения ‘сок’ и ‘вода’ соответственно. В итоге переменная А должна содержать ‘вода’, а В — ‘сок’. Проверим работу нашего алгоритма:

Таблица 4. Таблица трассировки.

№ шага	А	В	DOP
1	‘сок’	‘вода’	‘’
2	‘сок’	‘вода’	‘сок’
3	‘вода’	‘вода’	‘сок’
4	‘вода’	‘сок’	‘сок’

Результат работы алгоритма совпадает с ожидаемым, значит алгоритм составлен верно.

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

Линейные алгоритмы

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

Пример 5. В примерах 3, 4 рассмотрены линейные алгоритмы и различные способы их представления: в примере 3 – словесно-формульный, в примере 4 – графический, псевдокодом и таблицей трассировки.

Рекомендуется изучить [6] стр.10-13.

Задания для самостоятельного выполнения

Рекомендуется выполнить задания из [6] стр.298-311.

Разветвленные алгоритмы

Алгоритм ветвящейся структуры – алгоритм, в котором выбирается один из нескольких вариантов (путей) вычислительного процесса. Каждый подобный путь называется ветвью алгоритма.

Признаком разветвляющегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения и в зависимости от его значения выбирается конкретная ветвь алгоритма. В разветвляющихся алгоритмах используются структуры 2, 4, представленные в табл. 3. Кроме них рассматривается структура неполного ветвления, представленная на рис. 3.

Пример 6. Вычислить значение Y по одной из формул:

Решение: Исходные данные: х. Результат: Y. Метод решения задачи: необходимо выявить область, которой принадлежит значение х, для этого достаточно проверить заданные условия по порядку. Запишем алгоритм в псевдокодах:

Алгоритм Ветв_полн;

Переменные х, у: вещественные;

Начало

Ввод (х);

Если х<0

то у:=х2/2

иначе у:=х+5

Все-если;

Вывод (у);

Конец.

Алгоритм Ветв_неполн;

Переменные х, у: вещественные;

Начало

Ввод (х);

у:=х+5;

Если х<10

то у:=х2/2

Все-если;

Вывод (у);

Конец.

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

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

Пример 7. Найти максимальное из двух чисел X, Z: Y = max(X, Z).

Решение: Исходные данные: X, Z. Результат: Мах.

Метод решения задачи: нужно сравнить два числа и сделать вывод. Блок-схема алгоритма решения этой задачи представлена на рис. 4.

Рис. 4. Блок-схема

Рекомендуется изучить теоретический материал и разобрать примеры из [6] стр.13-16.

Задания для самостоятельного выполнения

1.  Для двух чисел Х, У определить, являются ли они корнями уравнения А*Р4+D*P2+C=0.

2.  Если среди трех чисел А, В,С имеется хотя бы одно четное – вычислить максимальное, иначе – минимальное.

3.  Ввести положительное А>=1. Найти наибольшее из выражений вида 1/А и sin(A).

4.  Ввести два числа. Меньшее заменить полусуммой, а большее – удвоенным произведением.

5.  Ввести три числа А, В,С. Удвоить каждое из них, если А>=В>=С, иначе поменять значения А и В.

6.  Определить, является ли точка с координатами X, Y точкой пересечения диагоналей квадрата со стороной R, одна вершина которого расположена в начале координат.

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

Рекомендуется выполнить задания из [6] стр. 311-320.

Циклические алгоритмы

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

Цикл – это последовательность действий, выполняемых многократно, каждый раз при новых значениях параметров. Действия выполняемые при однократном прохождении цикла (описанные внутри цикла) называются телом цикла.

Пример 8. Составить алгоритм покраски забора.

Решение: Рассмотрим этот алгоритм в словесно-формульном виде:

Шаг I. Подготовить исходные данные (забор, краску, кисть).

Шаг II. Подойти к забору.

Шаг III. Обмакнуть кисть в краску.

Шаг IV. Нанести краску кистью на поверхность забора.

Шаг V. Если забор еще не весь окрашен, то повторить алгоритм, начиная с пункта (Шаг III).

Телом цикла будет являться последовательность шагов III, IV.

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

·  Счетные циклы (циклы с заданным количеством повторений) – циклические процессы, для которых количество повторений известно. Например, заполнение массива.

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

·  Поисковые циклы – циклические процессы, из которых возможны два варианта выхода: выход по завершению процесса и досрочный выход по какому-либо дополнительному условию. Например, нахождение первого отрицательного элемента массива.

Циклы можно организовать с помощью структур 3, 5, 6, представленных в табл. 3.

Пример 9. Записать алгоритм возведения числа Х в степень n.

Решение: Исходные данные: Х – вещественное, n – целое.

Результат: Y – вещественное.

Модель решения задачи: Y=Xn =Хn-1´Х. Метод решения: Алгоритм может быть реализован на основе операции умножения. Табличное представление такого алгоритма, отражающего зависимость У от Х при изменении показателя степени n от 1 до 3, представлено в табл. 5, в которой также даны рекуррентные соотношения между У и Х, определяющие как на каждом шаге зависит значение У от значения Х и от значения У, вычисленного на предыдущем шаге.

Таблица 5.

n	Y	Рекуррентные соотношения
1	Y[1] = X	Y = X
2	Y[2] = X*X или Y[2] = Y[1]*X	Y = X*X или Y = Y*X
3	Y[3] = X*X*X или Y[3] = Y[2]*X	Y = X*X*X или Y = Y*X

О рекурсии рекомендуется прочесть в [3] стр.168-179., [6] стр.81-82. О циклических алгоритмах в [6] стр.16-19, стр. 65-68.

Задания для самостоятельного выполнения

1. Составить циклические алгоритмы в виде блок-схем, псевдокодов, таблицы трассировки для следующих задач:

А) Вычислить число в факториале Y = X!

Б) Вычислить сумму ряда, общий член которого задан формулой An=(x*n)/n! с заданной степенью точности и Sn.

В) При табулировании функции y = cos(x + a) на отрезке [1,10] c шагом h=1 определить сумму значений y, больших p.

Г) Подсчитать количество цифр в целом числе Х.

Д) Вычислить сумму значений функции у = x2 на отрезке [1,5] c шагом 1.

Е*) Найти минимальное значение функции Y = sin(X)*X, на отрезке [C, D] с шагом 0.001. Реализовать циклом с постусловием.

2. Протабулировать функцию y = sin(x) на отрезке [1,5] с шагом h=0,5. Вывести предпоследнее положительное значение функции.

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

Условие N>0	S	N
	0	125
125 > 0 – да	0 + 5 = 5	12
12 > 0 – да	5 + 2 = 7	1
1 > 0 – да	7 + 1 = 8	0
0 > 0 – нет

4. Составить графическую и табличную формы алгоритма по его текстовому представлению, а также определить конечное значение S.

А) I := 0; S := 0; Цикл-пока I < 3 I := I+3; S := S+I*I; Все-цикл Вывод S

Б) I :=1; S := 0; Цикл-пока I > 1 S := S+1/I; I := I-1; Все-цикл; Вывод S

5.  Протабулировать функцию Y = tg(X), при изменении X на отрезке [A, B] с шагом K и определить количество точек разрыва (M) этой функции.

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

I	J	S
		0
1	2	0 + 1 + 2 = 3
	3	3 + 1 + 3 = 7
2	2	7 + 2 + 2 = 11
	3	11 + 2 + 3 = 16

7. Определите местонахождение ошибок в алгоритмическом решении задачи: Найти минимальное значение функции Y =A*X2+Sin(X)*X0,5, для Х, изменяющегося на отрезке [C, D] с шагом 0,01. Блок-схема алгоритма приведена на рис. 5.

Рис. 5. Блок-схема алгоритма задачи 7.

Рекомендуется выполнить задания из [6] стр. 320-327.

Алгоритмы обработки последовательностей чисел (значений)

Примером последовательности целых чисел может быть следующий набор значений: {2,5,-4,10,1,0}. Последовательности значений отличаются от массивов значений тем, что в памяти одновременно все значения последовательности не хранятся. Для обозначения значения последовательности используют одну переменную, в которую на каждом шаге итерации вводится очередное значение последовательности. Отличительной особенностью последовательности является также возможность содержания неизвестного заранее количества ее значений. В этом случае критерием окончания последовательности служит некоторое особое значение, например, ноль. Для реализации таких алгоритмов могут быть использованы все три циклических структуры.

Рекомендуется изучить в [6] стр. 81-88.

Задания для самостоятельного выполнения

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

1. В последовательности N чисел найти произведение чисел, кратных 3.

2. В последовательности N чисел сравнить, что больше: сумма положительных или произведение отрицательных.

3. В последовательности N чисел определить предпоследнее отрицательное число. (При решении введите дополнительную переменную для хранения предпоследнего отрицательного числа).

4. В последовательности целых положительных чисел определить максимальное число. Рекомендуем реализовать такой алгоритм следующим образом:

Вводим Х; mах :=Х;

Цикл с постусловием

a) Если элемент Х > max

то max := Х {значение этого элемента};

б) Вводим новый элемент последовательности Х

Условие выхода из цикла Х=0.

5. В последовательности целых чисел определить третье положительное число и подсчитать количество цифр в нем.

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

Под структурой данных типа массив понимают однородную структуру однотипных данных, одновременно хранящихся в последовательных ячейках оперативной памяти. Эта структура должна иметь имя и определять заданное количество данных (элементов). Однотипность данных определяет возможность использования циклических алгоритмов для обработки всех элементов массива. Количество итераций цикла определяется количеством элементов массива. Одновременное хранение в памяти всех элементов массива позволяет решать большой набор задач, среди них: поиск элементов, упорядочение и изменение порядка следования элементов. Доступ к любому элементу массива осуществляется по его номеру (индексу). Для обращения к элементу массива используют имя массива (номер элемента), например, А(5).

Пример 10. Составить алгоритм ввода элементов одномерного массива А, состоящего из 9 элементов.

Решение: В этом циклическом алгоритме условие выхода из цикла определяется значением специальной переменной К, которая называется счетчиком элементов массива А (рис. 5), эта же переменная К определяет количество итераций циклического алгоритма ввода элементов массива. На каждом шаге итерации переменная К (значение номера элемента массива А) изменяется на 1, то есть происходит переход к новому элементу массива. В дальнейшем, при рассмотрении алгоритмов обработки одномерных массивов в целях устранения дублирования алгоритм ввода элементов массива будем заменять одним блоком, подразумевая, что он реализуется по схеме циклического алгоритма, представленного на рис. 6.

Существуют несколько более сложных алгоритмов, в которых осуществляется изменение порядка следования элементов в одномерном массиве. К таким алгоритмам относят алгоритмы с перестановкой элементов местами, алгоритмы удаления некоторых элементов или циклического переноса некоторых элементов в начало или конец массива. Основным требованием при составлении алгоритмов обработки массивов является использование минимально необходимых переменных. Чтобы точнее уяснить постановку задачи, следует сначала рассмотреть частные решения для некоторых значений входных данных (провести анализ), затем обобщить полученные решения и определить набор решаемых задач. Составив алгоритм в виде блок-схемы, его следует проверить на различных наборах исходных данных. Эти наборы исходных данных требуется подбирать таким образом, чтобы при заполнении таблиц трассировок проверить все пути вычислений данного алгоритма от начальной вершины до конечной.

Рекомендуется работа с [6] стр.104-11, выполнение практикума из [3] стр. 87-96.

Задания для самостоятельного выполнения

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

1.  В одномерном массиве определить первый отрицательный элемент и его номер.

2.  Исключить из массива А1..AN пеpвый отpицательный элемент.

3.  Исключить из массива А1..AN пеpвый четный элемент, следующий за максимальным.

4.  Дан массив целых чисел a1, …, an. Выяснить, какая из трех ситуаций имеет место: все числа a1, …, an равны нулю, в последовательности a1, ..., an первое ненулевое число – положительное, первое ненулевое число – отрицательное.

5.  Даны целые числа a1, ..., an. Определить количество целых чисел, входящих в последовательность a1, ..., an по одному разу.

6.  Даны действительные числа a1, ..., an. Требуется найти b равное среднему арифметическому чисел a1, ..., an, и наибольшее отклонение от среднего, т. е. max(½a1-b½,½a2-b½,..½an-b½).

7.  Дан массив действительных чисел a1, ..., an. Найти максимальный элемент среди отрицательных элементов и поменять его местами с минимальным положительным.

8.  В одномерном массиве перенести в начало максимальный элемент.

9.  Пеpенести в начало одномеpного массива втоpой нулевой элемент.

10.  Ввести массив а1, ..., а16. Получить новый массив по правилу (а1+а16, а2+а15,..., а8+а9). Найти минимальный элемент полученного массива.

11.  В одномерном массиве перенести в конец минимальный элемент.

12.  Пеpенести в конец одномеpного массива все отpицательные элементы.

13.  Пеpенести в начало одномеpного массива все нечетные элементы.

14.  В одномерном массиве найти первую группу повторяющихся элементов.

15. Выполните примеры 10 и 11, реализуя ввод элементов массива в цикле, в котором производится их обработка.

Рекомендуется выполнить задания из [6] стр.338-344.

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

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

Рекомендуется ознакомиться с основными методами сортировки в [6] стр.110-113, [5] стр.328-336. Выполнить практикум [3] стр.96-104.

Задания для самостоятельного выполнения

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

1.  Ввести массив a1, a2, ..., a15. Расположить ненулевые элементы по убыванию.

2.  Ввести массив x1, x2, ..., x20. Элементы, на нечетных местах, расположить в порядке возрастания, а на четных - в порядке убывания.

3.  Ввести массив a1, a2, ..., a15. Требуется упорядочить его по возрастанию абсолютных значений элементов

4.  Ввести массив x1, x2, ..., x20. Требуется расположить отрицательные элементы в порядке убывания.

Рекомендуется выполнить задания из [6] стр.344-346.

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

Поиск элементов в упорядоченном массиве

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

Задача поиска значения Х в упорядоченном по возрастанию значений массиве решается методом бинарного поиска (методом деления пополам). Сущность этого метода поиска заключается в последовательном определении номера s элемента, расположенного в точке деления упорядоченного массива пополам и сравнении искомого значения Х с этим элементом массива A(s). Если A(s) = Х, то поиск заканчивается. В противном случае возможны две ситуации: если A(s) < Х, то все элементы, имеющие номера с 1 по s также меньше Х, если A(s) > Х, то все элементы, имеющие номера с s по n также больше Х в силу упорядоченности массива по возрастанию значений. Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае – левую, во втором случае – правую половину.

Пример 11. Требуется определить совпадает ли значение Х = 12 с каким-либо элементом в упорядоченном массиве А и если совпадает, то определить порядковый номер S этого элемента.

Решение: Иллюстрация применения метода бинарного поиска для поиска элемента Х=12 в массиве {2,3,4,6,10,12,20,30,35,45) приведена на рис. 7.

1 шаг. Элементы массива А={2,3,4,6,10,12,20,30,35,45}.

Номера элементов 9 10

Первое деление S = 5, А(5) = 10 А(5) < Х), исключаем левую половину.

2 шаг. Элементы массива А={12,20,30,35,45}.

Номера элементов 6, 7, 8, 9, 10

Второе деление S = 8, А(8) = 30 А(8) > Х), исключаем правую половину.

3 шаг. Элементы массива А={12,20}.

Номера элементов 6, 7

Третье деление S = 6, А(6) = 12 А(12) = Х), элемент Х = 12 найден.

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

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

Рекомендуется [5] стр. 326-328.

Линейный поиск рассмотрен в [5] стр. 327.

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

Одномерные символьные массивы. Основными операциями, выполняемыми над текстами, являются операции по определению слов, выделению слова с максимальной длиной, удаление и перестановка слов, сортировка по алфавиту и др. Для простоты будем считать, что символьный массив представляет одну строку произвольного текста, слово – любую последовательность подряд идущих символов не содержащую пробела. Пробел – это специальный символ, используемый для отделения слов, он не может располагаться перед первым словом. Учитывая все эти допущения, можно предложить: для решения задачи определения количества слов использовать подсчет количества элементов массива, равных пробелу минус 1. Рассмотрим алгоритмическое решение распространенной задачи определения в массиве символов слова с максимальной длиной. Пусть исходный массив А содержит N символов. Для определения слова с максимальной длиной будем использовать сравнение длины текущего слова М с длиной предыдущего слова МАХ. Длина слова определяется как содержащееся в нем количество символов. Для того чтобы вывести слово с максимальной длиной, необходимо запомнить номер элемента S, с которого начинается это слово.

Пример 12. Разработать алгоритм поиска в символьном массиве слова с максимальной длиной

Решение: Алгоритм поиска в символьном массиве слова максимальной длины приведен на рис. 8а), и таблица трассировки для массива ‘Дул теплый ветер’ (размерность массива N=16) – в табл. 6.