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 でない場合は、解が見つかったことを意味します)。

Ruby の関数の戻り値は最後に実行されたステートメントであり、コインの有効な組み合わせが見つかった後でも関数はコマンドを実行し続けるため、コードは機能しません。基本的に、関数は、解決策であるかどうかを確認するためにチェックした最後のコインの組み合わせを返します。

于 2012-10-14T17:26:39.997 に答える