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

liangbch

我的程序计算的结果是{6,37,234,1479,9355}，比8楼的结果更均衡。
这个程序只对第二项以后的数进行调整，楼主可改良一下，看看是否在某些情况下，调整首项更好些。
下面是全部源代码。

1. #include "stdio.h"
   
2. #include "stdlib.h"
   
3. #include "math.h"
   
4. 
   
5. void calc_max_min_ratio(int arr[], int len, int* pIdx_max, int* pIdx_min)
   
6. {
   
7.         int i,idx_max,idx_min;
   
8.         double max,min;
   
9. 
   
10.         idx_max=idx_min=0;  
    
11.         min=max=(double)arr[1] / (double)arr[0];
    
12.         for (i=1;i<len-1;i++)
    
13.         {
    
14.                 if  ( (double)arr[i+1] / (double)arr[i] > max)
    
15.                 {
    
16.                         max=(double)arr[i+1] / (double)arr[i];
    
17.                         idx_max=i;
    
18.                 }
    
19.                
    
20.                 if  ( (double)arr[i+1] / (double)arr[i] < min)
    
21.                 {
    
22.                         min=(double)arr[i+1] / (double)arr[i];
    
23.                         idx_min=i;
    
24.                 }
    
25.         }
    
26.         *pIdx_max=idx_max;
    
27.         *pIdx_min=idx_min;
    
28. }
    
29. 
    
30. void split_int(int s,int n, int arr[] )
    
31. {
    
32.         double q0,q1;
    
33.         double qMin, qMax;
    
34.         int i,idx_max,idx_min,s1,s2;
    
35. 
    
36.         q0=pow( (double)s,1.0/(double)n);
    
37.         arr[0]=(int)q0;
    
38. 
    
39.         for (i=1;i<n;i++)
    
40.                 arr[i]=(int)( (double)arr[i-1] * q0);
    
41.        
    
42.         for (s1=0,i=0;i<n;i++)
    
43.                 s1+=arr[i];
    
44. 
    
45.         calc_max_min_ratio(arr,n,&idx_max,&idx_min);
    
46.        
    
47.         //printf("s1=%d\n",s1);
    
48.         //printf("max ratio is %.6f\n", (double)arr[idx_max+1]/(double)arr[idx_max]);
    
49.         //printf("min ratio is %.6f\n", (double)arr[idx_min+1]/(double)arr[idx_min]);
    
50. 
    
51.         //以下迭代过程调整数组的公比
    
52.         while (s1 != s)
    
53.         {
    
54.                 if (s1>s)  //降低公比
    
55.                 {
    
56.                         arr[idx_max+1]--;
    
57.                         q1=(double)(arr[idx_max+1])/(double)(arr[idx_max]) ;
    
58.                        
    
59.                         for (i=idx_max+2;i<n;i++)
    
60.                                 arr[i]=(int)( (double)arr[i-1] * q0);
    
61.                 }
    
62.                 else                //增加公比
    
63.                 {
    
64.                         arr[idx_max+1]++;
    
65.                         q1= (double)(arr[idx_min+1])/(double)(arr[idx_min]);
    
66.                        
    
67.                         for (i=idx_min+2;i<n;i++)
    
68.                                 arr[i]=(int)( (double)arr[i-1] * q0);
    
69.                 }
    
70.                
    
71.                 calc_max_min_ratio(arr,n,&idx_max,&idx_min);
    
72.                
    
73.                 for (s2=0,i=0;i<n;i++)
    
74.                         s2+=arr[i];
    
75.                
    
76.                 if (s1>s && s2<s)
    
77.                         break;
    
78.                 else if (s1<s && s2>s)
    
79.                         break;
    
80.                
    
81.                 s1=s2;
    
82.                 q0=q1;
    
83. 
    
84.                 //printf("s1=%d\n",s1);
    
85.                 //printf("max ratio is %.6f\n", (double)arr[idx_max+1]/(double)arr[idx_max]);
    
86.                 //printf("min ratio is %.6f\n", (double)arr[idx_min+1]/(double)arr[idx_min]);
    
87.         }
    
88.        
    
89.         if (q1<q0)
    
90.         {
    
91.                 double t;
    
92.                 t=q0; q0=q1; q1=t;  //q0是公比期望下限， q1是公比期望上限
    
93.         }
    
94. 
    
95.         if (s2==s)
    
96.                 return;
    
97.         else if (s2<s)
    
98.                 arr[n-1] += ( s-s2);
    
99.         else
    
100.                 arr[n-1] -= ( s2-s);
     
101.        
     
102.        
     
103.         //以下迭代过程对数组各个元素进行微调
     
104.         while ( 1)
     
105.         {
     
106.                
     
107.                 double tq,d;
     
108. 
     
109.                 tq=(q0+q1)/2;
     
110.                
     
111.                 calc_max_min_ratio(arr,n,&idx_max,&idx_min);
     
112.                 qMin=(double)(arr[idx_min+1])/(double)(arr[idx_min]) ;
     
113.                 qMax=(double)(arr[idx_max+1])/(double)(arr[idx_max]) ;
     
114.                 //printf("max ratio is %.6f\n", qMax);
     
115.                 //printf("min ratio is %.6f\n", qMin);
     
116. 
     
117.                 if (qMax>q1) //某2项的比超过期望值
     
118.                 {
     
119.                         d= ((double)(arr[idx_max+1]) - (double)(arr[idx_max]) * tq)/(tq+1) ;
     
120.                         if ( fabs(d)<0.6)
     
121.                                 break;
     
122.                         arr[idx_max+1] -= (int)d;
     
123.                         arr[idx_max] += (int)d;
     
124.                 }
     
125.                 else if ( qMin<q0)        //某2项的比低于期望值
     
126.                 {
     
127.                         d= ( (double)(arr[idx_max]) * tq -(double)(arr[idx_max+1]))/(tq+1) ;
     
128.                         if ( fabs(d)<0.6)
     
129.                                 break;
     
130.                         arr[idx_max+1] += (int)d;
     
131.                         arr[idx_max] -= (int)d;
     
132.                 }
     
133.                 else
     
134.                 {
     
135.                         break;
     
136.                 }
     
137.         }
     
138. 
     
139.         printf("array is {");
     
140.         for (s1=0,i=0;i<n;i++)
     
141.         {        s1+=arr[i]; printf("%d,",arr[i]); }
     
142.         printf("}\nsum is %d\n",s1);
     
143.        
     
144.         calc_max_min_ratio(arr,n,&idx_max,&idx_min);
     
145.         qMin=(double)(arr[idx_min+1])/(double)(arr[idx_min]) ;
     
146.         qMax=(double)(arr[idx_max+1])/(double)(arr[idx_max]) ;
     
147.         printf("max ratio is %.6f\n", qMax);
     
148.         printf("min ratio is %.6f\n", qMin);
     
149. }
     
150. 
     
151. 
     
152. int main(int argc, char* argv[])
     
153. {
     
154.         int s,n;
     
155.         int arr[64];
     
156. 
     
157.         s=11111;
     
158.         n=5;
     
159. 
     
160.         split_int(s,n,arr);
     
161. 
     
162.         return 0;
     
163. }
     
164. 
     

复制代码

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
直觉告诉我，应该有方法，不需要手工来微调

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