Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Рекурсия

Автор: Nike0 6.12.2009 19:42

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

Автор: Lapp 6.12.2009 23:29

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

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


Успехов! smile.gif

Автор: Nike0 8.12.2009 0:57

Цитата(Lapp @ 6.12.2009 18:29) *
Вот код, но я в нем специально убрал один оператор, так что он не совсем рабочий. Сможешь разобраться, как починить? Если нет - задавай вопросы.

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

Автор: Lapp 8.12.2009 3:14

Цитата(Nike0 @ 7.12.2009 20:57) *
я так понял что рекурсия это такая штука, которая саму себя вызвывает в процедуре, я что-то пытался понять и думал куда вставить, но что-то не покатило smile.gif
Да, правильно, опущен вызов процедуры из самой себя.

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

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

smile.gif

Автор: Nike0 8.12.2009 14:38

Цитата(Lapp @ 7.12.2009 22:14) *

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

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

Автор: volvo 8.12.2009 14:52

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

Автор: Nike0 9.12.2009 2:42

Цитата(volvo @ 8.12.2009 9:52) *

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

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

Автор: Lapp 9.12.2009 7:12

Цитата(Nike0 @ 8.12.2009 22:42) *
кстати, когда поставил Split куда надо, его надо с какими параметрами записывать? Split(j,n)?
Хороший вопрос! Я его переадресую тебе.. smile.gif
Внимательно прочитай мои пояснения (см. выше) и сделай выводы.

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

Автор: Nike0 20.12.2009 16:58

Цитата(Lapp @ 9.12.2009 2:12) *

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

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

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 20.12.2009 17:07

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

Автор: Lapp 20.12.2009 18:32

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

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


   Split(j,n-i);


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

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

Автор: Nike0 21.12.2009 16:32

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

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

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

Автор: Nike0 21.12.2009 16:57

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

Split(j+k,n-i);

Автор: Lapp 21.12.2009 17:05

Цитата(Nike0 @ 21.12.2009 12:57) *
думать то подумал, вроде все хорошо работает, теперь осталось сделать, чтобы перестановки убрало и все) 
Split(j+k,n-i);
Нет, Nike0. Не так. И не нужно ничего убирать, все УЖЕ УБРАНО.

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

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


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


Автор: Nike0 21.12.2009 17:12

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

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

Автор: Lapp 21.12.2009 17:19

Цитата(Nike0 @ 21.12.2009 13:12) *
Split(j+1,n-i)? у меня ничего не изменилось, или я настолько тупой... и насчет этого увеличения я наверно читал не один раз...
Уфф )). Ну наконец ты хоть стал разговаривать! Я уж думал, этого не произойдет.. smile.gif

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

Автор: Nike0 21.12.2009 17:37

Цитата
Смотри, первый параметр, переданный в эту процедуру - это j, да. Но дальше мы перебираем в цикле по i, начиная с этого числа. Значит, что нужно увеличивать на 1? ...
о Госпади, я это сделал( точнее Вы сделали) smile.gif smile.gif Split(i+1,n-i); cool.gif

Автор: Lapp 21.12.2009 17:42

Цитата(Nike0 @ 21.12.2009 13:37) *
о Госпади, я это сделал( точнее Вы сделали) smile.gif smile.gif Split(i+1,n-i); cool.gif
Ты это сделал ))

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

Автор: Nike0 21.12.2009 17:56

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