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

无心人

我觉得应该分配给最大最小值

然后，最大最小值将内敛

重新分配给新的最大最小值

依次循环搞定

无心人

比值的分子分母一次调整，将涉及到比值本身跟相邻两个比值的调整

所以，并不是很容易能得到优化的

wayne

无心人 发表于 2013-8-24 08:23
我觉得应该分配给最大最小值

然后，最大最小值将内敛

我觉得根据等比公式计算出q，取圆整之后， q 的最大值和最小值 已经是 刚性的了，把配额 给他们两个的话，不仅达不到财富均匀的目的，反而会牵一发而动全身，引起骚乱。

应该分配给那种 肉大身沉，体量庞大的项，
另外，分给最后两项，不会影响前面的既得利益者。

gxqcn

当初为了发现规律，
我先用 Mathematica 解出浮点的公比，
然后打开 Excel，进行余下的半手工操作。

先人为的在数列之前加一项“1”，
计算出相邻数之比（后面的除以前面的），
找出最大者，将其对应的数-1，加在最小者对应的数上。
由于比例是除法关系，敏感度与分母的大小相关，
所以该微调若作用于前几项，甚至会让q_min、q_max发生变化，
而微调作用于较大的项上，则对评价值影响不那么敏感。
此即楼上 wayne 所总结的那样。

注：上述微调也许需要进行多次。

wayne

是否能证明或者证否这个：

根据等比公式计算出理想情况的浮点数q，各项取圆整之后，得到的圆整数列的 q 的最大值和最小值 已经是 刚性的了，即最优

当最优确定之后，多余的那部分财产，似乎只能分给最后一项，或者最后两项

无心人

好吧，我是倾向于逐渐调整的
你们是倾向于定向爆破

无心人

wayne 发表于 2013-8-24 08:39
是否能证明或者证否这个：

应该不是最优

gxqcn

当最优确定之后，多余的那部分财产，似乎只能分给最后一项，或者最后两项

由于圆整（可以理解为四舍五入）带来的误差，会对相邻项之比带来波动，
所以即便完成了多余财产（可正可负）的分配，往往仍需进行微调。

无心人

按照我的思路，做个穷举程序，
按照你们的思路，做个调整程序，

看两者得到的结果一致么

KeyTo9_Fans

假设【前提$1$】成立，那么：

解决该问题的算法的时间复杂度的理论下界是$\Omega(n)$，

原因是将结果输出来就需要$\Omega(n)$的时间了。

但目前我只找到了时间复杂度为$O(n\log(s))$的算法，

该算法是确定的算法，输出结果一定是最优解，而且不需要使用浮点运算。

是否存在时间复杂度为$O(n)$的算法，我现在还不知道。

【前提$1$】：

任何两个$0$到$s$的整数进行一次代数运算或逻辑运算的时间复杂度是$O(1)$。

引入该前提是为了避免分析大数运算的时间复杂度。

#####

该算法的核心是二分法。

该算法一共有$2$个步骤。

步骤一：二分法确定首项
　　读入$n$和$s$，用二分法求$a_0$，使得：
　　　　$a_0+a_0^2+a_0^3+...+a_0^n\leq s$
　　　　$(a_0+1)+(a_0+1)^2+(a_0+1)^3+...+(a_0+1)^n>s$

步骤二：二分法确定公比
　$1$、如果$a_0+a_0^2+a_0^3+...+a_0^n=s$，那么输出$a_0,a_0^2,a_0^3,...,a_0^n$，结束；否则继续下面的步骤。

　$2a$、取公比$q$，满足$a_0<q<a_0+1$，令$a_1=\lfloor a_0*q\rfloor$、$a_2=\lfloor a_1*q\rfloor$、……
　$3a$、如果$a_0+a_1+a_2+...+a_{n-1}<s$，则加大公比，否则减小公比。
　$4a$、重复$2a$、$3a$，直到试遍$(a_0,a_0+1)$中所有可能的公比为止。

　$2b$、取公比$q$，满足$a_0<q<a_0+1$，令$a_1=\lceil (a_0+1)*q\rceil$、$a_2=\lceil a_1*q\rceil$、……
　$3b$、如果$a_0+a_1+a_2+...+a_{n-1}>s$，则减小公比，否则加大公比。
　$4b$、重复$2b$、$3b$，直到试遍$(a_0,a_0+1)$中所有可能的公比为止。

　$5$、假设$4a$试出来的公比是$q_a$，$4b$试出来的公比是$q_b$，比较$(q_a-a_0)$和$(a_0+1-q_b)$的大小，输出较小者及相应的数列。

#####

步骤一的时间复杂度是$O(n\log(s))$。

对于步骤二，要试的公比肯定都是分子和分母均不超过$s$的分数，这样的分数不超过$s^2$个。

因此步骤二的时间复杂度是$O(n\log(s^2))=O(n\log(s))$。

综上所述，该算法的时间复杂度是$O(n\log(s))$，且不需要浮点运算。