Пирамида, С++ Опции

[first_day]

Задача: необходимо найти кол-во возможных вариантов постройки пирамиды, если основание n кубиков, а высота k кубиков. Каждый следующий ряд можно уложить только так, чтобы слеа и справа был хотя бы 1 свободный кубик.

Идея у меня такая: поднимаясь на следующую ступеньку, ставим n-2 кубиков (это становится новое основание), дальше пытаемся сдвинуть эту группу кубиков вправо, попутно проверяя возможность подняться наверх. Уменьшаем эту группу на 1, повторяем. Если какой-то из функций достигается нужный уровень, т.е. k, то кол-во вариантов увеличиваем.
Рекурсию никогда раньше не использовал, попробова, вот, что получилось:

#include <iostream>
using namespace std;
int step(int, int, int);
int main ()
{
	int n,k,otv=0;
	cin>>n>>k;
	otv+=step(n,k,1);
	cout<<otv;
	return 0;
}

int step(int x, int y, int z)
{
	int l,r,size,st,l2,r2,sum=0;
	st=z;
	size=x;
	if (size-2>=1) //возможна ли следующая ступенька
	{	
		r=size-1;
		l=size-r;
		size=size-2;
		st++;
		while (l!=r) //уменьшение кубиков на ступеньке
		{
			l2=l;
			r2=r;
			while (r2<size) //сдвиг кубиков на ступеньке
			{
				if ((r-l>2) && (st<=y)) step(size,y,st); //подъем наверх
				l2++;
				r2++;
			}
			r--;
		}
		if (st==y) sum++;	
	}
	return sum;
}

Выдает либо 0, либо 1...

Сообщение отредактировано: first_day - 19.12.2007 14:27

[first_day]

где используется результат?

Вроде, нет. Мне нужно, чтобы в этом месте вызывалась функция, которая знала лишь номер ступеньки на которой она "находится", макс. кол-во ступенек и кол-во кубиков в основании. Т.е. каждая из подпрограмм должна передать результат либо 1 (если она достигла последней требуемой ступеньки), либо 0.

Несложно убедиться, что f(n, k) = f(n - 2, k - n) * 1 + f(n - 3, k - n) * 2 + f(n - 4, k - n) * 3 + ...

Поэтому можно без всякой рекурсии просто заполнить табличку значений для f:

for (int n = ...)
  for (int k = ...)
  {
    f[n][k] = 0;
    if (k - n > 0)
      for (int i = 0; i < ...) 
        f[n][k] += f[n - 2 - i][k - n] * (1 + i);
  }

А почему k-n? если изначально будет n=5, k=2, тогда как?

И т.е. первые 2 цикла завершатся, когда завершится 3-ий(с параметром i)? А третий завершится тогд, когда (k - n) станет равно 0?

Сообщение отредактировано: first_day - 19.12.2007 18:14