1.イントロダクション

最大公約数を求める

• たとえば、1058と943の最大公約数を自分で求めるとしたら、どうやるだろう。
• まずは、例題を通して自分ならどうやるだろうかと考えてみよう。
• 実は、とても巧い方法（手続き）が存在する。
• そこで、次は、その手続きを、手続きの具体例をみて、自分で考え、例題を試し、整理しよう。プログラムを意識して、整理しよう。
• 本当に最大公約数が求まっているのかは、実際に割り算して、確かめてみるとよい。
• 今日学ぶ、「必ず２つの数の最大公約数を見つけることのできる」一定の手続き（アルゴリズム）は、ユークリッドの互除法と呼ばれています。
  • Euclid（さんなのか、グループなのか、はっきりしないけれど）は、紀元前3世紀ごろの数学者
    • 中学で学んだ幾何学（角や辺を求めよ、合同や相似を証明せよ、など）は、この時代の知識。ユークリッドの原論として編纂された書物に登場する。
  • というわけで、ユークリッドの互除法は、最古のアルゴリズム、と言われています。

今回の活動

1. アルゴリズムを納得しよう
   1. 自分の手続きを考え、まとめてみよう(MaNaBo)
   2. 自分の解法、みんなの解法を比較、見直してみよう(リンクします)
   3. ユークリッドの互除法を確かめ、自分なりのまとめをしてみよう
   4. みんながまとめたユークリッドの互除法を確認しよう(リンクします)
2. 解説
   • ユークリッドの互除法についての詳しい説明(MaNaBo, explanation.html)
3. 実装しよう
   • STEP 5.1 再帰を使わないバージョン
   • STEP 5.2 再帰を使うバージョン（再帰のほうが、すっきり書けるね、と感じられるようになったら、素晴らしい）