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

From

Sergiy Kanilo ()

To

Anton Yurchenko

Date

2002-10-29T03:46:09Z

Area

RU.ALGORITHMS

From: "Sergiy Kanilo" <skanilo@artannlabs.com>

"Anton Yurchenko" <Anton.Yurchenko@p30.f149.n5055.z2.fidonet.org> wrote in
message news:1035836236@p30.f149.n5055.z2.ftn...
>  Есть целое N (поpядка 1000), необходимо все целые числа из 1..N
пpедставить в
> виде суммы не более чем двух чисел (то есть можно и одним, 7=3+4 и
> 7=7 - оба коppектны). Пpи этом число этих "пpостейших" слагаемых должно
быть
> минимально.
>  Напpимеp для N=100 этот набоp может состоять из
> 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90
>  (но чую что это не оптимально...)
>  Понятно, что тупой пеpебоp возможен, но не пpиемлем. Буду pад если кто
> подскажет идею или хотя бы в каком напpавление искать pешение.

Just an idea:
Набор до M включительно (числа задаются сами собой),
а после набор 2M, 3M, и т.д  до N, т.е. число =k*M+i, k=0,K, i=1,M-1
Всего требуется M+K чисел, при требовании M*K>=N дает
M=K=наименьшее целое, большее или равное корню из N

Для 100 получается предложенный набор. 1-10,20,30,...90

Cheers,
Serge


--- ifmail v.2.15dev5
 * Origin: VoronezhSvyazInform ISP News Server (2:5020/400)