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

4.2.4. Постройте конечный автомат таблично, складывающий:

0)четные натуральные числа в D5;	1)нечетные натуральные числа в D8;
2)натуральные числа в D4;	3)нечетные натуральные числа в D6;
4)четные натуральные числа в D6;	5)нечетные натуральные числа в D5;
6)четные натуральные числа в D7;	7)натуральные числа в D3;
8)четные натуральные числа в D8;	9)нечетные натуральные числа в D7

Решение.

Символы алфавита	Состояния
x1	x2	q0	q1

4.2.5. Постройте конечный автомат таблично, сравнивающий два числа x₁ и x₂, заданные в двоичной системе счисления. При совпадении разрядов на выходе формируется сигнал 0, иначе 1. X = {00, 01, 10, 11}, Y = {0, 1}.

Решение.

Функционирование системы определяется двумя состояниями:
Q = {q₀, q₁}, где q₀ – состояние, соответствующее равенству разрядов, иначе q₁ .

Символы алфавита	Состояния
x1	x2	q0	q1

Глава 5. Алгоритмы

Способы описания алгоритмов

К основным изобразительным средствам алгоритмов можно отнести следующие способы записи:

- словесная;

- словесно-формульная;

- в графическом виде (в виде блок-схем);

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

Примеры выполнения заданий

1. Опишите в словесной форме алгоритм вычисления значения логической функции, реализующую операцию конъюнкции:

Решение.

1. Ввести значения аргументов x и y. Перейти к п. 2.

2. Проверить, x равно 1 и y равно 1? Если да, то выдать сообщение: ‘Значение функции равно true’, перейти к п. 4, иначе перейти к п. 3.

3. Проверить, x равно 1 и y равно 0 или x равно 0 и y равно 1 или x равно 0 и y равно 0? Если да, то выдать сообщение: ‘Значение функции равно false’, перейти к п. 4, иначе выдать сообщение об ошибке ввода.

4. Завершить процесс.

2. Опишите пример 1 в словесно-формульной форме.

1. Ввести значения аргументов x и y. Перейти к п. 2.

2. Проверить, x = 1 и y = 1? Если да, то выдать сообщение: ‘Значение функции равно true’, перейти к п. 4, иначе перейти к п. 3.

3. Проверить, x = 1 и y = 0 или x = 0 и y = 1 или x = 0 и
y = 0? Если да, то выдать сообщение: ‘Значение функции равно false’, перейти к п. 4, иначе выдать сообщение об ошибке ввода.

4. Завершить процесс.

3. Опишите пример 1 в виде текста программы на алгоритмическом языке.

Program func;

var x, y: integer;

begin

writeln (‘Введите значения двух аргументов функции (0/1)’); readln (x, y);

if (x = 1) and (y = 1) then write (‘Значение функции равно true’);

if (x = 1) and (y = 0) or (x = 0) and (y = 1) or (x = 0) and (y = 0)

then write (‘Значение функции равно false’)

else write (‘Ошибка ввода‘)

end.

 

5. Опишите пример 1 в виде блок-схемы

 

 

x, y

Начало

x=1 & y=1?

Да

Нет

 

 

 

 

 

(x=1)&(y=0)? r (x=0)&(y=1)? (x=0)&(y=0)?

Окончание

Ошибка ввода

F(x,y)= true

Да

Нет

F(x,y)= false

 

 

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

5.1.1. Опишите алгоритмы в словесной форме:

1. Переменной d присваивают длину окружности, площадь круга и объем шара одного и того же заданного радиуса.

2. Даны произвольные числа a, b, c. Если нельзя построить треугольник с такими длинами сторон, то напечатать 0, иначе напечатать 3 - если треугольник равносторонний, 2 - если треугольник равнобедренный или 1 - в противном случае.

3. Даны целые числа k и m, действительные числа x, y, z. При
k < m², k = m² или k > m², замените модулем соответственно значения x, y, z., а два других уменьшить на 0.5.

 

5.1.2. Опишите алгоритмы в словесно-формульной форме:

1. Даны два числа а и в. Обменяйте их значениями, не используя третьей переменной.

2. Для заданного числа a найдите корень уравнения f(x)=0, где:

.

3. Найдите корни квадратного уравнения, если заданы коэффициенты а, в, с.

4. Вычислите площадь треугольника по заданным сторонам, если это возможно.

5. Даны действительные числа x, y, z. Вычислите: max (min (y + z, x * y), y + e^x).

6. Дано число а. Определите первый отрицательный член и его номер в последовательности x₁, x₂, …x_n, где x₁=a, x_n=tg (x_n-1).

Виды алгоритмов

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

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

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

Примеры выполнения заданий

1. Опишите графическим способом алгоритм расчета нормы расхода гербицида (л/га) по формуле: .

Решение.

На рис. 5.2. приведена блок-схема решения задачи.

 

Начало Ввод Действие 1 W, V, D, n     …. Окончание Действие N Вывод	Начало Окончание A / B
Рис. 5.1. Блок-схема линейного процесса обработки информации	Рис.5.2. Блок-схема алгоритма задачи 1

 

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

1. Опишите алгоритмы в графической форме, в которых переменной d присваивают:

0) длину окружности, площадь круга и объем шара одного и того же заданного радиуса;

1) периметр и площадь прямоугольного треугольника по длинам двух катетов;

2) площадь и периметр некоторого треугольника по координатам трех вершин;

3) длину третьей стороны и площадь треугольника по длинам двух сторон и углу (в градусах) между ними;

4) произведение цифр заданного четырехзначного числа;

5) дробную часть среднего геометрического трех заданных положительных чисел;

6) корень уравнения: ;

7) корень уравнения: ;

8) расстояние между точками с координатами A(x1,y1) и B(x2,y2);

9) площадь треугольника со сторонами a, b, c.

2. Опишите алгоритмы в графической форме. Даны положительные вещественные числа x и y. Присвойте целой переменной z:

0) сумму цифр из дробной части чисел x и y;

1) произведение второй и третьей цифр дробной части числа x;

2) сумму цифр целой части числа x;

3) куб разности третьей и второй цифр целой части числа x;

4) произведение вторых цифр из дробной части двух чисел x и y;

5) абсолютную часть разности целых частей чисел x и y;

6) квадрат разности второй и первой цифр из дробной части числа x;

7) сумму третьих цифр из дробной части чисел x и y;

8) целую часть от квадратного корня суммы первых цифр чисел x и y;

9) целую часть частного вторых цифр из дробной части чисел x и y.

Разветвляющиеся алгоритмы

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

Алгоритм, описывающий разветвляющийся процесс представлен на рис. 5.3.

 

условие

Действие 1

Да

Нет

Действие 2

Действие 1

условие

Да

Нет

 

 

a) b)

 

Рис. 5.3. Блок-схема разветвляющегося процесса обработки информации:

a) краткая форма вида “Если …, то …”;

b) полная форма вида “Если …, то …, иначе”.

Примеры выполнения заданий

1. Опишите графическим способом алгоритм вычисления значения выражения:

Предполагается, что выражение знаменателя дроби (x + a) больше нуля.

Решение: на рис. 5.4. приведена блок-схема решения задачи.

2. Даны действительные числа x, y и z. Составьте блок-схему алгоритма вычисления: max (min (x² + y, z²), z³ - e^y).

Решение: н а рис. 5.5. приведена блок-схема решения задачи.

Начало Нет Да Да Нет Окончание REZ2 REZ2= Z^3-E^Y REZ1>Z^3-E^Y REZ2=REZ1 REZ1=Z^2 Начало X, Y, Z X^2+Y < Z^2 REZ1=X^2+Y     a, x         . Окончание z = m / n z
Рис. 5.4. Блок-схема решения задачи 1	Рис. 5.5. Блок-схема решения задачи 2

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

Опишите алгоритмы в графической форме для следующих задач:

1. Даны произвольные числа a, b, c. Если нельзя построить треугольник с такими длинами сторон, то напечатать 0, иначе напечатать 3 - если треугольник равносторонний, 2 - если треугольник равнобедренный или 1 - в противном случае.

2. Даны целые числа k и m, действительные числа x, y, z. При
k < m², k = m² или k > m², замените модулем соответственно значения x, y, z., а два других уменьшить на 0.5.

3. Для заданного числа a найдите корень уравнения f(x)=0, где:

0)	1)
2)	3)
4)	5)
6)	7)
8)	9)

4. Даны действительные числа x, y и z. Вычислите:

0) max (min (y + z, x * y), e^{(x + y)});

1) max (x, y / z) / min³ (y, z);

2) min² (x + y - z, x / y * z);

3) max (x + y, z²) / min (x, y + z);

4) max (x³ + z, min (x * z, y / z));

5) max² (x, y, z) / (x * y + z);

6) (x * y * z) / min² (x, y, z);

7) min (x / y, y / z) * max (x, y);

8) max (e^{(y + z)}, min (x², y³, z⁴));

9) min (max (x² + y, x + z³), x² + z²).

Где max – максимальное значение, а min – минимальное значение.

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

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

Иногда возникает ситуация организации “бесконечного цикла”, в таком случае принято говорить, что процесс “зацикливается”. В этом случае необходимо задать управление циклом. Существуют несколько вариантов управления циклом посредством задания условий продолжения и завершения.

Графическая схема управления циклическим процессом посредством задания условия продолжения выполнения вычислительного процесса:: a) цикл с проверкой постусловия; b) цикл с проверкой предусловия.

 

Продол-жать?

Да

Нет

Серия действий

Продол-жать?

Да

Нет

Серия действий

 

Выход из цикла

Выход из цикла

a ) b) b)

 

Примеры выполнения заданий

1.Составьте блок-схему алгоритма вычисления среднеквадратической взвешенной по формуле:

Решение: на рисунке приведен алгоритм решения задачи:

 

Начало

sum_x =0 sum_f = 0

n < 0

Нет

Ошибка

j = 1

i <= n

Нет

Да

x, f

sum_x = sum_x+x^2* f

sum_f = sum_f + f

i = i + 1

Да

x>=0 and f>=0

Нет

Да

Ошибка

Окончание

n