Привет всем. Такая задача:
{$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.
Исправил логику (раньше у меня в любом случае суммировались все 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.
Спасибо, это подошло. Для этой задачи, кстати, у меня есть решение, только оно на Си (как я понял), и там вроде бы не разложением решается:
#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;
}
Быть может я конечно чего-то не понимаю, но, по-моему, эта задача лучше всего решается с помощью одномерной динамики. Пусть у нас есть массив 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;
Ого, интересное решение, я бы не додумался... Только оно немного не попадает, при длине дорожки = 4 количество комбинаций равняется 8, а код выдаёт 7 если С[1]=0 или 11, если C[1]=1. Всё равно спасибо, +.
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;