我做的google數組隨機排序的算法
面試筆試1.67W
發信人: northor(追求理想的過程是曲折艱辛的!), 信區: Job
標 題: 我做的google數組隨機排序的算法
發信站: 瀚海星雲 (2006年05月30日23:44:13 星期二), 站內信件 WWWPOST
由於一開始覺得這個題目不太好做,
就放在最後做了,
結果時間不夠,只寫了算法:
我考慮題幹強調的是一定要隨機,就是越亂越好,
於是我就聯想到了一堆乒乓球在籠子裏搖啊搖的,抽獎的過程,
這個過程應該算是符合題目的要求吧,
那麼怎麼用random函數來實現這個功能呢?
我又建立了三個int型數組,b[len],c[len],d[len]
首先N = len,乒乓球的個數是N,
然後搖獎:利用random產生0到N-1的隨機數,
記作b[0],d[0]=b[0];
這是搖出的第一個球的號碼,然後對c[len]賦值,
這個數組,我規定它的作用是對剩下的乒乓球標記,
因為搖出了一個球,剩下了N-1個,
而隨機數只能在0開始的連續整數之間產生,
所以剩下的球的號碼要是連續整數就可以繼續搖了,
所以c[len]記錄我對乒乓球的重新標號,
如果最初乒乓球的號碼小於b[0],就保持原來的號碼,
等於b[0],就讓號碼為N(作廢),
大於b[0]的,全部減1,
這樣剩下的N-1個乒乓球的標號就是0到N-2了,
然後產生利用random產生0到N-2的隨機數,
對標記號碼搖獎,利用搖出的乒乓球的標記號碼b[1],
查到它的真實號碼d[1],
這樣第二個隨機位置d[1]就產生了,
然後再根據b[1]給剩下的N-2個乒乓球重新標記,
如果乒乓球的標記號碼小於b[1],就保持原來的標記號碼,
等於b[1],就讓號碼為N(作廢),
大於b[1]不等於N的,全部減1,
大於b[1]等於N的,不變。
重新標記之後,產生0到N-3的隨機數,
就產生了第三個乒乓球的隨機號碼b[2],
反回去查詢真實號碼,得到d[2];
......
最後我們得到了d[len]這個數組,
可以讓c[i]=a[d[i]];
然後再把c賦給a,
這樣一個模擬乒乓球搖獎的隨機過程就完成了,
如果有可能,可以看到a[len]
打亂後排列的順序,
和一個一個地搖出乒乓球號碼的概率分佈是一致的。
期待高手點評,^_^.
標 題: 我做的google數組隨機排序的算法
發信站: 瀚海星雲 (2006年05月30日23:44:13 星期二), 站內信件 WWWPOST
由於一開始覺得這個題目不太好做,
就放在最後做了,
結果時間不夠,只寫了算法:
我考慮題幹強調的是一定要隨機,就是越亂越好,
於是我就聯想到了一堆乒乓球在籠子裏搖啊搖的,抽獎的過程,
這個過程應該算是符合題目的要求吧,
那麼怎麼用random函數來實現這個功能呢?
我又建立了三個int型數組,b[len],c[len],d[len]
首先N = len,乒乓球的個數是N,
然後搖獎:利用random產生0到N-1的隨機數,
記作b[0],d[0]=b[0];
這是搖出的第一個球的號碼,然後對c[len]賦值,
這個數組,我規定它的作用是對剩下的乒乓球標記,
因為搖出了一個球,剩下了N-1個,
而隨機數只能在0開始的連續整數之間產生,
所以剩下的球的號碼要是連續整數就可以繼續搖了,
所以c[len]記錄我對乒乓球的重新標號,
如果最初乒乓球的號碼小於b[0],就保持原來的號碼,
等於b[0],就讓號碼為N(作廢),
大於b[0]的,全部減1,
這樣剩下的N-1個乒乓球的標號就是0到N-2了,
然後產生利用random產生0到N-2的隨機數,
對標記號碼搖獎,利用搖出的乒乓球的標記號碼b[1],
查到它的真實號碼d[1],
這樣第二個隨機位置d[1]就產生了,
然後再根據b[1]給剩下的N-2個乒乓球重新標記,
如果乒乓球的標記號碼小於b[1],就保持原來的標記號碼,
等於b[1],就讓號碼為N(作廢),
大於b[1]不等於N的,全部減1,
大於b[1]等於N的,不變。
重新標記之後,產生0到N-3的隨機數,
就產生了第三個乒乓球的隨機號碼b[2],
反回去查詢真實號碼,得到d[2];
......
最後我們得到了d[len]這個數組,
可以讓c[i]=a[d[i]];
然後再把c賦給a,
這樣一個模擬乒乓球搖獎的隨機過程就完成了,
如果有可能,可以看到a[len]
打亂後排列的順序,
和一個一個地搖出乒乓球號碼的概率分佈是一致的。
期待高手點評,^_^.
-
聯想武大筆經
昨天是聯想公司武漢大學宣講會。中午一點開始,去了發現人太多了,人文館裏都已經坐滿了,門外還有一批人進不去,於是向保安打聽了下,得知聯想有分兩批筆試的想法,於是寬心回宿舍玩了玩,再估摸着時間差不多的時候去了。剛巧第一批筆試結束,但是側門還是黑壓壓的一批人在擠...
-
2005年交通銀行筆試
12月10號上午10點.通知我叫我12:50去的,我下午有事,就自做主張上午衝過去了.大家都在門口等,沒什麼熟面孔,就有個金融班的,還有王潔和她的同學,我知道了應該還有不少復旦的人.還遇見了FJ,跟她説看見她在PWC的名單裏,她樂的跳了起來.(不用這麼開心吧,哈哈)好象...
-
筆試大唐和Moto
匆忙中又進行了兩門筆試,懷着不一樣的心理,做着同樣的事。星期天筆試Moto,從投簡歷到Moto一直以來從來沒有想過會有後面的事情,算自己走運,通過了簡歷篩選這一關進入第一輪的筆試。Moto的筆試分為兩輪進行,第一輪為軟素質測試,説白了就是智力測試,第二輪是真正的技術筆...
-
花旗商行筆試
花旗商行筆試發信站:北大未名站(2005年12月06日18:46:48星期二),轉信看有人問,説一下吧先是numericalreasoning,和shl的題感覺不太相同,時間稍緊一些不許使用計算器,總體來説還沒什麼問題然後是groupdiscussion,一組九個人,15min看案例(5頁英文)30min英文討論,最後要有...