нахождение нужной суммы в списке чисел

← →
jinn (2003-02-23 15:20) [0]

Привет!
Такой вот вопрос: как, например, из 10 данных чисел выбрать те, сумма которых даёт нужное число??
Ясно, что делаетя тупым перебором, но вот реализовать его никак не получается... Видимо, не такой он тупой :)
Есть мысли по этому поводу??

← →
Юрий Зотов (2003-02-23 15:25) [1]

Если количество чисел заранее известно, то такой перебор реализуется вложенными циклами. Если же нет, то рекурсией.

← →
jinn (2003-02-23 15:28) [2]

Количество чисел заранее неизвестно...
А можно примерчик, хоть с чего начать чтобы было?

← →
mrcat (2003-02-23 15:35) [3]

Не проверял на вычислительную сложность, но есть идея графовой модели - каждая вершина представлена определенным числом.
Помимо этого есть еще одна вершина, величина которой равна 0.

1. Волновым алгоритмом "распространяешся" из этой 0-й вершины;
2. Как достигнеши необходимой суммы - все! Рез-т достигнут.

← →
jinn (2003-02-23 15:43) [4]

ммм, вообще-то я предполагал, что решение задачи будет проще, чем реализация самого метода нахождения этого решения :) Короче говоря, теория графов - это хорошо, но это нехило усложнит весь алгоритм.
Я-то думал, что это тривиальная задача, которую человечество решило со времен 1-го дельфи :))
Ну ладно, а ещё есть предложения?

← →
mrcat (2003-02-23 15:54) [5]

>>Короче говоря, теория графов - это хорошо, но это нехило усложнит весь алгоритм.

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

Я-то думал, что это тривиальная задача, которую человечество решило со времен 1-го дельфи :))

Не совсем так. Задача оптимизации существовала всегда.

← →
jinn (2003-02-23 16:05) [6]

да, количество чисел неизвестно. Но одно можно сказать точно - оно в разумных пределах... где-то от 5 до 15...
По крайней мере это не десятки, сотни и тысячи :)
В конце концов кто здесь криптограф ? :)))
Ведь должен же тебе быть известен хоть какой-нибудь алгоритмик перебора...

← →
Uncle Archi (2003-02-23 16:40) [7]

Отсортируй их подсчётом(сложность - O(n), ссылка
http://www.zeiss.net.ru/docs/izone/izone309/pub/izone15.htm
) и иди вот так

for i:=1 to n do
If a[i]+a[n-i+1]=sum then Break;

Всё!!!!!!!!!

← →
mrcat (2003-02-23 17:45) [8]

jinn (23.02.03 16:05)

Тебе предложил вариант. А как сильно он увеличит "сложность всего алгоритма" - зависит от тебя.
З.Ы. В сети есть готовые компоненты для работы с графами.

Uncle Archi © (23.02.03 16:40)

for i:=1 to n do If a[i]+a[n-i+1]=sum then Break;

Кто сказал, что именно 2 числа дают заданную сумму?

← →
MXA (2003-02-24 02:02) [9]

ну нехитрым рекурсивным перебором можно так:

============================================
var
Cnucok: array of byte;

function nouck(CyMMa :integer; Pa3MeP_MaCCuBa :byte) :boolean;
var
n :integer;
begin
Result:=false;
for n:=Pa3MeP_MaCCuBa-1 downto 0 do
if (Cnucok[n]=CyMMa)or
( (CyMMa>Cnucok[n])and(nouck(CyMMa-Cnucok[n], n)) ) then begin
Result:=true; // сложилось типа, Cnucok[n] - слагаемое
Form1.Memo2.Lines.Add(IntToStr(Cnucok[n]));
Break;
end;
end;

ну и что-то вроде:

procedure TForm1.Button1Click(Sender: TObject);
var
n :integer;
begin
Randomize;
Memo1.Lines.Clear;

SetLength(Cnucok, 5);
for n:=0 to length(Cnucok)-1 do begin
Cnucok[n]:=Random(9)+1;
Memo1.Lines.Add(IntToStr(Cnucok[n]));
end;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
Memo2.Lines.Clear;
nouck(StrToInt(Edit2.Text), length(Cnucok));
end;

← →
jinn (2003-02-24 20:32) [10]

Сенкс, МХА!
Всё просто супер...очень просто и изящно. Именно что-то подобное я и надеялся услышать от кого-либо!

нахождение нужной суммы в списке чисел Найти похожие ветки