IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Про кенгуру
сообщение
Сообщение #1


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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

Перед кенгуру дорожка длиной 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 -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Исправил логику (раньше у меня в любом случае суммировались все 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.




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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






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

Больше подойдет вот такой вариант:
разложение числа
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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

#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;
}




--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


Быть может я конечно чего-то не понимаю, но, по-моему, эта задача лучше всего решается с помощью одномерной динамики. Пусть у нас есть массив 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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


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


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 17
Пол: Мужской

Репутация: -  1  +


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

Код должен быть таким:
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;
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 20:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name