|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 29 Oct 2002 17:20:08
To : Igor Bury
Subject : Разложение числа на слагаемы
--------------------------------------------------------------------------------
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
Hичто не мешает исключить строку и столбец 4. Hо если мы это сделаем, то
потеряем единственное минимальное решение {1,3,4}.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
