sp-6. リストと繰り返し処理

>100 Views

January 26, 22

スライド概要

(Scheme プログラミング)
URL: https://www.kkaneko.jp/cc/scheme/index.html

profile-image

金子邦彦(かねこくにひこ) 福山大学・工学部・教授 ホームページ: https://www.kkaneko.jp/index.html 金子邦彦 YouTube チャンネル: https://youtube.com/user/kunihikokaneko

シェア

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

sp-6. リストと繰り返し処理 (Scheme プログラミング) URL: https://www.kkaneko.jp/cc/scheme/index.html 金子邦彦 1

2.

アウトライン 6-1 リストと繰り返し処理 6-2 パソコン演習 6-3 課題 2

3.

本日の内容 1. リストを扱う関数の書き方について • 再帰 • cond 文との組み合わせ • リストの要素に対する繰り返し処理 2. 再帰を使ったプログラムに慣れ,自力で読み書 きできるようになる 3

4.

リストと繰り返し処理 リストを扱うプログラムでは リストの要素の数だけ, 同じ処理を繰り返す ことが多い • 長さが10のリストなら,処理を10回繰り返 したい ⇒ 「再帰」のテクニック(次ページ) 4

5.

再帰 再帰関数のパターン (define (foo パラメータの並び) (cond [終了条件 自明の答] [else (foo 新たなパラメータの並び)])) • 関数(上では foo)の内部に ,同じ関数 foo が登場 • foo の実行が繰り返される 5

6.

再帰での終了条件 (define (foo ...) (cond [終了条件 自明の答] [else (foo 新たなパラメータ)])) 終了条件 No Yes 再帰呼び出し 自明な解 • 条件文(cond) と組み合わせ • 繰り返しのたびに 「終了条件」の真偽が判定される • 「終了条件」が満足されるまで ,処理が繰り返される 6

7.

リストでの繰り返しと終了条件 • ある終了条件(例えば、リストが empty に なるなど)が満足されたら,処理を終える • リストの rest をとりながら,処理を繰り返 すことが多い 7

8.

パソコン演習 8

9.

パソコン演習の進め方 • 資料を見ながら,「例題」を行ってみる • 各自,「課題」に挑戦する • 自分のペースで先に進んで構いません 9

10.

DrScheme の使用 • DrScheme の起動 プログラム • → PLT Scheme → DrScheme 今日の演習では「Intermediate Student」 に設定 Language → Choose Language → Intermediate Student → Execute ボタン 10

11.

例題1.リストの総和 数のリスト a-list から総和を求める関数 listsum を作り,実行する • • x1, x2, … , xn のリストに対して,総和 x1 + x2 + … + xn を求める 11

12.

「例題1.リストの総和」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) 2. その後,次を「実行用ウインドウ」で実行しなさい (sum (list 1 2 3)) (sum (list 11 12 13)) ☆ 次は,例題2に進んでください 12

13.

まず,Scheme のプログラムを コンピュータに読み込ませている 13

14.

これは, (list-sum (list 1 2 3)) と書いて,a-list の値を (list 1 2 3) に設定しての実行 実行結果である「6」が 表示される 14

15.

入力と出力 6 (list 1 2 3) list-sum 入力は 1つのリスト 出力は 1つの数値 15

16.

list-sum 関数 「関数である」ことを 示すキーワード 関数の名前 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) 値を1つ受け取る(入力) a-list の値から リストの総和を求める(出力) 16

17.

リストの総和 1. リストが空ならば: 0 → 終了条件 → 自明な解 2. そうで無ければ: • リストの rest を求める(これもリスト). 「その総和と,リストの先頭との和」が, 求める総和である 17

18.

リストの総和 リストが空で無いとき 総和を求める ... first ... rest 総和を求める ... ... (それを,リストの first と足す) 18

19.

リストの総和 (define (list-sum a-list) (cond 終了条件 [(empty? a-list) 0]自明な解 [else (+ (first a-list) (list-sum (rest alist)))])) 19

20.

No (empty? a-list) Yes (+ (first a-list) (list-sum (rest a-list))) 0 が自明な解である 20

21.

リストの総和 list-sum • list-sum の内部に list-sum が登場 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) • sum の実行が繰り返される 例: (list-sum (list 1 2 3)) = (+ 1 (list-sum (list 2 3))) 21

22.

例題2.ステップ実行 • 関数 list-sum (例題1)について,実行結果 に至る過程を見る • (list-sum (list 1 2 3)) から 6 に至る過程を見る • DrScheme の stepper を使用する = (list-sum (list 1 2 3)) = ... = (+ 1 (list-sum (list 2 3))) = ... = (+ 1 (+ 2 (list-sum (list 3)))) = ... = (+ 1 (+ 2 (+ 3 (list-sum empty)))) = ... = (+ 1 (+ 2 (+ 3 0))) = (+ 1 (+ 2 3)) = (+ 1 5) =6 基本的な計算式 への展開 演算の実行 22

23.

「例題2.ステップ実行」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • Intermediate Student で実行すること • 入力した後に,Execute ボタンを押す (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) (list-sum (list 1 2 3)) 例題1と同じ 2. DrScheme を使って,ステップ実行の様子を 確認しなさい (Step ボタン,Next ボタンを使用) • 理解しながら進むこと ☆ 次は,例題3に進んでください 23

24.

(list-sum (list 1 2 3)) から 6 が得られる過程の概略 = (list-sum (list 1 2 3)) (list 1 2 3) の和 最初の式 = ... = (+ 1 (list-sum (list 2 3))) (list 2 3) の和に1を足す = ... = (+ 1 (+ 2 (list-sum (list 3)))) (list 3) の和に1,2を足す = ... = (+ 1 (+ 2 (+ 3 (list-sum empty)))) emptyの和に1,2,3を足す = ... = (+ 1 (+ 2 (+ 3 0))) = (+ 1 (+ 2 3)) = (+ 1 5) コンピュータ内部での計算 =6 実行結果 24

25.

(list-sum (list 1 2 3)) から (+ 1 (list 2 3)) が得られる過程 (list-sum (list 1 2 3)) = (list-sum (list 1 2 3)) = (cond = ... [(empty? (list 1 2 3)) 0] [else (+ (first (list 1 2 3)) = (+ 1 (list-sum (list 2 3))) (list-sum (rest (list 1 2 3))))]) この部分は = ... = (cond = (+ 1 (+ 2 (list-sum (list 3)))) [false 0] [else (+ (first (list 1 2 3)) = ... (list-sum (rest (list 1 2 3))))]) = (+ (first (list 1 2 3)) = (+ 1 (+ 2 (+ 3 (list-sum empty)))) (list-sum (rest (list 1 2 3)))) = ... = (+ 1 (list-sum (rest (list 1 2 3)))) = (+ 1 (+ 2 (+ 3 0))) = (+ 1 = (+ 1 (+ 2 3)) (list-sum (list 2 3))) = (+ 1 5) =6 25

26.

(list-sum (list 1 2 3)) から (+ 1 (list 2 3)) が得られる過程 (list-sum (list 1 2 3)) = (list-sum (list 1 2 3)) = (cond = ... [(empty? (list 1 2 3)) 0] [else (+ (first (list 1 2 3)) = (+ 1 (list-sum (list 2 3))) (list-sum (rest (list 1 2 3))))]) この部分は = ... = (cond = (+ 1 (+ 2 (list-sum (list 3)))) [false 0] [else (+ (first (list 1 2 3)) = ... (list-sum (rest (list 1 2 3))))]) = (+ (first (list 1 2 3)) = (+これは, 1 (+ 2 (+ 3 (list-sum empty)))) (list-sum (rest (list 1 2 3)))) = ... (define (sum a-list) = (+ 1 (cond (list-sum (rest (list 1 2 3)))) = (+ 1 (+ [(empty? 2 (+ 3 0))) a-list) 0] = (+ 1 = (+ 1 (+ [else 2 3))(+ (first a-list) (list-sum (list 2 3))) (sum (rest a-list)))])) = (+ 1 5) の a-list を (list 1 2 3) で置き換えたもの =6 26

27.

(contains-5? (list 3 5 7 9)) から (contains-5? (list 5 7 9))が得られる過程 (list 3 5 7 9)) (contains-5? (list 3 5 7 9))(contains-5? = (cond [(empty? (list 3 5 7 9)) false] [else (cond =… この部分は [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) =(contains-5? (list 5 7 9)) = (cond [false false] =… [else (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) = これは, true = (cond (define (contains-5? a-list) [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) (cond = (cond [(empty? a-list) false] [(= 3 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (cond = (cond [(= (first a-list) 5) true] [false true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (contains-5? (rest a-list))])])) = (contains-5? (rest (list 3 5 7 9))) の a-list を (list 3 5 7 9) で置き換えたもの = (contains-5? (list 5 7 9)) 27

28.

例題3.平均点 • 点数のリストから,平均点を求めるプログラ ム average を作り,実行する • 点数のデータはリストとして扱う • 合計を求める関数 list-sum と,リストの長さを求 める関数 length を組み合わせる list-sum, length については、以前の授 業の資 料を参照のこと 28

29.

平均点 平均点 = リストの総和/リストの長さ 29

30.

「例題3.平均点」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す ;; list-sum: list -> number ;; total of a list ;; (list-sum (list 40 90 80)) = 210 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) ;; average: list -> number ;; average of a list ;; (average (list 40 90 80)) = 70 (define (average a-list) (/ (list-sum a-list) (length a-list))) 2. その後,次を「実行用ウインドウ」で実行しなさい (average (list 40 90 80)) (average (list 100 200 300 400 500)) ☆ 次は,例題4に進んでください 30

31.

まず,Scheme のプログラムを コンピュータに読み込ませている 31

32.

これは, (average (list 40 90 80)) と書いて,a-list の値を (list 40 90 80) に設定しての実行 実行結果である「70」が 表示される 32

33.

入力と出力 (list 40 90 80) 70 average 入力 入力はリスト 出力 出力は数値 33

34.

平均点のプログラム ;; list-sum: list -> number ;; total of a list ;; (list-sum (list 40 90 80)) = 210 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) ;; average: list -> number ;; average of a list ;; (average (list 40 90 80)) = 70 (define (average a-list) (/ (list-sum a-list) (length a-list))) list-sum の部分 average の部分 34

35.

list-sum, average の関係 • list-sum • 「数のリスト」から「リストの総和」を求める • average • 「数のリスト」から「平均」を求める • list-sum を使用 35

36.

例題4.ステップ実行 • 関数 average (例題3)について,実行結果 に至る過程を見る • (average (list 40 90 80)) から 70 に至る過程を見 る • DrScheme の stepper を使用する (average (list 40 90 80)) = (/ (list-sum (list 40 90 80)) (length (list 40 90 80))) =… = (/ 210 (length (list 40 90 80))) = ... = (/ 210 3) = 70 36

37.

「例題4.ステップ実行」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • Intermediate Student で実行すること • 入力した後に,Execute ボタンを押す ;; list-sum: list -> number ;; total of a list ;; (list-sum (list 40 90 80)) = 210 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) ;; average: list -> number ;; average of a list ;; (average (list 40 90 80)) = 70 (define (average a-list) (/ (list-sum a-list) (length a-list))) (list-sum (list 40 90 80)) 例題3と同じ 2. DrScheme を使って,ステップ実行の様子を 確認しなさい (Step ボタン,Next ボタンを使用) • 理解しながら進むこと ☆ 次は,例題5に進んでください 37

38.

(average (list 40 90 80)) から 70 が得られる過程の概略 最初の式 (average (list 40 90 80)) = (/ (list-sum (list 40 90 80)) (length (list 40 90 80))) =… = (/ 210 (length (list 40 90 80))) = ... = (/ 210 3) コンピュータ内部での計算 = 70 実行結果 38

39.

(average (list 40 90 80)) から 70 が得られる過程の概略 (average (list 40 90 80)) = (/ (list-sum (list 40 90 80)) (length (list 40 90 80))) =… = (/ 210 (length (list 40 90 80))) これは, = ... (define (average a-list) = (/ 210(/3)(list-sum a-list) (length a-list))) = 70 の a-list を (list 40 90 80) で置き換えたもの 39

40.

例題5.「5」を含むか調べる • リストの要素の中に「5」を含むかどうか調 べる関数 contains-5? を作り,実行する 40

41.

「例題5.「5」を含むか調べる」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す ;; contains-5?: list -> true or false ;; it investigates whether 5 is included ;; (contains-5? (list 3 5 7 9)) = true (define (contains-5? a-list) (cond [(empty? a-list) false] [else (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))])])) 2. その後,次を「実行用ウインドウ」で実行しなさい (contains-5? (list 1 2 3 4)) (contains-5? (list 3 5 7 9)) ☆ 次は,例題6に進んでください 41

42.

まず,Scheme のプログラムを コンピュータに読み込ませている 42

43.

これは, (contains-5? (list 3 5 7 9)) と書いて,a-list の値を (list 3 5 7 9) に設定しての実行 実行結果である「true」が 表示される 43

44.

入力と出力 true (list 3 5 7 9) contains-5? 入力は 1つのリスト 出力は true/false 値 44

45.

contains-5? 関数 ;; contains-5?: list -> true or false ;; it investigates whether 5 is included ;; (contains-5? (list 3 5 7 9)) = true (define (contains-5? a-list) (cond [(empty? a-list) false] [else (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))])])) 45

46.

「5」を含むか調べる 1. リストが空ならば: → 終了条件 false → 自明な解 2. そうで無ければ: • リストの first が「5」であるかを調べ る. • 「5」ならば: true • 「5」で無いならば: リストの rest が「5」 を含むかどうかを調べる 46

47.

「5」を含むか調べる リストが空で無いとき 「5」 を含むか調べる ... ... first 「5」で無いならば rest 「5」 を含むか調べる ... ... 47

48.

「5」を含むか調べる ;; contains-5?: list -> true or false ;; it investigates whether 5 is included ;; (contains-5? (list 3 5 7 9)) = true (define (contains-5? a-list) (cond 終了 [(empty? a-list) false] 自明な解 条件 [else (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))])])) 48

49.

(empty? a-list) Yes No (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))] false が自明な解である 49

50.

「5」を含むか調べる contains-5? • contains-5? の内部に contains-5? が登場 (define (contains-5? a-list) (cond [(empty? a-list) false] [else (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))])])) • contains-5? の実行が繰り返される 例: (contains-5? (list 3 5 7 9)) = (contains-5? (list 5 7 9)) 50

51.

例題6.ステップ実行 • 関数 contains-5? (例題5)について,実行 結果に至る過程を見る • (contains-5? (list 3 5 7 9)) から true に至る過程 を見る • DrScheme の stepper を使用する (contains-5? (list 3 5 7 9)) =… =(contains-5? (list 5 7 9)) =… = true 51

52.

「例題6.ステップ実行」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • • Intermediate Student で実行すること 入力した後に,Execute ボタンを押す (define (contains-5? a-list) (cond [(empty? a-list) false] [else (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))])])) (contains-5? (list 3 5 7 9)) 例題5と同じ 2. DrScheme を使って,ステップ実行の様子を 確認しなさい (Step ボタン,Next ボタンを使用) • 理解しながら進むこと ☆ 次は,例題7に進んでください 52

53.

(contains-5? (list 3 5 7 9)) から true が得られる過程の概略 (contains-5? (list 3 5 7 9))最初の式 (list 3 5 7 9) から探す =… =(contains-5? (list 5 7 9)) =… (list 5 7 9) から探す コンピュータ内部での計算 = true 実行結果 先頭が 5 なので true 53

54.

(contains-5? (list 3 5 7 9)) から (contains-5? (list 5 7 9))が得られる過程 (list 3 5 7 9)) (contains-5? (list 3 5 7 9))(contains-5? = (cond =… =(contains-5? (list =… = true [(empty? (list 3 5 7 9)) false] [else (cond この部分は [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) 5 7 9)) = (cond [false false] [else (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) = (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) = (cond [(= 3 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) = (cond [false true] [else (contains-5? (rest (list 3 5 7 9)))]) = (contains-5? (rest (list 3 5 7 9))) = (contains-5? (list 5 7 9)) 54

55.

(contains-5? (list 3 5 7 9)) から (contains-5? (list 5 7 9))が得られる過程 (list 3 5 7 9)) (contains-5? (list 3 5 7 9))(contains-5? = (cond [(empty? (list 3 5 7 9)) false] [else (cond =… この部分は [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) =(contains-5? (list 5 7 9)) = (cond [false false] =… [else (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) = これは, true = (cond (define (contains-5? a-list) [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) (cond = (cond [(empty? a-list) false] [(= 3 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (cond = (cond [(= (first a-list) 5) true] [false true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (contains-5? (rest a-list))])])) = (contains-5? (rest (list 3 5 7 9))) の a-list を (list 3 5 7 9) で置き換えたもの = (contains-5? (list 5 7 9)) 55

56.

例題7.ベクトルの内積 • 2つのベクトルデータ x, y から2つのベクトル の内積を求めるプログラム product を作り,実 行する • 2つのベクトルデータ x, y はリストとして扱う 56

57.

「例題7.ベクトルの内積」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す ;; product: list list -> number ;; inner product of two vectors ;; (product (list 1 2 3) (list 4 5 6)) = 32 (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 2. その後,次を「実行用ウインドウ」で実行しなさい (product (list 1 2 3) (list 4 5 6)) ☆ 次は,例題8に進んでください 57

58.

まず,Scheme のプログラムを コンピュータに読み込ませている 58

59.

これは, (product (list 1 2 3) (list 4 5 6)) と書いて,x の値を(list 1 2 3) に, y の値を (list 4 5 6) に設定しての実行 実行結果である「32」が 表示される 59

60.

入力と出力 (list 1 2 3) (list 4 5 6) 32 product 入力 入力は, 2つのリスト 出力 出力は数値 60

61.

product 関数 ;; product: list list -> number ;; inner product of two vectors ;; (product (list 1 2 3) (list 4 5 6)) = 32 (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 61

62.

よくある勘違い (define (product x y) (cond [(= x empty) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 終了条件の判定: ・ 正しくは「(empty? x)」 ・ x がリストのとき、(= x empty) はエラー ・ 「=」は数値の比較には使えるが,リスト同士の比較に は使えない 62

63.

ベクトルの内積 1. リストが空ならば: 0 → 終了条件 → 自明な解 2. そうで無ければ: – 「2つのリストの rest の内積と,2つの リストの先頭の積との和」 が求める解 63

64.

ベクトルの内積 ;; product: list list -> number ;; inner product of two vectors ;; (product (list 1 2 3) (list 4 5 6)) = 32 (define (product x y) 終了 条件 (cond [(empty? x) 0] 自明な解 [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 64

65.

No (empty? x) Yes (+ (* (first x) (first y)) (product (rest x) (rest y))) 0 が自明な解である 65

66.

ベクトルの内積 product • product の内部に product が登場 (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) • product の実行が繰り返される 例: (product (list 1 2 3) (list 4 5 6)) = (+ (* 1 4) (product (list 2 3) (list 5 6))) 66

67.

例題8.ステップ実行 • 関数 product (例題7)について,実行結果に至 る過程を見る • (product (list 1 2 3) (list 4 5 6)) から 32 に至る過程を見 る • DrScheme の stepper を使用する (product (list 1 2 3) (list 4 5 6)) =… = (+ (* 1 4) (product (list 2 3) (list 5 6))) =… 基本的な計算式 = (+ 4 への展開 (+ 10 (product (list 3) (list 6)))) =… = (+ 4 (+ 10 (+ 18 (product empty empty)))) =… 演算の実行 = 32 67

68.

「例題8.ステップ実行」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • • Intermediate Student で実行すること 入力した後に,Execute ボタンを押す (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) (product (list 1 2 3) (list 4 5 6)) 例題7と同じ 2. DrScheme を使って,ステップ実行の様子を 確認しなさい (Step ボタン,Next ボタンを使用) • 理解しながら進むこと ☆ 次は,課題に進んでください 68

69.

(product (list 1 2 3) (list 4 5 6)) から 32 が得られる過程の概略 最初の式 (product (list 1 2 3) (list 4 5 6)) =… = (+ (* 1 4) (product (list 2 3) (list 5 6))) =… = (+ 4 (+ 10 (product (list 3) (list 6)))) =… = (+ 4 (+ 10 (+ 18 (product empty empty)))) コンピュータ内部での計算 =… 実行結果 = 32 69

70.

(product (list 1 2 3) (list 4 5 6)) から (+ 4 (product (list 2 3) (list 5 6))) が得られる過程 (product (list 1 2 3) (list 4 5 6)) = (cond (product (list 1 2 3) (list 4 5 6)) [(empty? (list 1 2 3)) 0] [else (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6))))]) この部分は = (cond = (+ 4 [false 0] (* (first (list 1 2 3)) (first (list 4 5 6))) (product (list 2 3) (list 5 6))) [else (+(product (rest (list 1 2 3)) (rest (list 4 5 6))))]) = (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ (* 1 (first (list 4 5 6))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ (* 1 4) (+ 10 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) (product (list 3) (list 6)))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ 4 (product (list 2 3) (rest (list 4 5 6)))) =… = (+ 4 (product (list 2 3) (list 5 6))) = (+ 4 (+ 10 (+ 18 (product empty empty)))) =… = 32 70

71.

(product (list 1 2 3) (list 4 5 6)) から (+ 4 (product (list 2 3) (list 5 6))) が得られる過程 (product (list 1 2 3) (list 4 5 6)) = (cond (product (list 1 2 3) (list 4 5 6)) [(empty? (list 1 2 3)) 0] [else (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6))))]) この部分は = (cond = (+ 4 [false 0] (* (first (list 1 2 3)) (first (list 4 5 6))) (product (list 2 3) (list 5 6))) [else (+(product (rest (list 1 2 3)) (rest (list 4 5 6))))]) = (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6)))) これは, = (+ (* 1 (first (list 4 5 6))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) (define (product x y) = (+ (* 1 4) (+ 10 (cond (product (rest (list 1 2 3)) (rest (list 4 5 6)))) (product (list 3) [(empty? x) (list 0] 6)))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ 4 (product (list 2 3) (rest (list 4 5 6)))) [else (+ (* (first x) (first =y)) =… (+ 4 (product (list 2 3) (list 5 6))) (product (rest x) (rest y)))])) = (+ 4 (+ 10 (+ 18 (product empty empty)))) の x を (list 1 2 3) で,y を (list 4 5 6) で置き換えたもの =… = 32 71

72.

今日のパソコン演習課題 72

73.

課題1 • 関数 list-sum (授業の例題1)についての問 題 • (list-sum (list 1 2 3)) から 6 が得られる過程の概略 を数行程度で説明しなさい • DrScheme の stepper を使うと,すぐに分かる (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) 73

74.

課題2 DrScheme の stepper を利用した実行エラーの解決 に関する問題 1. まずは,次を「定義用ウインドウ」で,実行しなさい – 入力した後に,Execute ボタンを押す ⇒ すると,実行用ウインドウに(赤い文字で)エラーメッ セージが表示される(これは実行エラー) (define (list-length a-list) (cond [(empty? a-list) 0] [else (+ 1 (list-length (rest a-list)))])) (list-length 100) 2. DrScheme で stepper を使ってステップ実行を行って, エラーの箇所を特定しなさい.エラーの原因について 報告しなさい. 74

75.

課題3 シンボル出現の判定プログラム作成 • シンボルのリスト a-list と,シンボル a-symbol から,a-list が a-symbol を含むときに限り true を返す関数 contains? を作りなさい 75

76.

課題3のヒント: すべての要素が10以上か? • リストの要素を調べ, • すべての要素が10以上 → true • そうでなければ → false (define (all-are-large alon) (cond [(empty? alon) true] [else (and (<= 10 (first alon)) (all-are-large (rest alon)))])) 76

77.

課題4 • リストの要素の中に 「偶数」を含むかどう か調べる関数を作りなさい • 偶数を1つでも含めば true.1つも含まなけれ ば false • even? を使うこと 77

78.

課題5 • n次の多項式 f(x) = a0 + a1・x + a2・x2+ ・・・ +ann・x について,次数 n と,係数 a0 から an から,f(x) を計算するプログラムを作りなさい • 次ページ以降で説明する Horner法を使うこと 78

79.

多項式の計算 • n次の多項式 f(x) = a0 + a1・x + a2・x2 + ・・・ +an・xn について,次数 n ,係数 a0 から an と x か らf(x) を計算する 79

80.

Horner法による多項式の計算 f(x) n = a0 + a1・x + a2・x2 + ・・・ +an・x = a0 + ( a1 + ( a2 + ・・・ + ( an-1 + an ・x ) x ・・・) x ) x 例えば, 5 + 6x + 3x = 5 + ( 6 + 3x2) x 計算手順 ① an ② an-1 + an・x ③ an-2 + ( an-1 + an・x ) x ・・・ (a0 まで続ける) 80

81.

さらに勉強したい人への 補足説明資料 81

82.

リストに関係する関数 • (length list) リストの要素の個数 • (list-ref list n) リストのn番目の要素(先頭は0番目) これらの関数と同じ機能を持つ関数 my-length, my-list-ref を敢えて書いて みた例を以下に紹介する 82

83.

例題9.リストの n 番目の要素 • リストの n 番目の要素(先頭は 0 番 目)を得る関数 my-list-ref を作り, 実行する 83

84.

まず,Scheme のプログラムを コンピュータに読み込ませている 84

85.

これは, (my-list-ref (list 11 12 13 14) 1) と書いて,a-list の値を (list 11 12 13 14) に, n の値を 1 に設定しての実行 実行結果である「12」が 表示される 85

86.

入力と出力 (list 11 12 13 14) 1 12 my-list-ref 入力 出力 86

87.

my-list-ref 関数 「関数である」ことを 示すキーワード 関数の名前 (define (my-list-ref a-list n) (cond [(= n 0) (first a-list)] [else (my-list-ref (rest a-list) (- n 1))])) 値を2つ受け取る(入力) a-list と n の値から n 番目の要素を求める(出力) 87

88.

(my-list-ref (list 11 12 13 14) 1) から12が得られる過程 (my-list-ref (list 11 12 13 14) 1) 最初の式 = (cond [(= 1 0) (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) = (cond [false (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) = (my-list-ref (rest (list 11 12 13 14) ) (- 1 1)) = (my-list-ref (list 12 13 14) (- 1 1)) = (my-list-ref (list 12 13 14) 0) = (cond [(= 0 0) (first (list 12 13 14))] [else (my-list-ref (rest (list 12 13 14) ) (- 0 1))]) = (cond [true (first (list 12 13 14))] [else (my-list-ref (rest (list 12 13 14) ) (- 0 1))]) コンピュータ内部での計算 = (first (list 12 13 14)) 88 = 12 実行結果

89.

(my-list-ref (list 11 12 13 14) 1) から12が得られる過程 (my-list-ref (list 11 12 13 14) 1) = (cond [(= 1 0) (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) = (cond [false (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) これは, = (my-list-ref (rest (list 11 12 13 14) ) (- 1 1)) (define (list (my-list-ref a-list = (my-list-ref 12 13 14) (1 1))n) = (my-list-ref (cond(list 12 13 14) 0) = (cond [(= n 0) (first a-list)] [(= 0 0) (first (list 12 13 14))] [else (my-list-ref 1))])) [else (my-list-ref (rest (list(rest 12 13a-list) 14) ) (-(-0 n 1))]) =の (cond a-list を (list 11 12 13 14) で,n を 1 で置き換えたも の [true (first (list 12 13 14))] [else (my-list-ref (rest (list 12 13 14) ) (- 0 1))]) = (first (list 12 13 14)) 89 = 12

90.

(my-list-ref (list 11 12 13 14) 1) から 12が得られる過程の概略 (my-list-ref (list 11 12 13 14) 1) =… = (my-list-ref (list 12 13 14) 0) = … = (first (list 12 13 14)) = 12 リストの1番目 の要素 リスト rest を取って, その0番目の要素 リストの先頭 90

91.

my-list-ref の「a-list」は「(list 11 12 13 14)」で 「n」は「1」で置き換わる 91

92.

「(= 1 0)」 は 「false」で置き換わる 92

93.

「(cond [false 式X] [else 式Y])」は 「式Y」で置き換わる 93

94.

「(rest (list 11 12 13 14))」は 「(list 12 13 14)」で置き換わる 94

95.

「(- 1 1)」は「0」で置き換わる 95

96.

my-list-ref の「a-list」は「(list 12 13 14)」で, 「n」は「0」で置き換わる 96

97.

「(= 0 0)」 は 「true」で置き換わる 97

98.

「(cond [true 式X] [else 式Y])」は 「式X」で置き換わる 98

99.

「(first (list 12 13 14))」は 「12」で置き換わる 99

100.

リストの n 番目の要素 1. n = 0 ならば: → 終了条件 リストの first → 自明な解 2. そうで無ければ: – 「リストの rest を求める(これもリ スト).その n-1 番目の要素」が求 める解 100

101.

リストの n 番目の要素 n > 0 のとき n 番目を探す ... first ... rest n-1 番目を探す ... ... 101

102.

リストの n 番目の要素 (define (my-list-ref a-list n) (cond 終了 [(= n 0) (first a-list)] 自明な解 条件 [else (my-list-ref (rest a-list) (- n 1))])) 102

103.

(= n 0) No Yes (my-list-ref (rest a-list) (- n 1)) (first a-list) が自明な解である 103

104.

リストの n 番目の要素 my-list-ref • my-list-ref の内部に my-list-ref が登場 (define (my-list-ref a-list n) (cond [(= n 0) (first a-list)] [else (my-list-ref (rest a-list) (- n 1))])) • my-list-ref の実行が繰り返される 例: (my-list-ref (list 11 12 13 14) 1) = (my-list-ref (list 12 13 14) 0) 104

105.

例題10.リストの長さ • リストの要素の個数を求める関数 my-length を作り,実行する 105

106.

まず,Scheme のプログラムを コンピュータに読み込ませている 106

107.

これは, (my-length (list 11 12)) と書いて,a-list の値を (list 11 12) に設定しての実行 実行結果である「2」が 表示される 107

108.

入力と出力 2 (list 11 12) my-length 入力 出力 108

109.

my-length 関数 「関数である」ことを 示すキーワード 関数の名前 (define (my-length a-list) (cond [(empty? a-list) 0] [else (+ 1 (my-length (rest a-list)))])) 値を1つ受け取る(入力) a-list の値から リストの長さを求める(出力) 109

110.

(my-list-ref (list 11 12)) から 2 が得られる過程 (1/2) (my-length (list 11 12)) 最初の式 = (cond [(empty? (list 11 12)) 0] [else (+ 1 (my-length (rest (list 11 12))))]) = (cond [false 0] [else (+ 1 (my-length (rest (list 11 12))))]) = (+ 1 (my-length (rest (list 11 12)))) = (+ 1 (my-length (list 12))) = (+ 1 (cond [(empty? (list 12)) 0] [else (+ 1 (my-length (rest (list 12))))])) = (+ 1 (cond [false 0] [else (+ 1 (my-length (rest (list 12))))])) コンピュータ内部での計算 110

111.

(my-list-ref (list 11 12)) から 2 が得られる過程 (2/2) = (+ 1 (+ 1 (my-length (rest (list 12))))) = (+ 1 (+ 1 (my-length empty))) = (+ 1 (+ 1 (cond [(empty? empty) 0] [else (+ 1 (my-length empty))])) = (+ 1 (+ 1 (cond [true 0] [else (+ 1 (my-length empty))])) = (+ 1 (+ 1 0)) コンピュータ内部での計算 = (+ 1 1) =2 実行結果 111

112.

(my-length (list 11 12)) から 2 が得られる過程の概略 (my-length (list 11 12)) (list 11 12) の長さ = ... = (+ 1 (my-length (list 12))) (list 12) の長さに1を足す = ... = (+ 1 (+ 1 (my-length empty))) empty の長さに2を足す = ... = (+ 1 (+ 1 0)) = (+ 1 1) =2 112

113.

よくある勘違い (define (my-length a-list) (cond [(= a-list empty) 0] [else (+ 1 (my-length (rest a-list)))])) 終了条件の判定: ・ 正しくは「(empty? a-list)」 ・ x がリストのとき、(= x empty) は実行エラー ・ 「=」は数値の比較には使えるが,リスト同士の比較に は使えない 113

114.

実行エラーの例 114

115.

リストの長さ 1. リストが空ならば: 0 → 終了条件 → 自明な解 2. そうで無ければ: • リストの rest を求める(これもリスト). 「その長さに1を足したもの」が,求め る総和である 115

116.

リストの長さ リストが空で無いとき 長さを求める ... first ... rest 長さを求める ... ... (それを1 と足す) 116

117.

リストの長さ (define (my-length a-list) (cond 終了条件 [(empty? a-list) 0] 自明な解 [else (+ 1 (my-length (rest a-list)))])) 117

118.

No (empty? a-list) Yes (+ 1 (my-length (rest a-list))) 0 が自明な解である 118

119.

リストの長さ my-length • my-length の内部に my-length が登場 (define (my-length a-list) (cond [(empty? a-list) 0] [else (+ 1 (my-length (rest a-list)))])) • my-length の実行が繰り返される 例: (my-length (list 11 12)) = = (+ 1 (my-length (list 12))) 119