Сколькими способами можно заданное число S представить в виде суммы чисел из заданного множества?

@derp · Регистрация: 04.10.2015

Author24 — интернет-сервис помощи студентам

Помогите пожалуйста! Задача – найти количество различных способов, которыми можно заданное число S представить в виде суммы чисел из заданного множества. Суммы, отличающиеся только порядком слагаемых, не учитываются.
пример входа и выхода
Примеры входа и выхода:
input.txt
3 5
1 2 3
output.txt
5

@JuriiMW · 18.11.2015, 08:44

Что-то я не понял из примера: от куда взялась пятёрка в output?

@derp · 22.11.2015, 20:28 **[ТС]**

Сообщение от JuriiMW

Что-то я не понял из примера: от куда взялась пятёрка в output?

Пояснение
Сумму 5 можно набрать следующими способами: 1 + 1 + 1 + 1 + 1 = 5, 1 + 1 + 1 + 2 = 5, 1 + 1 + 3 = 5, 1 + 2 + 2 = 5, 2 +3 = 5.

@JuriiMW · 23.11.2015, 05:37

Pascal

var
  s : Integer;
  a : array [1..100] of Integer;
  c : Integer;
  r : Integer;
 
procedure Find(Sum, index : Integer);
begin
  if Sum = s then
    r += 1
  else if Sum < s then
    for var i := index to c do
      Find(Sum + a[i], i);
end;
 
begin
  reset(input, 'input.txt');
  c := ReadInteger();
  s := ReadLnInteger();
  for var i := 1 to c do
    a[i] := ReadInteger();
  
  r := 0;
  Find(0, 1);
  rewrite(output, 'output.txt');
  Write(r);
end.

@derp · 26.11.2015, 13:51 **[ТС]**

спасибо

@derp 0 / 0 / 1 Регистрация: 04.10.2015 Сообщений: 6
		1
	Сколькими способами можно заданное число S представить в виде суммы чисел из заданного множества? 17.11.2015, 23:29. Показов 3658. Ответов 4 Метки нет (Все метки) Помогите пожалуйста! Задача – найти количество различных способов, которыми можно заданное число S представить в виде суммы чисел из заданного множества. Суммы, отличающиеся только порядком слагаемых, не учитываются. пример входа и выхода Примеры входа и выхода: input.txt 3 5 1 2 3 output.txt 5 0

@JuriiMW 5084 / 2655 / 2350 Регистрация: 10.12.2014 Сообщений: 10,047
	18.11.2015, 08:44	2
	Что-то я не понял из примера: от куда взялась пятёрка в output? 0

@derp 0 / 0 / 1 Регистрация: 04.10.2015 Сообщений: 6
	22.11.2015, 20:28 [ТС]	3
	Сообщение от JuriiMW Что-то я не понял из примера: от куда взялась пятёрка в output? Пояснение Сумму 5 можно набрать следующими способами: 1 + 1 + 1 + 1 + 1 = 5, 1 + 1 + 1 + 2 = 5, 1 + 1 + 3 = 5, 1 + 2 + 2 = 5, 2 +3 = 5. 0

@derp 0 / 0 / 1 Регистрация: 04.10.2015 Сообщений: 6
	26.11.2015, 13:51 [ТС]	5
	спасибо 0

Опции темы

Сколькими способами можно заданное число S представить в виде суммы чисел из заданного множества?

Решение