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

wayne

无心人 发表于 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是一个不错的特例，拿来当优化实例吧

KeyTo9_Fans

要试的公比肯定都是分子和分母均不超过$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$个，

可是你需要证明啊

焉知只需要在有理数域测试，而不是在代数数域中找呢？

wayne

无心人 发表于 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种：

1. {352,16,4}
   
2. {815,14,4}
   
3. {841,15,4}
   
4. {1097,12,-4}
   
5. {1099,12,-4}
   
6. ...
   
7. {60233,16,-4}
   
8. {61457,14,4}
   
9. {62565,11,-4}
   
10. {64673,13,4}

复制代码

KeyTo9_Fans

定理$1$：

如果$a_0=b_0$，且区间$[q_a,q_b]$不包含分子和分母均不超过$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}$在区间$[q_a,q_b]$中，矛盾。

所以$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$，且区间$[q_a,q_b]$不包含分子和分母均不超过$s$的分数，

能不能进一步缩小范围

感觉这个条件还是太宽了