数学研发论坛

 找回密码
 欢迎注册
查看: 816|回复: 7

[讨论] 谁能帮我将我的算法编写函数式语言程序

[复制链接]
发表于 2017-1-21 21:28:15 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
问题是这样:我想编写一个求解形如:a1x1+a2x2+...+anxn=m多元线性丢番图方程的程序.
以下是未完成的程序
two_euclidean (a,b)=case b
              of 0-> (a,1,0)
              otherwise-> (gcd,y,x-q*y)
where r=a mod b
      q=a div b
      (gcd,x,y)=two_euclidean(b,r)
list_euclidean ::
list_euclidean (a,b)=
f []=[]
  | (x:xs)= g x $ f xs
我的想法是每次递归将列表拆成x:xs的形式,g从a,b两个元素的时候开始计算.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-1-22 10:36:56 | 显示全部楼层
这个专门有套算法,需要打hash表,我只做过C语言版的,因为C语言速度快,最后生成2000M的解。别的语言我不相信能完成这种活,最后的解真的非常多。

点评

但是你的程序我想看看,好吗?  发表于 2017-1-22 10:40
这个程序我想出点眉目了,大家就不要打断我的思路了.  发表于 2017-1-22 10:40
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-1-22 10:39:08 | 显示全部楼层
happysxyf 发表于 2017-1-22 10:36
这个专门有套算法,需要打hash表,我只做过C语言版的,因为C语言速度快,最后生成2000M的解。别的语言我不 ...

你是怎么做的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-1-22 10:49:48 | 显示全部楼层

举个例子:

试问方程1999a+1299b+1499c+2799d+2499e+3299f=2328450.在约束条件 a∈[0,607]、 b∈[0,534]、 c∈[0,60]、 d∈[0,660]、 e∈[0,100]、 f∈[0,209]下的整数解?


  1. #include <stdio.h>

  2. int main(int argc, char *argv[])
  3. {
  4.     int *m=(int*)calloc(776151, sizeof(int));
  5.     int a,b,c,d,e,f,sum,x,y,i;
  6.     for(b=0;b<=534;b++){
  7.         for(d=0;d<=660;d++){
  8.             if(sum=433*b+933*d,sum<28576){continue;}
  9.             else if(sum>776150){break;}
  10.             m[sum]=b*1000+d;
  11.         }
  12.     }
  13.     printf("求解完毕,请按任意键存为solutions.txt");
  14.     getchar();
  15.     FILE *fp=fopen("solutions.txt","w");
  16.     printf("正在保存,这需要一些时间和数GB硬盘空间!");
  17.     for(f=0;f<=209;f++){
  18.         for(c=0;c<=60;c++){
  19.             for(a=0;a<=607;a++){
  20.                 if((1999*a+1499*c+3299*f)%3!=0){continue;}
  21.                 for(e=0;e<=100;e++){
  22.                     if(sum=776150-833*e-(1999*a+1499*c+3299*f)/3,(sum<28576)||(m[sum]==0)){continue;}
  23.                     else if(sum>776150){break;}
  24.                     x=m[sum]/1000,y=m[sum]%1000;
  25.                     /*由于给出的b的取值x最大才534,因此连while循环也省了。
  26.                     while(x>0)
  27.                     {
  28.                         fprintf(fp,"%d,%d,%d,%d,%d,%d\n",a,x,c,y,e,f);
  29.                         x-=933,y+=433;i++;
  30.                     }
  31.                     */
  32.                     fprintf(fp,"%d,%d,%d,%d,%d,%d\n",a,x,c,y,e,f);
  33.                 }
  34.             }
  35.         }
  36.     }
  37.     fclose(fp);
  38.     return 0;
  39. }
复制代码

保存需3GB硬盘空间,且保存速度由硬盘读写速度决定。如果不打印的话,只需要2秒就可以求解1亿五千万个解。仅在赛扬cpu上测试过。酷睿系列耗时不足1秒、
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-1-22 10:53:52 | 显示全部楼层
本帖最后由 happysxyf 于 2017-1-22 11:00 编辑

目前编程还是用hash打表法最快。当未知数数量太多时,系数太大时,递归次数接近数亿时,就得改用新的压缩存储技术。因为这时的全部解可以达到数千GB的硬盘。一般电脑装不下。

求解复杂度取决于你给的方程系数,如果系数特殊就一个解,如果系数是任意的,那解的数目不确,取决于gcd系数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-8-18 09:16 , Processed in 0.063633 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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