Задачка на рекурсию!, Что я не правильно делаю? Опции

[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...



Сообщение отредактировано: Akella - 15.11.2008 6:39

[Lapp]

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

Не видя конкретно того, что у тебя было, и не слыша того, что она сказала, я не стану говорить, что она ошиблась. Может, она имела в видо, что на в сумме на месте k стоит i, а может, еще что. Верить тебе - верю, но вопрос, поняли ли вы друг друга..