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

math_humanbeing

问题是这样：我想编写一个求解形如：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两个元素的时候开始计算．

happysxyf

这个专门有套算法，需要打hash表，我只做过C语言版的，因为C语言速度快，最后生成2000M的解。别的语言我不相信能完成这种活，最后的解真的非常多。

math_humanbeing

happysxyf 发表于 2017-1-22 10:36
这个专门有套算法，需要打hash表，我只做过C语言版的，因为C语言速度快，最后生成2000M的解。别的语言我不 ...

你是怎么做的？

happysxyf

math_humanbeing 发表于 2017-1-22 10:39
你是怎么做的？

举个例子：

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

复制代码

保存需3GB硬盘空间，且保存速度由硬盘读写速度决定。如果不打印的话，只需要2秒就可以求解1亿五千万个解。仅在赛扬cpu上测试过。酷睿系列耗时不足1秒、

happysxyf

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

求解复杂度取决于你给的方程系数，如果系数特殊就一个解，如果系数是任意的，那解的数目不确，取决于gcd系数。