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

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

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

> Нахождение двух минимальных сумм чисел
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

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


Здравствуйте!
Вот такая задачка:

Дана упорядоченная последовательность N чисел. (2<=N<=200). Каждое число больше 0, но меньше 30000. Нужно из этого ряда найти два набора чисел, величины которых должны быть равны и минимальны. Гарантируется, что эта величина будет меньше 100000. Эту величину нужно выписать.

Примеры:
Дано: 1 2 3 4 5. Группы чисел: 1 2 и 3. Ответ: 3.
Дано: 1 2 5 5 8 10 102. Группы чисел: 5 и 5. Ответ: 5.
Дано: 2 3 4 5. Группы чисел: 2 3 и 5. Ответ: 5.
Дано: 1 3 5 7 13 21. Группы чисел: 1 7 и 3 5. Ответ: 8.
Дано: 1 2 5 8 14. Группы чисел: 1 2 5 и 8. Ответ: 8.


Вот я придумал вот такое решение:
http://img401.imageshack.us/img401/500/20308125la9.png
const
MaxCount=200;
MaxSum=100000;
type
pair=record
l,r:longint;
end;
var
a:array [1..MaxCount] of integer;
b:array [0..50000] of pair; //чтоб хватило
f:text;
n,i,j,k,d:integer;
begin
assign(f,'file.in');
reset(f);
readln(f,n);
for i:= 1 to n do readln(f,a[i]);
close(f);

d:=0;
repeat
inc(d);
b[0].l:=a[d];
b[0].r:=0;
i:=1;
k:=d;

repeat
inc(k);
for j:= 0 to (i-1) do begin
b[j+i].l:=b[j].l;
b[j+i].r:=b[j].r+a[k];
inc(b[j].l , a[k]);
end;
j:=1;
inc(i,i);
while (j<=i) and (b[j-1].l<>b[j-1].r) do inc(j);
until(j<=i) or (b[0].l>MaxSum)

until j<=i;

writeln(b[j-1].l);
end.


Программа перебирает все возможне пары сначало с участием первого числа. Если сумма этих пар больше 100000, а равные величины так и не найдены, то перебирает все возможные пары с участием второго числа и т.д.

Это решение кушает очень много памяти и при большом N вылетает. Возможно, есть более элегантное и правильное решение? =)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
S_lip   Нахождение двух минимальных сумм чисел   25.12.2007 18:23
Michael_Rybak   Любые решения этой задачи будут эвристическими, по…   25.12.2007 18:51
andriano   Непонятно условие: - что такое набор чисел? - поч…   25.12.2007 20:48
S_lip   andriano, ок. постараюсь по подробней. В файле …   25.12.2007 21:51
andriano   Понятно. Просто уже неоднократно сталкивался с тем…   26.12.2007 22:41
S_lip   andriano, нет это ты меня извини, что задачу описа…   27.12.2007 4:10
andriano   Задача переборная. Поэтому основная идея в решении…   27.12.2007 13:07
klem4   в общем вот грубый перебор :) Все приведенные тобо…   28.12.2007 1:26
S_lip   Спасибо всем большое за ответы! klem4, спасибо…   29.12.2007 3:26
andriano   Не мог бы ты объяснить, почему надо перебирать име…   29.12.2007 3:38
S_lip   Именно эти - чтоб получилась цепочка максимальной …   29.12.2007 4:24
andriano   Не понял. Прочитав эту фразу: я понял, что ты, го…   29.12.2007 16:10
S_lip   Я имел ввиду нахождение наибольшего количества чис…   29.12.2007 17:46
andriano   Так и не получил ответа на вопрос: Но предполагаю,…   29.12.2007 18:31
S_lip   andriano, мне не нужен ни один из предложенных вар…   30.12.2007 19:32
Michael_Rybak   Во-первых, посыпая голову пеплом, вынужден признат…   30.12.2007 21:00
andriano   Похоже, что так. Сейчас прикинул, - действительно,…   30.12.2007 21:13
Michael_Rybak   Его решение оптимально, поэтому твое в лучшем случ…   30.12.2007 22:16
andriano   Спасибо, идею алгоритма понял. Его решение оптима…   30.12.2007 23:13
Michael_Rybak   В приведенном мной объяснении многое описано не с…   31.12.2007 0:07
andriano   В приведенном мной объяснении многое описано не с…   31.12.2007 0:21
Michael_Rybak   сейчас попробуем.   31.12.2007 0:25
Michael_Rybak   выбрать не получилось. видимо, можно доказать, чт…   31.12.2007 0:49
andriano   выбрать не получилось. видимо, можно доказать, ч…   31.12.2007 2:50
Michael_Rybak   Ну 15. Какая разница. Это не обязательно прав…   31.12.2007 3:22
S_lip   Michael_Rybak, спасибо за пример. Вот исправленный…   31.12.2007 21:03
Michael_Rybak   на самом деле 15. 1 15000 15002 15004 ... 29998 2…   31.12.2007 21:27
S_lip   15000+15006 = 15002+15004 = 30006 1+29998 = 29999   31.12.2007 22:49
Michael_Rybak   А, теперь я понял, к чему этот пример был. Отличн…   1.01.2008 2:35
S_lip   Спасибо большое всем, кто потратил свое время чита…   1.01.2008 22:31
Michael_Rybak   Отлично, поздравляю. Приходи еще :)   2.01.2008 8:29
andriano   andriano, видишь, этот тест показывает, что нельзя…   2.01.2008 16:46
Michael_Rybak   Такая задача возникает всегда. Именно поэтому уро…   2.01.2008 19:50


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

 





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