10/12レポート講評

問題

// 実行結果は (1) になります
class Collatz{
    public static void main(String[] args){
        // (2)の部分は自分の学生証番号の下4桁を入れなさい。
        // 頭の0はつけないでください。
	int n= (2);
	int count=0;
	while(n!=1){
	    System.out.println(n);
	    if((n%2)==0){
		// nを2で割る
		(3) ;
	    }
	    else{
		// nを3倍して1を足す
		(4) ;
	    }
	    // 変数countを1増やす
	    (5) ;
	}
	System.out.println("count="+count);
    }
}

講評

• 53名が提出(うち1名は期限後: 6割を上限に採点)
• (1)を埋めなかった人がいた．(1)は作成したプログラムを自分で実行したことの確認のために入れているので，次回からは注意して欲しい．
• インデント(字下げ)が適切でなく読みにくいプログラムになっている人がいた．
• ファイル名(Collatz.java)とクラス名(class Collarz)の対応が取れていない人がいた．
• これらのミスは今回は減点しないが，次回からは注意して欲しい．

解答例とコメント

// 実行結果は 7 になります
class Collatz{
    public static void main(String[] args){
        // (2)の部分は自分の学生証番号の下4桁を入れなさい。
        // 頭の0はつけないでください。
        int n= 128;
        int count=0;
        while(n!=1){
            System.out.println(n);
            if((n%2)==0){
                // nを2で割る
                n=n/2 ;
            }
            else{
                // nを3倍して1を足す
                n=3*n+1 ;
            }
            // 変数countを1増やす
            count=count+1 ;
        }
        System.out.println("count="+count);
    }
}

  n=n/2;

  n/=2;

  n=n>>1;

  n>>=1;

  count=count+1;

  count++;

オプション課題

1. 課題の問題を改造して，M以下の数で1にたどりつくまでの回数がもっとも大きくなるプログラムにしてみなさい(難易度 中)
2. 課題の問題を改造して，32ビット整数のintや64ビット整数のlongで桁あふれが生じてしまうような場合にも正しく計算できるプログラムを作成しなさい(難易度 高)．
3. プログラムの高速化のアイデアを持っている人は自分の考えた高速化の方法に従ってプログラムを変更して，高速化を確認できる計測をおこないなさい(難易度 高)．

   講評

   • 1に挑戦したのが4名
   • 2(3も含む)に挑戦したのが2名

   ---

   解答例

   import java.lang.*;
   import java.io.*;
   class optCollatz{
       public static void main(String[] args){
           int n,j;
           int count=0;
   	int M;
   	int Max=0,Maxj=0;
   	String SM = null;
   	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   	System.out.print("M=?");
   	try{
   	    SM=br.readLine();
   	}
   	catch(java.io.IOException e){
   	}
   	M = Integer.valueOf(SM).intValue();
   	if(M>1){
   	    for(j=M;j>=1;j--){
   		n=j;
   		while(n!=1){
   		    if((n%2)==0){
   			// nを2で割る
   			n=n/2 ;
   		    }
   		    else{
   			// nを3倍して1を足す
   			n=3*n+1 ;
   		    }
   		    // 変数countを1増やす
   		    count++ ;
   		}
   		if(count>Max){
   		    Max=count;
   		    Maxj=j;
   		}
   		count = 0;
   	    }
   	    System.out.println("M以下の数で1にたどり着くまでの回数が最も大きいのは"+Maxj + "です");
   	}
   	else{
   	    System.out.println("2以上の数を入力してください！");
   	}
       }
   }
   

   正解です．Mをキーボードから入力するところまで作ってくれましたね．Integer.valueOf(SM).intValue()は，Integer.parseInt(SM)でも良いところです．

   ---

   /*
   int型やlong型で桁あふれがおこる場合の対処について。(オプション課題の２つめ)
   完全な対応ではないが、このプログラムを用いると計算途中で
   128Bit(0〜2^128-1)までの数値を扱うことが出来る。
   計算は出来るだけビット演算を用いている。
   2進数でとらえると、三倍して1をたす計算でおこる桁あふれは高々２桁であるので、
   以下のプログラムではそれを前提に計算を行っている。
   
   10/19追記
   御指摘のあった、終了条件にm==0が無かったことと、
   0xaaaaaaaaaaaaaaabの計算に不手際があったことを修正しました。
   */
   import java.io.*;
   class Collatz2{
       public static void main(String[] args) throws IOException{
   	BufferedReader Buf=new BufferedReader(new InputStreamReader(System.in));
   	System.out.println("計算する数値を入力してください(1〜9223372036854775807)");
   	long n=Long.parseLong(Buf.readLine());
   	long m=0;
   	long l=0;
   	long count=0;
   	while((n!=0x1)||(m!=0)){
   	    //System.out.println("9223372036854775807*"+m+"+"+n); 64Bit以上の数値を綺麗に表示させることが難しいため省略。
   	    if(((n & 0x1)==0)){
   			n = n >>>1;
   			if((m&0x1)==1) n=n|0x8000000000000000L;
   			m= m >>> 1;
   	    }else{
   			m=m+(m<< 1)+(((n>>>2)+(n>>>1))>>>62);
   			l=n+(n<< 1);
   			if(l==0xffffffffffffffffL) m++;
   			n=n+(n<< 1)+0x1;
   	    }
   	    ++count;
   	}
   	
   	System.out.println("count="+count);
       }
   }
   

   多倍長計算を自分で実装するのは大変ですね． ビット演算を使っているので普通の人は読めないと思いますが，上手に書いています．