1

这段代码旨在获取一个整数硬币值数组、要进行的更改数量和一个用于收集答案的空数组，并且应该返回一组硬币，这些硬币可以产生正确的更改数量（假设问题是可能的）。

从 puts 语句看来，递归似乎表现良好并寻求正确答案，但返回的解决方案不是有效答案。有人可以让我知道我做错了什么吗？

我的代码：

    def brute_solver(coins,amount,answer)
        puts "Coins: #{coins}, Amount: #{amount}, Answer: #{answer}"
        return answer.sort! if amount == 0
        coins.each do |c|
            brute_solver(coins, amount - c, answer.dup << c) unless amount - c < 0
        end 
    end

运行 brute_solver 的示例尝试：

    1.9.3p194 :001 > require './change_challenge.rb'
     => true 
    1.9.3p194 :002 > brute_solver([1,3,5],7,[])
    Coins: [1, 3, 5], Amount: 7, Answer: []
    Coins: [1, 3, 5], Amount: 6, Answer: [1]
    Coins: [1, 3, 5], Amount: 5, Answer: [1, 1]
    Coins: [1, 3, 5], Amount: 4, Answer: [1, 1, 1]
    Coins: [1, 3, 5], Amount: 3, Answer: [1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [1, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 1, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 1, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 1, 1, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 1, 1, 3]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 1, 3, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [1, 1, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 1, 3, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 3, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 1, 5]
    Coins: [1, 3, 5], Amount: 3, Answer: [1, 3]
    Coins: [1, 3, 5], Amount: 2, Answer: [1, 3, 1]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 3, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 3, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 3, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [1, 5]
    Coins: [1, 3, 5], Amount: 0, Answer: [1, 5, 1]
    Coins: [1, 3, 5], Amount: 4, Answer: [3]
    Coins: [1, 3, 5], Amount: 3, Answer: [3, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [3, 1, 1]
    Coins: [1, 3, 5], Amount: 1, Answer: [3, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [3, 1, 1, 1, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [3, 1, 3]
    Coins: [1, 3, 5], Amount: 1, Answer: [3, 3]
    Coins: [1, 3, 5], Amount: 0, Answer: [3, 3, 1]
    Coins: [1, 3, 5], Amount: 2, Answer: [5]
    Coins: [1, 3, 5], Amount: 1, Answer: [5, 1]
    Coins: [1, 3, 5], Amount: 0, Answer: [5, 1, 1]
     => [1, 3, 5]
4

1 回答 1

1 
def brute_solver(coins,amount,answer)

        puts "Coins: #{coins}, Amount: #{amount}, Answer: #{answer}"

        return answer.sort! if amount == 0

        coins.each do |c|
            if amount - c < 0
                break
            end
            result = brute_solver(coins, amount - c, answer.dup << c)
            if result != -1
                return result
            end
        end 
        return -1

end

puts brute_solver([5, 7],26,[])

这样，如果函数找到正确的解决方案，则返回一个数组，否则返回-1。当您进行递归调用时，您还会返回递归找到的解决方案（如果返回值不是 -1，则意味着它找到了解决方案）

Your code does not work because the return value for a function in ruby is the last statement executed, and your functions keeps executing commands even after it had found a valid combination of coins. Basically, your function returns the last combination of coins that it had checked to see if they are a solution.

于 2012-10-14T17:26:39.997 回答