Перестановки, Олимпиадная задача Опции

[roma]

Расмотрим строфу стихотоворного текста, состоящую из N строчек.
Любая строка рифмуется хотя бы с одной другой.
Нужна зная число n вывести все возможные схемы рифмовки.

Пример: n=4 - 4 схемы. Это схемы AABB, ABAB, ABBA и AAAA.

Может кто-нибудь подкинет идею.

P. S. ДОЖ и Altair , К своему стыду не могу сформулировать кратко идею данной задачи

[volvo]

roma,
объясни мне, почему у тебя в вариантах есть AAAA, но нет BBBB?

[Дож]

объясни мне, почему у тебя в вариантах есть AAAA, но нет BBBB?

Это схемы. Одинаковые буквы- рифмующиеся строки. Неодинаковые- нерифмующиеся. Поэтому AAAA и BBBB одно и тоже.

[volvo]

Дож,
тебя зовут roma ?

[Дож]

тебя зовут roma ?

Нет, но я уже видел подобную задачу.

[roma]

roma,
объясни мне, почему у тебя в вариантах есть AAAA, но нет BBBB?

Дож правильно ответил на данный вопрос.
Аналогично одинаковы AAABB и BBBAA...

[Дож]

• Пусть первая строка рифмуется с n-1 другой. Тогда кол-во схем=1
• Пусть первая строка рифмуется с n-3 другой. Тогда перебираем все варианты.
• Аналогично для n-4, n-5 и т.д...

[Дож]

Function stih(n:integer):integer;
Var i,r:integer;
i:=n; r:=0;
While i>2 do begin
r:=r+Choose(n-1,i-1)*stih(n-i);
end;
stih:=r
end;

(Где Choose(n,k)- кол-во способов выбрать k из n, как такую функцию написать см. FAQ)
_____________________________________________________________________
Ой, в проге ошибка!

После строки r:=r+Choose(n-1,i-1)*stih(n-i); нужно поставить dec(i);

Сообщение отредактировано: Дож - 5.12.2005 16:16

[Guest]

Function stih(n:integer):integer;
...

Что-то здесь не так, в данном виде функция всегда выдает ноль (r=0);
Я предположил что перед stih:=r должно стоять if r=0 then r:=1; но все равно не получается: для n=6 ответ 41, а у меня выдает 37

[Дож]

Я предположил что перед stih:=r должно стоять if r=0 then r:=1;

Самый простой пример: n=1, следовательно
Кол-во схем=0.