Математическая логика и теория алгоритмов: Методические указания к практическим занятиям, страница 12

Ответ:  Программа искомой машины может иметь вид:  ,

      

Занятие 8. Вычислительные  алгоритмы

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

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

Разделение арифметических и логических этапов в процессе составления алгоритма можно  производить с помощью блок-схем.

Блок-схема  алгоритма – это графическое изображение  структуры алгоритма, где под блоком понимается арифметический или логический этап алгоритма.

Блок-схема   содержит блоки общей обработки в виде прямоугольника с одним входом и одним выходом и элементы принятия решений (логические элементы) в форме ромба с одним входом и двумя выходами (соответственно, рис. 1 и рис.2).

                                                     

Рис. 1

Элемент общей обработки         Рис.2

Элемент принятия решений

Пример 1. ([7], c. 97). Блок-схема вычисления функции

    (см. рис. 3):

 

                                   да                                

                                          

нет

  

Рис. 3. Вычисление  функции

При словесной записи алгоритма логическому элементу соответствует предписание условного перехода:   если    идти  к    где   проверяемое условие, номер предписания, к которому  следует переходить, когда     истинно.

Если    ложно, то происходит переход к следующему после предписания условного перехода предложению (в порядке возрастания номеров).

Пример 2.  ([7], c. 107). Алгоритм решения уравнения    в словесной записи имеет вид:

1  чтение

2  если   идти  к  5

3 

4  запись    идти   к  8

5  если    идти к  7

6  запись  «решений нет»;  идти  к 8

7  запись  «любое»; идти   к 8

8  конец.

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

Пример 3. ([7], c. 111). Блок-схема алгоритма Евклидова нахождения  наибольшего общего делителя (НОД) двух целых положительных чисел      и      имеет вид (см. рис. 4):

       

нет

да

         

да  да

                                

	нет

       

 

Рис. 4. Алгоритм Эвклида нахождения  НОД

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

Развилка бывает:   полная  (рис. 5 а)  и  неполная  (рис. 5 б)

                                                                                                                                                       

                                                                                                                             

                   

Рис. 5 а. Полная развилка                              Рис. 5 б. Неполная развилка

Циклы бывают:  цикл-пока (рис.6 а)   и  цикл-до  (рис. 6 б).

                                 

                                                                                                                  

Рис. 6 а. Цикл-ПОКА                                         Рис. 6 б. Цикл-ДО