【C算法】第5章 再帰的アルゴリズム

Cで再帰。楽しみだ！

• う、ユークリッドの互除法自体がわからない。考えてみる。
  
  
  
  • 最大公約数の定義は、整数x,yがあって、x=az, y=bzとなるzのうち最大のもの。z = gcd(x, y)とあらわす。
    
  • ここで、gcd(x, y) = gcd(y, x)。どうでもいいけど。
    
  • さらに定義として、gcd(x, 0) = x。
    
  • で、ユークリッド互除法とは、gcd(x, y) = gcd(y, x % y) ということ。なんで?
    
  • 便宜上、x > yとする。すると、x % y = 0ならば、yがgcdであることは自明。
    
  • つづいて、x % y != 0とする。するとyがgcdでないことは自明。
    
  • このとき、とあるAにて、x = Ay + x % y となっている。ここで、Ayの部分はもちろんgcdで割り切れるものである。よって、x % yもgcdで割り切れなければならないことがあらたにわかる。x > y > x % y だから、x,yのgcdを考えることは、より小さな問題である y,x%yを考える問題と等価であるといえる。よって、gcd(x,y)=gcd(y,x%y)。
    
  • で、x < yであっても、gcd(x,y) = gcd(y, x%y)するなかで、大きい方が左の引数に寄っていくので同じ結果となる。
    
  • という感じかなぁ。
    
  
  
• とりあえず5-2まで完了。
  
• なんか、再帰を楽しむというより、再帰は悪って感じだなぁ。。。
  

こつこつ。