考研論壇
標(biāo)題: (Mutimedia Dr)第1次算法設(shè)計(jì)作業(yè) [打印本頁(yè)]
作者: 598788523 時(shí)間: 2012-10-31 13:38
標(biāo)題: (Mutimedia Dr)第1次算法設(shè)計(jì)作業(yè)
本帖最后由 * 于 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;//儲(chǔ)存位置
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個(gè)女的求婚
if(result[1][mpos]== -1) //第mpos個(gè)女的沒(méi)有訂婚
{
result[0][mcount]= mpos;
result[1][mpos]= mcount;
mcount= findFree(result);
continue;
}else//第mpos個(gè)女的訂婚了
{
if(!judge(mpos,mcount,result))//第mpos比當(dāng)前的好
{
result[0][result[1][mpos]]= -1; //結(jié)束訂婚
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求婚的人是否比當(dāng)前的男的好
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; }
}
對(duì)于每個(gè)事例都有file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png，是錯(cuò)誤的，舉一個(gè)反例。
男生的喜好矩陣
[[0, 1, 2], [1, 2, 0], [2, 0,1]]
女生的喜好矩陣
[[0, 1, 2], [1, 0, 2], [0, 1,2]]
男生主動(dòng)的匹配
[[1, 2, 0], [2, 0, 1]]
女生主動(dòng)的匹配
[[0, 1, 2], [0, 1, 2]]
從上可以看出男生主動(dòng)第0個(gè)男生與第1個(gè)女生匹配，而女生主動(dòng)第一個(gè)女生與第一個(gè)男生匹配因此對(duì)于每個(gè)事例都有file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png，是錯(cuò)誤的
4 Complexity Analysis
算法實(shí)現(xiàn)：
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!!!");
}
}
[attach]622230[/attach]
作者: panda2029 時(shí)間: 2013-4-27 16:56
本來(lái)還好。。?？戳艘院笸蝗缓茴^疼。。。怎么搞。。。暈。。。
作者: 可可米露 時(shí)間: 2013-5-15 17:00
panda2029 發(fā)表于 2013-4-27 16:56 
本來(lái)還好。。?？戳艘院笸蝗缓茴^疼。。。怎么搞。。。暈。。。
噗。哈哈。。。。。
我覺(jué)得還好啊。。。
因?yàn)樯耨R都不懂╮(╯▽╰)╭
作者: panda2029 時(shí)間: 2013-5-15 17:05
可可米露 發(fā)表于 2013-5-15 17:00
噗。哈哈。。。。。
我覺(jué)得還好啊。。。
因?yàn)樯耨R都不懂╮(╯▽╰)╭
算法。。。虐人。。。我神經(jīng)衰弱了。。。
作者: 可可米露 時(shí)間: 2013-5-15 17:08
panda2029 發(fā)表于 2013-5-15 17:05
算法。。。虐人。。。我神經(jīng)衰弱了。。。
所以改行是對(duì)滴~~~
這個(gè)算法的結(jié)果是神馬？？有結(jié)果么？？
作者: 可可米露 時(shí)間: 2013-5-15 17:09
是個(gè)神馬故事？？？？？白雪公主？？？？？？？
作者: panda2029 時(shí)間: 2013-5-15 17:10
因?yàn)槊總€(gè)女生最中意的男生都不同，所以只要讓女生們都選擇跟自己最中意的男生在一起，她們就都不會(huì)有和其他男生私奔的想法。雖然男生們會(huì)表示略苦逼啊！仍然不失為一個(gè)stable matching。。。。。
作者: panda2029 時(shí)間: 2013-5-15 17:11
第一天早上：所有男生都向自己最中意的女生表白。
第一天中午：每個(gè)女生都被表白了n次（可能是0次）之后，拒絕了相對(duì)不太中意的那n-1位，hold住其中最中意的那位。。。即暫時(shí)不答應(yīng)也不拒絕
第一天晚上，被拒絕的男生們?cè)谧约旱膒reference列表中劃掉了那個(gè)拒絕他的人。。。
第二天早上：所有沒(méi)有被hold住的男生都向自己最中意的女生（無(wú)視已經(jīng)被劃掉的）表白。
第二天中午：女生們?cè)谀切┫蛩戆椎哪猩鸵呀?jīng)hold住的那男生中選擇最中意的一位，拒絕掉其他的。
第二天晚上：被拒絕的男生們?cè)谧约旱膒reference列表中劃掉拒絕了自己的人。。。。
第三天，重復(fù)同樣的過(guò)程。。。
第四天。。。。
。。。。。。。
作者: panda2029 時(shí)間: 2013-5-15 17:12
這樣的過(guò)程是有限的，不會(huì)一直循環(huán)下去。
在這樣的過(guò)程結(jié)束之后，每個(gè)女生都會(huì)hold住一個(gè)男生。即在那一天之后沒(méi)有男生可以繼續(xù)表白了，這時(shí)女生們終于都向那個(gè)男生說(shuō)了yes！
按照這樣的過(guò)程，最后不會(huì)存在一對(duì)男女有私奔傾向
即完成了stable matching。
作者: panda2029 時(shí)間: 2013-5-15 17:12
師兄。。。我說(shuō)的對(duì)么？男女穩(wěn)定匹配。。。。
作者: panda2029 時(shí)間: 2013-5-15 17:13
翻頁(yè)。。。強(qiáng)迫癥。。。囧。。。
作者: 可可米露 時(shí)間: 2013-5-15 17:18
哎。。。。。。。難道是我缺乏常識(shí)？？
作者: panda2029 時(shí)間: 2013-5-15 17:30
博士大哥。。。想表達(dá)“一個(gè)蘿卜一個(gè)坑”。。。不用如此費(fèi)勁。。。折騰啊。。。那天太累我沒(méi)仔細(xì)瞅。。。今天頓悟。。。這個(gè)么。。。囧了個(gè)囧。。。
作者: panda2029 時(shí)間: 2013-5-15 17:40
可可米露 發(fā)表于 2013-5-15 17:18
哎。。。。。。。難道是我缺乏常識(shí)？？
不是。。。此人高端黑。。。哼。。。把我家可可虐傻了。。。打他。。。
作者: 可可米露 時(shí)間: 2013-5-15 17:51
panda2029 發(fā)表于 2013-5-15 17:40
不是。。。此人高端黑。。。哼。。。把我家可可虐傻了。。。打他。。。
...
→ →交流太困難了╮(╯▽╰)╭
作者: 可可米露 時(shí)間: 2013-5-15 17:55
panda2029 發(fā)表于 2013-5-15 17:30
博士大哥。。。想表達(dá)“一個(gè)蘿卜一個(gè)坑”。。。不用如此費(fèi)勁。。。折騰啊。。。那天太累我沒(méi)仔細(xì)瞅。。。今 ...
。。。。。。。。難道以后師父的LP，叫他吃飯的時(shí)候，也要寫(xiě)個(gè)算法→ →
腫么那么有意思。。。。。。
作者: panda2029 時(shí)間: 2013-5-15 18:16
可可米露 發(fā)表于 2013-5-15 17:55
。。。。。。。。難道以后師父的LP，叫他吃飯的時(shí)候，也要寫(xiě)個(gè)算法→ →
所以。。。得有更高端的妹紙。。。才能搞定你那極其高端的師父。。。囧了個(gè)囧。。。
作者: 可可米露 時(shí)間: 2013-5-15 18:31
panda2029 發(fā)表于 2013-5-15 18:16
所以。。。得有更高端的妹紙。。。才能搞定你那極其高端的師父。。。囧了個(gè)囧。。。
...
哈哈，以后誰(shuí)跟著我就慘了。。一花錢(qián)我就讓他做會(huì)計(jì)分錄。。。。
作者: panda2029 時(shí)間: 2013-5-15 18:52
可可米露 發(fā)表于 2013-5-15 18:31
哈哈，以后誰(shuí)跟著我就慘了。。一花錢(qián)我就讓他做會(huì)計(jì)分錄。。。。
一分錢(qián)都跟他算清楚了。。。
作者: 可可米露 時(shí)間: 2013-5-15 18:54
panda2029 發(fā)表于 2013-5-15 18:52
一分錢(qián)都跟他算清楚了。。。
→ →年底還讓他做報(bào)表，做財(cái)務(wù)分析。
想想就覺(jué)得好有意思。。。
作者: 可可米露 時(shí)間: 2013-5-15 18:56
翻頁(yè)。。。
作者: AirCrystal 時(shí)間: 2013-5-15 20:07
{:3_102:}以前，其實(shí)了解過(guò)一點(diǎn)點(diǎn)的，后來(lái)，精力不允許了，就放棄了。。。
| 歡迎光臨 考研論壇 (http://www.5522pp.com/) |
Powered by Discuz! X3.2 |