Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2003.03.06;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2003.03.06;
Скачать: [xml.tar.bz2];

Наверх





Память: 0.58 MB
Время: 0.048 c
1-17071
IVANOV
2003-02-22 08:16
2003.03.06
Глобален ли TScreen?


1-17041
Stream2k
2003-02-22 08:41
2003.03.06
Реестр >>> Помогите плиз!!!!!


6-17247
Uncle Archi
2003-01-17 22:07
2003.03.06
Chat


14-17308
глупый
2003-02-17 13:50
2003.03.06
Fidonet


3-16959
VLL
2003-02-14 12:54
2003.03.06
Список серверов





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский