4843

Основы алгоритмизации. Основные аспекты алгоритмизации

Книга

Информатика, кибернетика и программирование

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

Русский

2012-11-27

306 KB

44 чел.

Введение

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

  1.  постановка задачи (формализация задачи);
  2.  алгоритмическая часть (алгоритмизация);
  3.  программирование;
  4.  оценка и анализ полученных результатов (контрольный расчет).

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

Практика показывает, что адекватная формализация (математическое описание) достаточно сложных задач требует порядка 70% временных затрат для реализации задачи на компьютере.

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

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

Следующим этапом решения задачи на компьютере является собственно программирование. Для этой цели можно использовать алгоритмический язык высокого уровня, например, ПАСКАЛЬ.

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

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

АЛГОРИТМИЗАЦИЯ

Вначале рассмотрим два общих  положения.

Первое

Существуют три основные (базовые) алгоритмические структуры:

1)  линейная структура;

2)  циклическая структура;

3)  разветвленная структура.

Считается, что алгоритм любой степени сложности состоит из различных комбинаций упомянутых выше трех базовых структур

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

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

Рис.1

 

a) цикл "до"                         б) цикл "пока"                  в) арифметический цикл

Рис.2

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

В алгоритмах разветвленной структуры вычислительный процесс формируется, как правило, в виде двух ветвей (путей) в соответствии с некоторым условием, которое может быть истинным (“да”) или  ложным (“нет”). Варианты оформления алгоритмов разветвленной структуры приведены на рис. 3.

 a) альтернатива б) обход б) коррекция

Рис.3

Второе

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

Пример 1

Необходимо вычислить максимальное значение  переменных .                    Существует много различных способов решения данной задачи. Рассмотрим один из них с использованием дополнительной переменной . Алгоритм примера 1 показан на рис. 4.

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

1 шаг                     2 шаг        3  шаг

Рис.4

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

1. ВЫЧИСЛЕНИЕ СУММЫ (СУММИРОВАНИЕ) ЭЛЕМЕНТОВ ВЕКТОРА

Для  вычисления  суммы    элементов  вектора, предположим, X = {},  i = 1, 2, ..., N, его значения и размерность N должны быть известны как для данного случая, так и для последующих задач.

Очевидно,

         (1) ( 1 )

Алгоритм суммирования элемен-тов вектора приведен на рис. 5.

Отметим, что начальное значение суммы .

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

Рис.5

Пример 2

Необходимо вычислить средне- арифметическое значение  четных по номеру элементов вектора X = {},   i=1, 2, ..., N.

     ( 2 )

Алгоритм примера 2 показан на рис. 6.

Рис.6

2. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ ЭЛЕМЕНТОВ ВЕКТОРА

Очевидно,

     ( 3 )

Алгоритм для вычисления произведения элементов вектора приведен на рис. 7.

Отметим, что начальное значение произве-дения  = 1.

Рис.7

Пример 3

Необходимо вычислить значение произведения  (факториала) натурального ряда целых чисел от 1 до N.

Следовательно,

           (4) ( 4 )

Схема алгоритма для вычисления факто-риала  показана на рис. 8.

Рис.8

Пример  4

Необходимо вычислить среднегеометрическое значение Q положитель-ных элементов вектора C = {}, . При формализации данной задачи приходим к следующему выражению:

, ( 5 )

где k – число положительных элементов < 0.

Эта задача может быть решена методом “сверху вниз”, как показано на рис. 9.

Рис. 9

Окончательная схема алгоритма решения данной задачи показана на рис. 10.

Рис.10

Пример 5

Дан вектор X = {}, i=1, 2, ..., N. Необходимо вычислить значение Р согласно следующему выражению:

P = k.                                                          ( 6 )

Например,  если  N = 4  тогда

 P =

Графическая схема алгоритма данной задачи представлена на рис. 11.

Рис.11

3. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ ДВУХ ВЕКТОРОВ

    Даны два вектора A = {ai} и B = {bi},

i=1, 2, ..., N . Отметим, что размер обоих векторов равен N, а результатом произве-дения двух векторов будет число

   C = A * B  =    (7)

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

Рис. 12

Пример 6

Дана матрица A = {} ,   i, j=1, 2, ..., N.

Необходимо вычислить элементы вектора X = {}, i=1, 2, ... , N. Каждый элемент вектора  вычисляется как произведение  i-го столбца и главной диагонали матрицы A.

Например, пусть N = 3 и известны все элементы матрицы A

A =  = .

Попутно отметим, что i-ая строка, j-ый столбец, главная и побочная диагонали матрицы A по сути является вектором.

Действительно,

- 2-ая строка  (вектор),

- 3-ий столбец  (вектор),

{}N - главная диагональ  (вектор),

{}N - побочная диагональ  (вектор).

В соответствии с условием задачи  (пример 6), элементы вектора xi могут быть рассчитаны следующим образом:

для  =*+*+*=;

для  =;

для  .

Формализация данной задачи приводит к следующему выражению:

,                i = 1, 2, . . . , N ( 8 )

Два варианта разработки алгоритма данной задачи показаны на рис. 13.

Рис.13

4. СУММИРОВАНИЕ (ВЫЧИТАНИЕ) МАТРИЦ

Данные действия над двумя матрицами A и B могут быть произведены, если размерности обоих матриц равны, предположим (M*N). Результатом сумми-рования (вычитания) будет матрица C такой же размерности  (M*N).

C = A + B =

+= , ( 9 )

,  i = 1, 2, . . . ,M;

                        j = 1, 2, . . . , N.        ( 10 )

Рис. 14

Алгоритм суммирования матриц показан на рис. 14.

Алгоритм вычитания матриц  аналогичен рассмотренному, за исключе-нием  очевидной замены знака " + " на "  ".

5. ВычислениЕ произведения матриц

Даны две прямоугольные матрицы A={}N*M  и  B={}M*K .

В результате вычисления произведения матриц A и B получим прямоугольную матрицу C={ }N*K , в которой число строк равно числу строк матрицы A  (т.e. N), а число столбцов - числу столбцов матрицы B (т.e. K). Отметим, что число столбцов матрицы A равно числу строк матрицы B  (т.e. M).

Например,

C = A*B =*= ( 11 )

Формализация данной задачи имеет следующий вид:

           ( 12 )

для   

   Алгоритм для вычисления произведения двух прямоуголь-ных матриц показан на рис. 15.

   Отметим, что в результате вычисления произведения двух квадратных матриц размерностью (N*N) получим квадратную матрицу такой же размерности.

Рис.15

6. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ МАТРИЦЫ НА ВЕКТОР

Даны прямоугольная матрица A={}N*M   и   вектор B={}M .

В результате вычисления произведения матрицы A и вектора B получим вектор C , в котором число элементов равно числу строк матрицы A (т.е. N). Отметим, что число элементов вектора B равно числу столбцов матрицы A (т.e. M).

Например,      C = A*B =

*= ( 13 )

Формализация данной задачи приводит к следующему выраже-нию:

        ( 14 )

для  

   Алгоритм вычисления произве-дения матрицы на вектор показан на рис. 16.

Рис.16

7. ВЫЧИСЛЕНИЕ ЕДИНИЧНОЙ МАТРИЦЫ

Формализация данной задачи приводит к следующему выраже-нию:

E={}N*N= ,    ( 15 )

        для  

    Алгоритм  вычисления единич-ной матрицы приведен на рис. 17.

Рис. 17

8. ТРАНСПОНИРОВАНИЕ  МАТРИЦЫ

Транспонирование матрицы A={}N*N  предполагает перестановку в ней элементов строк и столбцов.

Например,    A=,    тогда  AT = . ( 16 )

Существуют два способа решения данной задачи:

  1.  с использованием  новой матрицы AT={}N*N   ,

в этом случае        для    ;

  1.  путем перестановки в три шага соответствующих элементов в исходной матрице  A   (рис.18).

2-ой шаг

1-ый шаг 3-ий шаг

aij пустая ячейка b aji

Рис.18

Схемы алгоритмов транспонирования элементов матрицы для обоих способов показаны на рис. 19.

                                  1)                                                                  2)

Рис. 19

9.  инвертирование элементов вектора

Инвертирование вектора X={}N означает перечисление элементов вектора в обратном порядке. Например, если  X=(0, -3, 2, 6),   тогда  XIN =  (6, 2, -3, 0) .

Аналогично, существуют два способа решения данной задачи:

1) с использованием нового вектора XIN={}N     ,

в этом случае =     для     ;

2) путем перестановки в три шага соответствующих элементов в    исходном векторе X .

Схемы алгоритмов способов инвертирования элементов вектора пред-ставлены на рис. 20.

1)     2)

Рис. 20

Рассмотрим более сложную задачу.

Пример 7

Необходимо вычислить значение параметра Z в соответствии со следующим выражением:

Z = ( A - E ) * C1IN * ( C22 - 1 ) , ( 17 )

где A - исходная матрица, все элементы и размерность которой известны;

E – единичная матрица;

C1 – главная диагональ матрицы A;

C2 – побочная диагональ матрицы A.

Рассмотрим поэтапный процесс решения данной задачи.

  1.  Ввод размерности N и всех элементов матрицы   ().

Вычисление единичной матрицы  E={}N*N.

Вычисление главной диагонали  (вектор)  ().

Вычисление побочной диагонали (вектор)  ().

Инвертирование вектора C1:   ().

Вычисление квадратной матрицы B=A-E.

Вычисление вектора D=B*C1IN.

Вычисление значения F=C2*C2.

Вычисление значения K=F-1.

  1.  Вычисление вектора Z=D*K.
  2.  Вывод вектора Z={}N.

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

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

1) предусмотреть комментарии к каждому пункту задачи;

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

Данные рекомендации способствуют лучшему пониманию и контролю процесса поэтапных вычислений.

10. АЛГОРИТМ поиска МАКСИМАЛЬНОГО ( ИЛИ МИНИМАЛЬ-НОГО ) элемента  ВЕКТОРА

Дан вектор X={}N .

Необходимо найти элемент вектора Х , имеющий максимальное значение. Например,   пусть   X =  (3, 4, 2, -1, 6, 0).   Очевидно,    что    M(max) == 6;  L (порядковый номер максимального элемента)=5.

Процедура поиска максимального элемента вектора следующая: предположим, что максимальным является первый элемент, т.e. M=a1, L=1.

Затем каждый элемент ,   сравнивается со значением M, и если значение некоторого текущего элемента  больше M, тогда M принимает новое значение  с запоминанием его порядкового номе-ра L = i.

Алгоритм поиска максимального элемента вектора показан на рис. 21.

Данный алгоритм пригоден для поиска минимального элемента вектора при очевидной замене знака "<" на знак ">" в блоке проверки условия (рис. 21).

Рис. 21

11. алгоритм сортировки (упорядочивания) элементов вектора или матрицы

Сортировка означает перестановку элементов вектора или матрицы в определенном порядке (по возрастанию или по убыванию) в соответствии с их значениями.

Рассмотрим алгоритм сортировки (упорядочивания) элементов вектора, когда значение каждого последующего элемента вектора больше предыдущего. Например, пусть исходный вектор X={}6=(3, 4, 2, -1, 6, 0), тогда в результате сортировки получим вектор X=(-1, 0, 2, 3, 4, 6).

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

Процедура сортировки элементов вектора X по возрастанию их значений следующая.

Первый шаг

Среди N-1 элементов вектора X (за исключением ) произведем поиск минимального элемента вектора  и поменяем его местами с первым элементом, если  значение <. В результате выполнения первого шага сортировки получим следующий вектор  X=(-1, 4, 2, 3, 6, 0).

Второй шаг

Среди N-2 элементов вектора X (за исключением , ) произведем поиск  минимального элемента вектора  и поменяем его местами со вторым элементом, если значение <. В результате выполнения второго шага сортировки получим вектор X=(-1, 0, 2, 3, 6, 4).

Очевидно, после выполнения N-1 шага (в нашем примере после 5 шагов) получим окончательный упорядоченный вектор X=(-1, 0, 2, 3, 4, 6).

Алгоритм упорядочивания по возрастанию элементов вектора показан на рис. 22. Данный алгоритм пригоден для упорядочивания элементов вектора по убыванию с очевидной заменой знака " > " на знак " < " в блоке проверки условия (рис. 22).

Рассмотрим алгоритм сортировки элементов матрицы.

Дана матрица A={}P*N . Необходимо упорядочить элементы столбцов матрицы А в порядке убывания. Алгоритм сортировки элементов матрицы для этого случая приведен на рис. 23.

Рис.22

Рис.23

12. вычисление полинома по схеме горнера

Дан полином PN(x)  порядка N.

y = PN(x)= ( 18 )

Порядок N, значение аргумента  и коэффициенты  () известны. Поставим задачу разработки эффективной схемы вычисления полинома y = PN().

Представим уравнение (18) в следующем виде:

( 19 )

Очевидно, уравнение Горнера (19) предполагает меньший объем арифметических операций, чем исходное уравнение (18).

Рассмотрим следующую процедуру вычисления полинома с использованием рекуррентной формулы  (рис. 24):

,

для        . ( 20 )

Действительно,

для   

для   ( 21 )

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   

для  =PN()

Рис.24. Алгоритм вычисления полинома по схеме Горнера.

13. ВЫЧИСЛЕНИЕ  СУММЫ  ЧЛЕНОВ  РЯДА

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

,   ( 22 )

где   - общий член ряда.

Очевидно, сумма членов ряда S может быть вычислена только при конечном (заданном) числе членов ряда, предположим NZ = 10, или условием окончания вычислений может быть неравенство вида , где  достаточно малая величина, предположим  или . (Известно, что в сходящихся рядах , т.e. значение модуля каждого последующего члена ряда меньше предыдущего).

Приведем рекуррентную формулу для вычисления значения текущего члена ряда:

, где - рекуррентный множитель. ( 23 )

Для нашего примера  (уравнение 22)

M==. (24)

Покажем схему алгоритма вычисления суммы членов ряда на рис. 25.

Рис.25


 

А также другие работы, которые могут Вас заинтересовать

4187. Україна козацькаконспект. Довідник з історії України для студентів всіх спеціальностей УДУВГП 241.5 KB
  Вступ Козацький період в історії України (ХVІ – ХVІІІ ст.) надзвичайно важливий для розуміння складних державотворчих і націєтворчих процесів, що відбувалися на наших землях протягом багатьох століть, і які, на жаль, залишаються незавершеними щ...
4188. Корреспонденция – жанр-гибрид 65.5 KB
  Корреспонденция – жанр-гибрид Создание журналистского произведения всегда обусловлено рядом взаимозависимых процессов, к которым можно отнести поиск и рождение темы будущей публикации, формирование и разработку замысла конкретного произведения...
4189. Теория длинных волн Н.Д. Кондратьева 127.5 KB
  Введение. Я выбрала курсовую работу по теме: Теория длинных волн Н.Д. Кондратьева. Эта тема меня заинтересовала тем, что во-первых, спады и подъемы в экономической жизни любой страны всегда наблюдались и наблюдаются в наши дни. Мне захотелось самой...
4190. Предмет исследования экономической теории и ее функции 43.73 KB
  Введение Первым поводом к изучению экономической теории является то, что эта теория дело с такими проблемами, которые касаются нас всех без исключения: какие виды работ нужно выполнять Как они оплачиваются сколько товаров можно купить на доллар за...
4191. Методы нормирования оборотных средств предприятия 64 KB
  Введение Каждое предприятие, начиная свою производственно-хозяйственную деятельность, должно располагать определённой денежной суммой. На эти денежные ресурсы предприятие закупает на рынке или у других предприятий по договорам сырьё, материалы, топл...
4192. Концепции современного естествознания. Теория большого взрыва 140.5 KB
  Сценарий Большого взрыва Как и любая схема, претендующая на объяснение данных о спектре микроволнового космического излучения, химического состава догалактического вещества и иерархии масштабов космических структур, стандартная модель эволюции Вселе...
4193. Классный час. О чем поют птицы. Экологическая беседа 622.5 KB
  Цель: развивать у детей интерес к жизни птиц, в частности, к их голосам формировать умение вслушиваться в их звуковые сигналы воспитывать любовь к природе, бережное заботливое отношение к птицам. Оборудование: запись «Голоса птиц», таблицы с изобр...
4194. Табличний процесор Excel 667 KB
  Табличний процесор Excel Мета: Нагадати і закріпити принципи обробки даних, принципи побудови діаграм і графіків, принципи систематизації та аналізу даних, поданих у таблиці, розвивати вміння використовувати електронні таблиці в навчальній діяльност...