|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 29 Oct 2002 04:46:09
To : Anton Yurchenko
Subject : Re: Разложение числа на слагаемы
--------------------------------------------------------------------------------
"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остейших" слагаемых должно
быть
> минимально.
> Hап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:
Hабор до 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Разложение числа на слагаемы 
