我做的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]
打亂後排列的順序,
和一個一個地搖出乒乓球號碼的概率分佈是一致的。
期待高手點評,^_^.
-
金地集團筆試題(精華)
1.你為什麼選擇現在的專業?請列舉出你這個專業的三個特點?你最喜歡的一門課程是什麼?你從中的最大收穫是什麼?你最不喜歡的課程有哪些?為什麼?列舉出你記憶中最輕鬆的一件事情,最費勁的一件事情2.A公司:高速發展、制度不完善、?B公司:穩健發展、制度完善、??如果你是畢業...
-
AMD北京筆試經歷
分軟件,硬件兩套卷子,都要做1software都是簡答題,主要是彙編,計算機體系結構,AMD和Intel的cpu有什麼區別,實模式與保護模式。2hardware10道簡答題1個有緣RC迴路的電流方程us=uc+dUc/dt*RC?常見的計算機總線有什麼sram,dram,sdram,ddr都是什麼串行總線,並行總線哪個更...
-
大唐移動筆試歸來
組織的非常混亂,首先教室沒有安排好,人多位置少,最後臨時換了一個教室,大家緊挨着坐,本來8:45的筆試拖到9:15才開始,筆試的內容在宣講的時候説要考c語言,但是筆試的卷子都是通信知識,不過比較可取的一點就是不同的職位不同的卷子,目前為止,我參加的筆試內容都...
-
歐司朗筆試因禍得福
歐司朗筆試題目要求一小時搞定,主要包括:英語題目,專業題考什麼是光電效應,LED發光的原因,還有幾道畫圖的。都是電子的基礎題吧,可是我都不會做,唉!誰叫我過去不努力呢!胡亂寫些就過去了。前後不到10分鐘,然後就是問答題,英語回答,英語提問。第一題是中譯英,順便跟自己做下...