{"id":53,"date":"2008-05-06T22:49:49","date_gmt":"2008-05-06T14:49:49","guid":{"rendered":"http:\/\/www.zhuangbiaowei.cn\/?p=53"},"modified":"2008-05-06T22:49:49","modified_gmt":"2008-05-06T14:49:49","slug":"play-with-quiz-%e6%89%be%e9%9b%b6%e9%92%b1-3","status":"publish","type":"post","link":"https:\/\/blog.zhuangbiaowei.com\/?p=53","title":{"rendered":"Play with Quiz \u2014 \u627e\u96f6\u94b1 (3)"},"content":{"rendered":"<p>\u8981\u6539\u8fdb\u8fd9\u4e24\u79cd\u7b97\u6cd5\uff0c\u90fd\u662f\u4e00\u4e2a\u76ee\u6807\uff0c\u5c31\u662f\u5bfb\u627e\u4e0d\u9700\u8981\u5217\u51fa\u6240\u6709\u89e3\u7684\u529e\u6cd5\u6765\u3002<\/p>\n<p>\u524d\u4e00\u79cd\u7b97\u6cd5\uff0c\u662f\u6c42\u51fa\u6240\u6709\u7684\u53ef\u80fd\u89e3\uff0c\u7136\u540e\u518d\u627e\u5176\u4e2d\u7684\u6700\u4f18\u89e3\u3002\u8981\u8fdb\u884c\u4f18\u5316\uff0c\u5219\u53ef\u4ee5\u5c06\u6c42\u89e3\u4e0e\u6c42\u4f18\u5408\u4e8c\u4e3a\u4e00\u3002\u5728\u6bcf\u4e00\u4e2a\u9012\u5f52\u4e2d\uff0c\u90fd\u5bfb\u627e\u6700\u4f18\u89e3\u3002\u6bd4\u5982\uff0cmake_change(14,[10,7,2])\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5bfb\u627e14-10\u540e\u5269\u4f59\u76844\u7684\u6700\u4f18\u89e3\uff0c\u5f97\u5230[2,2]\uff0c\u4ee5\u53ca14-7\u540e\u5269\u4f59\u76847\u7684\u6700\u4f18\u89e3\uff0c\u5f97\u5230[7]\uff0c\u6700\u540e\u662f14-2\u540e\u5269\u4f59\u768412\u7684\u6700\u4f18\u89e3\uff0c\u5f97\u5230[10,2]\u3002\u7136\u540e\u9009\u62e9\u5176\u4e2d\u6700\u77ed\u7684\u4e00\u4e2a[7]\uff0c\u7ec4\u5408\u4e3a[7,7]\u4f5c\u4e3a\u7ed3\u679c\u8fd4\u56de\u3002<\/p>\n<p>\u4ee3\u7801\u5982\u4e0b\uff1a<br \/>\n[cc lang=&#8221;ruby&#8221; css=&#8221;no&#8221;]<br \/>\ndef make_change(amount, coins = [25, 10, 5, 1])<br \/>\n  return [amount] if coins.include?(amount)<br \/>\n  min_one_coin=nil<br \/>\n  min_coins=Array.new(amount)<br \/>\n  coins.each do |one_coin|<br \/>\n    if amount-one_coin>0<br \/>\n      other_coins=make_change(amount-one_coin,coins)<br \/>\n      if other_coins &#038;&#038; min_coins.size>other_coins.size<br \/>\n        min_one_coin=one_coin<br \/>\n        min_coins=other_coins<br \/>\n      end<br \/>\n    end<br \/>\n  end<br \/>\n  min_one_coin ? [min_one_coin]+min_coins : nil<br \/>\nend<br \/>\n[\/cc]<\/p>\n<p>\u540e\u4e00\u79cd\u7b97\u6cd5\uff0c\u4e5f\u53ef\u4ee5\u76f8\u5f53\u76f4\u89c2\u7684\u4f18\u5316\uff0c\u56e0\u4e3a\u6574\u4e2a\u6c42\u89e3\u7684\u8fc7\u7a0b\uff0c\u662f\u7531\u5c11\u81f3\u591a\uff0c\u56e0\u6b64\uff0c\u53ea\u8981\u6c42\u5230\u7b2c\u4e00\u4e2a\u6ee1\u8db3\u8981\u6c42\u7684\u627e\u96f6\u65b9\u6848\uff0c\u5c31\u4e00\u5b9a\u662f\u6700\u4f18\u89e3\u3002<br \/>\n\u4ee3\u7801\u5982\u4e0b\uff1a<br \/>\n[cc lang=&#8221;ruby&#8221; css=&#8221;no&#8221;]<br \/>\ndef make_change(amount, coins = [25, 10, 5, 1])<br \/>\n  change_list={}<br \/>\n  coins.each do |coin|<br \/>\n    return [amount] if amount==coin<br \/>\n    change_list[[coin]]=coin<br \/>\n  end<br \/>\n  while(true)<br \/>\n    new_change_list={}<br \/>\n    coins.each do |coin|<br \/>\n      change_list.each do |list,v|<br \/>\n        return list.insert(0,coin).sort  if coin+v==amount<br \/>\n        if v+coin<=amount\n          new_list=list.clone.insert(list.length,coin).sort\n          unless new_change_list[new_list]\n            unless new_change_list.has_value?(v+coin)\n              new_change_list[new_list]=v+coin\n            end\n          end\n        end\n      end\n    end\n    return nil if new_change_list.length==0\n    change_list=new_change_list\n  end\nend\n[\/cc]\n\n\u5f53\u7136\uff0c\u8fd9\u4e24\u4e2a\u7b97\u6cd5\uff0c\u90fd\u8fd8\u6709\u8fdb\u4e00\u6b65\u4f18\u5316\u7684\u4f59\u5730\uff0c\u54b1\u4eec\u4e0b\u56de\u518d\u8bf4\u3002\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u8981\u6539\u8fdb\u8fd9\u4e24\u79cd\u7b97\u6cd5\uff0c\u90fd\u662f\u4e00\u4e2a\u76ee\u6807\uff0c\u5c31\u662f\u5bfb\u627e\u4e0d\u9700\u8981\u5217\u51fa\u6240\u6709\u89e3\u7684\u529e\u6cd5\u6765\u3002 \u524d\u4e00\u79cd\u7b97\u6cd5\uff0c\u662f\u6c42\u51fa\u6240\u6709\u7684\u53ef\u80fd\u89e3\uff0c\u7136\u540e\u518d\u627e\u5176 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-53","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=\/wp\/v2\/posts\/53","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=53"}],"version-history":[{"count":0,"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=\/wp\/v2\/posts\/53\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=53"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=53"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.zhuangbiaowei.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=53"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}