IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Рекурсия, разложить число
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

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


Сообщение отредактировано: Nike0 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

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

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

Сообщение отредактировано: Nike0 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

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

ничего... что-то я сморозил... кстати, когда поставил Split куда надо, его надо с какими параметрами записывать? Split(j,n)?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


Цитата(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 в виде суммы не менее двух ПОПАРНО РАЗЛИЧНЫХ натуральных слагаемых. Представления, ОТЛИЧАЮЩИЕСЯ ЛИШЬ ПОРЯДКОМ слагаемых, различными не считаются. Вот тут поподробнее, какое условие надо написать, чтобы учитывался порядок слагаемых?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






А ты перед тем как печатать массив, пройди по нему, и убедись, что он содержит элементы в порядке неубывания, и только если это выполняется, тогда печатай. Таким образом отсечешь все повторения.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


Split(j,n-i);


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

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

то что я неделю делал время не позволяло, сложный график на учебе, да и сильно не было времени за компом сидеть, а то что Вы все сделали правильно, я не сомневаюсь, значит мои ошибки. А насчет клрскр это уже привычка, препод ругаться будет без него))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


думать то подумал, вроде все хорошо работает, теперь осталось сделать, чтобы перестановки убрало и все)
Split(j+k,n-i);
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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


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



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

Split(j+1,n-i)? у меня ничего не изменилось, или я настолько тупой... и насчет этого увеличения я наверно читал не один раз...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Илья

Репутация: -  0  +


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

Сообщение отредактировано: Nike0 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 19:43
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name