将一正整数打散成指定长度的近似等比整数数列

gxqcn

已知：整数 $s$ 和 $n$，$2<=n<=16<=s<=65535$，

要求：一整数数列${ a_0,a_1,...,a_{n-1} }$，满足如下条件

• $sum_{i=0}^{n-1}{a_i}=s$；
  
  
• $1<=a_0<=a_1<=...<=a_{n-1}$；
  
  
• 令 $q_0 = a_0; \ q_i =(("double")a_i)/a_{i-1}(i>0)$，需使 $max{q_i} - min{q_i}$ 尽可能地小。

请问算法思路在哪里？
如果代码全程不允许用浮点数据结构，又当如何编码？

gxqcn

这是我从工作中需要的一个问题提炼得到的，
看似很初等，实则又不简单。。。

mathematica

我对问题的背景更感兴趣

云梦

n=2为例：
a1+a2<65535
若使qi尽量小，则a1尽量大。
只有a1和a2为连续数时:a1/(a1-1)-a2/(a2-1)为最小。
a1/(a1-1)-（a1+m)/(a1+m-1)当m=1时为最小。
所以a1=32767   [65535/2]
a2=32768
a1+a2=65535
q1-q2=9.314*10^-10

云梦

n=3时:同理。
a1,a2,a3为连续数.
a1=21844   [65535/3]-1
a2=21845
a3=21846
a1+a2+a3=65535
q1-q3=4.19146*10^-9

gxqcn

注意：不是使 qi 尽可能地小，
而是使“公比”值域范围跨度（max - min）尽可能地小！

$q_0 = a_0; \ q_i =(("double")a_i)/a_{i-1}(i>0)$

注意：上面的 i 及 i-1 均为下标。

云梦

好像连续n个数是最符合条件的。

gxqcn

举例来说：

标准的等比数列{1,10,100,1000,10000}所有元素之和=11111，
但将“11111”打散成长度为5的最佳“等比数列”却非该数列，

比如说{6,38,240,1500,9327}的“公比”动态范围（max-min=6.333-6=0.333）
就比{1,10,100,1000,10000}的“公比”动态范围（max-min=10-1=9）
要小得多！

mathematica

没人能够解决你的问题

zeroieme

gxqcn 发表于 2013-8-16 08:11
举例来说：

标准的等比数列{1,10,100,1000,10000}所有元素之和=11111，

这样的 “公比”定义  等价有一个隐藏“超前项” a_-1恒等于 1