| 1 Пересадин Илья Валерьевич, 07 февраля 2010 г. 19:48:07 | |
|
Мас Мих В,я тоже вам очень благодарен,мне давно был нужен этот алгоритм :-) вы мне ОЧЕНЬ помогли :-)
|
|
|
| 2 Папава Илона Элгуджаевна, 07 февраля 2010 г. 19:17:34 | |
Мас Мих В
огромное вам спасибо.=)
|
|
|
| 3 Мас Мих В, 07 февраля 2010 г. 16:29:36 | |
А вообще для тех кто пишет на Паскале могут почитать такую вот книжку
http://e-maxx.ru/bookz/files/menshikov.djvu (книга)
http://e-maxx.ru/bookz/files/menshikov_cd.zip (сд к книге)
Может чего-то для себя найдете=)
|
|
|
| 4 Мас Мих В, 07 февраля 2010 г. 16:26:31 | |
В общем поставил себе паскаль) Написал, нашел конечно кучу ошибок (надо было сразу поставить)
В общем в первой строке файла toFind и N. (toFind - число которое надо получить суммой, N-число элементов данного массива. N должно быть не более 100)
Во второй строке через пробелы элементы массива
То есть например дан файл:
15 5
5 2 7 4 3
Ответом будет:
YES
5 7 3
для данных:
10 3
1 2 11
ответ будет: NO
код по ссылке: http://paste.ubuntu.com/370934/
|
|
|
| 5 Мас Мих В, 07 февраля 2010 г. 15:53:54 | |
|
сейчас все соберу
|
|
|
| 6 Пересадин Илья Валерьевич, 07 февраля 2010 г. 13:42:12 | |
|
Мас Мих В,не могли бы вы собрать ВСЮ программу в кучу... А то я долго пытался,но у меня это так и не получилось :-(
|
|
|
| 7 Папава Илона Элгуджаевна, 07 февраля 2010 г. 13:29:48 | |
'...procedure Rec(integer cur)
begin
if (cur<n)
begin
inc(cur);
used[cur]:=false;
Rec(cur);
if (sum+a[i]<=НужноеЧисло)
begin
....'
а какое значение имеет параметр i??
|
|
|
| 8 AC-SKYDOS, 07 февраля 2010 г. 13:20:55 | |
Папава Илона Элгуджаевна
завершение программы
а если не знаете, что значит такая функция подучите-ка паскаль
|
|
|
| 9 Папава Илона Элгуджаевна, 07 февраля 2010 г. 13:00:38 | |
|
а что означает halt??
|
|
|
| 10 Мас Мих В, 07 февраля 2010 г. 11:26:04 | |
procedure Rec(integer cur)
begin
if (cur<n)
begin
inc(cur);
used[cur]:=false;
Rec(cur);
if (sum+a[i]<=НужноеЧисло)
begin
used[cur]:=true;
sum:=sum+a[i];
Rec(cur);
sum:=sum-a[i];
end;
end
else
begin
if (sum=НужноеЧисло) then
begin
writeln('YES we can!");
//а тут выводим сами числа
for i:=1 to n do if used[i] then write(a[i]+' ');
halt;
end;
end;
end;
|
|
|
| 11 Мас Мих В, 07 февраля 2010 г. 11:25:36 | |
ой и я еще забыл наверно
надо все-таки где
sum:=sum+a[i];
Rec(cur);
после надо
sum:=sum-a[i];
|
|
|
| 12 Папава Илона Элгуджаевна, 07 февраля 2010 г. 11:07:49 | |
|
щас попробую осмыслить....
|
|
|
| 13 Папава Илона Элгуджаевна, 07 февраля 2010 г. 11:01:20 | |
|
ага...спасибо=)
|
|
|
| 14 Мас Мих В, 07 февраля 2010 г. 10:47:36 | |
Если честно так в голову например приходят только идеи оптимизации (так как думал, только над решением именно рекурсивного перебора)
Например вызывать процедуру каждый раз не добавляя, а добавлять и вызывать только если меньше или равно искомого числа, что то вроде вот так
procedure Rec(integer cur)
begin
if (cur<n)
begin
inc(cur);
used[cur]:=false;
Rec(cur);
if (sum+a[i]<=НужноеЧисло)
begin
used[cur]:=true;
sum:=sum+a[i];
Rec(cur);
end;
end
else
begin
if (sum=НужноеЧисло) then
begin
writeln('YES we can!");
//а тут выводим сами числа
for i:=1 to n do if used[i] then write(a[i]+' ');
halt;
end;
end;
end;
И кстати в основной программе наверно логичнее сделать, что-то вроде этого
sum:=0;
Rec(0);
|
|
|
| 15 Папава Илона Элгуджаевна, 07 февраля 2010 г. 10:24:24 | |
|
"...Ну это не рационально)...." а подскажите, какой способ будет являться рациональным??
|
|
|
| 16 Папава Илона Элгуджаевна, 07 февраля 2010 г. 10:18:33 | |
|
Спасибо огромное!!!!=)
|
|
|
| 17 Канзитдинов Батыр Никматуллаевич, 07 февраля 2010 г. 9:25:25 | |
Чем на Pascal писать такой огромный код, лучше переходи на С++, там STL тебе и не в этом поможет.
например перебор всех перестановок в 5 строчек:
#include <algorithm>
...
int a[MAXN] = {1, 2, 3, 4, . . . , MAXN};
do{
for(int i = 0; i < MAXN; i++)
cout << a[i] << " ";
}while(next_permutation(a, a + MAXN));
А на паскале в 20 - 30 обойдется...
|
|
|
| 18 Мас Мих В, 07 февраля 2010 г. 1:27:40 | |
там в процедуре после
sum:=sum+a[i];
тоже надо вызвать Rec(cur);
|
|
|
| 19 Мас Мих В, 07 февраля 2010 г. 1:25:31 | |
Ну это не рационально)
Ну если тебе надо перебрать все варианты
можно оформить это так
у тебя есть глобальный массив чисел
a:array[1..N] of integer;
sum:integer;
used:array[1..N] of boolean; //это если тебе надо еще и знать суммой из каких именно чисел получилось число
и ты каждое число либо добавляешь в общую сумму либо нет
делается это примерно так
в основной программe что-то вроде
sum:=0;
used[i]:=false;
Rec(1);
used[i]:= true;
sum:=a[i];
Rec(1);
а в процедуре примерно так
procedure Rec(integer cur)
begin
if (cur<n)
begin
inc(cur);
used[cur]:=false;
Rec(cur);
used[cur]:=true;
sum:=sum+a[i];
end
else
begin
if (sum=НужноеЧисло) then
begin
writeln('YES we can!");
//а тут выводим сами числа
for i:=1 to n do if used[i] then write(a[i]+' ');
halt;
end;
end;
end;
//может где ошибся, паскаля под рукой не было)
|
|
|
| 20 Папава Илона Элгуджаевна, 07 февраля 2010 г. 0:15:28 | |
|
Ну подскажите кто-нибудь!?
|
|
|
