Помощь - Поиск - Пользователи - Календарь
Полная версия: Задачка на рекурсию!
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Akella
Условие: Множество S, состоящее из n элементов, разбивается на k непустых подмножеств. Число таких подмножеств по рекурсивной формуле
Изображение
Нажмите для просмотра прикрепленного файла
Составить рекурсивный алгоритм и написать программу, вычисляющую Pk(n).
Вот я тут написал чуток, но что-то она не работает=(( не понимаю... Помогите плиз!
program _6_8;    
var
S,k,n : integer;
function P(k,n:integer):integer;
var i:integer;
begin s:=0;
for i:=1 to k do begin
if (i=n) and (i=1) then P:=1 else
if i>n then P:=0 else
end;
S:=S+P(i,n-i)
end;
begin
writeln('vvedite k,n');
read(k,n);
P(k,n);
write(S);
end.


Добавлено через 2 мин.
кстати для проверки можно взять k=2 и n=5, должно получиться 2! а мну ничего не получается, кстати когда в универе делал 0 получался, щас ваще ошибку 202 выдает... по памяти писал... может что-то упустил...
Lapp
Ты много чего делаешь неправильно.

Во-первых, ты почему-то перепутал i и k.
Во-вторых, базовые значения у тебя были заданы не там - они должны определяться непосредственно при входе в функцию. Ты просто должен описывать ТО, что ты сам стал бы делать при вычислении по этой формуле.

Вот смотри: тебе заданы k и n. Что ты делаешь в первую очередь? В первую очередь ты должен посмотреть, не попадают ли данные k и n в базовые случаи (k=n, n=1, k>n). Если попадают - просто возвращаешь нужное значение. Если нет - тогда считаешь по данной формуле. Но, будь добр, не подменяй одни числа другими.. Сказано i - значит, ставь i. Почему ты его стал заменять на k?

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

И наконец, переменную s необходимо (!) описать внутри функции, а не глобально. Иначе ее значения затираются в процессе вызова функции в цикле. Это одно из основных требований при рекурсивных вычислениях.

Короче, вот так:
program _6_8;
var
k,n : integer;

function P(k,n:integer):integer;
var
i,s:integer;
begin
if (k=n)or(k=1) then P:=1
else if k>n then P:=0
else begin
s:=0;
for i:=1 to k do s:=s+P(i,n-k);
P:=s
end
end;

begin
writeln('vvedite k,n');
read(k,n);
WriteLn(P(k,n))
end.

А ошибка 202 - это переполнение стека. Поскольку базовые значения у тебя стояли в неправильных местах (или из-за других ошибок), код зацикливался, поскольку никогда не выходил на базовые значения. Вообще, при написании рекурсивных процедур это очень частая ошибка.

Другие замечания:
- учись правильно форматировать, это сильно помогает (используй этот код, как пример);
- учи английский, без него в программировании тяжело (это ответ на другую твою тему).
Akella
За спасибо за помощь, в принципе когда я делал в аудитории у меня было что-то похожее, потом пришел домой и все перемешалось=))

"Во-первых, ты почему-то перепутал i и k."

не поверишь, мне так препод сказала, сначало у меня было k

"Соответственно, выводить на печать нужно не s, а P."

Это я ошибся, я потом переписал на P...

Lapp
Цитата(Akella @ 15.11.2008 6:28) *
не поверишь, мне так препод сказала, сначало у меня было k
Не видя конкретно того, что у тебя было, и не слыша того, что она сказала, я не стану говорить, что она ошиблась. Может, она имела в видо, что на в сумме на месте k стоит i, а может, еще что. Верить тебе - верю, но вопрос, поняли ли вы друг друга..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.