11/17 Java プログラミング入門(5)

予定よりも遅れがちだが，原因として，「余談が多すぎる」という指摘を TA から受けた．ついつい余談のつもりで書いた部分も説明してしまっているが，今回からは余談の部分の説明は略すことにする．

質問と回答

Q.: while文の途中から抜けるための構文はあるのか?
A.: まだやっていなかったが，break文というものがある．今回説明する．
Q.: 1110-3.htmlの，「なお，メソッドspacesを再帰を使わずに書くと，」のプログラムがおかしい．; プログラム中の「<」がHTMLタグの開始と見なされてしまった．修正した．
Q.: static を Static と書いたらエラーが出た．
A.: Java言語では名前(予約語，変数名，メソッド名，クラス名)の大文字と小文字は区別する．
Q.: 計算機プログラミング1の授業で11/10の”オブジェクトとは ”の真ん中付近のプログラムの public class ObjectTest1 の部分で先頭のpublic はどうしてついているの。不思議だったので省いてみても結果は変わらずよくわからない．
A.: クラスの宣言に public をつけることの意味は「複数のファイルからなるプログラムを作る際に，クラスを使える範囲を広げる」というである． ObjectTest1のように1つのファイルからなるプログラムを作るときは不要だが，昔の資料から引っ張ってきた際に取り忘れていたようだ．

前回の課題について

課題問題

次のプログラムは再帰を使って最大公約数を計算するプログラムである. なおこのアルゴリズム(計算の方法)はユークリッドの互除法として良く知られている(GCDは Greatest Common Divisorの略)．

class GCDTest {
  // ユークリッドの互除法により最大公約数を計算するメソッド gcd の定義
  // int型の引数 n, m をとり, int型の値を返す
  static int gcd(int n,int m){
    // デバッグ(プログラムのミスを直す)のための出力
    System.out.println("gcd("+n+","+m+")が呼ばれました");
    // 剰余を求めて rに入れる
    int r=n%m;
    // nがmの倍数になっているなら最大公約数は m自身になる．
    if(r==0) return m;
    // n,mの最大公約数は m,rの最大公約数と等しい
    else return gcd(m,r);
  }
  public static void main(String[] args){
    // コマンドラインから 
    // java GCDTest arg0 arg1 
    // のようにして起動した時, args[0] -> arg0, args[1] -> arg1 となる．
    // 文字列から int 型の整数値に変換するのは Integer.parseInt を使う
    int i0=Integer.parseInt(args[0]);
    int i1=Integer.parseInt(args[1]);
    System.out.println(i0+"と"+i1+"の最大公約数は"+gcd(i0,i1)+"です");
  }
}

実行例は以下のようになる．

dell.tanaka.ecc.u-tokyo.ac.jp% java GCDTest 96 1024
gcd(1024,96)が呼ばれました
gcd(96,64)が呼ばれました
gcd(64,32)が呼ばれました
96と1024の最大公約数は32です

このプログラムのメソッドgcdを繰り返し文(for文や while文など)を使って(再帰を使わずに)書き直したプログラムを作りなさい．なお，
```
    System.out.println("gcd("+n+","+m+")が呼ばれました");
```
にあたる表示は残しても残さなくても良い．
2数の最小公倍数を求めるメソッド lcm(Least Common Multipleの略)を作成して，最大公約数，最小公倍数の両方を表示するプログラムを作成しなさい．
実行例:
```
dell.tanaka.ecc.u-tokyo.ac.jp% java GCDTest 96 1024
96と1024の最大公約数は32です
96と1024の最小公倍数は3072です
```
ヒント
最小公倍数は(2数の積/2数の最大公約数)

解答例(1)

class GCDTest {
  static int gcd(int n,int m){
     // 剰余を求めて rに入れる
    int r=n%m;
     // 元のプログラムでは r==0 が再帰を終了するための条件だった
     // 繰り返しの場合は，その否定である r!=0 が繰り返すための条件となる
    while(r!=0){
      // デバッグ(プログラムのミスを直す)のための出力
      System.out.println("n="+n+",m="+m);
      // 再帰における引数の置き換えをおこなう．下の2つの文の順序は大切
      n=m;
      m=r;
     // 剰余を求めて rに入れる
      r=n%m;
    }
    return m;
  }
  public static void main(String[] args){
    // コマンドラインから 
    // java GCDTest arg0 arg1 
    // のようにして起動した時, args[0] -> arg0, args[1] -> arg1 となる．
    // 文字列から int 型の整数値に変換するのは Integer.parseInt を使う
    int i0=Integer.parseInt(args[0]);
    int i1=Integer.parseInt(args[1]);
    System.out.println(i0+"と"+i1+"の最大公約数は"+gcd(i0,i1)+"です");
  }
}

上の文は while文を使った例です．for文を使って以下のように短く書くことも可能ですが，読みやすくなっているかは疑問です．

  static int gcd(int n,int m){
     // 剰余を求めて rに入れる
    int r=n%m;
     // 元のプログラムでは r==0 が再帰を終了するための条件だった
     // 繰り返しの場合は，その否定である r!=0 が繰り返すための条件となる
    for(r=n%m;r!=0;r=n%m){
      // デバッグ(プログラムのミスを直す)のための出力
      System.out.println("n="+n+",m="+m);
      // 再帰における引数の置き換えをおこなう．下の2つの文の順序は大切
      n=m;
      m=r;
    }
    return m;
  }

解答例(2)

class LCMTest {
  // ユークリッドの互除法により最大公約数を計算するメソッド gcd の定義
  // int型の引数 n, m をとり, int型の値を返す
  static int gcd(int n,int m){
    // デバッグ(プログラムのミスを直す)のための出力
    // System.out.println("gcd("+n+","+m+")が呼ばれました");
    // 剰余を求めて rに入れる
    int r=n%m;
    // nがmの倍数になっているなら最大公約数は m自身になる．
    if(r==0) return m;
    // n,mの最大公約数は m,rの最大公約数と等しい
    else return gcd(m,r);
  }
  static int lcm(int n, int m){
    return n/gcd(n,m)*m;
  }
  public static void main(String[] args){
    // コマンドラインから 
    // java GCDTest arg0 arg1 
    // のようにして起動した時, args[0] -> arg0, args[1] -> arg1 となる．
    // 文字列から int 型の整数値に変換するのは Integer.parseInt を使う
    int i0=Integer.parseInt(args[0]);
    int i1=Integer.parseInt(args[1]);
    System.out.println(i0+"と"+i1+"の最大公約数は"+gcd(i0,i1)+"です");
    System.out.println(i0+"と"+i1+"の最小公倍数は"+lcm(i0,i1)+"です");
  }
}

ヒントにある通り，nとmの乗算結果から最大公約数を割るだけで，最小公倍数が計算できます．

n/gcd(n,m)*m;

は，演算子の優先順位により，

(n/gcd(n,m))*m;

という意味になります．

dell.tanaka.ecc.u-tokyo.ac.jp% java LCMTest 60000 60008
60000と60008の最大公約数は8です
60000と60008の最小公倍数は450060000です

のように，nとmの積が32ビットの符号付整数で表せないが，最小公倍数は表せるという場合，

(n*m)/gcd(n,m);

とすると，

dell.tanaka.ecc.u-tokyo.ac.jp% java LCMTest 60000 60008
60000と60008の最大公約数は8です
60000と60008の最小公倍数は-86810912です

のように誤った答えになってしまいますが，

(n/gcd(n,m))*m;

だと正しい答えが出ます．ただし，一般の除算は余りが出ることがあるので， a/b*cと a*c/bは一致するとは限らないことに注意してください．

今回は課題が1つある．課題をこなしたら， lectures.g99.cp1-ktanaka-W-Wed-5 のニュースグループに投稿すること．

ニュースグループへの投稿方法がわからない人は， HWB「ネットワークニュース」を読んで自習すること．
Subject(題名)は「Report1117」のような名前にする．
提出期限は1週間後の授業開始前まで
最初に学生証番号と名前を書く
各課題ごとに，解答のプログラムに加えて2行以上の説明をつける．
提出した内容に誤りが見つかった時は，期限内ならば再提出を認める．再提出の際は変更点だけでなくすべての課題の解答をもう一度出すこと．
全問できなくても，出さないよりは出した方が評価が高い．

次に進む