Про кенгуру Опции

[Unconnected]

Привет всем. Такая задача:

Перед кенгуру дорожка длиной K метров, по которой он может двигаться прыжками только вперед. Длина прыжка кенгуру 1, 2, 3, 4, 5 или 6 метров. Найти количество различных вариантов преодоления дорожки.

Я помню, точно помню, что уже создавал на этом форуме тему про эту задачу, и volvo там ответил, а сегодня очень долго эту тему я искал, но так и не нашёл. Уже все созданные собой темы пересматривал даже..
Для решения этой задачи я взял код volvo для получения всех перестановок в лексикографическом порядке и немного изменил функцию output. В качестве входной перестановки чисел ввёл 0-6 (метров). В output проверка, если очередная перестановка в сумме даёт длину дорожки, то увеличиваем счётчик вариантов. Только вот следующий код почему-то всегда выдаёт 0 в итоге..

{$APPTYPE CONSOLE}

var
  i, j, h, n, k, z, v: integer;
  a:array[0 .. 100] of integer;


procedure output;
var i,s: integer;
begin
  s:=0;
  for i:=1 to n do s:=s+a[i];
  if (s=v) then inc(z);
end;

begin
  z:=0;
  n:=6;
  writeln('Vvedite dlinu dorojki');readln(v);
  fillchar(a, sizeof(a), 0);
  for i:=1 to 7 do a[i]:=i-1;
  repeat
    output;
    i:=n;
    while a[i-1]>a[i] do dec(i);
    j:=i-1;
    h:=a[j];
    while a[i+1]>h do inc(i);
    a[j]:=a[i];  a[i]:=h;
    i:=j+1; k:=n;
    while i<k do begin
       h:=a[i]; a[i]:=a[k]; a[k]:=h;
       inc(i); dec(k)
    end
  until j=0;
  writeln(z);
  readln;
end.

Сообщение отредактировано: Unconnected - 13.01.2010 17:30

[Unconnected]

Исправил логику (раньше у меня в любом случае суммировались все 6 цифр), теперь так:

{$APPTYPE CONSOLE}

var
  i, j, h, n, k, z, v, i2: integer;
  a:array[0 .. 100] of integer;


procedure output;
var i,s: integer;
begin
  s:=0;
  for i:=1 to n do s:=s+a[i];
  if (s=v) then inc(z);
end;

begin
  z:=0;
  writeln('Vvedite dlinu dorojki');
  readln(v);
  if (v=1) then inc(z);
  for i2:=2 to 6 do
  begin
    n:=i2;
    fillchar(a, sizeof(a), 0);
    for i:=1 to i2 do a[i]:=i;
    repeat
      output;
      i:=n;
      while a[i-1]>a[i] do dec(i);
      j:=i-1;
      h:=a[j];
      while a[i+1]>h do inc(i);
      a[j]:=a[i];  a[i]:=h;
      i:=j+1; k:=n;
      while i<k do begin
         h:=a[i]; a[i]:=a[k]; a[k]:=h;
         inc(i); dec(k)
      end
    until j=0;
  end;
  writeln(z);
  readln;
end.

Только всё равно не работает.

[volvo]

Для решения этой задачи я взял код volvo для получения всех перестановок в лексикографическом порядке

Это не то, что нужно для решения данной задачи.

Больше подойдет вот такой вариант:
разложение числа

[Unconnected]

Спасибо, это подошло. Для этой задачи, кстати, у меня есть решение, только оно на Си (как я понял), и там вроде бы не разложением решается:

#include <stdio.h>

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n,i;
    long long r[7]={1,1};
    scanf("%d",&n);
    for (i=2;i<=n;++i)
        r[i%7]=r[(i-1)%7]*2-r[i%7];
    printf("%I64d\n",r[n%7]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

[Tony]

Быть может я конечно чего-то не понимаю, но, по-моему, эта задача лучше всего решается с помощью одномерной динамики. Пусть у нас есть массив C, где С[i] - количество возможных вариантов путей кенгуру до i-го метра дорожки. Т.к. из i-го метра дорожки у нас есть пути в i+1, i+2, i+3, i+4, i+5, i+6 метры дорожки, то получается примерно такой код (для наглядности я не использовал внутренний цикл):

for i := 1 to k do
begin
  C[i + 1] := C[i + 1] + C[i] + 1;
  C[i + 2] := C[i + 2] + C[i] + 1;
  C[i + 3] := C[i + 3] + C[i] + 1;
  C[i + 4] := C[i + 4] + C[i] + 1;
  C[i + 5] := C[i + 5] + C[i] + 1;
  C[i + 6] := C[i + 6] + C[i] + 1;
end; 

где С[1] = 1 (т.к. путь до первого метра дорожки лишь один).

Соответственно, результат будет находиться в C[k].

PS Естественно размер массива должен быть больше k (либо контролировать выход за пределы с помощью if).

Сообщение отредактировано: volvo - 4.11.2010 15:29

[Unconnected]

Ого, интересное решение, я бы не додумался... Только оно немного не попадает, при длине дорожки = 4 количество комбинаций равняется 8, а код выдаёт 7 если С[1]=0 или 11, если C[1]=1. Всё равно спасибо, +.

[Tony]

Только оно немного не попадает

Да, извиняюсь, немного ошибся... Почему-то я думал, что в начальный момент времени кенгуру стоит на первом метре дорожки... Также при вычислении нового элемента не нужно добавлять единицу (не знаю вообще, откуда я ее взял ).

Код должен быть таким:

C[0] := 1;

for i := 0 to k do
begin
  C[i + 1] := C[i + 1] + C[i];
  C[i + 2] := C[i + 2] + C[i];
  C[i + 3] := C[i + 3] + C[i];
  C[i + 4] := C[i + 4] + C[i];
  C[i + 5] := C[i + 5] + C[i];
  C[i + 6] := C[i + 6] + C[i];
end;