Массив из чисел, сумма которых равна заданному числу

@gooseim · Регистрация: 23.09.2010

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

Нужен алгоритм или программа на любом языке программирования.
Смысл:
есть число n > 2.
Необходимо получить массив (комбинацию) из чисел < n, сумма которых = n.
Пример:

JavaScript
1
2
3
4
3: [1, 2]
4: [1, 3]
5: [2, 3] | [1, 4]
6: [1, 2, 3]  | [2, 4] | [1, 5]

@vantfiles · 02.03.2019, 14:30

числа не должны повторяться?

3: [1, 2] [1, 1, 1]
4: [1, 3] [2, 2]

так неправильно?

@gooseim · 03.03.2019, 12:02 **[ТС]**

Да, числа не должны повторяться

@Shamil1 · 03.03.2019, 20:55

Добавляете натуральные числа по порядку, пока сумма меньше заданного числа. Затем, если надо, одно число ("излишек") удаляете из массива.

25
1 = 1
1 2 = 3
1 2 3 = 6
1 2 3 4 = 10
1 2 3 4 5 = 15
1 2 3 4 5 6 = 21
1 2 3 4 5 6 7 = 28
1 2 4 5 6 7 = 25

@vantfiles · 04.03.2019, 00:55

По-моему это задача на генерацию всех подмножеств заданного множества.

1 - генерируем множество натуральных чисел от 1 до ( n - 1 )
2 - генерируем все подмножества этого множества (например с помощью рекурсии)
3 - считаем сумму членов каждого из подмножеств и убираем те подмножества, сумма членов которых не равна n

Добавлено через 2 минуты
ps: для оптимизации сумму можно считать прямо во время генерации подмножества

Добавлено через 1 час 52 минуты
На Lua алгоритм выглядит примерно так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function arr1n( n )
    local t = {}
    for i = 1, n do
        t[ #t + 1 ] = i
    end
    return t
end
 
function arr2str( t )
    if #t == 0 then return( "" ) end
    local s = t[ 1 ]
    for i = 2, #t do
        s = s .. " " .. t[ i ]
    end
    return( s )    
end
 
function arr_copy( t )
    local a = {}
    for i = 1, #t do
        a[ i ] = t[ i ]
    end
    return a
end
 
function rec( t, n, s, sum )
 
    if n == #t then
       if sum == N then
          print( arr2str( s ) )
       end
       return
    end
 
    rec( t, n + 1, s, sum )
    local s = arr_copy( s )
    s[ #s + 1 ] = t[ n + 1 ]
    sum = sum + t[ n + 1 ]
    if sum > N then  return  end -- если сумма больше N, ветку можно сразу прервать
    rec( t, n + 1, s, sum )
    
end
 
-- -----------------------------------
 
N = 12 -- заданное число
 
arr = arr1n( N - 1 ) -- генерим множество
 
rec( arr, 0, {}, 0 ) -- и все подмножества

для заданного n = 12 вывод такой:

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	02.03.2019, 14:30
	числа не должны повторяться? 3: [1, 2] [1, 1, 1] 4: [1, 3] [2, 2] так неправильно? 0

@gooseim 516 / 421 / 92 Регистрация: 23.09.2010 Сообщений: 1,165
	03.03.2019, 12:02 [ТС]
	Да, числа не должны повторяться 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,883
	03.03.2019, 20:55
	Добавляете натуральные числа по порядку, пока сумма меньше заданного числа. Затем, если надо, одно число ("излишек") удаляете из массива. 25 1 = 1 1 2 = 3 1 2 3 = 6 1 2 3 4 = 10 1 2 3 4 5 = 15 1 2 3 4 5 6 = 21 1 2 3 4 5 6 7 = 28 1 2 4 5 6 7 = 25 1

Массив из чисел, сумма которых равна заданному числу

Решение