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

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

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


Пионер
**

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

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


Задача: необходимо найти кол-во возможных вариантов постройки пирамиды, если основание 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 -


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

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

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


Ой, столько промежуточных переменных... Если уж их заводишь, старайся давать осмысленные имена, иначе читать лень smile.gif

Я не разбирался почему не работает, просто предлагаю свой вариант.

Несложно убедиться, что 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);
}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Прогрессор
****

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

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


Вот, навскидку, вижу строчку:
if ((r-l>2) && (st<=y)) step(size,y,st); //подъем наверх

А где используется результат? Может, надо
if ((r-l>2) && (st<=y)) sum+=step(size,y,st); //подъем наверх
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

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

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


Цитата

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


Вроде, нет. Мне нужно, чтобы в этом месте вызывалась функция, которая знала лишь номер ступеньки на которой она "находится", макс. кол-во ступенек и кол-во кубиков в основании. Т.е. каждая из подпрограмм должна передать результат либо 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 -


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

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

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


Сори, я решил почему-то, что k - общее количество кубиков в пирамиде.

Раз k - высота, то там везде нужно не k - n, а k - 1. И если k = 1, то f[k][n] = 1 для всех n.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

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

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


Что-то не очень пойму... ну вот например n=5, k=2;
f(n,k) = (5-2-0)(2-1)*1+(5-2-1)(k-2)*(1+1)
Получается (3)(1)+(4)(0) = (7)(1) - Так? И что из этого кол-во вариантов?


--------------------
Я бы изменил мир, да Бог не дает исходников.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

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

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


f(n, k) = f(n - 2, k - 1) * 1 + f(n - 3, k - 1) * 2 + f(n - 4, k - 1) * 3 + ...

f(5, 2) = f(5 - 2, 2 - 1) * 1 + f(5 - 3, 2 - 1) * 2 + f(5 - 4, 2 - 1) * 3

f(5, 2) = f(3, 1) * 1 + f(2, 1) * 2 + f(1, 1) * 3

Чтобы посчитать f(5, 2), нужно сначала посчитать f(3, 1), f(2, 1) и f(1, 1).


 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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