Суммирование чисел из файла Опции

[Huver]

Задача:
Дано 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 22:39

[volvo]

Сначала уточни, что значит

кол-во различных сумм

? Именно на примере 1, 2, 3 что должно быть выведено?

[Huver]

В файле sums.in записывается вручную:
3 //кол-во чисел
1 1 2 //числа через пробел

Необходимо вычеслить кол-во различных значений сумм и записать результат в файл sums.out ввиде:

Ввод 1
3
1 1 2
Вывод 1
3 //результат

Поиск различных сумм (складываются все возможные варианты чисел):
1+1=2
1+1=2
1+2=3
2+1=3
2+1=3
1+1+2=4
1+2+1=4
2+1+1=4
2+1+1=4

Результат: кол-во различных сумм: 3.

Сообщение отредактировано: Huver - 14.11.2005 22:20

[volvo]

разложение числа ничего не напоминает?

[FreeMan]

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

[volvo]

To: FreeMan
Объясни мне, в свете твоего алгоритма, 1+2=3 и 2+1=3 это разные суммы?

[klem4]

Я предлагаю забить числа из файла в массив, а потом ипользовать прогу, которая находится по ссылке, которую дал volvo. Там решена абсолютно такая-же задача, только без файла.

[Huver]

To: volvo
значение сумм одинаковое, а порядок разный
1[1] 1[2] 2

1[1]+2=3
1[2]+2=3

[FreeMan]

To: volvo
Нашёл ты первую сумму. 1+2=3. Посмотрел, что 1 и 2 есть в файле. Если есть, то 3 подходит, переходишь к проверке 2.

[volvo]

Угу... Продолжаем. Нашел вторую, 2+1=3, посмотрел, 1 и 2 есть в файле, увеличиваем счетчик... А не надо, т.к. это просто перестановка уже существующей суммы.

Стоп.
Huver, ты бы для себя решил, чего тебе надо. В первом посте ты пишешь, что для

<1, 1, 2>

результат будет 5, в посте №3 - для той же входной последовательности результат уже равен 3...

Вопрос: Что будет ПРАВИЛЬНЫМ результатом?

[FreeMan]

Не. Когда мы нашли, что тройка подходит - надо к двойке переходить и раскладывать её, а тройку больше не трогать

[FreeMan]

Вот решение.
Volvo, извини, что так изуродовал твою процедуру

[volvo]

FreeMan,
я, например, жду ответа на свой вопрос (что считать правильным решением), прежде чем что-то выкладывать... По-моему, автор сам не знает, что хочет, а "принеси то, не знаю что" я не умею...

[c-ch]

прошу прощения за поднимание явно древней темы
уточняю условие задачи:
Дано 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 вычисления, мягко говоря, затягиваются
у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно
прошу помощи у корифеев алгоритмизации
хотелось бы получить рабочий исходник, т.к. времени мало осталось, но буду рад и ценным указаниям (желательно с примерами)
спасибо

[Lapp]

проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются
у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно

Этих ресурсов тут во много раз больше, чем достаточно (для тех пределов, которые в условии). Вот эта программка обходится примерно 50 КБ и 0.05 сек на моем ноуте (Turion 1.8 GHz) .

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.

[c-ch]

Lapp
всё гениальное просто, спасибо огромное

PS всем, кто будет копипастить прогу Lapp - будьте внимательны ;)

[Lapp]

PS всем, кто будет копипастить прогу Lapp - будьте внимательны

Таинственное замечание )). Написал бы прямым текстом, что я забыл инициализировать массив s нулями. Каюсь, FP расслабляет..
Извиняюсь. Ниже исправленный вариант. Также пофиксена неточность в комментарии и добавлена некоторая рацуха, которая может еще сократить время (а может и увеличить))).

const
  a=100;   {numbers range, 0..a}
  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 SizeOf(s) do s[i]:=false;   {initializing s}
  for i:=1 to n do begin
    ReadLn(f,b);
    if b>0 then for j:=(i-1)*a downto 0 do if s[j] then s[j+b]:=true  {condition on b added}
  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.

[c-ch]

нет-нет, никаких претензий, тем более, что Паскаль сам инициализацию вроде делает
намёк был на то, что в задании числа расположены в одной строке, а у тебя считывание идёт, как если бы они в столбик записаны были
к тому же, я решил, что ошибка сделана намеренно, в образовательных целях))) типа что бы уж не совсем халява была

[Lapp]

Паскаль сам инициализацию вроде делает

Как-то у меня странно получилось: при повторном запуске массив s не обнулялся (в ВР). Я уже так давно не работаю с ТР/ВР, что не могу объяснить этот феномен. Волво?..

намёк был на то, что в задании числа расположены в одной строке, а у тебя считывание идёт, как если бы они в столбик записаны были
к тому же, я решил, что ошибка сделана намеренно, в образовательных целях))) типа что бы уж не совсем халява была

Нет, просто невнимательность моя. При беглом просмотре твоей проги я не ощутил особой необходимости в подобных мерах . А "в образовательных целях" я обычно просто недописываю.

[volvo]

Как-то у меня странно получилось: при повторном запуске массив s не обнулялся

Угу... Так и должно быть. Турбо/Борланд Паскаль вообще ничего не инициализирует и не обнуляет, ни при первом запуске, ни при последующих. Просто при старте IDE память очищается, а при рестарте программы - нет. Каким было содержимое той области памяти, где компилятор расположил переменную - таким и остается. Как результат - непредсказуемое поведение программы (если переменные не инициализируются в коде самой программы).

В более продвинутых компиляторах с этим чуть лучше, но все-таки лучше взять инициализацию глобальных переменных на себя, а не полагаться на компилятор.