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

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

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

> Суммирование чисел из файла
Huver
сообщение 14.11.2005 15:32
Сообщение #1





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

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


Задача:
Дано N целых чисел A1, A2 ... An. Требуется найти кол-во различных сумм вида k1A1 + k2A2 + ... + knAn.
Ввод из файла sums.in. В первой строке находится число N, во второй - A1, A2 ... An через пробел.
Вывод в файл sums.out. Вывести одно число - количество различных значений сумм.

Пример 1:
Ввод 1
3
1 1 2
Вывод 1
5

Пример 2:
Ввод 2
5
49 100 98 49 0
Вывод 3
10

Заранее спасибо.

Сообщение отредактировано: Huver - 14.11.2005 18:39
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
c-ch
сообщение 14.03.2009 20:50
Сообщение #2


Новичок
*

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

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


прошу прощения за поднимание явно древней темы smile.gif
уточняю условие задачи:
Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN.

Входные данные

Входной файл INPUT.TXT в первой строке содержит число N, во второй - A1, A2, ..., AN через пробел. Ограничения: все числа целые, 1 <= N <= 500, 0 <= Ai <=100, 0 <= ki <= 1.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество различных значений сумм.


т.е., для приведённого примера с числами 1, 1, 2 правильный ответ будет 5, т.к. суммы будут следующие:
0, 1, 2, 3, 4 (все к=0, к1=1 остальные=0, к3=1 остальные=0, 1+2, 1+1+2)

я написал программку, решающую эту задачу, что называется, "в лоб"
program qq;
var a:array[1..500]of integer; {комбинации}
b:array[1..500]of 0..100; {числа из файла}
s:array[1..10000] of integer; {суммы}
n,k,q,z,c:integer;
f:text;

function Last:boolean;
begin
last:=a[1]=n-k+1
end;

procedure First;
var i:integer;
begin
for i:=1 to k do a[i]:=i
end;

procedure Next;
var i,j:integer;
begin
j:=k;
while a[j]=n-k+j do j:=j-1;
a[j]:=a[j]+1;
for i:=j+1 to k do a[i]:=a[i-1]+1;
end;

Function Sum:integer;
var i,s:integer;
begin
s:=0;
for i:=1 to k do s:=s+b[a[i]];
Sum:=s;
end;

Function InSums(x:integer):boolean;
var i:integer; flag:boolean;
begin
flag:=false;
for i:=1 to c do
if s[i]=x then flag:=true;
InSums:=flag;
end;

begin
assign(f,'input.txt');
reset(f);
readln(f,n);
for q:=1 to n do read(f,b[q]);
close(f);
s[1]:=0;
c:=1; {количество сумм}
for k:=1 to n do
begin
First;
while not Last do
begin
if not InSums(Sum) then begin c:=c+1; s[c]:=sum end;
Next
end;
if not InSums(Sum) then begin c:=c+1; s[c]:=sum end;
end;
assign(f,'output.txt');
rewrite(f);
write(f,c);
close(f)
end.

проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются smile.gif
у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно
прошу помощи у корифеев алгоритмизации sad.gif
хотелось бы получить рабочий исходник, т.к. времени мало осталось, но буду рад и ценным указаниям (желательно с примерами)
спасибо
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Lapp
сообщение 15.03.2009 11:51
Сообщение #3


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

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

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


Цитата(c-ch @ 14.03.2009 20:50) *
проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются smile.gif
у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно
Этих ресурсов тут во много раз больше, чем достаточно (для тех пределов, которые в условии). Вот эта программка обходится примерно 50 КБ и 0.05 сек на моем ноуте (Turion 1.8 GHz) smile.gif.
const
a=100; {numbers range, 0..a0}
k=500; {max number quantity}

var
n,m,i,j,b: word;
s: array[0..k*a]of boolean;
f: text;

begin
Assign(f,'input.txt');
ReSet(f);
ReadLn(f,n);
s[0]:=true;
for i:=1 to n do begin
ReadLn(f,b);
for j:=(i-1)*a downto 0 do if s[j] then s[j+b]:=true
end;
Close(f);
m:=0;
for i:=0 to n*a do if s[i] then Inc(m);
WriteLn(m);
Assign(f,'output.txt');
ReWrite(f);
WriteLn(f,m);
Close(f)
end.



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

Сообщений в этой теме
Huver   Суммирование чисел из файла   14.11.2005 15:32
volvo   Сначала уточни, что значит ? Именно на примере 1, ...   14.11.2005 16:06
Huver   В файле sums.in записывается вручную: 3 /...   14.11.2005 18:19
volvo   разложение числа ничего не напоминает?   14.11.2005 18:29
FreeMan   Суммированием всех чисел находишь максимум. Потом ...   14.11.2005 18:41
volvo   To: FreeMan Объясни мне, в свете твоего алгоритма...   14.11.2005 18:44
klem4   Я предлагаю забить числа из файла в массив, а пото...   14.11.2005 18:45
Huver   To: volvo значение сумм одинаковое, а порядок раз...   14.11.2005 19:23
FreeMan   To: volvo Нашёл ты первую сумму. 1+2=3. Посмотрел...   15.11.2005 9:39
volvo   Угу... Продолжаем. Нашел вторую, 2+1=3, посмотрел,...   15.11.2005 9:42
FreeMan   Не. Когда мы нашли, что тройка подходит - надо к д...   15.11.2005 9:53
FreeMan   Вот решение. Volvo, извини, что так изуродовал тв...   1.12.2005 10:17
volvo   FreeMan, я, например, жду ответа на свой вопрос (ч...   1.12.2005 10:22
c-ch   прошу прощения за поднимание явно древней темы :) ...   14.03.2009 20:50
Lapp   проблема в том, что этот алгоритм очень трудоёмок ...   15.03.2009 11:51
c-ch   Lapp всё гениальное просто, спасибо огромное :) P...   15.03.2009 14:02
Lapp   PS всем, кто будет копипастить прогу Lapp - будьте...   16.03.2009 3:19
c-ch   нет-нет, никаких претензий, тем более, что Паскаль...   16.03.2009 7:25
Lapp   Паскаль сам инициализацию вроде делает :)Как-то у ...   16.03.2009 11:37
volvo   Угу... Так и должно быть. Турбо/Борланд Паскаль во...   16.03.2009 13:35


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

 



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