本帖最后由 * 于 2012-10-31 13:45 編輯
2 Stable Matching import java.util.ArrayList; import java.util.List; public class StableMatch { privateint[][] mPref; privateint[][] fPref; privateint[] pos;//儲存位置 privateint count; publicStableMatch() { } publicStableMatch(int n) { mPref= new int[n][]; fPref= new int[n][]; count= n; for(int i = 0; i < n; i++) { mPref= randomIni(n); fPref= randomIni(n); } } publicint[] randomIni(int n) { int[]result = new int[n]; Listlist = new ArrayList(n); for(inti=0; i<n;i++) { list.add(i); } for(int i = 0; i < n; i++) { intindex = (int)(Math.random() * list.size()); result= (Integer)list.get(index); list.remove(index); } returnresult; } publicstatic void main(String[] args) { //TODO Auto-generated method stub while(true) { StableMatchsm = new StableMatch(3); int[][]result = sm.doMatch(true); int[][]result1 = sm.doMatch(false); if(resultTest(result[0],result1[0])) break; } } publicint[][] doMatch(boolean flag) { int[][]result = new int[2][count]; pos= new int[count]; for(int i = 0; i < pos.length; i++) { pos= -1; } for(int i = 0; i < result.length; i++) { for(int j = 0; j < result.length; j++) { result[j] = -1; } } //Initiallyall man, and wom are free. if(!flag) { int[][]temp = fPref; fPref= mPref; mPref= temp; } intmcount = findFree(result); while(mcount!= -1) { intmpos = mPref[mcount][++pos[mcount]]; //向第mpos個女的求婚 if(result[1][mpos]== -1) //第mpos個女的沒有訂婚 { result[0][mcount]= mpos; result[1][mpos]= mcount; mcount= findFree(result); continue; }else//第mpos個女的訂婚了 { if(!judge(mpos,mcount,result))//第mpos比當前的好 { result[0][result[1][mpos]]= -1; //結束訂婚 result[1][mpos]= mcount;//與mcount訂婚 result[0][mcount]= mpos;//與mpos訂婚 mcount= findFree(result); } } } returnresult; } publicint findFree(int[][] result) { intindex = -1; for(int i = 0; i < result[0].length; i++) { if(result[0]==-1) { index= i; break; } } returnindex; } //判斷向windex求婚的人是否比當前的男的好 publicboolean judge(int windex,int mindex,int[][] result) { booleanflag = false; intcur = result[1][windex]; for(int i = 0; i < mPref[windex].length; i++) { if(cur== mPref[windex]) { flag= false; break; } if(mindex== mPref[windex]) { flag= true; break; } } returnflag; } publicstatic boolean resultTest(int[] a,int b[]) { for(int i = 0; i < a.length; i++) { if(i!= b[a]) { returnfalse; } } returntrue; } } 對于每個事例都有file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png，是錯誤的，舉一個反例。 男生的喜好矩陣 [[0, 1, 2], [1, 2, 0], [2, 0,1]] 女生的喜好矩陣 [[0, 1, 2], [1, 0, 2], [0, 1,2]] 男生主動的匹配 [[1, 2, 0], [2, 0, 1]] 女生主動的匹配 [[0, 1, 2], [0, 1, 2]] 從上可以看出男生主動第0個男生與第1個女生匹配，而女生主動第一個女生與第一個男生匹配因此對于每個事例都有file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png，是錯誤的 4 Complexity Analysis
算法實現： public class HHindex { publicstatic void main(String[] args) { //TODO Auto-generated method stub Stringstr = "8,4,3,5,6,2"; String[]temp = str.split(","); int[]array = new int[temp.length]; int[]result = new int[temp.length]; for(int i = 0; i < array.length; i++) { array= Integer.parseInt(temp); result= 1; } for(int i = 1; i < result.length; i++) { if(array> array[i-1]) { intn = result[i-1]; result+=result[i-1]; while(i-1-n>=0&&array > array[i-1-n]) { result+=result[i-n]; n+=result[i-n]; } } } System.out.println("ok!!!"); } }
| 
發表于 2012-10-31 13:38
收藏
分享
支持
反對
