查看完整版本: 2008-04-15 Ruby 测试题(00012)

2008-04-15 Ruby 测试题(00012)

人民币按面值有（1毛，5毛，1元，5元，10元，20元，50元，100元）共8种；
现在需要支付100元钱，问总共有多少种支付组合？
比如，10个10元就是一种，2个50元又是另一种，甚至1000个1毛也是一种。

哈~PE 31的中国版，以前还有2元面值的，貌似现在和20元一起都已经退出历史舞台了。

**** Hidden Message *****

[[i] 本帖最后由 bbschat 于 2008-4-15 16:55 编辑 [/i]]

不会要搞哪么多循环把。。。

最古老的办法。
我就不贴出来了！

回复 2# 的帖子

看下你的

太慢啦 太慢啦。。。 数西瓜的办法太笨了。·～～～～
**** Hidden Message *****

400189，正解
已经出现了递归算法，穷举算法，我来添上回溯。
穷举是思路最简洁的，不要说写N多循环很累，程序运行时间很长。如果你对算法不是很了解，又处在一个特殊的工作地位，比如可以慢但不允许出错，或者时间紧要交货，那时候，适当的穷举，多重循环是可以考虑的方法。
递归是代码最简洁的，但是在没有递归思路的人看来，这个代码是天书，而且递归的效率问题往往要交给编译器去完成。
回溯是自寻烦恼的，简单的思想，复杂的代码，还需要做适当的测试，编写过程中搞不好就死循环去了。
我认为程序没有最好的，只有最恰当的。能掌握多少种方法就掌握多少种方法，总会有用武那一天的。[code]def Euler31(x)
  curr={1=>1000,2=>500,3=>200,4=>100,5=>50,6=>10,7=>5}
  bag=[0,0,0,0,0,0,0,0]
  count = 0
  total = 0
  while true
    count += 1
    isend = true
    7.downto(1) {|i|
      if (x - total) >= curr[i] then
        bag[i] += 1
        total += curr[i]
        isend = false
        break
      else
        total -= bag[i]*curr[i]
        bag[i] = 0
      end
    }
    break if isend
  end
  puts count
end
#test
Euler31(1000)[/code]代码是当时解31题时候写的，可能不够精简。

[[i] 本帖最后由 jmouse 于 2008-4-15 13:16 编辑 [/i]]

其实如果能真的理解编程思想的话，简单的程序是不需要注释的。
加上注释，希望大家能看懂。楼上说的没错，递归难在对递归思想的理解~~

**** Hidden Message *****

[[i] 本帖最后由 bbschat 于 2008-4-15 17:00 编辑 [/i]]

学习一下bbschat的解法.

我做的原始的版本[code]@all = 0
@coins = [200,100,50,20,10,5,2,1]
@result = 200
def addto(v, i)
  #p @all.to_s+" "+v.to_s+" "+i.to_s
  return if @coins.size <= i
  if (@coins.size-1==i)
    @all += 1
    return
  end
  0.upto(@result/@coins[i]) do |j|
    @all += 1 if @result == j*@coins[i]+v
    break if @result <= j*@coins[i]+v
    addto(j*@coins[i]+v, i+1)
  end
end
start = Time.new
addto(0,0)
p @all
p Time.new - start[/code]时间是0.531, bbs是0.21. 于是想学习一下.
-------------------------------------------------------
1. @all 可以用返回来代替, return if @coins.size <= i 删掉.

第二版[code]@coins = [200,100,50,20,10,5,2,1]
@result = 200
def addto(v, i)
  return 1 if (@coins.size-1==i)
  all = 0
  0.upto(@result/@coins[i]) do |j|
    all += 1 if @result == j*@coins[i]+v
    return all if @result <= j*@coins[i]+v
    all += addto(j*@coins[i]+v, i+1)
  end
end
start = Time.new
p addto(0,0)
p Time.new - start[/code]快了一点, 0.484. 但还是慢, 问题在哪儿?
bbschat的循环里没有判断, 这可能是关键. 但为什么不需要呢?

我注意到程序的循环条件是从0到value除币值, 这儿的value和我的@result是不一样的.是指剩下来还有多少钱没找.
所以我的循环必须要判钱是否找多了, bbschat的不用判.

----------------------------------------------------
去掉这些判断, 第三版[code]@coins = [200,100,50,20,10,5,2,1]
Result = 200
LastI = @coins.size - 1
def addto(v, i)
  return 1 if (LastI==i)
  all = 0
  0.upto((Result-v)/@coins[i]) {|j| all += addto(j*@coins[i]+v, i+1)}
  all
end
start = Time.new
p addto(0,0)
p Time.new - start[/code]这个好象差不多了. 0.234

[code]def try1(step1)
  if step1 == 8
    $count += 1
    return
  end
  return if step1 >= 9
  return if $need < 0
  for j in 0 .. $need / $a[step1]
    $need -= j * $a[step1]
    if $need < 0
      $need += j * $a[step1]
      break
    end
    try1(step1+1)
    $need += j * $a[step1]
  end
end
$count = 0
$need = 1000
#$a = [nil, 1, 5, 10, 50, 100, 200, 500, 1000]
$a = [nil, 1000, 500, 200, 100, 50, 10, 5, 1]
try1(1)
puts $count[/code]

都是高手啊，我要好好学习一下了...:)

直接用系统栈进行“深度优先搜索”，用递归代码表示出来，就十分的简洁明了

这就是深度优先搜索的递归代码，大家可以研究一下

$mo=[0.1,0.5,1,5,10,20,50,100]
def try(t)           #深度优先搜索过程开始
  if $s==0 then $count+=1
    else 0.upto(7){|i| if $s>=$mo[i] then
           $s-=$mo[i]  
           try(t+1)
           $s+=$mo[i]   end
            }
       end
     end      #深度优先搜索过程结束
$s=100      #主程序开始
$count=0
try(1)
puts $count[/i][/i][/i]

[[i] 本帖最后由 aegiryy 于 2008-6-24 06:39 编辑 [/i]]

回贴 学习中

再一次陷入迷茫！