Банк задач по математике

Задача 538

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

?

(а)

$x \leftarrow s(x) ; z \leftarrow y ; \quad u \leftarrow (s(x)<z)$ ; if $u$ then $y \leftarrow z$ ; else $y \leftarrow x$ ; end;

(б)

$x \leftarrow s(x) ; z \leftarrow y ; z \leftarrow s(z)$ ; if $x \leftarrow z$ then $y \leftarrow z$ ; else $y \leftarrow x$ ; end;

(в)

$x \leftarrow y ; \quad u \leftarrow z ; \quad u \leftarrow s(u) ; \quad x \leftarrow (u>z)$ ; while $x$ do $y \leftarrow z$ ; $u \leftarrow s(u)$ ; end;

(г)

$x \leftarrow s(z) ; z \leftarrow y ; x \leftarrow (x<x)$ ; if $x$ then $y \leftarrow z$ ; else $x \leftarrow y$ ; end;

(д)

$x \leftarrow x ; x \leftarrow x ; y \leftarrow y ; y \leftarrow y$ ;

(е)

$x \leftarrow y ; \quad u \leftarrow z ; \quad u \leftarrow s(u) ; \quad x \leftarrow (z<u)$ ; while $x$ do $y \leftarrow z$ ; $u \leftarrow s(u) ;$ end $; x \leftarrow y ;$

(ж)

$x \leftarrow s(x) ; \quad z \leftarrow y ; \quad z \leftarrow s(z) ; \quad x \leftarrow (x \leftarrow z)$ ; if $x$ then $y \leftarrow z$ ; $z \leftarrow s(z)$ ; else $y \leftarrow x$ ; end; $\circledast$

Задача 539

Для следующей структурированной программы $\Pi$ найти $\Pi (\sigma )$ , где $\sigma =\left\{ (x, 3) ;(y, 4) ;(z, 2)\right\}$ : $\circledast$

\begin{aligned} x \leftarrow y ; x \leftarrow s(x) ; y \leftarrow z ; y & \leftarrow s(y) ; z \leftarrow s(z) ; \\ y & \leftarrow s(x) ; z \leftarrow y ; z \leftarrow s(z) ; x \leftarrow s(x) ; \end{aligned}

?

Задача 540

Для структурированной программы П на рис. 34 (слева) найти $П(\sigma )$ , где $\sigma =\left\{ (x, 0) ;(y, 3) ;(z, 5) ;(u, 4); (v, 2)\right\}$ . $\circledast$

$x \leftarrow y ; x \leftarrow s(x) ; y \leftarrow u ;$
$y \leftarrow s(y) ; v \leftarrow z ; v \leftarrow s(v) ;$
$u \leftarrow (x<v) ; v \leftarrow (x<y) ;$
if $u$ then
$\quad$ if $v$ then
$\quad \quad z \leftarrow y ; z \leftarrow s(z) ;$
$\quad$ else
$\quad \quad z \leftarrow x ;$
$\quad$ end;
else
$\quad z \leftarrow s(x) ;$
end;
: Рис. 34 (слева): Программа из задач 540 и 541.

?

Задача 541

Для структурированной программы П на рис. 34 (справа) найти $\Pi (\sigma )$ , где $\sigma =\left\{ (x, 2) ;(y, 3) ;(z, 7) ;(u, 5); (v, 0)\right\}$ . $\circledast$

$x \leftarrow y ; x \leftarrow s(x) ; v \leftarrow u ;$
$v \leftarrow s(v) ;$
$z \leftarrow (x<v) ;$
while $z$ do
$\quad z \leftarrow (y<x) ;$
$\quad$ if $z$ then
$\quad \quad y \leftarrow s(y) ;$
$\quad$ else
$\quad \quad x \leftarrow s(x) ; u \leftarrow s(u) ;$
$\quad$ end;
$\quad z \leftarrow (x<v) ;$
end;
: Рис. 34 (справа): Программа из задач 540 и 541.

?

Задача 542

Написать структурированную программу $\Pi_{+}$ , которая имеет входные переменные $x$ и $y$ и вычисляет функцию $x+y$ в переменной $x$ , не изменяя $y$ . $\circledast$

?

Задача 543

Пусть $\Pi_{+}$ - это программа, которая вычисляет функцию $x+y$ в переменной $x$ , не изменяя $y$ и используя дополнительные переменные $z_{0}$ и $z_{1}$ . Какие из структурированных программ на рис. 35 вычисляют в переменной $x$ произведение $xy$ ? $\circledast$

$z_{3} \leftarrow x$ ;	$z_{3} \leftarrow y ; y \leftarrow x ;$
$z_{2} \leftarrow 0 ; x \leftarrow 0 ;$	$x \leftarrow 0 ;$
$z_{1} \leftarrow \left(z_{2}<z_{3}\right) ;$	$z_{0} \leftarrow \left(z_{2}<z_{3}\right) ;$
while $z_{1}$ do	while $z_{0}$ do
$\quad z_{1} \leftarrow 0 ; \Pi _{+}$	$\quad z_{0} \leftarrow 0 ; z_{1} \leftarrow 0 ;$
$\quad z_{0} \leftarrow 0$ ;	$\quad \Pi _{+} z_{2} \leftarrow s\left(z_{2}\right) ;$
$\quad z_{2} \leftarrow s\left(z_{2}\right) ;$	$\quad z_{0} \leftarrow \left(z_{2}<z_{3}\right) ;$
$\quad z_{1} \leftarrow \left(z_{2}<z_{3}\right) ;$	end;
end;
: Рис. 35: Программы из задачи 543.

?

Задача 544

Пусть $\Pi_{\times }$ - это программа, которая вычисляет функцию $x y$ в переменной $x$ , используя вспомогательные переменные $z_{i}, i=0,1, \ldots , m$ , построенная в задаче 543. $\Pi_{z}$ — программа, обнуляющая переменные $z_{i}: z_{0} \leftarrow 0 ; \ldots z_{m} \leftarrow 0$ ; . Какие из структурированных программ на рис. 36 вычисляют в переменной $x$ квадратный корень из $x$ , то есть функцию $\operatorname {sqrt}(x)=\lfloor \sqrt{x}\rfloor$ ? $\circledast$

$u \leftarrow x ; x \leftarrow 0 ;$	$u \leftarrow x ;$	$u \leftarrow x ; u \leftarrow s(u) ;$
while $x$ do	while $x$ do	while $x$ do
$\quad \Pi _{z} \Pi _{\times }$	$\quad y_{1} \leftarrow y ;$	$\quad y_{1} \leftarrow y ;$
$\quad y_{1} \leftarrow y ;$	$\quad y \leftarrow s(y) ;$	$\quad y \leftarrow s(y) ;$
$\quad y \leftarrow s(y) ;$	$\quad x \leftarrow y ;$	$\quad x \leftarrow y ;$
$\quad x \leftarrow (x<u) ;$	$\quad \Pi _{z} \Pi _{\times }$	$\quad \Pi _{z} \Pi _{\times }$
end;	$\quad x \leftarrow (x<u) ;$	$\quad x \leftarrow (x<u) ;$
$u \leftarrow (u<x) ;$	end;	end;
if $u$ then	$u \leftarrow (u<x) ;$	$x \leftarrow y_{1} ;$
$\quad x \leftarrow y_{1} ;$	$x \leftarrow y ;$
else	if $u$ then
$\quad x \leftarrow y ;$	$\quad x \leftarrow y_{1} ;$
end;	end;
: Рис. 36: Программы из задачи 544.

?

Задача 545

Пусть $\Pi_{\times }$ и $\Pi_{z}$ — программы из задачи 544. Какие из структурированных программ на рис. 37 вычисляют в переменной $x$ целую часть частного: $\lfloor x / y\rfloor$ ? При $y=0$ результат тоже должен быть равен нулю. $\circledast$

$u \leftarrow s(x) ; x \leftarrow 0 ;$	$u \leftarrow s(x) ; x \leftarrow 0 ; i \leftarrow y$ ;	$u \leftarrow x ; i \leftarrow y ;$
$i \leftarrow (x<u) ;$	while $i$ do	while $i$ do
while $i$ do	$\quad x \leftarrow j ;$	$\quad j_{1} \leftarrow j ;$
$\quad j_{1} \leftarrow j ;$	$\quad \Pi _{z} \Pi _{\times }$	$\quad j \leftarrow s(j) ;$
$\quad j \leftarrow s(j) ;$	$\quad i \leftarrow (x<u) ;$	$\quad x \leftarrow j ;$
$\quad \Pi _{z} \Pi _{\times }$	if $i$ then	$\quad \Pi _{z} \Pi _{\times }$
$\quad i \leftarrow (x<u) ;$	$\quad j_{1} \leftarrow j ;$	$\quad i \leftarrow (x<u) ;$
end;	end;	end;
$x \leftarrow j_{1} ;$	$j \leftarrow s(j) ;$	$i \leftarrow (u<x) ;$
	$i \leftarrow (j<u) ;$	$x \leftarrow j ;$
	end;	if $i$ then
		$\quad x \leftarrow j_{1} ;$
		end;
: Рис. 37: Программы из задачи 545.

?

Задача 546

Построить программы, вычисляющие в переменной $x$ следующие функции, и доказать их корректность. Для двухместных функций значение переменной $y$ должно остаться неизменным.

?

(а)

$\operatorname {mult}(x, y)=x y$ ;

(б)

$\operatorname {dec}(x)=x \div 1$ , где $0 \div 1=0$ и $(x+1) \div 1=x$ ;

(в)

$\operatorname {sub}(x, y)=x \div y$ , где $x \div y=x-y$ , если $x \geqslant y$ , и $x \div y=0$ иначе;

(г)

$\operatorname {fact}(x)=x!$ — факториал;

(д)

$\operatorname {div}(x, y)=\lfloor x / y\rfloor$ — целочисленное частное;

(е)

$\operatorname {sqrt}(x)=\lfloor \sqrt{x}\rfloor$ ;

(ж)

$\operatorname {pow}(x, y)=x^{y}$ — возведение в степень;

(з)

$\log (y, x)=\left\lfloor \log_{y} x\right\rfloor$ ;

(и)

$\bmod (x, y)$ — остаток от деления $x$ на $y$ ;

(к)

$\tau (x)$ — количество различных делителей числа $x, \tau (0)=0$ . $\circledast$

Задача 547

Построить программу с метками, которая по натуральному числу $i$ вычисляет число Фибоначчи $F_{i}$ . $\circledast$

?

Задача 548

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

?

(а)

$f_{1}(x, y)= \begin{cases} \lfloor (x+y) / 2\rfloor & \text{ при } x<y, \\ x^{2} y^{3} & \text{ в противном случае; }\end{cases}$

(б)

$f_{2}(x, y)= \begin{cases} 3^{y} & \text{ при } \log_{2}(x+1) \geqslant y, \\ \left|x-y\right| & \text{ в противном случае; }\end{cases}$

(в)

$f_{3}(x, y)= \begin{cases} \lfloor x y / 2\rfloor & \text{ при } \log_{2} x \leqslant y+2, \\ \left\lfloor x^{\lfloor y / 2\rfloor }\right\rfloor & \text{ в противном случае; }\end{cases}$

(г)

$f_{4}(x, y)= \begin{cases} \left\lfloor \log_{3}(x+y+1)\right\rfloor & \text{ при } 2 x \leqslant y^{3}+y, \\ \lfloor \sqrt{x+y}\rfloor & \text{ в противном случае; }\end{cases}$

(д)

$f_{5}(x, y)= \begin{cases} 1, & \text{ если } x \text{ — простое число, } \\ 0 & \text{ в противном случае. }\end{cases}$ $\circledast$

Задача 549

Для каждой из заданных ниже рекурсивными соотношениями функций $A(x, y), B(x, y), C(x, y), D(x, y), E(x, y), G(x, y)$ и $H(x, y)$ построить вычисляющую её структурированную программу:

?

(а)

$A(0, y)=y+1$ ,

\begin{aligned} & A(x+1,0)=2 A(x, 1) \\ & A(x+1, y+1)=A(x, y)+x y \end{aligned}

(б)

$B(0, y)=2 y$ ,

\begin{aligned} & B(x+1,0)=B(x, 1)+1 \\ & B(x+1, y+1)=x+B(x+1, y) \end{aligned}

(в)

$C(0, y)=y+2$ ,

\begin{aligned} & C(x+1,0)=C(x, 1)+1 \\ & C(x+1, y+1)=C(x+1, y)-x \end{aligned}

(г)

$D(x, 0)=x, D(0, y)=y$ ,

D(x+1, y+1)=D(x, y+1)+x^{y} ;

(д)

$E(0, y)=y+1$ , $E(x+1,0)=E(x, 1)$ , $E(x+1, y+1)=x E(x+1, y) ;$

(е)

$G(0, y)=3$ , $G(x+1,0)=G(x, 0)+\left\lfloor \log_{2}(x+1)\right\rfloor$ , $G(x+1, y+1)=G(x+1, y)+x^{2} y ;$

(ж)

$H(0, y)=y$ , $H(x+1,0)=H(x, 1)+2$ , $H(x+1,1)=H(x, 0)+1$ , $H(x+1, y+2)=y+H(x+1, y)$ . $\circledast$

Задача 550

Написать программу, которая будет реализовывать присваивание $a \leftarrow (b<c)$ ; , используя присваивания видов $x \leftarrow 0 ; x \leftarrow y$ ; $x \leftarrow s(y) ;$ и $x \leftarrow \operatorname {eq}(y, z) ;$ . Последнее изменяет значение $x$ на 1, если значения $y$ и $z$ равны, или на 0 в противном случае. $\circledast$

?

Задача 551

Доказать, что для вычисления любой вычислимой функции можно написать структурированную программу без ветвлений. Указание. Сначала показать, что можно написать программу без полных ветвлений. $\circledast$

?

Задача 552

Пусть программа П с одной входной переменной $x$ вычисляет в переменной $y$ некоторую всюду определённую взаимно однозначную функцию $f$ , область значений которой совпадает с множеством всех натуральных чисел $\omega$ . Пусть $\operatorname {Var}\left[\Pi \right]=\left\{ x, y, z_{1}, \ldots , z_{m}\right\}$ . Построить программу, которая вычисляет обратную к $f$ функцию $f^{-1}$ : $f^{-1}(y)=x$ , если $f(x)=y$ . $\circledast$

?

Задача 553

(а)(б)(в)

Пусть $П$ — программа и $\left|\operatorname {Var}\left[\Pi \right]\right|=m$ . Из определений следует, что при различном выборе входных переменных и выходных переменных программа может вычислять различные функции.

?

(а)

Каково максимальное количество функций от $n \leqslant m$ переменных, которое может вычислять П? Сколько всего разных функций может вычислить П? Функции, имеющие различное количество аргументов, считаем разными a priori.

(б)

Построить программу $\Pi_{m, n}$ , которая вычисляет максимальное количество различных функций от $n \leqslant m$ переменных.

(в)

Построить программу $\Pi_{m},\left|\operatorname {Var}\left[\Pi_{m}\right]\right|=m$ , которая для каждого $n \leqslant m$ вычисляет максимальное количество различных функций от $n$ переменных. $\circledast$

Задача 554

Определить, сколько всего существует попарно неэквивалентных программ с метками, имеющих не более $n$ операторов и только одну переменную, которая является одновременно входной и выходной. $\circledast$

?

Задача 555

Определить, какие всюду определённые функции могут вычисляться программами с метками, которые имеют только одну переменную, являющуюся одновременно входной и выходной, и используют только ветвления и присваивания видов $x \leftarrow s(x)$ ; и $x \leftarrow \operatorname {dec}(x)$ ;. $\circledast$

?

Задача 556

Пусть программа с метками содержит только пропозициональные переменные $x_{1}, \ldots , x_{n}$ , ветвления и присваивания с булевыми связками: $x_{i} \leftarrow x_{j} \wedge x_{k} ; x_{i} \leftarrow x_{j} \vee x_{k} ; x_{i} \leftarrow x_{j} \rightarrow x_{k} ; x_{i} \leftarrow \neg x_{j}$ ;. Предложить способ, который позволяет определить, какую функцию вычисляет такая программа. $\circledast$

?

Задача 557

Доказать, что никакая из функций $x+y, x \div y, x y$ и $\lfloor x / y\rfloor$ не вычисляется никакой структурированной программой без циклов. $\circledast$

?

Программная вычислимость