объясните, пожалуйста

[brainstorm]

пожалуйста, объясните чайнику как решать задачи такого типа:

Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца.

взято с Алголист.ру, даже если там и есть объяснение, я все равно не могу написать код

[Shadow_Wind]

var
N, K,P: integer;
begin
writeln('Введите длину пути');
readln(N);
writeln('Введите длину хода фишки');
readln(K);
P:=N/K;
writeln('Число путей равно ',P);
readln();

Это код Паскаля.

[mihali4]

Думается, не все так просто. Дело в том, что N может не делиться без остатка на К... Это - раз.
Второе - ходы могут и должны быть различной длины.
Задача, насколько я понимаю, состоит именно в том, чтобы найти все сочетания ходов с учетом наложенных ограничений по длине хода и общей длине пути.

[Shadow_Wind]

Какие могут быть сочетания ходов, если движение только вперёд? Т.е. задача выполняется один раз с известными переменными. Число найдено, другое дело, если были бы заданы другие условия задачи.

[mihali4]

Какие могут быть сочетания ходов, если движение только вперёд

Пусть общая длина пути - 11, ход не более 3.
Вариант 1: 3,3,3,2
Вариант 2: 1,1,1,1,1,1,1,1,1,1,1
Вариант 3: 2,3,2,3,1
и так далее...
Дальше объяснять? Или дошло?

[Shadow_Wind]

Всем извинения приношу! Упустил в задаче НЕ БОЛЕЕ ))

[Shadow_Wind]

Теперь труднее... Может массив создать и в нём подсчёт вести?

[mihali4]

Делаете процедурку вычисления очередной комбинации ходов и поехали...
Берете первую комбинацию и проверяете сумму ходов на равенство суммарному пути. Равно - в правильные результаты, не равно - вычисляете следующую комбинацию.
Примерно так:
1 1 1 1 1 1 1 1 1 1 1 подходит
1 1 1 1 1 1 1 1 1 1 2 не подходит
1 1 1 1 1 1 1 1 1 2 подходит
1 1 1 1 1 1 1 1 2 1 подходит
1 1 1 1 1 1 1 2 1 1 подходит
....
Правда, из условия не совсем ясно, нужно ли учитывать все перестановки. Вполне возможно, что итоговый результат может выглядеть и таким образом:
1. Одиннадцать единиц
2. Девять единиц и одна двойка
3. Восемь единиц и одна тройка
...
N. Три тройки и одна двойка.

[Vladko]

Стандартный подход конечно это банальный перебор и без рекурсий не обойтись, хотя некоторые умельцы могут и циклами обойтись. Главная идея перебрать все варианты, че и предлагает Михалыч.
Ну а другой вариант это нехилое знание построения рекурсивных алгоритмов.
Вот сижу я дома думаю че это моя рекурсия по перебору путей не работает(выпендриться млин захотел), а тут папа с работы приходит и "бэмс" решение за 15-20 минут вывел(сам выводил, потому что не его специализация и подобным не занимаеться), а я спрограмировал его идею где-то за столько же...
Сканера у мя нету, так что просто код, а сам объяснить почему оно именно так слабо... В целом принцип тот же что и у Фибоначчи.

int calcPath(N, K)
{
	int returnval=0;
	int i, j;
	int* cyclicbuff;

	if(K==1)
		return 1;	

	cyclicbuff = (int*) malloc (sizeof(int)*K);

	for(j=0; j<K; j++)
		cyclicbuff[j] = 1 << j; // placing 2^j into corresponding locations

	/* Calculating */
	for(j=K; j<N; j++)
		for(i=1;i<K;i++)
			cyclicbuff[ (j%K) ] += cyclicbuff[ ((j+i)%K) ];

	returnval = cyclicbuff[ ((N-1)%K) ];
	free(cyclicbuff);
	
	return returnval;
}

[brainstorm]

спасибо огромное!
принцип использования рекурсии понятен, попробую разобраться в коде и решить несколько задач такого типа.
может тогда дойдет.