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

From

Max Alekseyev (2:5015/60)

To

Igor Bury

Date

2002-10-29T16:20:08Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Igor !

Replying to a message of Igor Bury to Anton Yurchenko:

 AY>>  Есть целое N (порядка 1000), необходимо все целые числа из 1..N
 AY>> представить в виде суммы не более чем двух чисел (то есть можно и
 AY>> одним, 7=3+4 и 7=7 - оба корректны). При этом число этих
 AY>> "простейших" слагаемых должно быть минимально. 

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

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

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

Результат зависит от порядка исключения, и вовсе не обязан быть минимальным.

Пример: N=8. Массив выглядит так:

12345678
23456780
34567800
45678000
56780000
67800000
78000000
80000000

Ничто не мешает исключить строку и столбец 4. Но если мы это сделаем, то потеряем единственное минимальное решение {1,3,4}.

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)