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

gxqcn

现在这个问题我已经有比较成熟算法了，只是要用到浮点数据类型。

zeroieme

引入超前项 1之后，就变成求比例q的方程 (q^n-1)/(q-1)=(Sum(an)+1)

mathe

1，10，100，1000，10000公比变化范围不是0吗，不全是10 吗，9从哪来

mathe

而这个题还有麻烦之处在于答案可能不唯一，比如和21，n为3，可以7，7，7也可3，6，12

mathe

看到，相当于最前面添加了1，那么基本没什么选择自由了

gxqcn

{7，7，7} 的比例动态范围=7-1=6；
{3，6，12}的比例动态范围=3-2=1；
后者优于前者。

注意：$q_0=a_0$

KeyTo9_Fans

当$n=2$时，

$a_0=A000196(s)$
$a_1=A028391(s)$

其中：

$A000196(n)=\lfloor\sqrt{n}\rfloor$
https://oeis.org/A000196

$A028391(n)=n-\lfloor\sqrt{n}\rfloor$
https://oeis.org/A028391

两个数列均需要求平方根，很难避免实数运算。

当$n>2$时，在oeis里面找不到答案。

zgg___

可以用12层的公式呀，然后用二分法求根，因为根是整数，所以几次就够了。得到了公比q，各项再调整一下就ok了，呵呵。

gxqcn

关键是根不见得是整数啊，比如：把100打散成8项。

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. 
     

复制代码