PI-16 ИДЗ Гаев

1

1. Пусть дан фрагмент программы:

S:=0;
For i:=1 to n do
begin s:=s+A[i, j, k, m];
For j:=1 to n do
begin s:=s+A[i, j, k, m];
For k:=1 to i+j do s:=s+A[i, j, k, m]; end; end;
For m:=1 to n do s:=s+A[i, j, k, m];
Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 50? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы

S:=0; readln(n);
For i:=1 to n do
For j:=i to n do
For k:=j to i+j do
s:=s+A[i, j]
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы

S:=0; j:=1; readln(n);
Repeat
k:=1;
While k< j do
Begin s:=s+A[j, k];
k:=k*2;
end;
j:=j+3;
Until j > n do
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана функция
Function V(n : integer) : integer;
Var i, j, S :integer;
Begin S:=0;
For i:=n to 2*n do
begin
if i<=n then readln(a[i]);
else For j:=1 to n do a[j]:=i*j;
S:=S+a[i];
end;
V:=S; {result:=S}
End;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
var t:integer;
begin n0:=10;
for t:=1 to 10 do
if V(15) * V(10) > t*10
then Writeln (V(n0)+V(15))
else Writeln (V(30));
End;



Вариант № 2

1. Пусть дан фрагмент программы:
S:=0;
For i:=1 to n do
begin s:=s+i;
For j:=1 to n do s:=s+j; end;
For k:=1 to 3*n do
begin s:=s+A[i, j, k, k];
For m:=1 to n do s:=s+A[i, j, k, m]; end;
Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 70? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы
S:=0; readln(n);
For i:=1 to n do
For j:=1 to i do
For k:=1 to i+j do
s:=s+A[i, j ,k]
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы
S:=0; readln(n);
For i:=1 to n do
Begin
j:=1;
While j< n do
Begin k:=1;
Repeat
s:=s+A[i, i, k];
k:=k+2;
Until k>= n;
j:=j*2;
end;
end

Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана функция
Function Z(n, m : integer): integer;
Var i, j :integer;
begin
if m<=n
then
For i:=1 to n do a[i]:=i*m
else
For j:=1 to m*m do a[j]:=j*n;
Z:=n+m; {result:=n+m}
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
var t:integer;
begin
for t:=1 to 15 do
if Z(10, 20) > t*t
then Writeln (Z(30, 28)
else Writeln (Z(20, 10)+Z(5, 25));
End;



Вариант № 3

1. Пусть дан фрагмент программы:
S:=0;
For i:=1 to n*n do
begin s:=s+A[4, 3, 2, 1];
For j:=1 to 2*i do
begin s:=s+A[5, 6, 7, 8];
For k:=1 to n do s:=s+A[2, 3, 4, 5]; end; end;
For m:=1 to n do s:=s+A[1, 2, 3, 4];
Сколько раз за время выполнения фрагмента происходило обращений к элементам массива A, если n = 80? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы
S:=0; readln(n);
For i:=1 to n do
Begin j:=1;
While j< n-i do
begin
For k:=1 to j do s:=s+A[i, j, k];
j:=j+2;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы:
S:=0; readln(n);
For i:=1 to n do
Begin j:=1;
While j< n do
Begin m:=n
While m<= n do
begin
For k:=1 to n-2 do s:=s+A[i,k];
m:=m+1;
end;
j:=j*3;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана процедура
Procedure G(n, x : integer);
Var i, j :integer;
begin
S:=0;
For i:=n to 4*n do
if a[i] > х then
For j:=1 to n do s:=s+A[j];
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
Var t, u : integer;
begin
for u:=1 to 10 do begin G(u, 10)
for t:=1 to 20 do G(t, u);
end;
End;


Вариант № 4

1. Пусть дан фрагмент программы:
S:=0;
For i:=1 to n do
begin s:=s+A[i, j, k, m];
if i> n/2 then
For j:=1 to n do s:=s+A[2, 3, 2, 3];
For k:=1 to n+j do
begin s:=s+A[1, 2, 3, 4];
if i+j+k < 2*k then
For m:=1 to n do s:=s+A[i,j,k,m];
end; end;
Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 30? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы

S:=0; readln(x, n);
For i:=1 to n do
For k:=1 to х+i do
For j:=1 to n do
s:=s+A[i, j]

Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы:
S:=0; readln(n);
For i:=1 to n do
Begin
j:=1;
While j< n do
Begin k:=1;
Repeat
s:=s+A[i, i, k];
k:=k+2;
Until k< n;
j:=j+j;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана процедура
Procedure H(n : integer);
Var i, j :integer;
begin
For i:=2 to n*n*n do
Begin a[i]:=0;
if i<=n then a[i]:=a[i-1]+i;
end;
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
Var t : integer;
begin
H(10);
for t:=1 to 20 do H(2*t);
end;



Вариант № 5

1. Пусть дан фрагмент программы:
i:=1; j:=1; k:=1; m:=1;
S:=0;
For i:=1 to n do begin s:=s+A[5, 6, 7, 8];
For j:=1 to n-i do begin s:=s+A[1, 2, 3, 2];
For k:=1 to n do
if k=n then s:=s+A[2, 3, 4, 5]; end;
For m:=1 to n do
if mСколько раз за время выполнения фрагмента выполнялась ветка THEN операторов if, если n = 60? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы
S:=0;
For i:=1 to n do
Begin k:=1;
For j:=1 to n-1 do
begin
k:=k+1;
For m:=i downto 1 do
s:=s+A[i, j, k, m];
end;
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы:
S:=0; readln(n);
For i:=1 to n do
Begin
j:=1; While j< n do
Begin k:=j;
While k< n*i do
Begin s:=s+A[i, j, k];
k:=k+5;
end;
j:=j*2;
end;
end
Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(N), где N – длина входа

4. Пусть дана процедура
Procedure P(n : integer);
Var i, j :integer;
begin
For i:=n to n*n do
if i For j:=1 to n do readln(a[i])
else
A[i]:=A[i-n];
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5 Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
Var t1, t2 : integer;
begin

for t1:=1 to 20 do
begin
P(t1);
For t2:=1 to t1 do P(t2);
end; end;

Вариант № 6

1. Пусть дан фрагмент программы:

S:=0;
For i:=1 to 2*n do
begin s:=s+A[i, 3]+i;
For j:=1 to n-1 do
begin s:=s+A[i, j]+2*j;
·end;
For k:=1 to i do s:=s+A[k, j];
For m:=1 to n-1 do s:=s+A[m, i]; end;
Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 50(Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы

S:=0; readln(n);
For i:=1 to n-1 do
For j:=i to n+i do
For k:=1 to j do
s:=s+A[i, j mod n]

Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы

S:=0; j:=1; readln(n);
Repeat
k:=n;
While k > j do
Begin s:=s+A[j, k];
k:=k div 5;
end;
j:=j + 2;
Until j >= n do
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

1. Пусть дана функция

Function W(n : integer) : integer;
Var i, j, S :integer;
Begin S:=0;
For i:=1 to n-3 do
begin
if i<=n then readln(a[i]);
else For j:=1 to n do a[j]:=i*j;
S:=S+a[i];
end;
W:=S; {result:=S}
End;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
var t:integer; n0:integer;
begin n0:=20;
for t:=1 to 10 do
if W(n0)* W(15) < t*10
then Writeln (W(n0))
else Writeln (W(3)* W(5));
End;



Вариант № 8

1. Пусть дан фрагмент программы:
S:=0;
For i:=1 to n do
begin s:=s+A[i];
For j:=1 to n+i do a[i]:=s+A[j]; end;
For k:=1 to n do
begin s:=s+A[k];
For m:=1 to n do s:=s+A[m]; end;
Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 10? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы
S:=0; readln(n);
For i:=1 to n - 2 do
For j:=1 to i do
Begin s:=s+A[i, j ,i]
For k:=1 to j*j do
s:=s+A[i, j ,k mod n]
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы
S:=0; readln(n);
For i:=1 to n do
Begin
j:=i;
While j > 1 do
Begin k:=i;
Repeat
s:=s+A[i, i, k];
k:=k+2;
Until k >= n;
j:=j div 2;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана функция
Function Y(n, m : integer): integer;
Var i, j :integer;
begin
if m<=n
then
For i:=1 to 2*n do a[i]:=i*m
else
For j:=1 to m div 2 do a[j]:=j*n;
Y:=n+m; {result:=n+m}
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
var t:integer;
begin
for t:=1 to 15 do
if Y(20, 20) - Y(10, 10) > t
then Writeln (Y(10, 10)
else Writeln (Y(20, 10)-Y(5, 25));
End;



Вариант № 10

1. Пусть дан фрагмент программы:
i:=1; j:=1; k:=1; m:=1;
S:=0;
For i:=1 to n do begin s:=s+A[i];
For j:=1 to n do if a[j]>0 then s:=s+A[j];
For k:=1 to n do
if kFor m:=1 to n do
if m > n then s:=s+A[m] else if m=n then s:=2*s else s:=0;
Сколько раз за время выполнения фрагмента выполнялись ветви “НЕТ” (else) в операторах if, если n = 60? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

3. Пусть дан фрагмент программы
S:=0;
For i:=1 to n do
Begin k:=1;
For j:=1 to n-1 do
begin k:=k+1;
For m:=i+j to 2*n do s:=s+A[i, j];
end;
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы:
S:=0; readln(n);
For i:=1 to n do
Begin
j:=1;While j< n do
Begin k:=j;
While k< n*i do
Begin s:=s+A[i, j, k]; k:=k*5; end;
j:=j+3;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана процедура
Procedure B(n : integer);
Var i, j :integer;
begin
For i:=n to 3*n do
if i For j:=1 to n do readln(a[i])
else
A[i]:=A[i-n];
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)
Var t1, t2 : integer;
begin
for t1:=1 to 20 do
begin
For t2:=1 to t1*t1 do B(t1);
B(10);
end; end;




Вариант № 12

1. Пусть дан фрагмент программы:
S:=0;
For i:=1 to n do
begin if A[i]>0 then s:=s+A[i];
For j:=1 to 2*i*n do s:=s + A[j];
For k:=i to n do
begin s:=s + A[k];
if i For m:=1 to n do if A[m]>0 then s:=s+A[m];
end; end;
Сколько раз за время выполнения фрагмента проверялось условие в операторах if, если n = 30? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы

S:=0; readln(x, n);
For i:=1 to n do
For k:=x to x*i do
For j:=1 to n*i do
s:=s+A[i, j]
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы:
S:=0; readln(n);
For i:=1 to n do
Begin
j:=1;
While j< n do
Begin k:=n-j;
Repeat
s:=s+A[i, i, k];
k:=k-2;
Until k < n div 4;
j:=j*10;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана процедура

Procedure F(n : integer);
Var i, j :integer;
begin
For i:=2 to 2*n do
Begin a[i]:=0;
if i<=n then a[i]:=a[i-1]+i;
end;
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5. Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
Var t1, t2 : integer;
begin
F(20);
for t1:=1 to 10 do begin F(t1);
for t2:=1 to t2 do F(50);
end; end;

Вариант № 14

1. Пусть дан фрагмент программы:
S:=0; For i:=1 to n*2 do
begin s:=s+A[i];
For j:=1 to n - 2 do
begin s:=s+A[j];
For k:=1 to j do s:=s+A[k]; end; end;
For m:=1 to n - 4 do s:=s+A[m];
Сколько раз в указанном фрагменте выполняется операция адресации к элементу массива A, если n = 200? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

2. Пусть дан фрагмент программы
S:=0; readln(n);
For i:=1 to n do
Begin j:=1;
While j< n-i do
begin
For k:=i*i to n*n do s:=s+A[i, j];
j:=j+2;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

3. Пусть дан фрагмент программы:
S:=0; readln(n);
For i:=1 to n do
Begin j:=1;
While j< i*(i-1) do
Begin m:=n div 2;
While m<= n do
begin
For k:=1 to n do s:=s+A[1,3,4];
m:=m + n div 4;
end;
j:=j*3;
end;
end
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

4. Пусть дана процедура
Procedure R(n, x : integer);
Var i, j :integer;
begin
S:=0;
For i:=1 to 2*n do
if a[i] > х then
For j:=1 to n*n do
s:=s+A[j]
end;
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки (( f(N)), O(f(N)), (( f(N)), o(f(N)), (( f(N)), где N – длина входа.

5 Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в задании №4
Var t, u : integer;
begin
for q:=1 to 10 do begin R(5, q)
for t:=1 to 20 do R(2*t, q);
end;
End;



Заголовок 1 Заголовок 2 Заголовок 315

Приложенные файлы

  • doc 166702
    Размер файла: 150 kB Загрузок: 0

Добавить комментарий