找回密码
 欢迎注册
楼主: gxqcn

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

[复制链接]
发表于 2013-8-22 18:23:12 | 显示全部楼层
我的程序计算的结果是{6,37,234,1479,9355},比8楼的结果更均衡。
这个程序只对第二项以后的数进行调整,楼主可改良一下,看看是否在某些情况下,调整首项更好些。
下面是全部源代码。
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "math.h"

  4. void calc_max_min_ratio(int arr[], int len, int* pIdx_max, int* pIdx_min)
  5. {
  6.         int i,idx_max,idx_min;
  7.         double max,min;

  8.         idx_max=idx_min=0;  
  9.         min=max=(double)arr[1] / (double)arr[0];
  10.         for (i=1;i<len-1;i++)
  11.         {
  12.                 if  ( (double)arr[i+1] / (double)arr[i] > max)
  13.                 {
  14.                         max=(double)arr[i+1] / (double)arr[i];
  15.                         idx_max=i;
  16.                 }
  17.                
  18.                 if  ( (double)arr[i+1] / (double)arr[i] < min)
  19.                 {
  20.                         min=(double)arr[i+1] / (double)arr[i];
  21.                         idx_min=i;
  22.                 }
  23.         }
  24.         *pIdx_max=idx_max;
  25.         *pIdx_min=idx_min;
  26. }

  27. void split_int(int s,int n, int arr[] )
  28. {
  29.         double q0,q1;
  30.         double qMin, qMax;
  31.         int i,idx_max,idx_min,s1,s2;

  32.         q0=pow( (double)s,1.0/(double)n);
  33.         arr[0]=(int)q0;

  34.         for (i=1;i<n;i++)
  35.                 arr[i]=(int)( (double)arr[i-1] * q0);
  36.        
  37.         for (s1=0,i=0;i<n;i++)
  38.                 s1+=arr[i];

  39.         calc_max_min_ratio(arr,n,&idx_max,&idx_min);
  40.        
  41.         //printf("s1=%d\n",s1);
  42.         //printf("max ratio is %.6f\n", (double)arr[idx_max+1]/(double)arr[idx_max]);
  43.         //printf("min ratio is %.6f\n", (double)arr[idx_min+1]/(double)arr[idx_min]);

  44.         //以下迭代过程调整数组的公比
  45.         while (s1 != s)
  46.         {
  47.                 if (s1>s)  //降低公比
  48.                 {
  49.                         arr[idx_max+1]--;
  50.                         q1=(double)(arr[idx_max+1])/(double)(arr[idx_max]) ;
  51.                        
  52.                         for (i=idx_max+2;i<n;i++)
  53.                                 arr[i]=(int)( (double)arr[i-1] * q0);
  54.                 }
  55.                 else                //增加公比
  56.                 {
  57.                         arr[idx_max+1]++;
  58.                         q1= (double)(arr[idx_min+1])/(double)(arr[idx_min]);
  59.                        
  60.                         for (i=idx_min+2;i<n;i++)
  61.                                 arr[i]=(int)( (double)arr[i-1] * q0);
  62.                 }
  63.                
  64.                 calc_max_min_ratio(arr,n,&idx_max,&idx_min);
  65.                
  66.                 for (s2=0,i=0;i<n;i++)
  67.                         s2+=arr[i];
  68.                
  69.                 if (s1>s && s2<s)
  70.                         break;
  71.                 else if (s1<s && s2>s)
  72.                         break;
  73.                
  74.                 s1=s2;
  75.                 q0=q1;

  76.                 //printf("s1=%d\n",s1);
  77.                 //printf("max ratio is %.6f\n", (double)arr[idx_max+1]/(double)arr[idx_max]);
  78.                 //printf("min ratio is %.6f\n", (double)arr[idx_min+1]/(double)arr[idx_min]);
  79.         }
  80.        
  81.         if (q1<q0)
  82.         {
  83.                 double t;
  84.                 t=q0; q0=q1; q1=t;  //q0是公比期望下限, q1是公比期望上限
  85.         }

  86.         if (s2==s)
  87.                 return;
  88.         else if (s2<s)
  89.                 arr[n-1] += ( s-s2);
  90.         else
  91.                 arr[n-1] -= ( s2-s);
  92.        
  93.        
  94.         //以下迭代过程对数组各个元素进行微调
  95.         while ( 1)
  96.         {
  97.                
  98.                 double tq,d;

  99.                 tq=(q0+q1)/2;
  100.                
  101.                 calc_max_min_ratio(arr,n,&idx_max,&idx_min);
  102.                 qMin=(double)(arr[idx_min+1])/(double)(arr[idx_min]) ;
  103.                 qMax=(double)(arr[idx_max+1])/(double)(arr[idx_max]) ;
  104.                 //printf("max ratio is %.6f\n", qMax);
  105.                 //printf("min ratio is %.6f\n", qMin);

  106.                 if (qMax>q1) //某2项的比超过期望值
  107.                 {
  108.                         d= ((double)(arr[idx_max+1]) - (double)(arr[idx_max]) * tq)/(tq+1) ;
  109.                         if ( fabs(d)<0.6)
  110.                                 break;
  111.                         arr[idx_max+1] -= (int)d;
  112.                         arr[idx_max] += (int)d;
  113.                 }
  114.                 else if ( qMin<q0)        //某2项的比低于期望值
  115.                 {
  116.                         d= ( (double)(arr[idx_max]) * tq -(double)(arr[idx_max+1]))/(tq+1) ;
  117.                         if ( fabs(d)<0.6)
  118.                                 break;
  119.                         arr[idx_max+1] += (int)d;
  120.                         arr[idx_max] -= (int)d;
  121.                 }
  122.                 else
  123.                 {
  124.                         break;
  125.                 }
  126.         }

  127.         printf("array is {");
  128.         for (s1=0,i=0;i<n;i++)
  129.         {        s1+=arr[i]; printf("%d,",arr[i]); }
  130.         printf("}\nsum is %d\n",s1);
  131.        
  132.         calc_max_min_ratio(arr,n,&idx_max,&idx_min);
  133.         qMin=(double)(arr[idx_min+1])/(double)(arr[idx_min]) ;
  134.         qMax=(double)(arr[idx_max+1])/(double)(arr[idx_max]) ;
  135.         printf("max ratio is %.6f\n", qMax);
  136.         printf("min ratio is %.6f\n", qMin);
  137. }


  138. int main(int argc, char* argv[])
  139. {
  140.         int s,n;
  141.         int arr[64];

  142.         s=11111;
  143.         n=5;

  144.         split_int(s,n,arr);

  145.         return 0;
  146. }

复制代码

评分

参与人数 1威望 +9 金币 +9 鲜花 +9 收起 理由
gxqcn + 9 + 9 + 9 谢谢啊!算法蛮巧的。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-22 18:35:38 | 显示全部楼层
对某些数据,楼上的代码可导致死循环。对公比的求法需要改进。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-22 20:34:54 来自手机 | 显示全部楼层
我觉得先贪心就可以得到很不错的方案,然后搜索,利用已知结果来裁剪
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-8-23 07:36:03 | 显示全部楼层
这个问题最后采用了将最终数列直接导入的方式,
所以计算过程不再局限于整型,
甚至可人工参与编辑结果。

这样,就有一个简单朴素可行的思路:
  • 计算公比$q$:用迭代逼近解方程 ${q^{n+1}-q}/{q-1} = s$
  • 得到初始数列:依此计算 $q, q^2, q^3, ..., q^n$ 并圆整;
  • 微调数列,提高其评价值。

点评

老大,你微调的时候,是在哪些位置调的  发表于 2013-8-24 08:22
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-23 22:13:28 | 显示全部楼层
好像印象中,比是e的时候最优化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-23 22:17:19 | 显示全部楼层
理解错了,呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-24 07:02:16 | 显示全部楼层
好吧,我说下我的思路,
假设以[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取多少能囊括理想情况,并且运算量不大

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-24 07:12:02 | 显示全部楼层
对于充分大的{q}来说,我猜测,d等于1就足够了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-24 07:26:39 | 显示全部楼层
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的不足近似。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-8-24 07:40:37 | 显示全部楼层
wayne 发表于 2013-8-24 07:26
直觉告诉我,应该有方法,不需要手工来微调

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

点评

额,老痕迹被你发现了。  发表于 2013-8-24 07:42
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-7-9 05:38 , Processed in 0.039810 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表