|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 28 Oct 2002 23:04:18
To : Anton Yurchenko
Subject : Разложение числа на слагаемы
--------------------------------------------------------------------------------
Replying to a message of Anton Yurchenko to All:
AY> Есть целое N (порядка 1000), необходимо все целые числа из 1..N
AY> представить в виде суммы не более чем двух чисел (то есть можно и
AY> одним, 7=3+4 и 7=7 - оба корректны). При этом число этих "простейших"
AY> слагаемых должно быть минимально.
Это частный случай The Postage Stamp Problem для h=2.
Вот пара ссылок:
http://www.ams.org/journal-getitem?pii=S0025-5718-99-01204-1
http://erdos.math.swt.edu/teach/2000/fall/5336/projects/projectall.pdf
В последней статье приводится результат:
2/7 k^2 <= n(2,k) <= (1-0.1329) k^2/2
Из которого следует:
для N=100 оптимально число "слагаемых" s удовлетворяет неравенству 16<=s<=19
для N=1000 соответственно 49<=s<=60
AY> Hапример для N=100 этот набор
AY> может состоять из 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90 (но
AY> чую что это не оптимально...)
Восемнадцать слагаемых не противоречит указанному выше неравенству ;-)
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
