Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
gooseim
Эксперт С++
511 / 415 / 92
Регистрация: 23.09.2010
Сообщений: 1,165
1

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

02.03.2019, 12:37. Просмотров 928. Ответов 4

Нужен алгоритм или программа на любом языке программирования.
Смысл:
есть число 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]
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2019, 12:37
Ответы с готовыми решениями:

Алгоритм подбора множителей к числам из массива, сумма произведений которых равна заданному числу
Число и массив для наглядности. Входные данные (вводим вручную): А = 3563 всегда целое...

Одномерный массив чисел. Найти индексы элементов, сумма значений которых равна заданному числу
Добрый день, помогите дописать программу. Условие: Одномерный массив чисел a1...a20. Найти...

Найти количество натуральных трехзначных чисел, сумма которых равна заданному числу N
Составить программу, определяющую количество натуральных трехзначных чисел , сумма которых равна...

Найти все группы чисел, сумма которых равна заданному числу
Есть такое задание: Задано n произвольных натуральных чисел. Найти все группы по k чисел, сумма...

В последовательности целых чисел найти пары, сумма которых равна заданному числу
Дана последовательность целых чисел а1, а2,..., аn. Указать пары чисел ai, aj, таких, что ai + aj =...

4
vantfiles
164 / 85 / 35
Регистрация: 07.05.2013
Сообщений: 300
02.03.2019, 14:30 2
числа не должны повторяться?

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

так неправильно?
0
gooseim
Эксперт С++
511 / 415 / 92
Регистрация: 23.09.2010
Сообщений: 1,165
03.03.2019, 12:02  [ТС] 3
Да, числа не должны повторяться
0
Shamil1
Модератор
2269 / 1563 / 352
Регистрация: 26.03.2015
Сообщений: 5,641
03.03.2019, 20:55 4
Добавляете натуральные числа по порядку, пока сумма меньше заданного числа. Затем, если надо, одно число ("излишек") удаляете из массива.

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
vantfiles
164 / 85 / 35
Регистрация: 07.05.2013
Сообщений: 300
04.03.2019, 00:55 5
Лучший ответ Сообщение было отмечено gooseim как решение

Решение

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

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 вывод такой:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 7
4 8
3 9
3 4 5
2 10
2 4 6
2 3 7
1 11
1 5 6
1 4 7
1 3 8
1 2 9
1 2 4 5
1 2 3 6
1
04.03.2019, 00:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.03.2019, 00:55

Получить все пятерки натуральных чисел сумма которых равна заданному числу
Ввести с клавиатуры натуральное число n(n&gt;=5). Получить все пятерки натуральных чисел...

Вывести все четырёхзначные числа, сумма чисел которых равна заданному числу
#include &lt;iostream&gt; using namespace std; int main(){ int N, i, j; cout&lt;&lt;&quot;Vvedite...

Определить количество трёхзначных чисел, сумма цифр которых равна заданному числу
Определить количество трёхзначных натуральных чисел, сумма цифр которых равна заданному числу N.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru