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

liangbch

对某些数据，楼上的代码可导致死循环。对公比的求法需要改进。

mathe

我觉得先贪心就可以得到很不错的方案，然后搜索，利用已知结果来裁剪

gxqcn

这个问题最后采用了将最终数列直接导入的方式，
所以计算过程不再局限于整型，
甚至可人工参与编辑结果。

这样，就有一个简单朴素可行的思路：

• 计算公比$q$：用迭代逼近解方程 ${q^{n+1}-q}/{q-1} = s$
• 得到初始数列：依此计算 $q, q^2, q^3, ..., q^n$ 并圆整；
• 微调数列，提高其评价值。
  

无心人

好像印象中，比是e的时候最优化

无心人

理解错了，呵呵

无心人

好吧，我说下我的思路，
假设以[x]表示截断形式的求整，{x}表示四舍五入形式的求整
显然{x}更适合本题

按照幂和形式求出小数形式的q， 这个gxqcn已经给出方程
然后求出
a0 = {q}, a1={q^2}, ...., ai={q^(i+1)}

现在作图
把相邻数字的比作为y轴，而序号作为x轴的话，在理想情况下，点应该是在一条直线上
但是由于取整的关系，只有q为整数时，才有这种可能
于是，现实情况，点偏离了直线，有的在直线上方，有的在下方

1、我们需要尽可能的修正，使得点偏离的区域在y轴上的投影最小，这就是gxqcn的目的

2、考虑其实这种方法求出的整数，由于偏移，其和并不是等于s的，因此也有个修正过程

考虑如下算法，

假设原始序列和为sq
对序列中的每个整数，都加上一个绝对值不大于d的偏移量，即[-d, d]中包含的整数，可以是0
偏移量的和为sd，显然sq + sd 必须等于s
以偏移量为变量，可以写成多元一次方程
结合满足题目条件的方程，我们得到一个能穷举搜索的n元方程组

现在问题是d取多少能囊括理想情况，并且运算量不大

无心人

对于充分大的{q}来说，我猜测，d等于1就足够了

wayne

gxqcn 发表于 2013-8-23 07:36
这个问题最后采用了将最终数列直接导入的方式，
所以计算过程不再局限于整型，
甚至可人工参与编辑结果。 ...

第三步微调是否可以用算法实现，代替手工？
===
$q_n ={q^{n+1}}/{q^n}$
所以最大的$q_i$应该发生在 后项是q^n的过剩近似，前项是q^n的不足近似。
最小的$q_i$发生在 前项是q^n的过剩近似，后项是q^n的不足近似。

无心人

wayne 发表于 2013-8-24 07:26
直觉告诉我，应该有方法，不需要手工来微调

现在我在考虑是否能求出这个问题的上下界来

wayne

貌似分析q_min,q_max的发生位置对最终结果没啥帮助。

===============
不过，微调的时候，应该将多余的配额(圆整数列之和与s之差)分配给数值大的项。
(因为圆整之后的数列之和与s之差不会大于n，而n基本上远小于s，远小于圆整数列的最后两项)

所以，第三步的微调有算法了：
根据23楼 步骤二，得到各项的圆整值之后。
计算多余的配额，即 d =s - 圆整数列所有项的和。

然后将d统统分配给 圆整数列的最后两项(或者若干项？)

设圆整数列的最后两项为A，B，分给的配额分别为x,d-x，则需要解一个方程：${B+d-x}/{A+x} = q$
解得x，取圆整 即可