ВШ. ДЗ 1. ДП - Тест: теория сложности и подчсёт

Задача F. Тест: теория сложности и подчсёт ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	А. Ким, А. Кленин	Ограничение времени:	1 сек
Входной файл:	input.txt	Ограничение памяти:	256 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

Данная задача — тест. Требуется ответить на приведённые вопросы и отправить ответ в тестирующую систему в указанном ниже формате. Если в вопросе предлагается выбор одного из нескольких вариантов, укажите номер правильного варианта. За каждый правильный ответ будут начисляться баллы. Баллы за все вопросы, кроме нулевого, будут видны после окончания тура.

Вопрос 0

Сколько будет 3 × 3?

Вопрос 1

Функция 8 + 6 ⋅ n + 3 ⋅ n² + 3 ⋅ n⁵ является

O(n)
O(n⁵)
O(n²)
O(8)

Вопрос 2

Всякая функция, являющаяся O(n⁵), является также и

O(n^-5)
O(n^{(1 / 5)})
O(4ⁿ)
O(log(n) + n³)

Вопрос 3

Асимптотическую сложность следующего алгоритма равна Θ(m^x):

Си	Бейсик
j = pow(m, 2); for (i = 0; i <= pow(j, 2); ++i){ for (k = 0; k <= pow(m, 3); ++k){ if (k == 0) for (ib = 0; ib <= pow(j, 3); ++ib) print(ib, i, k); if (i <= pow(j, 2)) for (a = 0; a <= pow(m, 2); ++a) print(k, a, i); } for (jb = 0; jb <= pow(i, 2); ++jb) if (jb == i) for (c = 0; c <= ib; ++c) print(c, jb, i); }	j = m ^ 2 FOR i = 0 TO j ^ 2 FOR k = 0 TO m ^ 3 IF k = 0 THEN FOR ib = 0 TO j ^ 3 PRINT ib, i, k NEXT ib IF i <= j ^ 2 THEN FOR a = 0 TO m ^ 2 PRINT k, a, i NEXT a NEXT k FOR jb = 0 TO i ^ 2 IF jb = i THEN FOR c = 0 TO ib PRINT c, jb, i NEXT c NEXT jb NEXT i
Паскаль	Алгоритмический
j := m 2; for i := 0 to j 2 do begin for k := 0 to m 3 do begin if k = 0 then for ib := 0 to j 3 do write(ib, i, k); if i <= j 2 then for a := 0 to m 2 do write(k, a, i); end; for jb := 0 to i ** 2 do if jb = i then for c := 0 to ib do write(c, jb, i); end;	j := m 2 нц для i от 0 до j 2 нц для k от 0 до m 3 если k = 0 то нц для ib от 0 до j 3 вывод ib, i, k кц все если i <= j 2 то нц для a от 0 до m 2 вывод k, a, i кц все кц нц для jb от 0 до i ** 2 если jb = i то нц для c от 0 до ib вывод c, jb, i кц все кц кц

Си

Бейсик

j = pow(m, 2);
for (i = 0; i <= pow(j, 2); ++i){
  for (k = 0; k <= pow(m, 3); ++k){
    if (k == 0)
      for (ib = 0; ib <= pow(j, 3); ++ib)
        print(ib, i, k);
    if (i <= pow(j, 2))
      for (a = 0; a <= pow(m, 2); ++a)
        print(k, a, i);
  }
  for (jb = 0; jb <= pow(i, 2); ++jb)
    if (jb == i)
      for (c = 0; c <= ib; ++c)
        print(c, jb, i);
}

j = m ^ 2
FOR i = 0 TO j ^ 2
  FOR k = 0 TO m ^ 3
    IF k = 0 THEN FOR ib = 0 TO j ^ 3
      PRINT ib, i, k
    NEXT ib
    IF i <= j ^ 2 THEN FOR a = 0 TO m ^ 2
      PRINT k, a, i
    NEXT a
  NEXT k
  FOR jb = 0 TO i ^ 2
    IF jb = i THEN FOR c = 0 TO ib
      PRINT c, jb, i
    NEXT c
  NEXT jb
NEXT i

Паскаль

Алгоритмический

j := m ** 2;
for i := 0 to j ** 2 do begin
  for k := 0 to m ** 3 do begin
    if k = 0 then
      for ib := 0 to j ** 3 do
        write(ib, i, k);
    if i <= j ** 2 then
      for a := 0 to m ** 2 do
        write(k, a, i);
  end;
  for jb := 0 to i ** 2 do
    if jb = i then
      for c := 0 to ib do
        write(c, jb, i);
end;

j := m ** 2
нц для i от 0 до j ** 2
  нц для k от 0 до m ** 3
    если k = 0 то
      нц для ib от 0 до j ** 3
        вывод ib, i, k
      кц
    все
    если i <= j ** 2 то
      нц для a от 0 до m ** 2
        вывод k, a, i
      кц
    все
  кц
  нц для jb от 0 до i ** 2
    если jb = i то
      нц для c от 0 до ib
        вывод c, jb, i
      кц
    все
  кц
кц

Чему равен x?

Вопрос 4

Дан алгоритм

Си	Бейсик
for (j = 0; j <= pow(m, 2); ++j){ b = m; for (k = 0; k <= pow(b, 2); ++k) print(j, k); for (c = 0; c <= pow(k, 3); ++c) for (i = 0; i <= pow(c, 3); ++i){ cc = m; if (XXXXX) for (ib = 0; ib <= pow(c, 3); ++ib) print(i, ib, j, c); for (kj = 0; kj <= pow(m, 3); ++kj) print(i, c, j, kj); } }	FOR j = 0 TO m ^ 2 b = m FOR k = 0 TO b ^ 2 PRINT j, k NEXT k FOR c = 0 TO k ^ 3 FOR i = 0 TO c ^ 3 cc = m IF XXXXX THEN FOR ib = 0 TO c ^ 3 PRINT i, ib, j, c NEXT ib FOR kj = 0 TO m ^ 3 PRINT i, c, j, kj NEXT kj NEXT i NEXT c NEXT j
Паскаль	Алгоритмический
for j := 0 to m 2 do begin b := m; for k := 0 to b 2 do write(j, k); for c := 0 to k 3 do for i := 0 to c 3 do begin cc := m; if XXXXX then for ib := 0 to c 3 do write(i, ib, j, c); for kj := 0 to m 3 do write(i, c, j, kj); end; end;	нц для j от 0 до m 2 b := m нц для k от 0 до b 2 вывод j, k кц нц для c от 0 до k 3 нц для i от 0 до c 3 cc := m если XXXXX то нц для ib от 0 до c 3 вывод i, ib, j, c кц все нц для kj от 0 до m 3 вывод i, c, j, kj кц кц кц кц

Си

Бейсик

for (j = 0; j <= pow(m, 2); ++j){
  b = m;
  for (k = 0; k <= pow(b, 2); ++k)
    print(j, k);
  for (c = 0; c <= pow(k, 3); ++c)
    for (i = 0; i <= pow(c, 3); ++i){
      cc = m;
      if (XXXXX)
        for (ib = 0; ib <= pow(c, 3); ++ib)
          print(i, ib, j, c);
      for (kj = 0; kj <= pow(m, 3); ++kj)
        print(i, c, j, kj);
    }
}

FOR j = 0 TO m ^ 2
  b = m
  FOR k = 0 TO b ^ 2
    PRINT j, k
  NEXT k
  FOR c = 0 TO k ^ 3
    FOR i = 0 TO c ^ 3
      cc = m
      IF XXXXX THEN FOR ib = 0 TO c ^ 3
        PRINT i, ib, j, c
      NEXT ib
      FOR kj = 0 TO m ^ 3
        PRINT i, c, j, kj
      NEXT kj
    NEXT i
  NEXT c
NEXT j

Паскаль

Алгоритмический

for j := 0 to m ** 2 do begin
  b := m;
  for k := 0 to b ** 2 do
    write(j, k);
  for c := 0 to k ** 3 do
    for i := 0 to c ** 3 do begin
      cc := m;
      if XXXXX then
        for ib := 0 to c ** 3 do
          write(i, ib, j, c);
      for kj := 0 to m ** 3 do
        write(i, c, j, kj);
    end;
end;

нц для j от 0 до m ** 2
  b := m
  нц для k от 0 до b ** 2
    вывод j, k
  кц
  нц для c от 0 до k ** 3
    нц для i от 0 до c ** 3
      cc := m
      если XXXXX то
        нц для ib от 0 до c ** 3
          вывод i, ib, j, c
        кц
      все
      нц для kj от 0 до m ** 3
        вывод i, c, j, kj
      кц
    кц
  кц
кц

Чтобы сложность этого алгоритма составляла Θ(m⁴²), строку XXXXX следует заменить на выражение

i = j
j ≤ b²
j ≤ cc
j = 0

Вопрос 5

Асимптотическую сложность следующего алгоритма равна Θ(m^x):

Си	Бейсик
for (i = 0; i <= pow(m, 3); ++i) for (j = 0; j <= pow(m, 2); ++j){ k = m; for (ib = 0; ib <= k; ++ib) for (b = 0; b <= pow(m, 3); ++b) print(j, i, ib, b); if (i == 0) for (jj = 0; jj <= ib; ++jj) for (ba = 0; ba <= pow(b, 2); ++ba) print(jj, j, ba, i); }	FOR i = 0 TO m ^ 3 FOR j = 0 TO m ^ 2 k = m FOR ib = 0 TO k FOR b = 0 TO m ^ 3 PRINT j, i, ib, b NEXT b NEXT ib IF i = 0 THEN FOR jj = 0 TO ib FOR ba = 0 TO b ^ 2 PRINT jj, j, ba, i NEXT ba NEXT jj NEXT j NEXT i
Паскаль	Алгоритмический
for i := 0 to m 3 do for j := 0 to m 2 do begin k := m; for ib := 0 to k do for b := 0 to m 3 do write(j, i, ib, b); if i = 0 then for jj := 0 to ib do for ba := 0 to b 2 do write(jj, j, ba, i); end;	нц для i от 0 до m 3 нц для j от 0 до m 2 k := m нц для ib от 0 до k нц для b от 0 до m 3 вывод j, i, ib, b кц кц если i = 0 то нц для jj от 0 до ib нц для ba от 0 до b 2 вывод jj, j, ba, i кц кц все кц кц

Си

Бейсик

for (i = 0; i <= pow(m, 3); ++i)
  for (j = 0; j <= pow(m, 2); ++j){
    k = m;
    for (ib = 0; ib <= k; ++ib)
      for (b = 0; b <= pow(m, 3); ++b)
        print(j, i, ib, b);
    if (i == 0)
      for (jj = 0; jj <= ib; ++jj)
        for (ba = 0; ba <= pow(b, 2); ++ba)
          print(jj, j, ba, i);
  }

FOR i = 0 TO m ^ 3
  FOR j = 0 TO m ^ 2
    k = m
    FOR ib = 0 TO k
      FOR b = 0 TO m ^ 3
        PRINT j, i, ib, b
      NEXT b
    NEXT ib
    IF i = 0 THEN FOR jj = 0 TO ib
      FOR ba = 0 TO b ^ 2
        PRINT jj, j, ba, i
      NEXT ba
    NEXT jj
  NEXT j
NEXT i

Паскаль

Алгоритмический

for i := 0 to m ** 3 do
  for j := 0 to m ** 2 do begin
    k := m;
    for ib := 0 to k do
      for b := 0 to m ** 3 do
        write(j, i, ib, b);
    if i = 0 then
      for jj := 0 to ib do
        for ba := 0 to b ** 2 do
          write(jj, j, ba, i);
  end;

нц для i от 0 до m ** 3
  нц для j от 0 до m ** 2
    k := m
    нц для ib от 0 до k
      нц для b от 0 до m ** 3
        вывод j, i, ib, b
      кц
    кц
    если i = 0 то
      нц для jj от 0 до ib
        нц для ba от 0 до b ** 2
          вывод jj, j, ba, i
        кц
      кц
    все
  кц
кц

Чему равен x?

Вопрос 6

Определите количество вызовов функции f при исполнении следующего алгоритма (в предположении неограниченной длины целых чисел):

Си	Бейсик
int f(int n) { int f; if (n >= 55555555555) f = f(n / 5) + 1; if (n < 55555555555 && n >= 5263157894) f = f(n - 3) + 1; if (n < 5263157894) f = 1; return f; } print(f(1000000000000));	FUNCTION f(n) IF n >= 55555555555 THEN f = f(n / 5) + 1 IF n < 55555555555 AND n >= 5263157894 THEN f = f(n - 3) + 1 IF n < 5263157894 THEN f = 1 END FUNCTION PRINT f(1000000000000)
Паскаль	Алгоритмический
function f(n: integer): integer; begin if n >= 55555555555 then f := f(n / 5) + 1; if (n < 55555555555) and (n >= 5263157894) then f := f(n - 3) + 1; if n < 5263157894 then f := 1; end; write(f(1000000000000));	алг цел f(цел n) нач если n >= 55555555555 то f := f(n / 5) + 1 все если n < 55555555555 и n >= 5263157894 то f := f(n - 3) + 1 все если n < 5263157894 то f := 1 все кон вывод f(1000000000000)

Си

Бейсик

int f(int n) {
  int f;
  if (n >= 55555555555)
    f = f(n / 5) + 1;
  if (n < 55555555555 && n >= 5263157894)
    f = f(n - 3) + 1;
  if (n < 5263157894)
    f = 1;
  return f;
}

print(f(1000000000000));

FUNCTION f(n)
  IF n >= 55555555555 THEN f = f(n / 5) + 1
  IF n < 55555555555 AND n >= 5263157894 THEN f = f(n - 3) + 1
  IF n < 5263157894 THEN f = 1
END FUNCTION

PRINT f(1000000000000)

Паскаль

Алгоритмический

function f(n: integer): integer;
begin
  if n >= 55555555555 then
    f := f(n / 5) + 1;
  if (n < 55555555555) and (n >= 5263157894) then
    f := f(n - 3) + 1;
  if n < 5263157894 then
    f := 1;
end;

write(f(1000000000000));

алг цел f(цел n)
нач
  если n >= 55555555555 то
    f := f(n / 5) + 1
  все
  если n < 55555555555 и n >= 5263157894 то
    f := f(n - 3) + 1
  все
  если n < 5263157894 то
    f := 1
  все
кон

вывод f(1000000000000)

Вопрос 7

Известно, что в дереве, каждый узел которого имеет степень либо 6 (внутренний узел), либо 0 (листовой узел), имеется 1486 листовых узлов. Определите количество узлов в этом дереве.

Вопрос 8

Известно, что в дереве, каждый узел которого имеет степень либо 5, либо 0, высота равна 7. Определите максимально возможное количество узлов такого дерева. (Высота дерева — максимальная длина пути от вершины дерева до его корня. Например, высота дерева, состоящего только из корня, равна 0.)

Вопрос 9

Графическая последовательность чисел — последовательность целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней. Какая из следующих последовательностей является графической?

5,5,2,2,1,1
5,4,3,3,2,1
5,4,3,2,1,1
5,5,4,3,2,1

Формат выходного файла

В качестве решения принимается текстовый файл, содержащий по одному числу в строке — ответы на каждый из вопросов. При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text". Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.