Из определений следует, что при
Задача 7.1.
Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида
?= пока x < y делай ?1 все.
Задача 7.2.Построить структурированные программы, вычисляющие в z следующие функции, и доказать их корректность:
- f{?}(x,y)= x*y;
- ffact(x)= x!;
- f-1(x)= x 1, где 01 = 0 и (x+1)1 = x;
- f-(x,y)= x y, где xy = x-y, если xy и xy=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).