找零问题——Scala实现

deltamaster posted @ Jul 06, 2014 12:51:20 PM in Scala with tags scala 递归 找零问题 pattern matching decomposition , 5680 阅读

首先简单描述一下这个经典的找零问题:

已知需要找零的数量,以及可用的硬币面值,求用这些面值的硬币,有多少种方法拼凑出要求的找零数量。

比如要求找零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,供后面的表达式使用。

* 本文在CC BY-SA(署名-相同方式共享)协议下发布。
XE88 APK FREE Downlo 说:
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 ,

Satta king 说:
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.

Oasis scholarship st 说:
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.

Bihar Board Question 说:
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.

zaiya 说:
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.

seo service london 说:
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

Albert 说:
May 25, 2026 08:46:26 PM

Most of the time I don’t make comments on websites, but I'd like to say that this article really forced me to do so. Really nice post! 清水斷崖獨木舟

Paul 说:
Aug 01, 2026 07:45:17 AM

Really I enjoy your site with effective and useful information. It is included very nice post with a lot of our resources.thanks for share. i enjoy this post. 台中包車

Matthew Wade 说:
Aug 07, 2026 11:51:39 PM

西宮市で家族葬や一日葬を検討する方に向けて、それぞれの特徴や費用の考え方、葬儀社を選ぶときに確認しておきたいポイントを紹介します。 西宮市 葬儀社

-

-

-


-

-

-

西宮市で葬儀社を探す際に役立つ情報を紹介。葬儀プランの種類や費用、見積もりで確認したい項目など、安心して依頼するためのポイントを解説します。 西宮市 葬儀社

-

-

-


-

-

-

西宮市で葬儀社を比較するときのポイントを紹介します。料金だけでなく、葬儀プランやスタッフの対応、アフターサポートなどを確認して選びましょう。 西宮市 葬儀社

-

-

-


-

-

-

西宮市で費用を抑えながら葬儀を行いたい方へ。家族葬や一日葬などのプランを選ぶ際のポイントや、見積もりで確認すべき費用を解説します。 西宮市 葬儀社

Matthew Wade 说:
Aug 13, 2026 09:13:29 PM

本編フル動画を楽しみたい方に向けて、視聴方法や注目ポイントをわかりやすく紹介します。 本編フル

-

-

-

-

-


-

-

-

-

-

本編フルを探している方へ、作品をより楽しむための視聴ポイントやチェックしたい情報を紹介します。 本編フル

-

-

-

-

-


-

-

-

-

-

AVメーカー【SODクリエイト】の作品情報を専門にまとめたサイト。人気作品や注目作品などを分かりやすく紹介します。 AVメーカー【SODクリエイト】作品専門まとめサイト

-

-

-

-

-


-

-

-

-

-

本編フル動画の魅力や見どころを知りたい方に向けて、視聴前にチェックしたいポイントをわかりやすく解説します。 本編フル

-

-

-

-

-


-

-

-

-

-

本編フルの内容を楽しみたい方必見。作品の見どころや視聴時に注目したいポイントを詳しく紹介します。 本編フル

Matthew Wade 说:
Aug 15, 2026 08:26:05 PM

Hello there! This is my first comment here so I just wanted to give a quick shout out and say I truly enjoy reading your articles. Can you suggest any other blogs/websites/forums that deal with the same subjects? Thank you! あくめくん

Paul 说:
Aug 18, 2026 06:42:53 PM

Thank you because you have been willing to share information with us. we will always appreciate all you have done here because I know you are very concerned with our. 花蓮海洋公園門票

Matthew Wade 说:
Aug 20, 2026 07:46:51 PM

既婚者マッチングの特徴や利用方法を紹介。既婚者同士だからこそ理解しやすい悩みや価値観を共有できる出会いを探しましょう。 既婚者マッチング

-

-

-

-

-


-

-

-

-

-

【無料エロ漫画】を探している方に向けて、話題の作品や読みやすいマンガ情報を紹介。作品の特徴や魅力をチェックして、お気に入りの一作を見つけよう。 【無料エロ漫画】

-

-

-

-

-


-

-

-

-

-

【フル漫画無料!!】で楽しめる話題の漫画や作品の魅力を紹介。無料で漫画を読む際のポイントやおすすめの楽しみ方を詳しく解説します。 【フル漫画無料!!】

-

-

-

-

-


-

-

-

-

-

【最新フル漫画free】で話題の漫画作品を探す方へ、作品情報や読み方をわかりやすく紹介。気になる漫画をチェックできます。 【最新フル漫画free】

-

-

-

-

-


-

-

-

-

-

素人エロ動画に関する話題や作品の特徴を紹介。人気の傾向や楽しみ方をチェックして、自分に合ったコンテンツを探せます。 素人エロ動画

-

-

-

-

-


-

-

-

-

-

同人エロ漫画の作品情報やジャンル、魅力などを紹介。さまざまな同人作品の特徴をチェックしながら、自分に合った作品を探せるガイドです。 同人エロ漫画

-

-

-

-

-


-

-

-

-

-

素人無料動画に関する情報をわかりやすく紹介。注目されている動画の特徴や楽しみ方、関連コンテンツをチェックして、自分に合った動画を探せます。 素人無料動画

-

-

-

-

-


-

-

-

-

-

同人エロマンガの特徴や魅力、作品の探し方を紹介。多彩なジャンルから自分に合った作品を見つけるためのポイントを詳しく解説します。 同人エロマンガ

-

-

-

-

-


-

-

-

-

-

素人エロ動画に関する話題や作品の特徴を紹介。さまざまなジャンルの魅力をわかりやすくチェックできます。 素人エロ動画

-

-

-

-

-


-

-

-

-

-

素人エロ動画Loverに関する情報を紹介。話題の動画や作品の特徴をチェックしながら、気になるコンテンツを探せます。 素人エロ動画Lover

-

-

-

-

-


-

-

-

-

-

エロ動画城【素人館】で楽しめる素人エロ動画を紹介。話題の作品や人気コンテンツをチェックして、お気に入りを探せます。 エロ動画城【素人館】

-

-

-

-

-


-

-

-

-

-

シコレビューで話題の動画や出演女優について紹介。気になる作品情報や女優名をチェックして、気になる動画を見つけよう。 シコレビュー【あのエロ動画に出演する女優名は何?】

-

-

-

-

-


-

-

-

-

-

エロ動画まとめ「3150!(サイコー)」の人気コンテンツを紹介。話題の動画や注目作品をチェックして、お気に入りを探せます。 エロ動画まとめ「3150!(サイコー)」

-

-

-

-

-


-

-

-

-

-

【無料立読みフル漫画】で話題の作品をチェック。無料で読める漫画の魅力や作品情報をわかりやすく紹介します。 【無料立読みフル漫画】

Matthew Wade 说:
Aug 23, 2026 04:24:32 PM

新人・デビュー作品を中心に、話題のAV動画をまとめて紹介。新人女優のプロフィールや作品情報などをチェックできます。 新人・デビュー専門!AV動画まとめサイト

-

-

-

-

-

--------------------------------------------------------------------------------------------

-

-

-

-

-

熟女専門のAV動画まとめサイト。大人の魅力を楽しめる作品を厳選して紹介し、気になる動画を見つけやすくまとめています。 熟女専門!AV動画まとめサイト

Alex 说:
Aug 25, 2026 05:59:31 AM

Thanks, that was a really cool read! 花蓮泛舟

Matthew Wade 说:
Sep 06, 2026 07:42:56 PM
【本編フル】で話題の動画をチェック。気になる内容や注目シーン、見どころをわかりやすく紹介します。 【本編フル】
-
-
-
-
-

-
-
-
-
-
Comic Loungeは、同人マンガの作品情報を探せるサイトです。気になる作品や作家をチェックして、あなた好みのマンガを見つけよう。 Comic Lounge
-
-
-
-
-

-
-
-
-
-
【本編フル】の動画内容を詳しく紹介。注目ポイントや見どころをチェックして、話題の動画を楽しみましょう。 【本編フル】
-
-
-
-
-

-
-
-
-
-
同人漫画の魅力やジャンル、作品の楽しみ方について詳しく紹介。自分に合った作品を見つけるためのポイントも解説します。 同人漫画
-
-
-
-
-

-
-
-
-
-
【本編フル】で注目されている動画の内容や見どころを紹介。話題のポイントをわかりやすくまとめています。 【本編フル】
Matthew Wade 说:
Sep 10, 2026 08:29:46 PM

新作&デビュー作品の最新情報をまとめて紹介。注目の作品や出演者情報をチェックしながら、気になる作品を見つけよう。 新作&デビューAVまとめ

-

-

-

-


-

-

-

-

おすすめエロ動画をまとめて紹介。人気ジャンルや話題の作品を探している方に向けて、見つけやすく整理しています。 おすすめエロ動画まとめ

-

-

-

-


-

-

-

-

素人エロ動画GIFを探している方に向けて、話題のGIF動画や関連コンテンツをまとめて紹介します。 素人エロ動画GIF

-

-

-

-


-

-

-

-

最新の素人動画に関する情報を紹介。話題のコンテンツや注目ポイントをチェックして、自分に合った動画を探そう。 最新の素人エロ動画

-

-

-

-


-

-

-

-

FANZA独占動画をまとめて紹介。注目の独占作品を探しやすく整理し、気になる動画をチェックできます。 FANZA独占動画まとめ

-

-

-

-


-

-

-

-

ニューシロウト!に登場する素人動画の女優名が気になる方へ。出演者情報や作品の特徴、確認方法などをわかりやすく紹介します。 ニューシロウト!あの素人動画の女優名は?

-

-

-

-


-

-

-

-

最新VR動画をまとめて紹介。話題のVR作品や注目コンテンツをチェックしながら、気になる動画を見つけられます。 最新VR動画まとめ

-

-

-

-


-

-

-

-

人気エロ同人マンガの特徴や作品選びのポイントを紹介。ジャンルや作風の違いを比較し、自分に合う作品を探すための情報をまとめます。 人気エロ同人マンガ

-

-

-

-


-

-

-

-

人気VR研究所では、VRの最新情報や話題のコンテンツ、注目作品などを詳しく紹介。VRの魅力をわかりやすく解説します。 人気VR研究所

-

-

-

-


-

-

-

-

エロ漫画の特徴や魅力、作品を楽しむためのポイントをわかりやすく紹介。ジャンルや表現の違いにも触れながら解説します。 エロ漫画

-

-

-

-


-

-

-

-

ゴールデンバズーカについて詳しく解説。基本情報や特徴、魅力、楽しみ方などをわかりやすく紹介します。 ゴールデンバズーカ

Matthew Wade 说:
Sep 11, 2026 10:10:26 PM

エロ同人誌の特徴やジャンル、作品を楽しむ際のポイントについて詳しく紹介。自分に合った作品を見つけるための基礎知識を解説します。 エロ同人誌

Matthew Wade 说:
Sep 18, 2026 04:31:54 PM

エロフルでエロい動画をフルで楽しみたい方へ。さまざまな動画コンテンツを見つけやすくまとめ、気になる作品をチェックできます。 エロフル!エロい動画をフルでお届けします!

-

-

-

-

-


-

-

-

-

-

raw漫画保管庫について、漫画RAWの保存や閲覧に関する基本情報をわかりやすく解説。利用時に知っておきたいポイントも紹介します。 raw漫画保管庫

Matthew Wade 说:
Sep 28, 2026 03:35:42 AM

女優コードについて、基本的な意味や検索時に知っておきたい情報をわかりやすく解説。関連するコード情報の見方も紹介します。 女優コード

-

-

-

-

-


-

-

-

-

-

エロ同人サーチについて、同人作品を探す際の検索方法や基本的な使い方をわかりやすく解説。作品検索のポイントも紹介します。 エロ同人サーチ

Matthew Wade 说:
Sep 30, 2026 04:29:08 PM

既婚者マッチングアプリの特徴や基本的な使い方を解説。サービスを比較するときのポイントや利用前に確認したい点も紹介します。 既婚者マッチングアプリ

Matthew Wade 说:
Oct 05, 2026 12:55:56 AM

「エロ動画」に関する基本情報を紹介。動画を探す際に知っておきたい安全性やプライバシー、年齢確認などのポイントをわかりやすく解説します。 「エロ動画」

Matthew Wade 说:
Oct 05, 2026 12:56:17 AM

「エロ動画」を利用する際に確認したい安全対策やプライバシー保護、年齢確認などの基本ポイントをわかりやすく紹介します。 「エロ動画」

Matthew Wade 说:
Oct 05, 2026 12:56:28 AM

「エロ動画」を探すときに役立つ基本情報を紹介。安全性や個人情報、サイト利用時に確認したいポイントを詳しく解説します。 「エロ動画」


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter