転んでも転んでも立ち上がる 諦めないための記録

諦めないために学習記録を残しています。日商簿記検定・情報処理技術者試験の勉強記録が多いです。

応用情報(ソフ開)から

 次に示すユークリッドの互除法(方法 1,方法 2)で、正の整数 a, b の最大公約数
は、それぞれ m と n のどちらの変数に求まるか。ここで,m mod n は,m を n
で割った余りを表す。

      方法 1            方法 2
     _____          _____
    ( 開 始 )        ( 開 始 )
      ̄ ̄│ ̄ ̄           ̄ ̄│ ̄ ̄
   ┌───┴───┐      ┌───┴───┐
   │  a → m  │      │  a → m  │
   │  b → n  │      │  b → n  │
   └───┬───┘      └───┬───┘
   ┌───┴───┐        ──┴──
   │ m mod n → r │       / ループ 2 \
   └───┬───┘      │       │
     ──┴──        └───┬───┘
    / ループ 1 \       ┌───┴───┐
   │   r = 0  │      │ m mod n → r │
   └───┬───┘      └───┬───┘
   ┌───┴───┐      ┌───┴───┐
   │  n → m  │      │  n → m  │
   └───┬───┘      └───┬───┘
   ┌───┴───┐      ┌───┴───┐
   │  r → n  │      │  r → n  │
   └───┬───┘      └───┬───┘
   ┌───┴───┐      ┌───┴───┐
   │ m mod n → r │      │   r = 0  │
   └───┬───┘       \ ループ 2 /
   ┌───┴───┐        ──┬──
   │       │        __|__
    \ ループ 1 /        ( 終 了 )
     ──┬──           ̄ ̄ ̄ ̄ ̄
     __|__
    ( 終 了 )
      ̄ ̄ ̄ ̄ ̄
 
 ┌─┬─────┬─────┐
 │ │ 方法 1 │ 方法 2 │
 ├─┼─────┼─────┤
 │ア│  m   │  m   │
 ├─┼─────┼─────┤
 │イ│  m   │  n   │
 ├─┼─────┼─────┤
 │ウ│  n   │  m   │
 ├─┼─────┼─────┤
 │エ│  n   │  n   │
 └─┴─────┴─────┘