這些天我正在查看 中的跳過串列代碼Algorithms in C, Parts 1-4，當將新值插入到跳過串列時比我想象的要復雜。在插入程序中，代碼應確保新值i以 的概率插入到級別中1/2^i，這由以下代碼實作：
static int Rand()
{
int i, j = 0;
uint32_t t = rand();
for (i = 1, j = 2; i < lg_n_max; i , j = j)
if (t > RANDMAX / j)
break;
if (i > lg_n)
lg_n = i;
return i;
}
我不知道Rand函式是如何確保這一點的，你能幫我解釋一下嗎，謝謝。
uj5u.com熱心網友回復：
大概RANDMAX是打算RAND_MAX。
忽略舍入問題，一半的回傳值rand高于RAND_MAX / 2，因此有一半的時間，回圈以i= 1退出。
如果回圈繼續，它將更新i為 2 和j4。然后剩余的回傳值的一半（總數的 3/4）高于RAND_MAX / 4，因此，四分之一的時間，回圈以i= 2退出。
進一步的迭代以相同的方式繼續，每次迭代都以回傳值的一半退出，直到lg_n_max達到限制。
因此，忽略舍入問題和最終限制，例程回傳 1 一半的時間，2 四分之一的時間，3 八分之一的時間，依此類推。
lg_n在例程中沒有定義。它似乎是迄今為止例程回傳的最大值的記錄。
uj5u.com熱心網友回復：
感謝Eric Postpischil很多他的回答，我必須了解如何保證的概率。我有一個更容易理解的答案：t是0和之間的隨機值RANDMAX，我們假設回圈將運行 2 次。在第一環路中，值t是小于RANDMAX/2^1，意味著值t落入從范圍0到RANDMAX/2，這樣做的概率是1/2。在第二回圈中，記住這一事實的值t是在的范圍內 (0, RANDMAX/2^i)，的值t是越小RANDMAX/2^2，意味著值t落入從范圍0到RANDMAX/2^2，這樣做的概率也是1/2，因為范圍(0, RANDMAX/2^2)僅是1/2第一個回圈中的范圍，第一個回圈顯示的值t在 的范圍內(0, RANDMAX/2^1)。并且注意第二次回圈的概率是條件概率，它是基于第一次回圈的概率，所以第二次回圈的概率是1/2*1/2=1/4。
簡而言之，每個回圈都會帶來一個* 1/2到最后一個回圈的概率。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344363.html