sp-12. 再帰と繰り返しの回数

>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-12. 再帰と繰り返しの回数 (Scheme プログラミング) URL: https://www.kkaneko.jp/cc/scheme/index.html 金子邦彦 1

2.

アウトライン 12-1 繰り返し計算 12-2 パソコン演習 12-3 課題 2

3.

本日の内容 • 再帰を使った,繰り返し計算 • 数学の「再帰的定義」と,Scheme プログラムの関係 • 繰り返し回数 • 関数は「何回繰り返して」実行され るか 3

4.

12-1 繰り返し計算 4

5.

繰り返しの例 • 階乗 • 「n - 1 の階乗」に n を足すことを繰り返す • ユークリッドの互助法 • m と n の最大公約数を求めるために,「割った余 りを求めること」を,余りが0になるまで繰り返 す 5

6.

12- 2 パソコン演習 6

7.

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

8.

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

9.

例題1. 階乗 • 階乗を計算する関数 ! を作り,実行す る • 次の方針でプログラムを作成する n > 0 のとき,n! = n × (n-1)! 例) 6! = 6×5! 9

10.

階乗 • n = 0 のとき n! = 1 • n > 0 のとき n ! = n  ( n − 1 )! 10

11.

「例題1.階乗」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す ;;! : number -> number ;;to compute n*(n-1)*...*2*1 (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) 2. その後,次を「実行用ウインドウ」で実行しなさい (! 3) (! 4) ☆ 次は,例題2に進んでください 11

12.

「例題1.階乗」の実行結果 12

13.

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

14.

これは, (! 4) と書いて,n の値を 4 に設定しての実行 実行結果である「24」が 表示される 14

15.

入力と出力 24 4 入力 入力は数値 ! 出力 出力は数値 15

16.

! 関数 ;; ! : number -> number ;; to compute n*(n-1)*...*2*1 ;; Example: (! 4) = 24 (define (! n) (cond 0! = 1 である [(= n 0) 1] [else (* n (! (- n 1)))])) n! は (n-1)! を計算して,n を掛ける 16

17.

階乗 1. n = 0 ならば: 1 → 終了条件 → 自明な解 2. そうで無ければ: – 「n - 1 の階乗」に n をかける ⇒ 結局,1 から n までのかけ算を繰り返 す 17

18.

階乗 ;; ! : number -> number ;; to compute n*(n-1)*...*2*1 ;; (! 4) = 24 (define (! n) (cond 終了条件 [(= n 0) 1] 自明な解 [else (* n (! (- n 1)))])) 18

19.

終了条件 (= n 0) No Yes (* n (! (- n 1))) 1 が自明の解 19

20.

階乗 • ! の内部に ! が登場 (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) • ! の実行が繰り返される 例: (! 5) = (* 5 (! 4)) (! 4) = (* 4 (! 3)) 20

21.

例題2.ステップ実行 • 関数 ! (例題1)について,実行結果に至る過程 を見る • (! 3) から 6 に至る過程を見る • DrScheme の stepper を使用する (define (! n) (cond [(= n 0) 1] [else (* n (! (- n 1)))])) (! 3) = ... = (* 3 (! 2)) = ... = (* 3 (* 2 (! 1))) = ... = (* 3 (* 2 (* 1 (! 0)))) = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) = 6 21

22.

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

23.

! の「n」は「3」で置き換わる 23

24.

「(= 3 0)」は「false」で 置き換わる 24

25.

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

26.

「(- 3 1)」は,「2」で 置き換わる 26

27.

! の「n」は「2」で置き換わる 27

28.

「(= 2 0)」は「false」で 置き換わる 28

29.

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

30.

「(- 2 1)」は,「1」で 置き換わる 30

31.

! の「n」は「1」で置き換わる 31

32.

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

33.

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

34.

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

35.

! の「n」は「1」で置き換わる 35

36.

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

37.

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

38.

「(* 1 1)」は,「1」で 置き換わる 38

39.

「(* 2 1)」は,「2」で 置き換わる 39

40.

「(* 3 2)」は,「6」で 置き換わる 40

41.

(! 3) から 6 が得られる過程の概略 最初の式 (! 3) = ... = (* 3 (! 2)) = ... = (* 3 (* 2 (! 1))) = ... = (* 3 (* 2 (* 1 (! 0)))) = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) コンピュータ内部での計算 = 6 実行結果 41

42.

(! 3) から 6 が得られる過程の概略 (! 3) = ... = (* 3 (! 2)) この部分は = ... = (* 3 (* 2 (! 1))) = ... = (* 3 (* 2 (* 1 (! 0)))) = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) = 6 (! 3) = (cond [(= 3 0) 1] [else (* 3 (! (- 3 1)))]) = (cond [false 1] [else (* 3 (! (- 3 1)))]) = (* 3 (! (- 3 1))) = (* 3 (! 2)) 42

43.

(! 3) から 6 が得られる過程の概略 (! 3) = ... = (* 3 (! 2)) = = = = = = = = この部分は (! 3) = (cond [(= 3 0) 1] [else (* 3 (! (- 3 1)))]) = (cond [false 1] [else (* 3 (! (- 3 1)))]) = (* 3 (! (- 3 1))) = (* 3 (! 2)) ... (* 3 (* 2 (! 1))) これは, ... (* (define 3 (* 2 (* (! 1 (!n)0)))) ... (cond (* 3 (* [(= 2 (*n1 0) 1)))1] (* 3 (* [else 2 1)) (* n (! (- n 1)))])) の を 3 で置き換えたもの (* 3n 2) = 6 43

44.

(! 3) から 6 に至る過程 (! 3) = ... = (* 3 (! 2)) = ... = (* 3 (* 2 (! 1))) = ... = (* 3 (* 2 (* 1 (! 0)))) = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) = (* 3 2) = 6 基本的な計算式への展開 「(! 3)」 が膨張して 「(* 3 (* 2 (* 1 (! 0))))」 になる 演算の実行 「(* 3 (* 2 (* 1 (! 0))))」 が収縮して6になる 44

45.

線形再帰的プロセス • 基本的な計算式へ展開 例 (! 3) ⇒ (* 3 (* 2 (* 1 (! 0)))) 再帰の呼び出し回数(=ステップ 数ともいう)に比例して成長する ⇒ 「線形再帰」の名前の由来 45

46.

! が繰り返される回数 (! 3) ① = ... = (* 3 (! 2)) ② = ... = (* 3 (* 2 (! 1))) ③ = ... = (* 3 (* 2 (* 1 (! 0)))) ④ = ... = (* 3 (* 2 (* 1 1))) = (* 3 (* 2 1)) n=3 のとき, = (* 3 2) = 6 4回繰り返して実行される 46

47.

! が繰り返される回数 (! 4) ① = ... = (* 4 (! 3)) ② = ... = (* 4 (* 3 (! 2))) ③ = ... = (* 4 (* 3 (* 2 (! 1)))) ④ = ... = (* 4 (* 3 (* 2 (* 1 (! 0))))) ⑤ = ... = (* 4 (* 3 (* 2 (* 1 1)))) = (* 4 (* 3 (* 2 1))) n=4 のとき, = (* 4 (* 3 2)) 5回繰り返して実行される = (* 4 6) 47 = 24

48.

例題3. 反復的プロセスでの階乗 • 階乗を計算する関数 ! を作り,実行す る • 次の方針でプログラムを作成する n > 0 のとき,1 から開始して,1 × 2 ×・・・×n を計算する 例) (! 6) = 1 × 2 × 3 × 4 × 5 × 6 48

49.

反復的プロセスでの階乗 • n! の計算 1. 2. 3. 4. まず,1 に 2 を掛ける 次に,3 を掛ける ・・・ n に達するまで続ける 49

50.

「例題3.反復的プロセスでの階乗」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す ;; ! : number -> number ;; to compute n*(n-1)*...*2*1 ;; (! 4) = 24 (define (! n) (factorial 1 1 n)) (define (factorial product counter max) (cond [(> counter max) product] [else (factorial (* counter product) (+ counter 1) max)])) 2. その後,次を「実行用ウインドウ」で実行しなさい (! 4) (! 10) (! 20) ☆ 次は,例題4に進んでください 50

51.

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

52.

これは, (! 4) と書いて,n の値を 4 に設定しての実行 実行結果である「24」が 表示される 52

53.

入力と出力 24 4 ! 入力 入力は数値 出力 出力は数値 53

54.

! 関数 ;; ! : number -> number ;; to compute n*(n-1)*...*2*1 ;; (! 4) = 24 (define (! n) (factorial 1 1 n)) (define (factorial product counter n) (cond product ← counter・product [(> counter n) product] [else (factorial (* counter product) (+ counter 1) n)])) counter ← counter + 1 54

55.

反復的プロセスでの階乗 counter: 1 から n まで数えるカウンタ product: 部分積(計算の途中結果) とする. product ← counter・product counter ← counter + 1 を繰り返す.counter が n に達すると n!が求まる 55

56.

反復的プロセスでの階乗 1. counter > n ならば:→ 終了条件 product → 自明な解 2. そうで無ければ: 次を実行する product ← counter・product counter ← counter + 1 56

57.

反復的プロセスでの階乗 ;; ! : number -> number ;; to compute n*(n-1)*...*2*1 終了条件 ;; (! 4) = 24 (define (! n) (factorial 1 1 n)) (define (factorial product counter n) (cond 自明な解 [(> counter n) product] [else (factorial (* counter product) (+ counter 1) n)])) 57

58.

終了条件 (> counter n) Yes No (factorial (* counter product) (+ counter 1) n) product が自明の解 58

59.

例題4.ステップ実行 • factorial の内部に factorial が登場 (define (factorial product counter n) (cond [(> counter n) product] [else (factorial (* counter product) (+ counter 1) n)])) • factorial の実行が繰り返される 例: (factorial 6 4 10) = (factorial 24 5 10) (factorial 24 5 10) = (factorial 120 6 10) 59

60.

例題4.ステップ実行 • 関数 ! (例題3)について,実行結果に至る過程 を見る • (! 4) から 24 に至る過程を見る • DrScheme の stepper を使用する (define (factorial product counter n) (cond [(> counter n) product] [else (factorial (* counter product) (+ counter 1) n)])) (! 4) = (factorial 1 1 4) = ... = (factorial 1 2 4) = ... = (factorial 2 3 4) = ... = (factorial 6 4 4) = ... = (factorial 24 5 4) = ... = 24 60

61.

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

62.

(! 4) から 24 が得られる過程の概略 (! 4) 最初の式 = (factorial 1 1 4) = ... = (factorial 1 2 4) = ... = (factorial 2 3 4) = ... = (factorial 6 4 4) = ... = (factorial 24 5 4) = ... コンピュータ内部での計算 = 24 実行結果 62

63.

(! 4) から 24 が得られる過程の概略 (! 4) = (factorial 1 1 4) = ... = (factorial 1 2 4) product, counter の = ... 値が変化する = (factorial 2 3 4) ・counter = ... → 繰り返し回数 = (factorial 6 4 4) ・product = ... → 部分積 = (factorial 24 5 4) = ... = 24 product counter max 63

64.

反復的プロセスの特徴 • 線形再帰的プロセスのような伸び縮みは無い • 関数を再帰的に呼び出す各ステップで計算が実 行される 例 (! 3) = (factorial 1 1 3) = (factorial 1 2 3) = (factorial 2 3 3) = (factorial 6 4 3) 伸び縮み無し 各ステップで, product と counter に関する計算が 実行される 64

65.

(factorial 1 1 4) から (factorial 1 2 4) が得られる過程 (! 4) (factorial 1 1 4) = (factorial 1 1 4) = (cond = ... [(> 1 4) 1] = (factorial 1 2 4) この部分は [else (factorial (* 1 1) (+ 1 1) = ... 4)]) = (factorial 2 3 4) = (cond [false 1] = ... [else (factorial (* 1 1) = (factorial 6 4 4) (+ 1 1) 4)]) = ... = (factorial (* 1 1) (+ 1 1) 4) = (factorial 24 5 4) = (factorial 1 (+ 1 1) 4) = ... = (factorial 1 2 4) = 24 65

66.

(factorial 1 1 4) から (factorial 1 2 4) が得られる過程 (! 4) (factorial 1 1 4) = (factorial 1 1 4) = (cond = ... [(> 1 4) 1] = (factorial 1 2 4) この部分は [else (factorial (* 1 1) (+ 1 1) = ... 4)]) = (factorial 2 3 4) = (cond これは, [false 1] = ...(define (factorial product counter n) [else (factorial (* 1 1) (cond = (factorial 6 4 4) (+ 1 1) [(> counter n) product] 4)]) = ... [else (factorial (* counter product) (+ counter 1) = (factorial (* 1 1) (+ 1 1) 4) = (factorial 24 n)])) 5 4) = (factorial 1 (+ 1 1) 4) counter を 1 で,product を 1 で,n を 4 で置き換えたもの = の... = (factorial 1 2 4) = 24 66

67.

(! 4) から (* 4 (! 3)) が得られる過程 (! 4) (! 4) = ... = (cond = (* 4 (! 3)) [(= 4 0) 1] この部分は [else (* 4 (! (- 4 1)))]) = ... = (cond = (* 4 (* 3 (! 2))) [false 1] = ... [else (* 4 (! (- 4 1)))]) これは, = (* 4 (* 3 (* 2 (! 1)))) = (* 4 (! (- 4 1))) = ... (define (! n) = (* 4 (! 3)) = (* 4 (* 3 (* 2 (* 1 (! 0))))) = ... (cond = (* 4 (* [(= 3 (*n2 0) (* 1] 1 1)))) = (* 4 (* [else 3 (* 2 (* 1)))n (! (- n 1)))])) = の (* 4n (* を342))で置き換えたもの = (* 4 6) = 6 67

68.

factorial が繰り返される回数 (! 4) = (factorial 1 1 4) ① = ... = (factorial 1 2 4) ② = ... = (factorial 2 3 4) ③ = ... = (factorial 6 4 4) ④ = ... = (factorial 24 5 4) ⑤ n=4 のとき, = ... 5回繰り返して実行される 68 = 24

69.

例題5.繰り返し回数 • 次のプログラムでは,square は何回実行されるか (define (square x) (* x x)) (define (total-square x) (cond [(empty? x) 0] [else (+ (square (first x)) (total-square (rest x)))])) 69

70.

繰り返し回数 実行結果の例 (total-square (list 10 20 30)) 1400 • square は,リストの要素数だけ実行される 70

71.

例題6.最大公約数の計算 • ユークリッドの互助法を使って,2つ の整数 m, n から,最大公約数を求める プログラム my-gcd を作り,実行する 例) 180, 32 のとき: 4 • ユークリッドの互助法を用いる 71

72.

ユークリッドの互助法 • 2つの整数 m, n の最大公約数: (m, n は正または0) • n = 0 なら 最大公約数は m • n ≠ 0 なら 最大公約数は, 「m を n で割った余り」 と n の最大公 約数に等しい 72

73.

「例題6.最大公約数の計算」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す ;; my-gcd: number number -> number ;; to find the greatest common divisor of n and m ;; Example: (my-gcd 180 32) = 4 (define (my-gcd m n) (cond [(= n 0) m] [else (my-gcd n (remainder m n))])) 2. その後,次を「実行用ウインドウ」で実行しなさい (mygcd 180 32) ☆ 次は,例題7に進んでください 73

74.

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

75.

これは, (my-gcd 180 32) と書いて,m の値を 180 に, n の値を 32 に設定しての実行 実行結果である「4」が 表示される 75

76.

入力と出力 180 32 4 my-gcd 入力 入力は,2つの数値 出力 出力は数値 76

77.

my-gcd 関数 ;; my-gcd: number number -> number ;; to find the greatest common divisor of n and m ;; Example: (my-gcd 180 32) = 4 (define (my-gcd m n) (cond [(= n 0) m] [else (my-gcd n (remainder m n))])) 77

78.

最大公約数の計算 1. n = 0 ならば: m → 終了条件 → 自明な解 2. そうで無ければ: (1) n (2) m を n で割った余り の2数の最大公約数を求める. 以上のことを,n が0に達するまで繰り返す 78

79.

;; my-gcd: number number -> number ;; to find the greatest common divisor of n and m ;; Example: (my-gcd 180 32) = 4 (define (my-gcd m n) (cond 終了 条件 [(= n 0) m]自明な解 [else (my-gcd n (remainder m n))])) 79

80.

終了条件 (= n 0) No Yes (my-gcd n (remainder m n) m が自明の解 80

81.

最大公約数の計算 • my-gcd の内部に my-gcd が登場 (define (my-gcd m n) (cond [(= n 0) m] [else (my-gcd n (remainder m n))])) • my-gcd の実行が繰り返される 例: (my-gcd 180 32) = (my-gcd 32 20) 81

82.

例題7.ステップ実行 • 関数 my-gcd (例題6)について,実行結果に至 る過程を見る • (my-gcd 180 32) から 4 に至る過程を見る • DrScheme の stepper を使用する (define (my-gcd m n) (cond [(= n 0) m] [else (my-gcd n (remainder m n))])) (my-gcd 180 32) =… = (my-gcd 32 20) =… = (my-gcd 20 12) =… = (my-gcd 12 8) =… = (my-gcd 8 4) =… = (my-gcd 4 0) =… =4 82

83.

「例題7.ステップ実行」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • • Intermediate Student で実行すること 入力した後に,Execute ボタンを押す ;; my-gcd: number number -> number ;; to find the greatest common divisor of n and m ;; Example: (my-gcd 180 32) = 4 例題6 (define (my-gcd m n) (cond と同じ [(= n 0) m] [else (my-gcd n (remainder m n))])) (my-gcd 180 32) 2. DrScheme を使って,ステップ実行の様子を 確認しなさい (Step ボタン,Next ボタンを使用) • 理解しながら進むこと ☆ 次は,課題に進んでください 83

84.

(my-gcd 180 32) から 4 が得られる過程の概略 (my-gcd 180 32) 最初の式 =… = (my-gcd 32 20) =… = (my-gcd 20 12) =… = (my-gcd 12 8) =… = (my-gcd 8 4) =… = (my-gcd 4 0) =… コンピュータ内部での計算 =4 実行結果 84

85.

(my-gcd 180 32)から (my-gcd 32 20) が得られる過程 (my-gcd 180 32) =… = (my-gcd 32 20) =… = (my-gcd 20 12) =… = (my-gcd 12 8) =… = (my-gcd 8 4) =… = (my-gcd 4 0) =… =4 (my-gcd 180 32) = (cond [(= 32 0) 180] この部分は [else (my-gcd 32 (remainder 180 32))]) = (cond [false 180] [else (my-gcd 32 (remainder 180 32))]) = (my-gcd 32 (remainder 180 32)) = (my-gcd 32 20) 180 を 32 で割った余り は 20 85

86.

(my-gcd 180 32) から (my-gcd 32 20) が得られる 過程 (my-gcd 180 32) (my-gcd 180 32) =… = (cond = (my-gcd 32 20) [(= 32 0) 180] =… この部分は [else (my-gcd 32 = (my-gcd 20 12) (remainder 180 32))]) =… = (cond = (my-gcd 12 8) [false 180] これは, =… [else (my-gcd 32 (define (my-gcd m n) = (my-gcd 8 4) (remainder 180 32))]) = (my-gcd 32 = … (cond [(= 4n 0) 0) m] (remainder 180 32)) = (my-gcd [else (my-gcd n = (my-gcd 32 20) =… (remainder m n))])) =4 の m を 180 で,n を 32 で置き換えたもの 86

87.

my-gcd が繰り返される回数 (my-gcd 180 32) ① =… = (my-gcd 32 20) ② =… = (my-gcd 20 12) ③ =… = (my-gcd 12 8) ④ =… = (my-gcd 8 4) ⑤ =… = (my-gcd 4 0) ⑥ =… m=180, =4 n=32 のとき, 6回繰り返して実行される 87

88.

12-3 課題 88

89.

課題1 • 関数 my-gcd (授業の例題6)に関する問題 • (my-gcd 210 66) から 6 が得られる過程の概略を 数行程度で説明しなさい • DrScheme の stepper を使うと,すぐに分かる 89

90.

課題2 バックの中のコインの合計を求める関数 sum-coin についての問題 • • • 下記の空欄を埋めて,関数 sum-coins の定義を終 えなさい.実行結果も報告しなさい sum-coins は,コインの個数のリストと,コイン の金額のリストの2つのリストを入力とする ;; Contract: sum-coins : a-list-of-numbers a-list-of-numbers -> number ;; Example: (sum-coins (list 23 0 5 7) (list 1 5 10 25)) = 248 (define (sum-coins a b) (cond [( [else (+ (* ( ( ( ) ) ( ] )) ) ( )))])) 90

91.

課題2のヒント • ここにあるのは「間違い」の例です.同じ間 違いをしないこと 1.(= a empty) は間違い ⇒ a がリストのとき、(= a empty) はエラーです. 「=」は数値の比較には使えるが,リスト同士 の比較には使えないものと考えて下さい 正しくは,(empty? a) です 91

92.

課題3.繰り返し回数 • 関数 my-gcd (授業の例題6)に関する問題 • m, n の最大公約数を,ユークリッドの互助法で求 めた場合と,次ページに示すような方法で求めた場 合とで,関数の繰り返し回数を比較し,自分なりの 考察を加えて報告しなさい 92

93.

(define (first-divisor n m i) (cond [(= i 1) 1] [else (cond [(and (= (remainder n i) 0) (= (remainder m i) 0)) i] [else (first-divisor n m (- i 1))])])) (define (gcd-structural n m) (first-divisor n m (min n m))) 「i で割り切れるかを調べながら, i を1減らす」ことを,割り切れる まで繰り返す 1. まず,n と m の小さい方を変数 i に入れる. 2. i が n と m の両方を割れれば i の値を返し,終了. 3. i の値を1小さくして2へ. → n と m は変わらない.i が変化 93

94.

課題4.エラトステネスのふるい • 「エラトステネスのふるい」の原理に基づ いて100以下の素数を求めるプログラムを作 りなさい 94

95.

エラトステネスのふるい (1/4) 2 3 4 5 6 7 8 9 10 11 ・・・ 2×2 2×3 2×4 2×5 まず,2の倍数を消す 95

96.

エラトステネスのふるい (2/4) 2 3 4 5 6 7 8 9 10 11 ・・・ 3×2 3×3 次に,3の倍数を消す 96

97.

エラトステネスのふるい (3/4) 2 3 4 5 6 7 8 9 10 11 ・・・ 5×2 次に,5の倍数を消す (「4の倍数」は考えない. それは,「4」がすでに消えているから)97

98.

エラトステネスのふるい (4/4) 2 3 4 5 6 7 8 9 10 11 ・・・ 以上のように,2,3,5・・・の倍数を消す. 10(これは100の平方根)を超えたら,この操作を止める (100以下で,11,13・・・の倍数はすでに消えている) 98