求教用awk怎樣湊數(shù)字

54nwq

1. 1:  95.09+88+80.26+7.22+4.75
   
2. 2:  95.09+78.01+43.11+34.83+12.29+7.22+4.77
   
3. 3:  95.09+68.87+54.77+28.17+12.9+12.29+3.23
   
4. 4:  95.09+68.87+38.59+34.83+12.9+12.29+4.77+4.75+3.23
   
5. 5:  95.09+66.61+54.99+43.11+12.29+3.23
   
6. 6:  95.09+54.99+54.77+34.83+12.9+12.29+7.22+3.23
   
7. 7:  88+78.01+56.27+28.17+12.9+7.22+4.75
   
8. 8:  88+77.26+56.27+38.59+7.22+4.75+3.23
   
9. 9:  88+68.87+54.99+38.59+12.9+7.22+4.75
   
10. 10:  88+64.04+56.27+38.59+12.9+12.29+3.23
    
11. 11:  88+56.27+54.77+43.11+12.9+12.29+4.75+3.23
    
12. 12:  88+56.27+54.77+38.59+28.17+4.77+4.75
    
13. 13:  83.95+80.26+43.11+34.83+12.9+12.29+4.75+3.23
    
14. 14:  83.95+80.26+38.59+34.83+28.17+4.77+4.75
    
15. 15:  83.95+77.26+43.11+38.59+12.9+12.29+7.22
    
16. 16:  83.95+77.26+43.11+34.83+28.17+4.77+3.23
    
17. 17:  83.95+68.87+56.27+34.83+28.17+3.23
    
18. 18:  83.95+66.61+54.77+38.59+28.17+3.23
    
19. 19:  80.26+78.01+56.27+43.11+12.9+4.77
    
20. 20:  80.26+64.04+54.99+43.11+28.17+4.75
    
21. 21:  80.26+56.27+54.99+54.77+12.29+7.22+4.77+4.75
    
22. 22:  80.26+56.27+54.99+38.59+28.17+12.29+4.75
    
23. 23:  79.08+78.01+54.77+38.59+12.9+7.22+4.75
    
24. 24:  79.08+77.26+54.99+43.11+12.9+4.75+3.23
    
25. 25:  79.08+68.87+66.61+43.11+12.9+4.75
    
26. 26:  79.08+64.04+54.99+38.59+28.17+7.22+3.23
    
27. 27:  79.08+54.99+54.77+43.11+28.17+7.22+4.75+3.23
    
28. 28:  78.01+77.26+64.04+43.11+12.9
    
29. 29:  78.01+77.26+56.27+38.59+12.9+12.29
    
30. 30:  78.01+68.87+54.99+34.83+28.17+7.22+3.23
    
31. 31:  78.01+64.04+54.77+43.11+28.17+7.22
    
32. 32:  78.01+64.04+43.11+38.59+34.83+7.22+4.77+4.75
    
33. 33:  78.01+56.27+54.77+38.59+28.17+12.29+7.22
    
34. 34:  77.26+64.04+54.99+54.77+12.29+7.22+4.75
    
35. 35:  77.26+56.27+54.99+43.11+28.17+12.29+3.23
    
36. 36:  77.26+54.77+43.11+34.83+28.17+12.9+12.29+7.22+4.77
    
37. 37:  68.87+66.61+56.27+43.11+28.17+12.29
    
38. 38:  68.87+64.04+54.77+38.59+28.17+12.9+4.75+3.23
    
39. 39:  68.87+56.27+54.77+34.83+28.17+12.9+12.29+7.22
    
40. 40:  66.61+64.04+54.99+43.11+38.59+4.75+3.23
    
41. 41:  66.61+56.27+54.99+43.11+34.83+12.29+7.22
    
42. 42:  64.04+54.99+54.77+38.59+34.83+12.9+7.22+4.75+3.23

復(fù)制代碼

bikkuri

把這些數(shù)排序以后可以發(fā)現(xiàn)最小的十一個(gè)數(shù)的和已經(jīng)大于275.32了，而最大的兩個(gè)數(shù)的和還小于275.32。
所以如何一個(gè)符合條件的組合，即和等于275.32的組合，一定由3-10個(gè)數(shù)組成。
少于3個(gè)數(shù)或者超過10個(gè)數(shù)的組合就不用窮舉了，可以直接排除。

zsszss0000

漂亮，這樣可以一下子消除好多根本就不可能的選擇，提高了效率。回復(fù) 22# bikkuri


   

jason680

回復(fù) 16# reyleon

It's floating number(Floating-Point Arithmetic) issue
http://zh.wikipedia.org/zh-cn/IEEE_754

There is no issue for integer number

$ time awk -vv=275.32 'function x(v,s,c,t,p,y){if(t>v)return;if(s-c>1)while(++p<=NR-s+c)x(v,s,c+1,t+a[p],p,y a[p]"("p")+");else{if(t+max<v||v<t+min)return;while(++p<=NR){if(v==t+a[p]){cnt++;print v"="y a[p]"("p")"}}}}{$1*=100;a[NR]=$1;N=NR;if(NR==1)max=min=$1;if(max<$1)max=$1;if(min>$1)min=$1;printf $1"("NR"), "}END{v*=100;print "\nv="v", max="max", min="min;for(n=1;n<=NR;n++)x(v,n);print "got total:"cnt}' FILE
4311(1), 5627(2), 8800(3), 722(4), 477(5), 3859(6), 9509(7), 6404(8), 6661(9), 5499(10), 5477(11), 3483(12), 323(13), 475(14), 8026(15), 1290(16), 7726(17), 2817(18), 7801(19), 6887(20), 8395(21), 1229(22), 7908(23),
v=27532, max=9509, min=323
27532=4311(1)+6404(8)+1290(16)+7726(17)+7801(19)
...
27532=477(5)+3859(6)+9509(7)+3483(12)+323(13)+475(14)+1290(16)+6887(20)+1229(22)
got total:42

real        0m2.960s
user        0m1.544s
sys        0m0.096s


It can be solved with small error

$ time awk -vv=275.32 'function abs(x){return(x>0?x:-x)}function x(v,s,c,t,p,y){if(t>v)return;if(s-c>1)while(++p<=NR-s+c)x(v,s,c+1,t+a[p],p,y a[p]"("p")+");else{if(t+max<v||v<t+min)return;while(++p<=NR){if(abs(v-t-a[p])<10^-6){cnt++;print v"="y a[p]"("p")"}}}}{a[NR]=$1;N=NR;if(NR==1)max=min=$1;if(max<$1)max=$1;if(min>$1)min=$1;printf $1"("NR"), "}END{print "\nmax="max", min="min;for(n=1;n<=NR;n++)x(v,n);print "got total:"cnt}' FILE
43.11(1), 56.27(2), 88(3), 7.22(4), 4.77(5), 38.59(6), 95.09(7), 64.04(8), 66.61(9), 54.99(10), 54.77(11), 34.83(12), 3.23(13), 4.75(14), 80.26(15), 12.9(16), 77.26(17), 28.17(18), 78.01(19), 68.87(20), 83.95(21), 12.29(22), 79.08(23),
max=95.09, min=3.23
275.32=43.11(1)+64.04(8)+12.9(16)+77.26(17)+78.01(19)
...
275.32=4.77(5)+38.59(6)+95.09(7)+34.83(12)+3.23(13)+4.75(14)+12.9(16)+68.87(20)+12.29(22)
got total:42

real    0m3.440s
user    0m1.780s
sys    0m0.108s

reyleon

回復(fù) 24# jason680


    對(duì)你的敬仰猶如滔滔井水連綿不絕又如黃河泛濫一發(fā)不可收拾

reyleon

回復(fù) 24# jason680


    有人想問你, 你的職業(yè)是與 IT 相關(guān)的么?

54nwq

回復(fù) 25# reyleon

確實(shí)是大牛啊，佩服，我理解不了

zsszss0000

估計(jì)可能不相關(guān)，不然怎么這么牛逼呢？回復(fù) 26# reyleon


   

刺客阿地

很好奇，坐等jason680大神分享職業(yè)。。

刺客阿地

很好奇，坐等jason680大神分享職業(yè)。。