找零问题——Scala实现
deltamaster
posted @ Jul 06, 2014 12:51:20 PM
in Scala
with tags
scala 递归 找零问题 pattern matching decomposition
, 5040 阅读
首先简单描述一下这个经典的找零问题：
已知需要找零的数量，以及可用的硬币面值，求用这些面值的硬币，有多少种方法拼凑出要求的找零数量。
比如要求找零4元，可用的硬币只有1元和2元两种面值，那么所有可能的方案是，[1, 1, 1, 1]、[1, 1, 2]、[2, 2]三种。（不同顺序不作为不同方案）
设计一个函数，接受两个参数：
- money：Int，表示需要拼凑的找零数量。
- coins：List[Int]，所有可用的硬币面值。
简单分析一下这个问题。直观地用递归的思路去考虑，所有可能的方案，就等于以下两部分之和：
- 用一枚某种面值的硬币x后，剩余找零数的找零方案数量；
- 用除了x以外的其他硬币的找零方案数量。
而递归终止条件就是，找零的数量小于或等于0，或者没有硬币可以用了。
def countChange(money: Int, coins: List[Int]): Int = {
if (money < 0) 0
else coins match {
case Nil => if (money == 0) 1 else 0
case x::xs => countChange(money - x, coins) + countChange(money, xs)
}
}
这段代码用到了Scala的Pattern Matching。Nil是空List对象，继承自List，而x::xs则表示一个非空的List，其中x是用来匹配列表的head，而xs则是列表的tail，xs可以匹配任何List，当然也包括Nil。所以这两个case覆盖了所有的情形，要么为空，要么不为空，如果不为空，则将这个列表decompose成构造参数x和xs，供后面的表达式使用。
Aug 30, 2021 12:40:09 AM
wow this saintly however ,I love your enter plus nice pics might be part personss negative love being defrent mind total poeple ,
Sep 25, 2021 05:29:51 AM
I simply want to tell you that I am new to weblog and definitely liked this blog site. Very likely I’m going to bookmark your blog . You absolutely have wonderful stories. Cheers for sharing with us your blog.
Aug 04, 2022 01:56:05 AM
The department of tribal development and the backward classes welfare department of West Bengal has initiated the Oasis Scholarship for the students of the backward class category. This Online Application for Scholarship in Studies (OASIS) will be provided to Scheduled caste, Oasis scholarship status The department of tribal development and the backward classes welfare department of West Bengal has initiated the Oasis Scholarship for the students of the backward class category. Scheduled Tribe, and OBC category students based on their merit marks. Students up to PG are eligible including those who register for West Bengal employment bank enrollment, but as a student of the course as per eligibility.
Sep 15, 2022 04:46:57 PM
Bihar Board Model Paper 2023 Class 11 Pdf Download for First Year Intermediate Arts, Science & Commerce Stream Question Bank by Every SCERT & NCERT Hindi Medium, English Medium & Urdu Medium Student of Bihar Patna Board can download BSEB 11th Model Paper 2023 or BSEB Intermediate Model Set 2023 for Paper-1 & Paper-2 Exam at Bihar Board Question Paper Class 11 Bihar School Examination, Patna Board and various private school teaching staff have designed and suggested the Intermediate Education First Year of STD-11 or Higher Secondary Education 11th Standard Arts, Science and Commerce Stream study & learning material as Bihar Board 11th Class Model Paper 2023.
Jan 13, 2023 01:34:55 PM
In software development, one of the most difficult problems to solve is change. This is because every time a software development team makes a change to their codebase, they run the risk of introducing new bugs and breaking existing functionality. home real estate Key West One language that has been designed to help mitigate these risks is Scala. Scala is a functional programming language that encourages immutability, which means that data structures can't be modified once they've been created. This makes it much easier to reason about code and to catch bugs early on.
Jan 13, 2024 10:30:01 PM
There is so much in this article that I would never have thought of on my own. Your content gives readers things to think about in an interesting wa