# 問題解決力を鍛える！アルゴリズムとデータ構造
## 日程
2022/12/23
## 第4.1~4.3章
- 任意参加
- ファシリテーター: Chen
### 話す・書く順番決めルーレット
in Ruby
```ruby
['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }
```
in JavaScript
```javascript
const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]
```
### ファシリテーター決め方
- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく
### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）
当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分
### 勉強会時にやること
各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め
## 各自が書き込む場所
>[name=tsujita]
> 4.1
本のサンプルコードをrubyで書いてみました
```ruby=
def func(n)
if (n == 0)
return 0
else
return n + func(n - 1)
end
end
```
- 再起させる時はベースケースに対する処理を必ず行う
- 再起呼び出しを行った時の引数が、ベースケースに近づくようにすること
- いつも再起させたくてうまくできない・・となっていたので学びだった
> ユークリッドの互除法
手を動かすとなるほど！となるけど使い所は正直謎でした
> フィボナッチ数列
```ruby=
def fibo(n)
if n == 0
return 0
elsif n == 1
return 1
else
return fibo(n - 1) + fibo(n - 2)
end
end
```
>[name=okura]
### 4.1 再帰とは
Catalのコードベースで再帰を使っていた箇所があったような気がするが、思い出せない…
プログラマは再帰が好きで、再帰的頭字語が有名。Yaml Ain't Markup Languageとか、PHP: Hypertext preprocessorとか。
再帰は「ゆきてかえりし物語」になっている。これは『ホビットの冒険』の副題で、"There and back again"
### 4.2 再帰の例(1)：ユークリッドの互除法
このコードが高速なのは後述される繰り返しがないからなのかな。
整数論、昔大学受験のためにちょこっとだけ勉強したし、大学時代にも整数論の本を読んだことがあった気がするけど、今勉強したらまた違って見えるのだろうなあ。
https://inupri.web.fc2.com/ichihashi.html
### 4.3 再帰の例(2)：フィボナッチ数列
フィボナッチ数列はあまりにも有名すぎて、むしろ再帰以外の方法で書くほうが難しい気がする。
```ruby=
def fibo(n)
if n == 0
return 0
elsif n == 1
return 1
else
define_method("fibo#{n}") { |i| method(:fibo).call(i) }
return send("fibo#{n}", n - 1) + send("fibo#{n}", n - 1)
end
end
p fibo(10)
```
>[name=teruya]
> p.95 再帰関数のテンプレート
この考え方が身についてから、だいぶ理解がしやすくなりました！！！
（再帰関数の先頭で、returnするifのケースを記述する）
DFS（深さ優先探索）もこんな感じ
> p.96 ユークリッドの互除法
1番わかりやすい例（再帰が1本道なので）
RubyにはInteger#gcdがあります
https://docs.ruby-lang.org/ja/latest/method/Integer/i/gcd.html
lcm（最小公倍数）もあります
https://docs.ruby-lang.org/ja/latest/method/Integer/i/lcm.html
> p.98 フィボナッチ数列
4.4 に出てくるfor文ループの方がわかりやすい＆自然と動的計画法になる気がする（人間が考える時の手順と同じになる）
1つのArrayで↓を表現する感じ
0, 1
0, 1, 1
0, 1, 1, 2
0, 1, 1, 2, 3,
0, 1, 1, 2, 3, 5 ....
4.1 トリボナッチ数列
```ruby=
def trib(num)
return 0 if num == 0
return 0 if num == 1
return 1 if num == 2
return trib(num - 1) + trib(num - 2) + trib(num - 3)
end
puts trib(gets.to_i)
```
4.2 ↑のメモ化
```ruby=
def memo_trib(num)
return 0 if num == 0
return 0 if num == 1
return 1 if num == 2
return $memo[num] if $memo[num]
return $memo[num] = memo_trib(num - 1) + memo_trib(num - 2) + memo_trib(num - 3)
end
num = gets.to_i
$memo = Array.new(num + 1)
# $memo[0] = 0
# $memo[1] = 0
# $memo[2] = 1
puts memo_trib(num)
p $memo
```
> [name=chen]
### 再帰：自分自身を呼び出すこと
> - 「スタック領域」：この「ベースケースに対する処理」がとても大切です。ベースケースの処理を行わないと、再帰呼び出しを無限に繰り返すことになります。
再帰は難しいと思いますが、その「スタック領域」の概念は非常重要だと思います。ベースケースが分かるどこから着手するのも分かるから。
#### 再帰の例 (1)：ユークリッドの互除法
> - ２つの整数 m,n の最大公約数GCD(m, n)を求めるアルゴリズムです
> - ユークリッドの互除法の計算量は、m>=n>0 として、O(logn)となります
ここまで理解できる、再帰の簡単な例と思います。
#### 再帰の例(2)：フィボナッチ数列
- ex. 0,1,1,2,3,5,8,13,21,34...
- 章末問題4.1（トリボナッチ数列）：
https://jsfiddle.net/cgm1jkaf/5/
```javascript=
function tribo(n){
// 再帰関数を呼び出す
console.log(`tribo(${n})を呼び出しました`)
if(n <= 1) return 0
if(n == 2) return 1
const result = tribo(n-1) + tribo(n-2) + tribo(n-3)
// 答えを示す
console.log('')
console.log(`${n} 項目 = ${result}`)
return result
}
// 0,0,1,1,2,4,7,13,24
const test = tribo(8)
console.log(test)
/* ===Output===
"tribo(8)を呼び出しました"
"tribo(7)を呼び出しました"
"tribo(6)を呼び出しました"
"tribo(5)を呼び出しました"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
""
"5 項目 = 4"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
""
"6 項目 = 7"
"tribo(5)を呼び出しました"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
""
"5 項目 = 4"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
""
"7 項目 = 13"
"tribo(6)を呼び出しました"
"tribo(5)を呼び出しました"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
""
"5 項目 = 4"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
""
"6 項目 = 7"
"tribo(5)を呼び出しました"
"tribo(4)を呼び出しました"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
""
"4 項目 = 2"
"tribo(3)を呼び出しました"
"tribo(2)を呼び出しました"
"tribo(1)を呼び出しました"
"tribo(0)を呼び出しました"
""
"3 項目 = 1"
"tribo(2)を呼び出しました"
""
"5 項目 = 4"
""
"8 項目 = 24"
*/
```
```ruby=
$memo = Array.new(num + 1) do |i|
case i
when 0, 1 then 0
when 2 then 1
else nil
end
end
```
## 振り返り
> [name=tsujita]
再起何処かで使いたい・・
> [name=okura]
https://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0%E7%9A%84%E9%A0%AD%E5%AD%97%E8%AA%9E
> [name=teruya]
再帰まじでむずかしい（キューを使ったBFS（幅優先探索）の方がわかりやすい）
> [name=chen]
$memoを使ってる方法、勉強になりました！！なるほど〜〜〜
## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める（2023/01/06）
- teruya
- 読む範囲を決める
- 第４章最後まで
Sign in with Wallet
Connect another wallet