Рекурсивное программирование (стр. 5 )

  4+1  4+2

  2+2+1  ! 4+1+1

  2+1+1+1  2+2+2

  1+1+1+1+1  ! 2+2+1+1

  ! 2+1+1+1+1

  ! 1+1+1+1+1+1

Теперь выпишем строки, оставшиеся непомеченными, то есть те, которые добавлены по другому закону (как раз и определяющему наше X):

  4+2

  2+2+2

Интересно, что все они составлены из четных чисел. Поделим все эти числа на 2, получим

  2+1

  1+1+1

А теперь обращаем внимание, что это как раз разложение числа 3, которое можно получить из числа 6 тоже делением на 2. Итого получаем X=K(i div 2)

А окончательное рекуррентное соотношение имеет вид

  K(i-1), если i нечетное и  K(i-1)+K(i div 2), если i четное.

Второй тестовый пример

  N=7  N=8

  4+2+1  8

  4+1+1+1  4+4

  2+2+2+1  4+2+2

  2+2+1+1+1  ! 4+2+1+1

  2+1+1+1+1+1  ! 4+1+1+1+1

  1+1+1+1+1+1+1  2+2+2+2

  ! 2+2+2+1+1

  ! 2+2+1+1+1+1

  ! 2+1+1+1+1+1+1

  ! 1+1+1+1+1+1+1+1

Непомеченными остались строки:

  8

  4+4

  4+2+2

  2+2+2+2

После деления всех чисел на 2 получим

  4

  2+2

  2+1+1

  1+1+1+1

А это как раз и есть разложение числа 4, которое может быть получено из исходного N=8 делением на 2. И тогда полное решение задачи может состоять в рекуррентном заполнении массива K[1..N] и выводе значения K[N].

Можно также заметить, что k[2]=k[1]+k[2 div 2]=k[1]+k[1]=2

То есть k[2] можно вычислять общим порядком. Достаточно задать только начальное значение k[1]. Вот полное (!) решение данной задачи:

program by00m1t2;

var

  N, i  : longint;

  K  : array [1..1000] of longint;

begin

  assign (input,'sum. in'); reset(input);

  assign (output,'sum. out'); rewrite(output);

  readln (N);

  k[1]:=1;

  for i:=2 to N do

  if odd(i)

  then k[i]:=k[i-1]

  else  k[i]:=k[i-1] + k [i div 2];

  writeln(K[N]);

  close (input); close (output);

end.

Задача 13 "Отбор в разведку"

Из N солдат, выстроенных в шеренгу, требуется отобрать нескольких в разведку. Для того, что бы сделать это, выполняется следующая операция: если солдат в шеренге больше чем 3, то удаляются все солдаты стоящие на четных позициях, или все солдаты, стоящие на нечетных позициях. Эта процедура повторяется до тех пор, пока в шеренге останется 3 или менее солдат. Их и отсылают в разведку. Подсчитайте сколькими способами могут быть сформированы таким образом группы разведчиков ровно из трех человек.

Решение.

Обозначим K(N) - количество способов, которым можно сформировать группы разведчиков из N человек в шеренге.

По условию задачи K(1) = 0, K(2)=1, K(3)=1, то есть из трех человек можно сформировать только одну группу, из одного или двух - ни одной.

Рассмотрим теперь случай с произвольным числом N солдат в шеренге.

Если N число четное, то применяя определенную в задаче операцию удаления солдат в шеренге, мы получим в качестве оставшихся либо N div 2 солдат стоящих на четных позициях, либо N div 2 солдат, стоящих на нечетных позициях. А общее количество способов можно найти по формуле: K(N) = 2 * K(N div 2) (если N четное). Количество способов сформировать группу разведки из солдат, оставшихся на четных позициях плюс количество способов сформировать группу разведки из солдат, оставшихся на нечетных позициях. Если N число нечетное, то у нас останется либо N div 2 солдат стоявших на четных позициях, либо (N div 2)+1 солдат, стоявших на нечетных позициях. А общее количество способов можно найти по формуле: K(N) = K(N div 2) + K((N div 2)+1) (если N нечетное)

Таким образом, рекуррентное соотношение имеет вид: / 0, если N=1 или N=2,  K(N) = 1, если N=3, K(N) = 2* K(N div 2),  если N -  четное, K(N) = K(N div 2) + K((N div 2)+1), если N – нечетное.

Применив рекурсивное вычисление рекуррентной величины K(N), получаем алгоритм:

{$m 65520,0,0}

program problem13;

var  N : longint;

  function K(N:longint):longint;

  begin

  if N<3

  then  K:=0  else  if N=3

  then K:=1

  else  if odd(N)

  then  K:= K(N div 2) + K(N div 2 + 1)

  else  K:= 2 * K(N div 2);

  end;

begin

  assign(input,'input. txt'); reset(input);

  assign(output,'output. txt'); rewrite(output);

  read(N);

  writeln(K(N));

  close(input); close(output);

end.

Список литературы

1.  , Марченко в среде TURBO PASCAL 7.0. – М.: Бином Универсал, 1998.

2.  , , Кузьмич для персональных  компьютеров. – Мн.: Вышэйшая школа, 1991.

3.  , Бушмелева по Турбо Паскалю. - Киров, 1997.

4.    Лекции. Общие сведения о рекуррентных соотношениях. – Гомель, 2005.

5. Журнал «Репетитор» № 9. – Мн:, 2001.