<jupyter_start><jupyter_text>SICP 习题 （2.19） 解题总结：重写零钱兑换程序 SICP 习题2.19 要求我们重新设计1.2.2节的零钱兑换程序，要求我们可以轻易改变程序里用的兑换币种。我们先看看1.2.2节的零钱兑换程序，代码是这样的：<jupyter_code>(define (RMB-Change amount)
  (format #t "Changing ~S~%" amount)
  (cond ((= amount 0) 0)
	((< amount 0) 0)
	(else (RMB-Change-Recursive amount 1 '() ))))

(define (RMB-Change-Recursive amount change-kind change-result)
  (format #t "( ~S ~S )" amount change-kind)
  (if (= amount 0) (format #t "Got one: ~S~%" change-result))
  (cond ((= amount 0) 1)
	((> change-kind amount) 0)
	((= change-kind 0) 0)
	(else (+ (RMB-Change-Recursive amount (RMB-Change-Next-Kind change-kind) change-result)
		 (RMB-Change-Recursive (- amount change-kind) change-kind (cons change-kind change-result))))))<jupyter_output><empty_output><jupyter_text>注意，我这里的代码是我自己写的，和书中的样例代码有出入。不过我们需要留意的是代码的思路，所以不需要留意代码细节。1.2.2节中的零钱兑换程序的主要思路就是将遍历所有面额，对每一种面额的钱币都对当前需要兑换的总数做两种假设，一是零钱兑换方式包括了当前面额，第二种是零钱兑换方式没包括当前面额。对第一种方式，就是将当前需要兑换的总数减当前面额，产生新的需要兑换的总数，然后递归处理。对第二种方式，就是将当前面额的从所有面额中除去，看当前总数对应剩下的面额有多少兑换方式，然后递归处理。为了方便地使用以上方法计算不同国家的币种，简单的方式就是将不同国家的零钱组合做成一个list，然后计算过程中就从该list中获取不同的零钱面额。代码如下：<jupyter_code>(define us-coins (list 50 25 10 5 1))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define cn-coins (list 100 50 20 10 5 2 1))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
	((or (< amount 0) (no-more? coin-values)) 0)
	(else 
	 (+ (cc amount 
		(except-first-denomination coin-values))
	    (cc (- amount 
		   (first-denomination coin-values))
		coin-values)))))

(define (first-denomination coin-values)
  (car coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (no-more? coin-values)
  (null? coin-values))

(define (test-it)
  (cc 101 cn-coins))

(test-it)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15402038505096263, 'fraction_numerical': 0.037938844847112116, 'mean_word_length': 5.425454545454546, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '16618', 'license': 'MIT', 'n_tokens_mistral': 1024, 'n_tokens_neox': 1024, 'n_words': 141, 'path': 'cn/.ipynb_checkpoints/sicp-2-19-checkpoint.ipynb', 'repo_name': 'DamonDeng/sicp_exercise', 'size': '1766'}