Билеты к РК (Трудоемкость алгоритмов) (1016831)

Контрольная работа по теме «Трудоемкость алгоритмов»

Вариант № 1

Шифр ____________ Группа_____________

Студент ______________________________

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

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 – длина входа.

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]

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

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 n 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? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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.

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

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 – длина входа.

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]

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

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? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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. Пусть дана процедура

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 – длина входа.

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

S:=0; readln(n);

For i:=1 to n do

Begin j:=1;

While j< n-i do

begin

For k:=i to j do s:=s+A[i, j, k];

j:=j+2;

end;

end

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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, i, k];

m:=m+1;

end;

j:=j*3;

end;

end

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

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

S:=0;

For i:=1 to n*n do

begin s:=s+A[4, 3, 2, 1];

For j:=1 to n 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];

Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 80? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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. Пусть дана процедура

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 – длина входа.

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]

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

S:=0;

For i:=1 to n do

begin s:=s+A[i, j, k, m];

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? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

Var t : integer;

begin

H(10);

for t:=1 to 20 do H(2*t);

end;

Контрольная работа по теме «Трудоемкость алгоритмов»

Вариант № 5

Шифр ____________ Группа_____________

Студент ______________________________

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

Procedure P(n : integer);

Var i, j :integer;

begin

For i:=n to n*n do

if i<n then

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 – длина входа.

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 to j do

s:=s+A[i, j, k, m];

end;

end;

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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. Пусть дан фрагмент программы:

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 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<n then s:=s+A[i, j, k, m];

Сколько раз за время выполнения фрагмента выполнялись (true) условия в операторах if, если n = 60? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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. Пусть дана функция

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 – длина входа.

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

S:=0; readln(n);

For i:=1 to n-1 do

For j:=i to n do

For k:=j-i+1 to j do

s:=s+A[i, j]

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

S:=0;

For i:=1 to 2*n do

begin s:=s+A[2, 3, 5, 2];

For j:=1 to n-1 do

begin s:=s+A[8, 2, 3, 4]; end;

For k:=1 to n do s:=s+A[6, 5, 4, 3];

For m:=1 to n-1 do s:=s+A[8, 3, 4, 5]; end;

Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 50? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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;

Контрольная работа по теме «Трудоемкость алгоритмов»

Вариант № 7

Шифр ____________ Группа_____________

Студент ______________________________

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

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 – длина входа.

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:=i to j do

s:=s+A[i, j ,k]

end

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

S:=0;

For i:=1 to n do

begin s:=s+A[i, j, k, m];

For j:=1 to n do s:=s+A[i, j, k, m]; end;

For k:=1 to n do

begin s:=s+A[i, j, k, m];

For m:=1 to n do s:=s+A[i, j, k, m]; end;

Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 100? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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;

Контрольная работа по теме «Трудоемкость алгоритмов»

Вариант № 8

Шифр ____________ Группа_____________

Студент ______________________________

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

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 – длина входа.

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

S:=0; readln(n);

For i:=1 to n do

Begin j:=1;

While j< n-i do

begin

For k:=i to n-j do

s:=s+A[i, j, k]; j:=j+2;

end;

end

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

S:=0; For i:=1 to n*2 do

begin s:=s+A[i, j, k, m];

For j:=1 to n - 2 do

begin s:=s+A[i, j, k, m];

For k:=1 to n do s:=s+A[i, j, k, m]; end; end;

For m:=1 to n - 4 do s:=s+A[i, j, k, m];

Сколько раз за время выполнения фрагмента происходило изменение ячейки S, если n = 200? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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;

Контрольная работа по теме «Трудоемкость алгоритмов»

Вариант № 9

Шифр ____________ Группа_____________

Студент ______________________________

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

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 – длина входа.

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]

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

S:=0;

For i:=1 to n do

begin s:=s+A[1, 3, 1, 3];

For j:=1 to 2*i*n do s:=s + A[1, 2, 4, 4];

For k:=i to n do

begin s:=s + A[5, 3, 4, 5];

if i+j+k< 2*k then

For m:=1 to n do s:=s+A[1, 3, 6, 4];

end; end;

Сколько раз за время выполнения фрагмента проверялось условие в операторе if, если n = 30? (Указание: получить формулу для вычисления)

5. Определите асимптотическую оценку функции роста трудоемкости O(N) следующего фрагмента программы (с учетом задания №1 и предложенного Вами на него ответа) и предполагаемое фактическое число инструкций f(N)

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;

Контрольная работа по теме «Трудоемкость алгоритмов»

Вариант № 10

Шифр ____________ Группа_____________

Студент ______________________________

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

Procedure B(n : integer);

Var i, j :integer;

begin

For i:=n to 3*n do

if i<n then

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 – длина входа.

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 to j do

s:=s+A[i, j, k, m];

end;

end;

Определите асимптотическую оценку функции роста трудоемкости данного алгоритма O(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

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

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

i:=1; j:=1; k:=1; m:=1;

S:=0;

For i:=1 to n do begin s:=s+A[8, 6, 6, 7];

For j:=1 to n do s:=s+A[9, 1, 3, 5];

For k:=1 to n do

if k<n then s:=s+A[3, 5, 7, 9]; end;

For m:=1 to n do

if m<n then s:=s+A[3, 5, 6, 8];

Сколько раз за время выполнения фрагмента выполнялись (true) условия в операторах if, если n = 60? (Указание: получить формулу для вычисления)

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;