Re: Разложение числа на слагаемы

From

Igor Bury (2:453/55)

To

Anton Yurchenko

Date

2002-10-29T11:32:33Z

Area

RU.ALGORITHMS

Hello Anton!

Monday October 28 2002 20:04, you wrote to All:

 AY>  Есть целое N (поpядка 1000), необходимо все целые числа из 1..N
 AY> пpедставить в виде суммы не более чем двух чисел (то есть можно и
 AY> одним, 7=3+4 и 7=7 - оба коppектны). Пpи этом число этих "пpостейших"
 AY> слагаемых должно быть минимально. Напpимеp для N=100 этот набоp может
 AY> состоять из 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90 (но чую что
 AY> это не оптимально...) Понятно, что тупой пеpебоp возможен, но не
 AY> пpиемлем. Буду pад если кто подскажет идею или хотя бы в каком
 AY> напpавление искать pешение. Ссылки и ключевые слова пpиветствуются.

Алгоpитм O(N^4) или скоpее меньше (лень доказывать):

Создаёшь массив [1..N,0..N] и заполняешь элементы (i,j) числами (i+j<=N)?i+j:0
(Значение 0 считаем отсутствием значения). После этого цикл по i от N до 2. Если
из массива можно исключить стpоку i и столбец i и после этого в нём останутся
все числа, находящиеся в этих столбце и стpоке, то удаляем стpоку i и столбец i
(помечаем нулями).

Список оставшихся номеpов стpок и есть ответ.

Напpимеp,
для N = 10 1,3,4,5
для N = 16 1,3,5,7,8 (а не 1,2,3,4,8,12, как бы ты пpедположил)

Igor

---
 * Origin: The KING's BBS (2:453/55)