---
title: HackMD presentation Sample1
tags: presentation
slideOptions:
theme: white
slideNumber: 'c/t'
center: false
transition: 'none'
keyboard: true
width: '93%'
height: '100%'
---
<style>
/* basic design */
.reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6,
.reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {
font-family: 'Meiryo UI', 'Source Sans Pro', Helvetica, sans-serif, 'Helvetica Neue', 'Helvetica', 'Arial', 'Hiragino Sans', 'ヒラギノ角ゴシック', YuGothic, 'Yu Gothic';
text-align: left;
line-height: 1.8;
letter-spacing: normal;
text-shadow: none;
word-wrap: break-word;
color: #444;
}
.reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6 {font-weight: bold;}
.reveal h1, .reveal h2, .reveal h3 {color: #2980b9;}
.reveal th {background: #DDD;}
.reveal section img {background:none; border:none; box-shadow:none; max-width: 95%; max-height: 95%;}
.reveal blockquote {width: 90%; padding: 0.5vw 3.0vw;}
.reveal table {margin: 1.0vw auto;}
.reveal code {line-height: 1.2;}
.reveal p, .reveal li {padding: 0vw; margin: 0vw;}
.reveal .box {margin: -0.5vw 1.5vw 2.0vw -1.5vw; padding: 0.5vw 1.5vw 0.5vw 1.5vw; background: #EEE; border-radius: 1.5vw;}
/* table design */
.reveal table {background: #f5f5f5;}
.reveal th {background: #444; color: #fff;}
.reveal td {position: relative; transition: all 300ms;}
.reveal tbody:hover td { color: transparent; text-shadow: 0 0 3px #aaa;}
.reveal tbody:hover tr:hover td {color: #444; text-shadow: 0 1px 0 #fff;}
/* blockquote design */
.reveal blockquote {
width: 90%;
padding: 0.5vw 0 0.5vw 6.0vw;
font-style: italic;
background: #f5f5f5;
}
.reveal blockquote:before{
position: absolute;
top: 0.1vw;
left: 1vw;
content: "\f10d";
font-family: FontAwesome;
color: #2980b9;
font-size: 3.0vw;
}
/* font size */
.reveal h1 {font-size: 5.0vw;}
.reveal h2 {font-size: 4.0vw;}
.reveal h3 {font-size: 2.8vw;}
.reveal h4 {font-size: 2.6vw;}
.reveal h5 {font-size: 2.4vw;}
.reveal h6 {font-size: 2.2vw;}
.reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {font-size: 2.2vw;}
.reveal code {font-size: 1.6vw;}
/* new color */
.red {color: #EE6557;}
.blue {color: #16A6B6;}
/* split slide */
#right {left: -18.33%; text-align: left; float: left; width: 50%; z-index: -10;}
#left {left: 31.25%; text-align: left; float: left; width: 50%; z-index: -10;}
</style>
<style>
/* specific design */
.reveal h1 {
margin: 0% -100%;
padding: 2% 100% 4% 100%;
color: #fff;
background: #fffa5e; /* fallback for old browsers */
background: linear-gradient(-45deg, #f7f439, #54ffa4, #23A6D5, #238ed5);
background-size: 200% 200%;
animation: Gradient 60s ease infinite;
}
@keyframes Gradient {
0% {background-position: 0% 50%}
50% {background-position: 100% 50%}
100% {background-position: 0% 50%}
}
.reveal h2 {
text-align: center;
margin: -5% -50% 2% -50%;
padding: 4% 10% 1% 10%;
color: #fff;
background: #fffa5e; /* fallback for old browsers */
background: -webkit-linear-gradient(to right, #c74646, #fffa5e); /* Chrome 10-25, Safari 5.1-6 */
background: linear-gradient(to right, #c74646, #fffa5e); /* W3C, IE 10+/ Edge, Firefox 16+, Chrome 26+, Opera 12+, Safari 7+ */
}
</style>
<!-- --------------------------------------------------------------------------------------- -->
# 第１５章 <br>新しい形の再帰
<br>
### 201803690 森田翔大
---
## 再帰関数の構造
```ocaml=
(*目的：受け取ったリストlstの各要素の和を求める＊)
(* sum : int list -> int *)
let rec sum lst = match lst with
[] -> 0
| first :: rest -> first + sum rest
```
再帰関数では、自明に答えが出るケースとそうでないケースに場合分けをする。
自明に答えが出るケースは入力が空リストだった場合。構造に従った再帰は入力した一部分を取り除くだけなので、ここではrestに再帰呼び出しをして、その結果とfirstを足している。
---
## 部分問題の作成（１）
例としてクイックソートを使用する。
問題を部分問題に分割して、それぞれを解く。その結果を用いて、全体の解を出す。
デザインレシピにしたがってプログラムを作っていく
___
目的
```ocaml=
(* 目的：受け取った整数のリストを昇順に並べる *)
(* quick_sort : int list -> int list *)
let rec quick_sort lst = []
```
例
```ocaml=
let test1 = quick_sort [] = []
let test2 = quick_sort [1] = [1]
let test3 = quick_sort [1; 2] = [1;2]
let test4 = quick_sort [2;1] = [1;2]
let test5 = quick_sort [5; 4; 9; 8; 2; 3]
= [2; 3; 4; 5; 8; 9]
```
___
本体の作成
一般の再帰を使う場合は、このタイミングで自明に答えが出るケースとそうでないケースで場合分けを行う。
先ほどと同様、自明に答えが出るケースはlstが空リストの時なので、再帰に対するテンプレートにlstが空という条件を加えると以下のようになる
```ocaml=
(*目的：受け取ったlstをクイックソートを使って昇順に整列する＊)
(*quick_sort : int list -> int list*)
let rec quick_sort lst =
if lst = []
then [] (*自明に答えが出るケース*)
else [] (*それ以外のケース*)
```
___
match文で表すと、
```ocaml=
(*目的：受け取ったlstをクイックソートを使って昇順に整列する＊)
(*quick_sort : int list -> int list*)
let rec quick_sort lst = match lst with
[] -> [] (*自明に答えが出るケース*)
| first :: rest -> [] (*それ以外のケース*)
```
---
## 部分問題の作成（２）
自明に答えが出ないケース
一般の再帰ではここで部分問題を作成する。
ここでは、firstを基準にして、restを二つに分割する。基準の要素より小さい要素のリストを返すものをtake_lessとし、大きい要素のリストを返すものをtake_greaterとする。
___
take_lessのヘッダ
```ocaml=
(*目的:lstの中からnより小さい要素のみを取り出す*)
(*take_less : int -> int list -> int list *)
let take_less n lst = [] (*未完成*)
```
take_greaterのヘッダ
```ocaml=
(* 目的:lstの中からnより大きい要素のみを取り出す*)
(*take_less : int -> int list -> int list *)
let take_greater n lst = [] (*未完成*)
```
___
この補助関数を用いて部分問題が作成できたので、テンプレートに打ち込む
```ocaml=
(* 目的：受け取ったlstをクイックソートを使って昇順に整列する *)
(* quick_sort : int list -> int list *)
let rec quick_sort lst = match lst with
[] -> [] (*自明に答えが出るケース*)
| first :: rest -> [] (*それ以外のケース*)
(*take_less first rest*)
(*take_greater first rest*)
```
___
まだ部分問題が作成できただけなので、再帰呼び出しをして部分問題を解かなくてはいけない。
```ocaml=
(* 目的：受け取ったlstをクイックソートを使って昇順に整列する *)
(* quick_sort : int list -> int list *)
let rec quick_sort lst = match lst with
[] -> [] (*自明に答えが出るケース*)
| first :: rest -> [] (*それ以外のケース*)
(* quick_sort (take_less first rest) *)
(* quick_sort (take_greater first rest) *)
```
___
あとはこれを上から順に繋げていけば完成するので、最終的には以下のようになる。
```ocaml=
(* 目的：受け取ったlstをクイックソートを使って昇順に整列する *)
(* quick_sort : int list -> int list *)
let rec quick_sort lst = match lst with
[] -> []
| first :: rest -> quick_sort (take_less first rest)
@ [first]
@ quick_sort (take_greater first rest)
```
---
## 補助関数の作成
テストプログラムがtrueを返さないのはtake_lessとtake_greaterが完成していないから。二つの違うところは大きいか小さいかだけなので、省略してtake_lessのみをやる。
デザインレシピに従って作ると、
```ocaml=
(* 目的:lstの中からnより小さい要素のみを取り出す *)
(* take_less : int -> int list -> int list *)
let rec take_less n lst = match lst with
[] -> []
| first :: rest -> if first < n
then first :: take_less n rest
else take_less n rest
```
となる。
___
filterを使って表すと、
```ocaml=
(* 目的 : lstの中からnより小さい要素のみを取り出す *)
(* take_less : int -> int lst -> int list *)
let take_less n lst = filter (fun item -> item < n) lst
```
___
これらを一般化した関数で表すと、
```ocaml=
(* 目的 : lstの中からnよりpである要素のみを取り出す *)
(* take : int -> int list -> (int -> int -> bool) -> int list *)
let take n lst p = filter (fun item -> p item n) lst
(* 目的 : lstの中からnより小さい要素のみを取り出す *)
(* take_less : int -> int list -> int list *)
let take_less n lst = take n lst (<)
(* 目的 : lstの中からnより大きい要素のみを取り出す *)
(* take_greater : int -> int list -> int list *)
let take_greater n lst = take n lst (>)
```
---
## 問題15.1
今作ったquick_sortではlstの中に重複した要素があった場合、その重複しているものと基準値の値が一緒のとき要素が取り除かれてしまう。
例
```ocaml=
let test1 = quick_sort [1;1] = [1]
let test2 = quick_sort [1;1;2;2;3;3] = [1;2;2;3;3]
```
よって、take_lessかtake_greaterのどっちかの不等号に=をつけなければいけない。
___
quick_sortの最終的な定義
```ocaml=
(* 目的：受け取った lst をクイックソートを使って昇順に整列する *)
(* quick_sort : int list -> int list *)
let rec quick_sort lst =
(* 目的：lst の中から n より p である要素のみを取り出す *)
(* take : int -> int list -> (int -> int -> bool) -> int list *)
let take n lst p = filter (fun item -> p item n) lst
(* 目的：lst の中から n より小さい要素のみを取り出す *)
(* take_less : int -> int list -> int list *)
in let take_less n lst = take n lst (<=)
(* 目的：lst の中から n より大きい要素のみを取り出す *)
(* take_greater : int -> int list -> int list *)
in let take_greater n lst = take n lst (>)
in match lst with
[] -> []
| first :: rest -> quick_sort (take_less first rest)
@ [first]
@ quick_sort (take_greater first rest)
```
---
## 停止性の判定
停止性とは、再帰呼び出しを行う際の部分問題が、何らかの意味でもとの問題よりも簡単になっていることと、それを繰り返すと、有限回で自明なケースに帰着することである。
しかし、部分問題が簡単になっていても有限回で終わらない時がある。
___
1/nの階乗を求めるプログラム
```ocaml=
(*目的 : 級数の第n項を求める*)
(* dai_n_kou : int -> float *)
let rec dai_n_kou n = if n = 0
then 1.0
else dai_n_kou (n - 1) /. float_of_int n
```
___
eを求めるプログラム
```ocaml=
(*目的 : e の近似値を求める*)
(* e : int -> float *)
let rec e n = if dai_n_kou n < 0.00001
then dai_n_kou n
else dai_n_kou n +. e (n + 1)
```
___
局所変数定義を用いて書くと
```ocaml=
(*目的 : eの近似値を求める*)
(* e : int -> float *)
let rec e n =
let d = dai_n_kou n in if d < 0.00001
then d
else d +. e (n + 1)
```
___
## 問題15.2(1)
```ocaml=
(* 目的：m > n > 0 なる自然数 m と n の最大公約数を求める *)
(* gcd : int -> int -> int *)
let rec gcd m n =
if n = 0
then m
else gcd n (m mod n)
```
これは再帰を行っていくにつれてnの値が減っていき、有限回で０になるので停止する。
___
## 問題15.2(2)
```ocaml=
(*テスト*)
# let test1 = gcd 7 5 = 1
let test2 = gcd 30 18 = 6
let test3 = gcd 36 24 = 12 ;;
val test1 : bool = true
val test2 : bool = true
val test3 : bool = true
#
```
---
## 問題15.3(1)
```ocaml=
(* 目的：2 から n までの自然数を受け取り 2 から n までの素数を返す *)
(* sieve : int list -> int list *)
let rec sieve lst = match lst with
[] -> []
| first :: rest ->
first :: sieve (List.filter (fun x -> x mod first <> 0) rest)
(* 再帰のたびに lst の長さが小さくなっているので、いずれ [] になり停止する *)
```
___
```ocaml=
(* テスト *)
# let test1 = sieve [2; 3; 4; 5; 6; 7; 8; 9; 10] = [2; 3; 5; 7] ;;
val test1 : bool = true
#
```
___
## 問題15.3(2)
まず初めに受け取った自然数を自然数のリストで返すものを作る
```ocaml=
(* 目的：2 から受け取った自然数 n までの自然数のリストを返す *)
(* two_to_n : int -> int list *)
let two_to_n n =
let rec loop i = if i <= n
then i :: loop (i + 1)
else []
in loop 2
```
___
```ocaml=
(* テスト *)
# let test2 = two_to_n 10 = [2; 3; 4; 5; 6; 7; 8; 9; 10] ;;
val test2 : bool = true
```
___
次に受け取った自然数を素数のみ返す関数を作る
```ocaml=
(* 目的：2 から受け取った自然数 n までの素数を返す *)
(* prime : int -> int list *)
let prime n = sieve (two_to_n n)
(* テスト *)
# let test3 = prime 10 = [2; 3; 5; 7] ;;
val test3 : bool = true
#
```
---
## 最短距離最小の点の分離
集合Vは最短距離が未確定の点、点Pは集合Vのなかの最短距離最小の点
集合Vが空リストのときが自明なケース、そうでないときは最短距離最小の点Pを確定しPを除いた集合Vを返す
パターンマッチではできない理由は、Vの中からPを求めるだけでなく、Pを除いたVのリストを返さなくてはいけないから
---
## 問題15.4(1)
eki_t list型のリストを受け取ったら、最短距離最小の駅Pと最短距離最小の駅以外からなる集合Vの組を返す関数saitan_wo_bunriを作る
```ocaml=
(* 目的：受け取った駅のリストを、最短距離最小の駅とそれ以外に分離する *)
(* saitan_wo_bunri : eki_t list -> eki_t * eki_t list *)
let rec saitan_wo_bunri eki_list = match eki_list with
[] -> ({namae = ""; saitan_kyori = infinity; temae_list = []}, [])
| first :: rest ->
let (p, v) = saitan_wo_bunri rest in match (first, p) with
({namae = fn; saitan_kyori = fs; temae_list = ft},
{namae = sn; saitan_kyori = ss; temae_list = st}) ->
if sn = "" then (first, v)
else if fs < ss then (first, p :: v)
else (p, first :: v)
```
___
## 問題15.4(2)
```ocaml=
(* 駅の例 *)
let eki1 = {namae="池袋"; saitan_kyori = infinity; temae_list = []}
let eki2 = {namae="新大塚"; saitan_kyori = 1.2; temae_list = ["新大塚"; "茗荷谷"]}
let eki3 = {namae="茗荷谷"; saitan_kyori = 0.; temae_list = ["茗荷谷"]}
let eki4 = {namae="後楽園"; saitan_kyori = infinity; temae_list = []}
(* 駅リストの例 *)
let lst = [eki1; eki2; eki3; eki4]
```
___
## 問題15.4(3)
```ocaml=
(*テスト*)
# let test = saitan_wo_bunri lst ;;
val test : eki_t * eki_t list =
({namae = "茗荷谷"; saitan_kyori = 0.; temae_list = ["茗荷谷"]},
[{namae = "池袋"; saitan_kyori = infinity; temae_list = []};
{namae = "新大塚"; saitan_kyori = 1.2;
temae_list = ["新大塚"; "茗荷谷"]};
{namae = "後楽園"; saitan_kyori = infinity; temae_list = []}])
#
```
___
## 問題15.5(1)
```ocaml=
(* 目的：受け取った駅のリストを、最短距離最小の駅とそれ以外に分離する *)
(* saitan_wo_bunri : eki_t list -> eki_t * eki_t list *)
let saitan_wo_bunri eki_list =
List.fold_right (fun first (p, v) ->
match (first, p) with
({namae = fn; saitan_kyori = fs; temae_list = ft},
{namae = sn; saitan_kyori = ss; temae_list = st}) ->
if sn = "" then (first, v)
else if fs < ss then (first, p :: v)
else (p, first :: v))
eki_list
({namae = ""; saitan_kyori = infinity; temae_list = []}, [])
```
___
## 問題15.5(2)
```ocaml=
(*テスト*)
# let test = saitan_wo_bunri lst ;;
val test : eki_t * eki_t list =
({namae = "茗荷谷"; saitan_kyori = 0.; temae_list = ["茗荷谷"]},
[{namae = "池袋"; saitan_kyori = infinity; temae_list = []};
{namae = "新大塚"; saitan_kyori = 1.2;
temae_list = ["新大塚"; "茗荷谷"]};
{namae = "後楽園"; saitan_kyori = infinity; temae_list = []}])
#
```
___
## 例の作成とデバックについて
プログラムが複雑になると間違いも多くなり、原因の解明も難しくなる。よって例を作って段階的に解く。
ミスが起こった場合は、まず動作のおかしいところを特定しなくてはいけない。その際、関数がテストデータに対して思った通りの値を返しているかで判断する。返していないときはテストプログラムを作り直し、間違いを訂正していく。
またその際、考え方に抜けがあった際は最初からやり直す。
___
Sign in with Wallet
Connect another wallet