山元進
初めにアンケートに答える時間をとる
自由記入欄にも積極的に書きこまれたし
出力を各ケタごとに縦に見ると、7周期に同じ
数字が繰り返すケタと、3周期に同じ数字を繰
り返すケタとに分かれる
グループA: 3周期のケタが3つ
グループB: 7周期のケタが7つ
基本的なルールは
グループAの中で巡回置換
グループBの中で巡回置換
の２つで、これを実装すれば"良い解答"になる
良い解答を実装するのは、若干難しい
そもそも、画面の出力だけみても巡回置換と
は分からないので、動作をチェックするプログ
ラムを作る必要がある
画面出力だけから判断すると、特定の数字の
下に表示される数字は決まっている
それを実装したのが"普通の解答"
0123456789
8901564237
3789645012
1237456890
9012564378
7890645123
2378456901
0123564789
8901645237
3789456012
1237564890
9012645378
7890456123
2378564901
0123645789
8901456237
3789564012
1237645890
9012456378
7890564123
2378645901
0123456789
Finished.
1行目は、繰り返し処理の前に実行した print で印字されたもの
繰り返し処理 1 回目
繰り返し処理 2 回目
繰り返し処理 3 回目
規則の明文化の例
0→8
1→9
2→0
3→1
4→5
5→6
6→4
7→2
8→3
9→7
繰り返し処理 21 回目 ここで元の並びに戻ったので繰り返し終了
終わったしるしに "Finished." と印字
class Ex01
{
public static void permutation(int in[]){
int[] permList = {8,9,0,1,5,6,4,2,3,7};
for(int i=0; i<10; i++){
in[i]=permList[in[i]]; // ここがポイント
}
}
public static boolean samePerm(int[] in1, int[] in2){
if(in1.length != in2.length ) return false;
boolean flag=true;
for(int i=0; i<in1.length; i++) if(in1[i]!=in2[i]) flag=false;
return flag; // 一つでも違う数値があったら false を返す
}
public static void main(String[] args){
int[] input1={0,1,2,3,4,5,6,7,8,9};
int[] input2={0,1,2,3,4,5,6,7,8,9};
int id=999;
do{
Perm.permutation(id,input1);
permutation(input2);
if(!samePerm(input1,input2)){
System.out.println("Differ!");
Perm.print(input1);
Perm.print(input2);
}
}while(!Perm.isIdentity(input1));
}
}
良い解答の解答例は示さない
permutation メソッドと Perm.permutation メ
ソッドが、どの入力に対しても 一致することを示す
ためには、入力の生成方法を考える必要あり
入力は、長さ10の整数配列であればなんで良いわけ
ではなく、0~9の数字を並べて作る順列である
今日は 0~9 の数字を並べて作る順列の生成法を
題材にする
指示をよく読むこと
後の課題で先週利用した Perm.class を使
うので、今日の課題プログラムを作成するディレ
クトリにコピーしておく
学籍番号の下3ケタを 999 と仮定しているサン
プルがあるので、それは自分の学籍番号の下3
ケタに書きかえる
0~3 の数字を並べて作る順列(先頭の数字が0で
ある場合を含める)を、小さい順に全てあげよ
(解答の最初の3項まで) 0123, 0132, 0213, …
次ページのEx02.java をどう書き換えれば上の
並びを出力するようになるか、説明せよ
Ex02は、001, 002, 003, という並びを生成して、同じ
数字が繰り返し出てきたら排除している
この方法は、簡単だが桁数を変えるのが面倒
上のケタから順に数字を決めてゆく際、使った数字の
リストを作り、重複を排除すると、もうすこしまし
発想が難しいが、プログラムが短くなる方法もある
0~2 の数字を並べてできる順列を、小さい順に全て表示するプログラム(工夫なし版)
class Ex02
{
public static void main(String[] args){
int[] input=new int[3];
for(int i0=0; i0<3; i0++){
input[0]=i0;
for(int i1=0; i1<3; i1++){
if(i1==i0) continue;
input[1]=i1;
for(int i2=0; i2<3; i2++){
if(i2==i0 || i2==i1) continue;
input[2]=i2;
Perm.print(input);
}
}
}
}
}
1) 0~5 の数字を並べ替えてできる順列を全
てあげるプログラムを作成せよ。ただし順列は、
長さ6の整数配列として表されるものとする。
2) この順列は 6! = 720 通りある。1行に1つ
順列を表示するとすれば、720行になる。人
手で出力をチェックするには行数が多いので、
linux のコマンドを利用してチェックする方法
を考えよ。
sort, uniq (, diff, wc) を使えばできる
3) 実際に出力をチェックせよ
0~9 の数字を並べ替えてできる順列を全てあ
げるプログラムを作成せよ。ただし、順列は長
さ10の整数配列として表されるものとする。
この課題の出力は 328800 行。人手でのチェック
は無理。
1) 課題3では、生成した順列を画面(標準出力)
に出力した。この課題では、画面に出力するかわ
りに、次の2つメソッドの入力として使え。
このパワーポイントの6ページにあげた permutation
メソッドを、自分の id 用に書き換えたもの
先週の Perm.class の Perm.permutation
注意: メソッドの引数として与えた配列は、上の各メ
ソッドによって書き換えられてしまう。書き換えは、後
の操作に支障をきたす。それを避けるため、各メソッド
の入力として２つの新たな配列を作り、値をコピーして
から各メソッドの引数とせよ。
2) 1) 2つのメソッドから戻ってきた後(書き変わっ
た後の)の整数配列を比較し、各要素の値が完
全に一致する場合が何通りあるか数えるプログラ
ムをつくれ。
sort は、ある欄の値をキーにして辞書式に並
べ替えるコマンド
uniq は、隣り合う行が重複する場合、重複を
取り除くコマンド
全ての順列が過不足なく印字されているなら
ば、並べ替えた時に重複する行はないはず
他に有用なコマンド1 : wc
語数を数えるコマンド。
-l オプションをつけると行の数を数える
他に有用なコマンド2 : diff
2つのファイルの違いを画面に表示する
Ex02.java を書き換えて、0~2 の数字を並べて作った順列のうち、210 という順列が何番目の順列かを表示するプログラム
class Ex03
{
public static boolean equiv(int[] in1, int[] in2){ // このメソッドは引数を書き変えない
if(in1.length != in2.length ) return false;
boolean flag=true;
for(int i=0; i<in1.length; i++) if(in1[i]!=in2[i]) flag=false;
return flag;
}
public static void main(String[] args){
int[] input=new int[3];
int[] ref={2,1,0};
int count=0;
for(int i0=0; i0<3; i0++){
input[0]=i0;
for(int i1=0; i1<3; i1++){
if(i1==i0) continue;
input[1]=i1;
for(int i2=0; i2<3; i2++){
if(i2==i0 || i2==i1) continue;
input[2]=i2;
count++;
if(equiv(input,ref)){
System.out.print(count+"番目の順列が");
for(int i=0; i<3; i++) System.out.print(ref[i]);
System.out.println("になりました。");
}
}
}
}
}
}
整数配列のコピー
int[] copy1 = input.clone();
copy1 が input のコピー(clone)になる
copy1 は input とは独立したメモリを確保している
copy1 の値を書き換えても input への影響はない
int[] alias=input; でも alias が整数配列として扱わ
れるが、データを確保するメモリは input と共有。つまり、
alias[i] を書き換えると、 input[i] も同じ値になる。
今回の課題では、
int[] copy1 = input.clone();
int[] copy2 = input.clone();
Perm.permutation(id,copy1);
permutation(copy2);
if(equiv(copy1,copy2)){
….
}
といった使い方を想定している。
© Copyright 2024 ExpyDoc
