Введение в схемы, автоматы и алгоритмы

Из определений следует, что при


Задача 7.1.
Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида
?= пока x < y делай ?1 все.
Задача 7.2.Построить структурированные программы, вычисляющие в z следующие функции, и доказать их корректность:
  • f{?}(x,y)= x*y;
  • ffact(x)= x!;
  • f-1(x)= x
    1, где 0
    1 = 0 и (x+1)
    1 = x;
  • f-(x,y)= x
    y, где x
    y = x-y, если x
    y и x
    y=0, если x < y;
  • fsqr(x)= [sqrt x];
  • fexp(x)= 2x;
  • flog(x)= [log2x];
  • f/(x,y)= [x/y].

Задача 7.3.
Пусть ? - структурированная программа и |Var?| = m. Из определений следует, что при различной фиксации входных переменных и выходной переменной программа может вычислять различные функции.
  • Каково максимальное число функций от n
    m переменных, которое может вычислять ?? Сколько всего разных функций может вычислить ??
  • Постройте программу ?(m,n), которая вычисляет максимальное число различных функций от n
    m переменных.
  • Постройте программу ?(m) с |Var?| = m, которая для каждого n
    m вычисляет максимальное число различных функций от n переменных.

Задача 7.4.Построить структурированные программы, вычисляющие в z следующие функции:









Задача 7.5.
Пусть структурированная программа ? вычисляет в переменной y некоторую всюду определенную взаимно однозначную функцию f(x), область значений которой совпадает с множеством всех натуральных чисел N. Пусть Var?={x, y, z1,… , zm}. Постройте структурированную программу, которая вычисляет обратную функцию f-1(x) = { z | f(z)=x}.
Задача 7.6. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) (элементы последовательности F(x) называются числами Фибоначчи). Постройте структурированную программу, которая вычисляет функцию F(x).

Содержание раздела