Форум программистов, компьютерный форум CyberForum.ru

Разложение числа на слагаемые - C++

Восстановить пароль Регистрация
 
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
04.01.2014, 11:21     Разложение числа на слагаемые #1
Дано целое число S и натуральное N (N>1). Создать массив из 2N целых чисел, так, чтобы сумма всех элементов равнялась S, но чтобы никакая сумма двух элементов из первой и второй половины массива не повторялась бы.

Например, если S=21; N=3;
То искомый массив M[6]={1, 2, 9, 0, 3, 6};

сумма всех элементов равна 21
1+2+9+0+3+6 = 21

попарные суммы (1,4,7,2,5,8,9,12,15) не повторяются:
1+0=1; 1+3=4; 1+6=7; 2+0=2; 2+3=5; 2+6=8; 9+0=9; 9+3=12; 9+6=15;

Если «в лоб»… то можно через random, подобрать 2N разных слагаемых, пока не получим желаемую сумму. Затем суммировать, комбинируя в парах, элементы первой и второй половины. Если повторений нет, то решение найдено. Если повторения есть, то всё сначала.
Согласен, что это тупой алгоритм … Но ничего другого пока в голову не пришло. Может подскажете как более рационально подобрать такие слагаемые?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2014, 11:21     Разложение числа на слагаемые
Посмотрите здесь:

C++ Разложение числа
Разложение числа на слагаемые C++
C++ Разложение на слагаемые
Разложение числа C++
Разложение натурального положительного числа на слагаемые? C++
C++ разложение на все возможные слагаемые
C++ разложение числа
C++ Подсчитать количество различных разбиений числа N на натуральные слагаемые

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 02:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru