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

 
 Ответить  Открыть новую тему 
> Разбиение числа на слагаемые, Надо разбить число N на суму из K слагаемых.
DarkWishmaster
сообщение 17.04.2011 22:14
Сообщение #1


Бывалый
***

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

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


Надо методом перебора. Я сделал, только они повторяются:
1 3 5 - 5 3 1
Может у вас есть алгоритм для этой задачи?
Я думал сохранить результаты в массиве, т.е если числа вектора не повторяются с теми что из массива то добавляем в массив, но это не эфективно, думаю есть более простой метод.
Спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 18.04.2011 5:42
Сообщение #2


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

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

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


Цитата(DarkWishmaster @ 17.04.2011 23:14) *
Надо методом перебора. Я сделал, только они повторяются:
1 3 5 - 5 3 1
Может у вас есть алгоритм для этой задачи?
Я думал сохранить результаты в массиве, т.е если числа вектора не повторяются с теми что из массива то добавляем в массив, но это не эфективно, думаю есть более простой метод.

Есть.
Подобные задачи решались на форуме много раз. Например, тут: Рекурсия (но не точно такая). А вообще - поиск..


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


Гость






Цитата
Может у вас есть алгоритм для этой задачи?
Алгоритм ты озвучил сам: перебор.

Есть реализация: числа, дающие в сумме заданное число
Повторений не наблюдается...
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 18.04.2011 16:38
Сообщение #4


Бывалый
***

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

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


Забыл сказать что все числа должны быть разными (т.е варианты типа 3 3 9 не печатать)
Вот моя идея:
например для n=9, k=3
создаем вектор: 1 2 3
Теперь увеличиваем 3 пока сума вектора не будет N
1 2 4
1 2 5
1 2 6 -> решение
теперь идем к переведущему числу, уже к 2 и увеличиваем его на 1 единицу:
и опять последний увеличиваем:
1 3 4
1 3 5 -> решение
увиличиваем 3
так как 1 4 5 больше N
то идем к первому элементу и увеличиваем его
2 3 4 ->решение
теперь уже ничего увеличивать нельзя, так как сума будет больше N
Вот что я пробовал сделать :
Program (Показать/Скрыть)

без рекурсии я знаю как сделать, а тут...

Сообщение отредактировано: DarkWishmaster - 18.04.2011 16:39
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 18.04.2011 16:48
Сообщение #5


Гость






Цитата
без рекурсии я знаю как сделать
Покажи то, что ты придумал без рекурсии...
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 18.04.2011 17:20
Сообщение #6


Бывалый
***

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

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


Цитата(volvo @ 18.04.2011 16:48) *

Покажи то, что ты придумал без рекурсии...


щяс попробую
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 18.04.2011 17:25
Сообщение #7


Гость






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

var
q : integer;
n : integer;

arr : array[1 .. 10] of integer;

procedure p(start, count : integer);
var i, s : integer;
begin
if count > q then
begin
s := 0;
for i := 1 to q do s := s + arr[i];
if s = n then
begin
for i := 1 to q do write(arr[i]:3);
writeln;
end;
end
else
begin
for i := start + 1 to n do // Вот основная идея: чтоб решения и слагаемые не повторялись
begin
arr[count] := i;
p(arr[count], count + 1); // рекурсия присутствует
end;
end;
end;

begin
n := 9;
q := 3;
p(0, 1);
end.
 К началу страницы 
+ Ответить 
DarkWishmaster
сообщение 18.04.2011 17:46
Сообщение #8


Бывалый
***

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

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


Спасибо, volvo, только что закончил, вот без рекурсии
только пока работает только с макс. с K=3
KOD (Показать/Скрыть)

твоя работает, иду разбираться, спасибо!

Сообщение отредактировано: DarkWishmaster - 18.04.2011 17:53
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 19.04.2011 4:11
Сообщение #9


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

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

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


Цитата(volvo @ 18.04.2011 16:26) *
Алгоритм ты озвучил сам: перебор.

Есть реализация: числа, дающие в сумме заданное число
Повторений не наблюдается...
volvo, а почему ты счел возможным совершенно проигнорировать мой пост (Разбиение числа на слагаемые) и даже не извиниться?.. blink.gif Мне кажется, это не принято.

По данной мной ссылке содержится решение, которое требует минимальных изменений (сделать вывод только в случае нужного числа слагаемых).

-1 norespect.gif

Добавлено через 7 мин.
Цитата(volvo @ 18.04.2011 16:26) *
Алгоритм ты озвучил сам: перебор.
Перебор - это класс алгоритмов, а не алгоритм.

Вот мое модифицированное решение:
const
m=1000;
var
a: array[1..m]of integer;
k,n,q: integer;

procedure Split(j,n: integer);
var
i: integer;
begin
if (n=0)and(k=q) 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(i+1,n-i);
Dec(k)
end
end;

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


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


Гость






Цитата
а почему ты счел возможным совершенно проигнорировать мой пост
Я не игнорировал пост. Зашел, посмотрел. Кстати, на мысль воспользоваться поиском меня навел именно твой пост. Но извиняться перед всей Вселенной за то, что может быть кто-то где-то когда-то уже писал подобную программу, или программу, которую можно минимальными усилиями преобразовать к нужному функционалу - не собираюсь.

Цитата
-1 norespect.gif
Запомни этот пост. И потом, если вдруг у тебя начнут появляться минусы, я буду давать тебе на него ссылку. Если, конечно, ты не воспользуешься раньше возможностью чистки своего рейтинга, что уже было. Хочешь - напомню, где? norespect.gif Я, как видишь, этим не пользуюсь.

И, на будущее: я не влазил ни в одно твое обсуждение (по крайней мере, не приводил там СВОЙ код, максимум - давал наводящие замечания). Ты - залез везде, где только можно. Везде, где бы я не ответил - ты потом ТОЖЕ ПОБЫВАЛ, и оставил свою версию программы. Ну что ж...
 К началу страницы 
+ Ответить 
Lapp
сообщение 19.04.2011 11:50
Сообщение #11


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

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

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


Цитата(volvo @ 19.04.2011 11:46) *
Я не игнорировал пост. Зашел, посмотрел. Кстати, на мысль воспользоваться поиском меня навел именно твой пост. Но извиняться перед всей Вселенной за то, что может быть кто-то где-то когда-то уже писал подобную программу, или программу, которую можно минимальными усилиями преобразовать к нужному функционалу - не собираюсь.

Запомни этот пост. И потом, если вдруг у тебя начнут появляться минусы, я буду давать тебе на него ссылку. Если, конечно, ты не воспользуешься раньше возможностью чистки своего рейтинга, что уже было. Хочешь - напомню, где? norespect.gif Я, как видишь, этим не пользуюсь.

И, на будущее: я не влазил ни в одно твое обсуждение (по крайней мере, не приводил там СВОЙ код, максимум - давал наводящие замечания). Ты - залез везде, где только можно. Везде, где бы я не ответил - ты потом ТОЖЕ ПОБЫВАЛ, и оставил свою версию программы. Ну что ж...

Очень впечатляет.
а. достаточно было сказать в начале того поста "я тоже добавлю"
хам ты, Володя
хамом был, хамом остался
и с хамами мне не по дороге

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


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


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

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

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


Тема разделена, остаток перенесен сюда: О недавних событиях на Форуме


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

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

 



- Текстовая версия 28.03.2024 17:08
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"