免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › Shell › 数字相加情况。
1234567下一页
最近访问板块 发新帖
楼主: zhkun
打印 上一主题 下一主题

数字相加情况。  关闭 [复制链接]

lightspeed

论坛徽章:
0
51楼 [报告]
发表于 2004-10-04 03:56 |只看该作者

数字相加情况。

重新修改了程序以符合本坛的宗旨： 无论算法深浅，只求语句巧妙。
另外还加了 bash 的版本。

KSH:

  2. #!/bin/ksh

  4. typeset -r MAX=150
  5. typeset -r MIN=100
  6. set -A data $(cat $1 | sort -n)

  8. getall () {
  9. typeset i=$3
  10. while [ $i -ge 0 ]
  11. do
  12.        typeset sum=$2
  13.        typeset list=$1${1:+' + '}${data[$i]}
  14.        sum=$(( sum + data[$i] ))
  15.         if [ $sum -le $MAX ]; then
  16.                 if [ $sum -ge $MIN ]; then
  17.                         echo $list" = "$sum
  18.                 fi

  20.                    ( getall "$list" $sum $((i - 1)) )
  21.         fi

  23. (( i -- ))
  24. done
  25. }

  27. getall "" 0 $(( ${#data[*]} - 1 ))

复制代码



BASH:

  2. #!/bin/bash

  4. MAX=150
  5. MIN=100
  6. data=($(cat $1 | sort -n))

  8. getall () {
  9. local i=$3
  10. while [ $i -ge 0 ]
  11. do
  12.         local sum=$2
  13.         local list=$1${1:+' + '}${data[$i]}
  14.         sum=$(( sum + data[$i] ))
  15.         if [ $sum -le $MAX ]; then
  16.                 if [ $sum -ge $MIN ]; then
  17.                         echo $list" = "$sum
  18.                 fi

  20.                     getall "$list" $sum $((i - 1))
  21.         fi

  23. (( i -= 1 ))
  24. done
  25. }

  27. getall "" 0 $(( ${#data[*]} - 1 ))


复制代码
[/quote]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
zhkun

论坛徽章:
0
52楼 [报告]
发表于 2004-10-04 11:00 |只看该作者

数字相加情况。

我想若将条件修改一下，大家看看这样行不行。
设置最大值，每个数字只能相加一次，不设置最小值，求最少加式（可以把没有相加的数字放到最后一组中）。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
落草为寇

论坛徽章:
0
53楼 [报告]
发表于 2004-10-05 13:24 |只看该作者

数字相加情况。

9494
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
寂寞烈火

论坛徽章:
1
荣誉会员 日期:2011-11-23 16:44:17
54楼 [报告]
发表于 2004-10-05 15:41 |只看该作者

数字相加情况。

强!
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
zhkun

论坛徽章:
0
55楼 [报告]
发表于 2004-10-05 20:42 |只看该作者

数字相加情况。

请各位高手显伸手！！！
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
lightspeed

论坛徽章:
0
56楼 [报告]
发表于 2004-10-06 04:04 |只看该作者

数字相加情况。

原帖由 "zhkun" 发表：
我想若将条件修改一下，大家看看这样行不行。
设置最大值，每个数字只能相加一次，不设置最小值，求最少加式（可以把没有相加的数字放到最后一组中）。


此题有点问题。 如我前面所讲， 无唯一解，所有我全列出了结果。
这次用 perl. 另外， 修改 $MINLEN, 可限制最少加项的数目。


  2. #!/bin/perl

  4. $MAX=150;
  5. $MINLEN=1;
  6. $min=9;

  8. open DATA, "<$ARGV[0]" or die "Can't open $ARGV[0]: $!";
  9. while (<DATA>) {
  10. chomp;
  11. @data=(@data, $_);
  12. }
  13. @data=sort { $a <=> $b } @data;

  15. sub getall {
  16. my $i=$_[2];
  17. for ( $i; $i >= 0; $i -- ) {
  18.         my $sum=$_[1];
  19.         my $list="$_[0]" . ($_[0] ? " + " : "") . "$data[$i]";
  20.         $sum += $data[$i];
  21.         if ( $sum <= $MAX ) {
  22.                 my $list1 = $list . " = " . $sum ;
  23.                 @str=split /\D+/, $list;
  24.                 $len=$#str + 1;
  25.                 if ( $len <= $min && $len >= $MINLEN ) {
  26.                  $min = $len;
  27.                     $store{$list1}=$len;
  28.                  @used=(@used, split /\s+/, $list);
  29.                 }
  30.         }
  31.                       &getall( $list, $sum, $i - 1);
  32. }
  33. }

  35. &getall( "", 0, $#data) ;

  37. foreach $key ( sort { $a <=> $b} keys %store ) {
  38.         print "$key\n";
  39. }

  41. print "\nUnused number\n\n";
  42. foreach (@used) {
  43. $u{$_}=$_;
  44. }
  45. for ( $i=0; $i <= $#data; $i++ ) {
  46.   print "$data[$i]\n" if ( ! exists $u{$data[$i]} );
  47. }

复制代码


  2. $MINLEN=1 时的结果：

  4. # ./1  data

  6. 1 = 1
  7. 2 = 2
  8. 3 = 3
  9. 4 = 4
  10. 12 = 12
  11. 24 = 24
  12. 32 = 32
  13. 45 = 45
  14. 53 = 53
  15. 97 = 97
  16. 100 = 100
  17. 145 = 145
  18. 150 = 150

  20. Unused number

  22. 170

复制代码


  2. $MINLEN=4 时的结果：

  4. # ./1  data

  6. 4 + 3 + 2 + 1 = 10
  7. 12 + 3 + 2 + 1 = 18
  8. 12 + 4 + 2 + 1 = 19
  9. 12 + 4 + 3 + 1 = 20
  10. 12 + 4 + 3 + 2 = 21
  11. 24 + 3 + 2 + 1 = 30
  12. 24 + 12 + 2 + 1 = 39
  13. 24 + 12 + 3 + 2 = 41
  14. 24 + 4 + 3 + 1 = 32
  15. 24 + 12 + 4 + 2 = 42
  16. 24 + 12 + 3 + 1 = 40
  17. 24 + 12 + 4 + 1 = 41
  18. 24 + 4 + 2 + 1 = 31
  19. 24 + 12 + 4 + 3 = 43
  20. 24 + 4 + 3 + 2 = 33
  21. 32 + 24 + 4 + 2 = 62
  22. 32 + 4 + 3 + 2 = 41
  23. 32 + 4 + 3 + 1 = 40
  24. 32 + 3 + 2 + 1 = 38
  25. 32 + 12 + 3 + 2 = 49
  26. 32 + 12 + 4 + 2 = 50
  27. 32 + 12 + 2 + 1 = 47
  28. 32 + 24 + 12 + 1 = 69
  29. 32 + 24 + 4 + 3 = 63
  30. 32 + 24 + 3 + 2 = 61
  31. 32 + 24 + 12 + 2 = 70
  32. 32 + 12 + 3 + 1 = 48
  33. 32 + 24 + 4 + 1 = 61
  34. 32 + 12 + 4 + 1 = 49
  35. 32 + 4 + 2 + 1 = 39
  36. 32 + 24 + 12 + 4 = 72
  37. 32 + 12 + 4 + 3 = 51
  38. 32 + 24 + 12 + 3 = 71
  39. 32 + 24 + 3 + 1 = 60
  40. 32 + 24 + 2 + 1 = 59
  41. 45 + 24 + 4 + 1 = 74
  42. 45 + 24 + 3 + 1 = 73
  43. 45 + 12 + 2 + 1 = 60
  44. 45 + 4 + 3 + 2 = 54
  45. 45 + 24 + 4 + 3 = 76
  46. 45 + 32 + 12 + 1 = 90
  47. 45 + 12 + 3 + 2 = 62
  48. 45 + 24 + 12 + 4 = 85
  49. 45 + 32 + 12 + 3 = 92
  50. 45 + 4 + 2 + 1 = 52
  51. 45 + 12 + 4 + 2 = 63
  52. 45 + 32 + 24 + 3 = 104
  53. 45 + 4 + 3 + 1 = 53
  54. 45 + 12 + 4 + 3 = 64
  55. 45 + 24 + 12 + 2 = 83
  56. 45 + 3 + 2 + 1 = 51
  57. 45 + 24 + 3 + 2 = 74
  58. 45 + 32 + 24 + 2 = 103
  59. 45 + 32 + 24 + 12 = 113
  60. 45 + 24 + 2 + 1 = 72
  61. 45 + 32 + 4 + 3 = 84
  62. 45 + 12 + 3 + 1 = 61
  63. 45 + 12 + 4 + 1 = 62
  64. 45 + 32 + 3 + 1 = 81
  65. 45 + 24 + 12 + 1 = 82
  66. 45 + 32 + 24 + 4 = 105
  67. 45 + 32 + 24 + 1 = 102
  68. 45 + 24 + 12 + 3 = 84
  69. 45 + 32 + 3 + 2 = 82
  70. 45 + 32 + 12 + 2 = 91
  71. 45 + 24 + 4 + 2 = 75
  72. 45 + 32 + 4 + 1 = 82
  73. 45 + 32 + 12 + 4 = 93
  74. 45 + 32 + 2 + 1 = 80
  75. 45 + 32 + 4 + 2 = 83
  76. 53 + 45 + 24 + 2 = 124
  77. 53 + 24 + 12 + 3 = 92
  78. 53 + 32 + 2 + 1 = 88
  79. 53 + 45 + 24 + 3 = 125
  80. 53 + 32 + 12 + 3 = 100
  81. 53 + 32 + 4 + 2 = 91
  82. 53 + 45 + 32 + 2 = 132
  83. 53 + 45 + 4 + 2 = 104
  84. 53 + 12 + 2 + 1 = 68
  85. 53 + 32 + 24 + 4 = 113
  86. 53 + 4 + 3 + 2 = 62
  87. 53 + 32 + 12 + 4 = 101
  88. 53 + 32 + 3 + 1 = 89
  89. 53 + 45 + 4 + 3 = 105
  90. 53 + 32 + 12 + 2 = 99
  91. 53 + 12 + 3 + 2 = 70
  92. 53 + 12 + 4 + 2 = 71
  93. 53 + 45 + 3 + 1 = 102
  94. 53 + 32 + 24 + 2 = 111
  95. 53 + 32 + 24 + 1 = 110
  96. 53 + 45 + 12 + 4 = 114
  97. 53 + 45 + 12 + 2 = 112
  98. 53 + 45 + 12 + 1 = 111
  99. 53 + 32 + 4 + 3 = 92
  100. 53 + 45 + 3 + 2 = 103
  101. 53 + 45 + 4 + 1 = 103
  102. 53 + 4 + 3 + 1 = 61
  103. 53 + 24 + 4 + 3 = 84
  104. 53 + 24 + 12 + 4 = 93
  105. 53 + 12 + 3 + 1 = 69
  106. 53 + 45 + 32 + 3 = 133
  107. 53 + 45 + 32 + 4 = 134
  108. 53 + 32 + 4 + 1 = 90
  109. 53 + 12 + 4 + 3 = 72
  110. 53 + 24 + 12 + 1 = 90
  111. 53 + 3 + 2 + 1 = 59
  112. 53 + 24 + 4 + 1 = 82
  113. 53 + 32 + 12 + 1 = 98
  114. 53 + 32 + 3 + 2 = 90
  115. 53 + 24 + 3 + 2 = 82
  116. 53 + 45 + 32 + 1 = 131
  117. 53 + 24 + 12 + 2 = 91
  118. 53 + 24 + 4 + 2 = 83
  119. 53 + 12 + 4 + 1 = 70
  120. 53 + 24 + 2 + 1 = 80
  121. 53 + 32 + 24 + 3 = 112
  122. 53 + 45 + 24 + 1 = 123
  123. 53 + 45 + 24 + 4 = 126
  124. 53 + 45 + 2 + 1 = 101
  125. 53 + 24 + 3 + 1 = 81
  126. 53 + 45 + 32 + 12 = 142
  127. 53 + 4 + 2 + 1 = 60
  128. 53 + 32 + 24 + 12 = 121
  129. 53 + 45 + 12 + 3 = 113
  130. 53 + 45 + 24 + 12 = 134
  131. 97 + 12 + 4 + 3 = 116
  132. 97 + 24 + 3 + 1 = 125
  133. 97 + 45 + 4 + 1 = 147
  134. 97 + 32 + 12 + 2 = 143
  135. 97 + 32 + 4 + 3 = 136
  136. 97 + 32 + 2 + 1 = 132
  137. 97 + 32 + 12 + 4 = 145
  138. 97 + 24 + 4 + 1 = 126
  139. 97 + 4 + 3 + 1 = 105
  140. 97 + 32 + 3 + 2 = 134
  141. 97 + 32 + 12 + 3 = 144
  142. 97 + 4 + 3 + 2 = 106
  143. 97 + 45 + 4 + 3 = 149
  144. 97 + 32 + 4 + 2 = 135
  145. 97 + 12 + 3 + 2 = 114
  146. 97 + 45 + 2 + 1 = 145
  147. 97 + 12 + 3 + 1 = 113
  148. 97 + 12 + 4 + 1 = 114
  149. 97 + 45 + 3 + 2 = 147
  150. 97 + 24 + 12 + 1 = 134
  151. 97 + 24 + 12 + 2 = 135
  152. 97 + 45 + 4 + 2 = 148
  153. 97 + 3 + 2 + 1 = 103
  154. 97 + 24 + 3 + 2 = 126
  155. 97 + 45 + 3 + 1 = 146
  156. 97 + 24 + 12 + 3 = 136
  157. 97 + 12 + 2 + 1 = 112
  158. 97 + 24 + 2 + 1 = 124
  159. 97 + 32 + 12 + 1 = 142
  160. 97 + 24 + 4 + 2 = 127
  161. 97 + 24 + 4 + 3 = 128
  162. 97 + 12 + 4 + 2 = 115
  163. 97 + 32 + 3 + 1 = 133
  164. 97 + 4 + 2 + 1 = 104
  165. 97 + 24 + 12 + 4 = 137
  166. 97 + 32 + 4 + 1 = 134
  167. 100 + 32 + 4 + 1 = 137
  168. 100 + 45 + 4 + 1 = 150
  169. 100 + 3 + 2 + 1 = 106
  170. 100 + 12 + 3 + 1 = 116
  171. 100 + 32 + 3 + 1 = 136
  172. 100 + 32 + 12 + 2 = 146
  173. 100 + 32 + 12 + 1 = 145
  174. 100 + 32 + 4 + 3 = 139
  175. 100 + 4 + 2 + 1 = 107
  176. 100 + 45 + 2 + 1 = 148
  177. 100 + 45 + 3 + 2 = 150
  178. 100 + 4 + 3 + 2 = 109
  179. 100 + 12 + 2 + 1 = 115
  180. 100 + 4 + 3 + 1 = 108
  181. 100 + 12 + 4 + 3 = 119
  182. 100 + 24 + 4 + 3 = 131
  183. 100 + 32 + 2 + 1 = 135
  184. 100 + 32 + 12 + 3 = 147
  185. 100 + 24 + 12 + 3 = 139
  186. 100 + 45 + 3 + 1 = 149
  187. 100 + 12 + 4 + 2 = 118
  188. 100 + 24 + 3 + 1 = 128
  189. 100 + 12 + 4 + 1 = 117
  190. 100 + 24 + 4 + 1 = 129
  191. 100 + 24 + 2 + 1 = 127
  192. 100 + 24 + 12 + 4 = 140
  193. 100 + 24 + 3 + 2 = 129
  194. 100 + 24 + 12 + 1 = 137
  195. 100 + 12 + 3 + 2 = 117
  196. 100 + 24 + 4 + 2 = 130
  197. 100 + 24 + 12 + 2 = 138
  198. 100 + 32 + 12 + 4 = 148
  199. 100 + 32 + 3 + 2 = 137
  200. 100 + 32 + 4 + 2 = 138

  202. Unused number

  204. 145
  205. 150
  206. 170


复制代码
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
wzk

论坛徽章:
0
57楼 [报告]
发表于 2004-10-06 10:43 |只看该作者

数字相加情况。

真的不错!!!,谢谢lightspeed
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
xchen301

论坛徽章:
0
58楼 [报告]
发表于 2004-10-06 20:20 |只看该作者

数字相加情况。

俩字，高手！
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
zhkun

论坛徽章:
0
59楼 [报告]
发表于 2004-10-09 11:28 |只看该作者

数字相加情况。

请大家继续！
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
lightspeed

论坛徽章:
0
60楼 [报告]
发表于 2004-10-10 13:22 |只看该作者

数字相加情况。

用一种算法最后解决了找出一组最少算式的问题。 由于楼主要求 ksh,  使工作
难于展开。ksh 中对数组的 size 限制，不得不用临时文件， 这样速度慢了，
但可处理大的数据文件。 有可能的话，还是用 perl 好。


  2. #!/bin/ksh

  4. typeset -r MAX=150
  5. TMP=.mytmp
  6. if [ -e $TMP ]; then
  7. rm -rf $TMP
  8. fi
  9. mkdir $TMP


  12. set -A data $(cat $1 | sort -n)

  14. getall () {
  15. typeset i=$1
  16. shift
  17. typeset sumsum=$1
  18. shift
  19. while [ $i -ge 0 ]
  20. do
  21.         typeset sum=$sumsum
  22.         typeset list
  23.         set -A list
  24.         list=($* "a${i}a")
  25.         sum=$(( sum + data[$i] ))
  26.         if [ $sum -le $MAX ]; then
  27.                 echo $sum" "${#list[*]}" "${list[*]} >> ${TMP}/a

  29.                     ( getall $((i - 1)) $sum  "${list[*]}" )
  30.         fi

  32. (( i -- ))
  33. done
  34. }

  36. i=0
  37. max_index=0
  38. while [ $i -le $(( ${#data[*]} - 1 )) ]
  39. do
  40.         if [ ${data[$i]} -le $MAX ]; then
  41.                 max_index=$i
  42.         else
  43.                 unused=$unused" "${data[$i]}
  44.         fi
  45. (( i ++ ))
  46. done

  48. echo
  49. echo Collect data ....

  51. getall  $max_index 0 ""

  53. sort -n -r -k 1 -k 2 ${TMP}/a |awk '{$1="";$2="";print}' > ${TMP}/b

  55. echo Process data ...
  56. echo
  57. set -A avail

  59. wfile=a
  60. rfile=b
  61. while true
  62. do
  63.         line=$(sed -n "1p" ${TMP}/$rfile)
  64.         current=$(echo $line|sed 's/a//g')

  66.         s=0
  67.         l=
  68.         for k in $current
  69.         do
  70.                 s=$(( s + data[k] ))
  71.                 l=$l" + "${data[k]}
  72.         done
  73.         l=$(echo $l|sed 's/+//')
  74.         echo $l" = "$s

  76.         avail=(${avail[*]} $current)
  77.         if [ ${#avail[*]} -gt $max_index ]; then
  78.                 break
  79.         fi
  80.         j=0
  81.         while [ $j -le $((${#avail[*]} - 1)) ]
  82.         do
  83.                 command=$command" | grep -v a${avail[$j]}a"        
  84.                 (( j++ ))
  85.         done
  86.                
  87.         command="cat ${TMP}/$rfile "$command" > ${TMP}/$wfile"
  88.         eval $command
  89.         command=
  90.         tfile=$wfile
  91.         wfile=$rfile
  92.         rfile=$tfile

  94. done

  96. echo "\nUnused number: $unused\n"
  97. echo Clear temp files ...

  99. rm -rf $TMP

  101. echo Done !


复制代码


运行：



  3. # ./1  data

  5. Collect data ....
  6. Process data ...

  8. 53 + 45 + 32 + 12 + 4 + 3 + 1 = 150
  9. 150 = 150
  10. 145 + 2 = 147
  11. 100 + 24 = 124
  12. 97 = 97

  14. Unused number:  170

  16. Clear temp files ...
  17. Done !   

复制代码
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
1234567下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP