Помощь - Поиск - Пользователи - Календарь
Полная версия: Рекурсия
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Nike0
Помогите пжлста с решением 1 задачки. Вычислите количество различных представлений заданного натурального числа n в виде суммы не менее двух попарно различных натуральных слагаемых. Представления, отличающиеся лишь порядком слагаемых, различными не считаются. Если можете чем-нибудь помочь, пишите, может мне надо толчок какой-то чтобы сам додумал.
Lapp
Цитата(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
Цитата(Lapp @ 6.12.2009 18:29) *
Вот код, но я в нем специально убрал один оператор, так что он не совсем рабочий. Сможешь разобраться, как починить? Если нет - задавай вопросы.

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

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

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

smile.gif
Nike0
Цитата(Lapp @ 7.12.2009 22:14) *

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

ну раз параметры изменяются перед вызовом процедуры, то Split нужно поставить после уменьшения k, но почему-то когда я поставил, выскакивает 202 ошибка(переполнение стеков)
volvo
Цитата
ну раз параметры изменяются перед вызовом процедуры, то Split нужно поставить после уменьшения k
Если Split поставить после уменьшения K, то параметры не очень-то и изменяются, тебе не кажется? Сначала увеличили, потом уменьшили, что поменялось?
Nike0
Цитата(volvo @ 8.12.2009 9:52) *

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

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

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

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


Split(j,n-i);


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

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

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

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

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

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


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

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

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

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

Если есть вопросы - задавай.
Nike0
думаю эту тему можно закрывать, все по полочкам мне разложили, спс большое)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.