euler project第18题求解

yinyuemi

回复 9# sequencing


    暴力解法（gawk 4.0.0）：

1. gawk '{for(i=1;i<=NF;i++)a[NR][i]=$i}
   
2. END{f(a[1][1],a[1][1],1,1);print max,cob}
   
3. function f(sum,com,x,y){
   
4. if(x==NR){print sum,com;if(max<sum){max=sum;cob=com};return -1}
   
5. else{if(a[x+1][y]>=a[x+1][y+1]){
   
6.   f(sum+a[x+1][y],com FS a[x+1][1],x+1,y)
   
7.   f(sum+a[x+1][y+1],com FS a[x+1][1],x+1,y+1)}
   
8. else{
   
9.   f(sum+a[x+1][y+1],com FS a[x+1][1],x+1,y+1)
   
10.   f(sum+a[x+1][y],com FS a[x+1][1],x+1,y)}
    
11. }
    
12. }'

复制代码

jils2013

逻辑：路由数量等于2^n个；对每个数字做2进制转化，然后藉此作左右摆动控制路由

简单修改了逻辑，打印出路由经过的数字。

1. [root@localhost shell]# cat -vte file1
   
2.                             75$
   
3.                           95  64$
   
4.                         17  47  82$
   
5.                       18  35  87  10$
   
6.                     20  04  82  47  65$
   
7.                   19  01  23  75  03  34$
   
8.                 88  02  77  73  07  63  67$
   
9.               99  65  04  28  06  16  70  92$
   
10.             41  41  26  56  83  40  80  70  33$
    
11.           41  48  72  33  47  32  37  16  94  29$
    
12.         53  71  44  65  25  43  91  52  97  51  14$
    
13.       70  11  33  28  77  73  17  78  39  68  17  57$
    
14.     91  71  52  38  17  14  91  43  58  50  27  29  48$
    
15.   63  66  04  68  89  53  67  30  73  16  69  87  40  31$
    
16. 04  62  98  27  23  09  70  98  73  93  38  53  60  04  23$
    
17. [root@localhost shell]# awk 'function binary(num){str="";while(num!=0){str=num%2str;num=int(num/2);};return sprintf("%0"bn"d",str)}
    
18.          {bn=NR;for(i=1;i<=NF;i++)ar[NR,i]=$i;}
    
19.          END{for(i=0;i<2^bn;i++)
    
20.                   {split(binary(i),bit,"");list="";
    
21.                    for(n=1;n<=bn;n++){if(n==1){r=1}else{r+=bit[n]};sum[i]+=ar[n,r];list=list" "ar[n,r]};
    
22.                    if(sum[i]>max){max=sum[i];maxlist=list}
    
23.                   }
    
24.                    print max,maxlist;
    
25.                }' file1
    
26. 1074  75 64 82 87 82 75 73 28 83 32 91 78 58 73 93   

复制代码

jils2013

yinyuemi 发表于 2012-06-12 03:57
回复 9# sequencing

能说下具体逻辑吗？我看了会，晕了

yinyuemi

回复 13# jils2013


    用递归遍历全部可能路径，每次走完一次，计算总和，并和当前的最大值比较，之后保存路径和总和

jason680

回复 1# sequencing

how about this
$ awk '{for(n=0;n++<NF;)s[NR,n]=a[NR,n]=$n}END{c[0,0]=1;for(n=NR;n>1;n--)for(t=0;++t<n;)if(s[n,t]>s[n,t+1]){c[n-1,t]=t;s[n-1,t]+=s[n,t]}else{c[n-1,t]=t+1;s[n-1,t]+=s[n,t+1]};m=0;for(n=0;n++<NR;){for(p=NR-n;p-->0;)printf "  ";for(t=0;t++<n;){if(c[n-1,m]==t)a[n,t]="\033[31m"a[n,t]"\033[0m";printf a[n,t]"  "};m=c[n-1,m];print ""}print "max="s[1,1]}' ep18




# for min   
$ awk '{for(n=0;n++<NF;)s[NR,n]=a[NR,n]=$n}END{c[0,0]=1;for(n=NR;n>1;n--)for(t=0;++t<n;)if(s[n,t]<s[n,t+1]){c[n-1,t]=t;s[n-1,t]+=s[n,t]}else{c[n-1,t]=t+1;s[n-1,t]+=s[n,t+1]};m=0;for(n=0;n++<NR;){for(p=NR-n;p-->0;)printf "  ";for(t=0;t++<n;){if(c[n-1,m]==t)a[n,t]="\033[31m"a[n,t]"\033[0m";printf a[n,t]"  "};m=c[n-1,m];print ""}print "min="s[1,1]}' ep18