无心人 发表于 2013-8-24 08:55
按照我的思路，做个穷举程序，
按照你们的思路，做个调整程序，
我突然间对多出来的那个配额d很感兴趣，发现d的绝对值很小，在n<=16的情况下，基本上都是0，1，2。
算一下，s=10^8,n=2->100，d的值为0的有19个，分别是n=2,3,6,8,14,15,16,22,24,26,28,30,35,38,43,44,49,65,69
{0,19,{2,3,6,8,14,15,16,22,24,26,28,30,35,38,43,44,49,65,69}}
{-1,20,{7,9,10,13,23,25,39,42,45,46,53,56,60,61,72,76,83,88,90,99}}
{1,24,{4,5,12,17,18,20,21,27,40,41,47,50,54,55,57,62,63,66,79,80,91,95,96,97}}
{-2,9,{11,36,48,51,59,64,71,81,89}}
{2,5,{19,31,37,73,100}}
{-3,7,{33,68,70,82,84,87,98}}
{3,9,{32,52,67,74,77,78,85,93,94}}
{-4,3,{29,86,92}}
{4,1,{34}}
{5,1,{75}}
{-6,1,{58}}
s=60000，n=2。。。200。统计如下：
{0,38,{2,3,6,8,13,16,17,19,23,28,33,35,48,52,54,60,64,78,81,82,83,87,90,91,97,100,101,104,106,108,110,119,121,122,136,151,161,199}}
{-1,31,{4,14,22,40,46,47,53,59,61,63,67,72,74,77,99,103,116,135,140,153,154,159,165,166,172,173,176,181,184,196,197}}
{1,38,{5,7,9,10,11,12,15,20,29,30,37,38,41,44,50,58,62,69,75,76,80,86,94,98,115,120,129,138,147,148,152,160,169,170,171,177,186,190}}
{-2,15,{25,26,34,39,55,68,71,92,114,123,124,132,134,145,158}}
{2,21,{18,21,31,43,49,56,66,73,88,89,137,139,142,143,144,146,156,167,179,194,200}}
{-3,17,{24,27,32,36,84,93,95,105,109,117,128,131,133,162,178,180,198}}
{3,12,{42,45,57,79,111,112,126,141,149,163,174,187}}
{-4,13,{51,65,85,102,107,113,127,150,164,182,183,189,193}}
{4,2,{70,118}}
{-5,4,{96,130,157,192}}
{5,1,{168}}
{-6,2,{125,188}}
{-7,2,{175,195}}
{7,1,{185}}
{-9,1,{155}}
{10,1,{191}}
KeyTo9_Fans 发表于 2013-8-24 09:14
假设【前提$1$】成立，那么：
解决该问题的算法的时间复杂度的理论下界是$\Omega(n)$，
两点疑问
1、如何确定是试遍所有公比？
2、如何避免大分数运算？
wayne 发表于 2013-8-24 10:08
我突然间对多出来的那个配额d很感兴趣，发现d的绝对值很小，在n100，d的值为0的有19个，分别是n=2,3,6, ...
s=10^8, n=58是一个不错的特例，拿来当优化实例吧
要试的公比肯定都是分子和分母均不超过$s$的分数，
这样的分数不超过$s^2$个，
因此采用二分法最多试$O(\log(s))$次就可以试遍。
具体的二分方法如下：
将分母固定为$s^2$，
分子的最小值是$a_0*s^2$，
最大值是$(a_0+1)*s^2$。
因此分子一共有$(s^2+1)$种选取方案，
最多二分$\lceil\log_2(s^2+2)\rceil$次就可以分完。
之所以可以这样做的原因是：
任意一段长度为$1/s^2$的区间里，最多只有$1$个分子和分母均不超过$s$的分数。
#####
如果$s$很大，是无法避免大数运算的。
此时需要用到大整数乘法和大整数除法。
如果大整数乘法和大整数除法的时间复杂度都是$O(log^2(s))$，
那么求最佳公比的二分算法的时间复杂度是$O(n\log^3(s))$。
KeyTo9_Fans 发表于 2013-8-24 12:35
要试的公比肯定都是分子和分母均不超过$s$的分数，
这样的分数不超过$s^2$个，
可是你需要证明啊
焉知只需要在有理数域测试，而不是在代数数域中找呢？
无心人 发表于 2013-8-24 12:31
s=10^8, n=58是一个不错的特例，拿来当优化实例吧
这个例子太大了。
我搜索了所有 2<n<=16,1<s<=65535 的空间,发现 d绝对值 最大的是5，
有5种情况(比如s=5020,n=15,d=-5)
{5020, 15, -5},
{8332, 16, -5},
{8333, 16, -5},
{53288,16, -5},
{56869, 16, -5}
d=4的情况有183种：{352,16,4}
{815,14,4}
{841,15,4}
{1097,12,-4}
{1099,12,-4}
...
{60233,16,-4}
{61457,14,4}
{62565,11,-4}
{64673,13,4}
定理$1$：
如果$a_0=b_0$，且区间$$不包含分子和分母均不超过$s$的分数，
那么数列
$A={a_0,a_1=\lfloor a_0*q_a\rfloor,a_2=\lfloor a_1*q_a\rfloor,...,a_{n-1}=\lfloor a_{n-2}*q_a\rfloor}$
和数列
$B={b_0,b_1=\lfloor b_0*q_b\rfloor,b_2=\lfloor b_1*q_b\rfloor,...,b_{n-1}=\lfloor b_{n-2}*q_b\rfloor}$
必定是同一个数列。
证明：
反证法，
假设$A$和$B$是不同的数列，
那么存在$i(0<i<n)$，使得：
$a_0=b_0$
$a_1=b_1$
……
$a_{i-1}=b_{i-1}$
$a_i<b_i$。
于是：
$q_a<(a_i+1)/a_{i-1}$，
$q_b\geq(a_i+1)/a_{i-1}$，
所以分子和分母均不超过$s$的分数$(a_i+1)/a_{i-1}$在区间$$中，矛盾。
所以$A$和$B$是相同的数列，证毕。
#####
通过定理$1$，我们可以知道：
我们所生成的数列只会在公比等于一个分子和分母均不超过$s$的分数的时候才会发生变化。
而这样的分数不超过$s^2$个，
因此最多二分$O(log(s^2))=O(log(s))$次就可以分完。
KeyTo9_Fans 发表于 2013-8-24 13:40
定理$1$：
如果$a_0=b_0$，且区间$$不包含分子和分母均不超过$s$的分数，
能不能进一步缩小范围
感觉这个条件还是太宽了