Рекурсия, разложить число Опции

[Nike0]

Помогите пжлста с решением 1 задачки. Вычислите количество различных представлений заданного натурального числа n в виде суммы не менее двух попарно различных натуральных слагаемых. Представления, отличающиеся лишь порядком слагаемых, различными не считаются. Если можете чем-нибудь помочь, пишите, может мне надо толчок какой-то чтобы сам додумал.

[Lapp]

пишите, может мне надо толчок какой-то чтобы сам додумал.

Насчет толчка..
Скажем, так: в рекурсивную процедуру передаешь два параметра: наибольшее из использованных слагаемых и остаток числа. А в процедуре, если остаток нулевой - печатаешь число, если нет - расщепляешь на два в цикле от первого параметра до второго. Первое из полученных чисел записываешь в массив, а второе передаешь рекурсивно вместе с увеличенным на 1 первым параметром. Типа так..

Вот код, но я в нем специально убрал один оператор, так что он не совсем рабочий. Сможешь разобраться, как починить? Если нет - задавай вопросы.. Если да - напиши, чего не хватает (для потомков ).

const
  m=1000;
var
  a: array[1..m]of integer;
  k,n: integer;

procedure Split(j,n: integer);
var
  i: integer;
begin
  if (n=0)and(k>1) then begin
    for i:=1 to k do Write(a[i]:4);
    WriteLn
  end
  else for i:=j to n do begin
    Inc(k);
    a[k]:=i;
    Dec(k)
  end
end;

begin
  Write('n = ');
  ReadLn(n);
  k:=0;
  Split(1,n);
  ReadLn
end.

Успехов!

[Nike0]

Вот код, но я в нем специально убрал один оператор, так что он не совсем рабочий. Сможешь разобраться, как починить? Если нет - задавай вопросы.

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


Сообщение отредактировано: Nike0 - 8.12.2009 1:06

[Lapp]

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

Да, правильно, опущен вызов процедуры из самой себя.

Ну, смотри. В процедуре Split два блока. Верхний - это просто печать результата (см. мои пояснения выше). Значит, где-то в нижнем.

Дальше.. В рекурсии обычно существенно, что параметры изменяются перед вызовом процедуры, а потом возвращаются в прежнее состояние. В данном случае мы увеличиваем количество слагаемых (k).. Стало яснее немного?

[Nike0]

В рекурсии обычно существенно, что параметры изменяются перед вызовом процедуры, а потом возвращаются в прежнее состояние. В данном случае мы увеличиваем количество слагаемых (k)

ну раз параметры изменяются перед вызовом процедуры, то Split нужно поставить после уменьшения k, но почему-то когда я поставил, выскакивает 202 ошибка(переполнение стеков)

Сообщение отредактировано: Nike0 - 8.12.2009 14:48

[volvo]

ну раз параметры изменяются перед вызовом процедуры, то Split нужно поставить после уменьшения k

Если Split поставить после уменьшения K, то параметры не очень-то и изменяются, тебе не кажется? Сначала увеличили, потом уменьшили, что поменялось?

[Nike0]

Сначала увеличили, потом уменьшили, что поменялось?

ничего... что-то я сморозил... кстати, когда поставил Split куда надо, его надо с какими параметрами записывать? Split(j,n)?

[Lapp]

кстати, когда поставил Split куда надо, его надо с какими параметрами записывать? Split(j,n)?

Хороший вопрос! Я его переадресую тебе..
Внимательно прочитай мои пояснения (см. выше) и сделай выводы.

P.S.
Кто-то что-то говорил о "толчке", а теперь не хочет минутку подумать..

[Nike0]

Внимательно прочитай мои пояснения и сделай выводы.

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

Program L11_26_1;
uses
 crt;
const
  m=1000;
var
  a: array[1..m] of integer;
  k,n: integer;

procedure Split(j,n: integer);
var
  i: integer;
begin
 if (n=0) and (k>1) then
 begin
  for i:=1 to k do
   Write(a[i]:4);
  Writeln;
 end
 else
 for i:=j to n do
  begin
   Inc(k);
   a[k]:=i;
   Split(j,n-i);
   Dec(k);
  end;
end;

begin
 clrscr;
 Write('n = ');
 ReadLn(n);
 k:=0;
 Split(1,n);
 Readln;
end.

P.S. но все-таки это решение не удовлетворяет моему условию:
нужно найти количество(тут просто, счетчик вставлю) различных представлений заданного натурального числа n в виде суммы не менее двух ПОПАРНО РАЗЛИЧНЫХ натуральных слагаемых. Представления, ОТЛИЧАЮЩИЕСЯ ЛИШЬ ПОРЯДКОМ слагаемых, различными не считаются. Вот тут поподробнее, какое условие надо написать, чтобы учитывался порядок слагаемых?

[volvo]

А ты перед тем как печатать массив, пройди по нему, и убедись, что он содержит элементы в порядке неубывания, и только если это выполняется, тогда печатай. Таким образом отсечешь все повторения.

[Lapp]

P.S. но все-таки это решение не удовлетворяет моему условию:
нужно найти количество(тут просто, счетчик вставлю) различных представлений заданного натурального числа n в виде суммы не менее двух ПОПАРНО РАЗЛИЧНЫХ натуральных слагаемых. Представления, ОТЛИЧАЮЩИЕСЯ ЛИШЬ ПОРЯДКОМ слагаемых, различными не считаются. Вот тут поподробнее, какое условие надо написать, чтобы учитывался порядок слагаемых?

Nike0, ты всерьез думаешь, что я не прочитал про (цитирую тебя) "ПОПАРНО РАЗЛИЧНЫХ" ? Ты правда думаешь, что я дал тебе неверное решение?? Ну-ну.. Вот ты правда решил, что ты-то, конечно уж, правильно подставил параметры, а я-то, вот, конечно, ошибся??

Ты подставлял их.. сейчас посмотрю на даты.. неделю! И за эту неделю ты не смог перевести точно с РУССКОГО на ПАСКАЛЬ! И вот теперь ты мне говоришь, что я неправильно решил?? ПЕРЕЧИТАЙ же НАКОНЕЦ мои ПОЯСНЕНИЯ. Там все написано. Переведи СЛОВО В СЛОВО. Неужели так трудно??

   Split(j,n-i);

- неправильно.

P.S.
к тому же еще всякой дряни навставлял.. к чему тут CRT? Зачем чистить экран? у тебя на нем порно что ли?..

[Nike0]

ты всерьез думаешь, что я не прочитал про (цитирую тебя) "ПОПАРНО РАЗЛИЧНЫХ" ? Ты правда думаешь, что я дал тебе неверное решение?? Ну-ну.. Вот ты правда решил, что ты-то, конечно уж, правильно подставил параметры, а я-то, вот, конечно, ошибся??

Ты подставлял их.. сейчас посмотрю на даты.. неделю! И за эту неделю ты не смог перевести точно с РУССКОГО на ПАСКАЛЬ!

то что я неделю делал время не позволяло, сложный график на учебе, да и сильно не было времени за компом сидеть, а то что Вы все сделали правильно, я не сомневаюсь, значит мои ошибки. А насчет клрскр это уже привычка, препод ругаться будет без него))

[Nike0]

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

Split(j+k,n-i);

[Lapp]

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

Split(j+k,n-i);

Нет, Nike0. Не так. И не нужно ничего убирать, все УЖЕ УБРАНО.

Слушай, давай я скопирую сюда из того моего мессадж - вдруг у тебя скролл на компе не работает? А методом тыка ты долго провозишься..

второе передаешь рекурсивно вместе с увеличенным на 1 первым параметром.

Может, поможет?

[Nike0]

с увеличенным на 1 первым параметром

Split(j+1,n-i)? у меня ничего не изменилось, или я настолько тупой... и насчет этого увеличения я наверно читал не один раз...

[Lapp]

Split(j+1,n-i)? у меня ничего не изменилось, или я настолько тупой... и насчет этого увеличения я наверно читал не один раз...

Уфф )). Ну наконец ты хоть стал разговаривать! Я уж думал, этого не произойдет..

Смотри, первый параметр, переданный в эту процедуру - это j, да. Но дальше мы перебираем в цикле по i, начиная с этого числа. Значит, что нужно увеличивать на 1? ...

[Nike0]

Смотри, первый параметр, переданный в эту процедуру - это j, да. Но дальше мы перебираем в цикле по i, начиная с этого числа. Значит, что нужно увеличивать на 1? ...

о Госпади, я это сделал( точнее Вы сделали) Split(i+1,n-i);

[Lapp]

о Госпади, я это сделал( точнее Вы сделали) Split(i+1,n-i);

Ты это сделал ))

Если есть вопросы - задавай.

[Nike0]

думаю эту тему можно закрывать, все по полочкам мне разложили, спс большое)

Сообщение отредактировано: Nike0 - 21.12.2009 17:56