Задачи для самостоятельного решения

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

• 5.1. Предлагается разработать машину деления целых двоичных 8-разрядных чисел в той последовательности шагов, которая использовалась для машины умножения:
  • • разработать рекуррентную формулу для деления (см. подпараграф 5.3.1);
  • • составить описание алгоритма вычисления на языке логики;
  • • тестировать алгоритм в C++;
  • • построить структурную схему машины деления;
  • • построить модель алгоритма в форме конечного автомата (см. подпараграф 5.3.3);
  • • тестировать КА в C++.
• 5.2. Предлагается разработать машину вычисления функции sinх в целых числах. Необходимые операции деления и умножения в современной элементной базе выполняются специальными схемами. Таким образом, достаточно организовать управление соответствующими процедурами.

Пояснения к задаче. Вычисления с фиксированной точкой^[1] позволяют существенно сократить время вычислений и объем программ, если операнды имеют ограниченную область значений (например, только дробные). Формирование рекуррентной формулы приближения осуществляется с использованием разложения функции в ряд Тейлора:

при всех х < 1. Вычисления рядов выполняются по схеме Горнера или по формуле с общим членом ряда.

Преобразование, но схеме Горнера:

Выберем аргумент в диапазоне дробных чисел 0—0,99 радиан и преобразуем в целые с масштабом т:

^sb= 1 — x^[2]/a_iS_i —> $i+1 = (т — (x²/m/afSi)/m). Вычисления в C++ в целых числах с двоичным масштабом т = 2⁸:

unsigned int х, у, S;

main ().

{.

while (1).

for (x = 0; х < Oxff; х++).

{ у = (х * х) «8; S = Oxff; // у = (х * х)/т, S₀ = Oxff.

S = Oxff — ((у * S) «8) /42;

S = Oxff — ((y * S) «8)/20;

S = Oxff — ((y * S) «8) /6;

P2 = (S * x) «8;

}.

При вычитании в формате байта используем значение единицы Oxff в масштабе т = 2⁸. Если вычитаемое не равно нулю, можно добавить единицу для повышения точности.

Очевидно, что эту тему можно рассматривать применительно ко всем известным приближениям.

• 5.3. На рис. 5.4 представлено конструктивное размещение элементов неориентированного графа на плоскости. Требуется сформулировать в логике задачу выбора минимального числа плоскостей для размещения ребер графа без пересечений, полагая, что существует доступ конечных точек ребра к элементам на плоскости, где размещены элементы. Разработать программу на C++.
• 5.4. Требуется сформулировать в логике задачу поиска минимального пути на ориентированном графе (см. рис. 5.5), используя дизъюнкты, определяемые коэффициентом разветвления вершин. Разработать программу на C++.
• 5.5. Требуется разработать логику алгоритма работы с простой базой данных из параграфа 5.5 и (или) подпараграфа 5.6.1. Разработать программу на C++.

• [1] Довгий П. С., Скорубский В. И. Организация ЭВМ. Пособие к лабораторным. СПб. :
• [2] Изд-во НИУ ИТМО, 2009.