判断推理の出勤簿の問題をJavaで解いてみました。(^_^;
A〜Eの5人が、ある1週間、各自の都合のよい日にアルバイトをした。
表は5人の働いた日数、曜日ごとの働いた人数を示したものである。
さらに次のことがわかっている。
ア Aは1日おきに働いた(2日連続で休んだことはない)
イ CとDは同じ日に働いたことはなかった
ウ EとDは同じ日に働いたことはなかった
エ Eは3日続けて休んだ日月火水木金土 日数 A□□□□□□□ 3 B□□□□□□□ 5 C□□□□□□□ 4 D□□□□□□□ 3 E□□□□□□□ 4 人3413143 数以上のことから、正しいのはどれか。
1 日曜日にCは休んだ
2 月曜日にAは休んだ
3 火曜日にDは働いた
4 水曜日はBは休んだ
5 木曜日はEは働いた
●AttendanceBook.java
/* * AttendanceBook.java */ class AttendanceBook { // 順列生成 static boolean nextPerm(int[] p, int n, int r) { int i, j; int t; if(r <= 0 || n < r) return(false); for(i = r + 1; i <= n-1; i++) for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){ t = p[j]; p[j] = p[j-1]; p[j-1] = t; // swap(p,j,j-1); } for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--); if(i==0) return(false); for(j = n - 1; j > i && p[i-1] >= p[j]; j--); t = p[j]; p[j] = p[i-1]; p[i-1] = t; // swap(p,j,i-1); for(j = n - 1; i < j; i++, j--){ t = p[i]; p[i] = p[j]; p[j] = t; // swap(p,i,j); } return(true); } // n日連休になっているか static boolean isCconsecutive(int n, int[] a) { int i,j,s; for(i=0; i< a.length-n+1; i++){ for(s=j=0; j< n; s+=a[i+j++]); if(s==0) return(true); } return(false); } // 一緒に出勤した日数を調べる static int numOfDaysTog(int[] a,int[] b) { int cnt=0; for(int i=0; i< a.length; i++) if(a[i]==1 && b[i]==1) cnt++; return(cnt); } // 出勤者数のチェック static boolean chechAttendance(int[][] p,int[] s) { for(int i = 0; i< 7; i++){ int t = 0; for(int j = 0; j< 5; j++) t+=p[j][i]; if(t!=s[i]) return(false); } return(true); } // 表の1行を文字列で得る static String getRowOfTable(int[] a) { String r=""; for(int i=0; i< a.length; i++) r+=(a[i]==1 ? "○" : "×"); return(r); } // aの出席表からc曜日に働いたか調べる static boolean hasWorked(int[] a, char c) { return a["日月火水木金土".indexOf(c)]==1; } public static void main(String[] args) { final int[] S = {3,4,1,3,1,4,3}; // 曜日ごとの働いた人数 final int[] A = {0,0,0,0,1,1,1}; // 要素を昇順にソートしたもの final int[] B = {0,0,1,1,1,1,1}; // 以下同様 final int[] C = {0,0,0,1,1,1,1}; final int[] D = {0,0,0,0,1,1,1}; final int[] E = {0,0,0,1,1,1,1}; int[] a = (int[])A.clone(); int[] b = (int[])B.clone(); int[] c = (int[])C.clone(); int[] d = (int[])D.clone(); int[] e = (int[])E.clone(); boolean[] ch = {true,true,true,true,true}; long tm = System.nanoTime(); // Timer Start a = (int[])A.clone(); do{ //--- a loop ---// if( isCconsecutive(2, a)) continue; // 条件ア b = (int[])B.clone(); do{ //--- b loop ---// c = (int[])C.clone(); do{ //--- c loop ---// d = (int[])D.clone(); do{ //--- d loop ---// if(numOfDaysTog(c,d)!=0) continue; // 条件イ e = (int[])E.clone(); do{ //--- e loop ---// if(numOfDaysTog(d,e)!=0) continue; // 条件ウ if(!isCconsecutive(3, e)) continue; // 条件エ //int[][] p = new int[][] {a,b,c,d,e}; if(!chechAttendance(new int[][] {a,b,c,d,e},S)) continue; // チェックを潜り抜けたものだけを表示 System.out.println(" 日月火水木金土"); System.out.println("A"+getRowOfTable(a)); System.out.println("B"+getRowOfTable(b)); System.out.println("C"+getRowOfTable(c)); System.out.println("D"+getRowOfTable(d)); System.out.println("E"+getRowOfTable(e)); System.out.println(); // 選択肢のチェック if(!hasWorked(c,'日')) ch[0]&=true; else ch[0]&=false; if(!hasWorked(a,'月')) ch[1]&=true; else ch[1]&=false; if( hasWorked(d,'火')) ch[2]&=true; else ch[2]&=false; if(!hasWorked(b,'水')) ch[3]&=true; else ch[3]&=false; if( hasWorked(e,'木')) ch[4]&=true; else ch[4]&=false; }while(nextPerm(e,7,7)); }while(nextPerm(d,7,7)); }while(nextPerm(c,7,7)); }while(nextPerm(b,7,7)); }while(nextPerm(a,7,7)); System.out.print("∴"); for(int i=0; i< 5; i++) if(ch[i]) System.out.print(" "+(i+1)); System.out.println(); tm = System.nanoTime()-tm; // Timer Stop System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9); } }
●実行結果
日月火水木金土 A×○×○×○× B○○×○×○○ C○○×××○○ D××○○○×× E○○×××○○ ∴ 3 Runtime : 0.012 [sec]
P.S.
問題がリンク切れになっていたので知恵袋で同じような問題を見つけて作り直しました。(^_^;
※参考URL
●知恵袋で見つけた判断推理の出勤簿の問題をPythonで解いてみた。
●知恵袋で見つけた判断推理の出勤簿の問題をPythonで解いてみた。(2)
- 作者: 柴田望洋
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2007/08/08
- メディア: 単行本
- 購入: 16人 クリック: 271回
- この商品を含むブログ (55件) を見る