主題

【zerojudge】c031. 00264 - Count on Cantor

椰果(?ω?)ノ奶茶 | 2024-03-19 22:32:38 | 巴幣 0 | 人氣 104

根據(jù)題目的規(guī)則，數(shù)字的排列模式如下圖所示

接著把上圖按照箭頭方向展開成一個(gè)數(shù)列，並且分組 :

只看紅色畫線的部分可以明顯看出每組都以自然數(shù)順序排列，只是有偶數(shù)個(gè)數(shù)字的組以分子排，有奇數(shù)個(gè)數(shù)字的組以分母排，題目給定一個(gè)數(shù)字 n 為此數(shù)列的項(xiàng)數(shù)，要你回答第 n 項(xiàng)數(shù)字為何，這裡我使用二分搜尋的方式解題，先找出第 n 項(xiàng)數(shù)字在第幾組內(nèi)，再去算他是該組當(dāng)中第幾個(gè)數(shù)字。

首先依題目規(guī)律第一組有一個(gè)數(shù)字、第二組有兩個(gè)數(shù)字、第三組有三個(gè)數(shù)字...... ，則前 k 組一共有 1+2+3+...+k = k * (k+1) / 2 個(gè)數(shù)字，為了包含所有測資，前 k 組的數(shù)字要超過 n 的上限一千萬，

即 k * (k+1) / 2 >= 10000000，算出 k 的最小值為 4472，所以我們就從第 1 組 ~ 第 4472 組來搜尋。

下面是大致的二分搜尋邏輯 :

head = 1;
middle = 0;
end = 4472;
while(head <= end) {
        middle = (head + end) / 2;
        sum = (1+middle) * middle / 2;
        if(n == sum)
                return ;
        else if(n < sum)
                end = middle-1;
        else
                head = middle+1;
}
middle = -1;
return ;

首先定義頭 head 跟尾 end 代表搜尋上下限，然後進(jìn)入迴圈求中間組 middle，算出前 middle 組共有 sum 個(gè)數(shù)字，與測資 n 比較，如果 n 等於 sum 代表 n 恰好是第 middle 組的最後一個(gè)數(shù)字，就可以先離開程式去求答案，而如果 n 小於 sum 則讓 end 設(shè)成 middle -1，如果 n 大於 sum 則讓 head 設(shè)成 middle +1，一般而言絕大部分的 n 都不會(huì)等於 sum，最後都會(huì)因?yàn)闂l件不符才離開迴圈，此時(shí) n 一定會(huì)在第 head 組，第 end 組則是比第 head 組少一組 ( end = head - 1 )，以下是詳細(xì)的解釋 :

(前提)

(1) n == sum，前面講過了 n 一定是第 middle 組最後一個(gè)數(shù)字，在 head == end 之前就會(huì)離開

(2) n < sum 代表前 middle 組總數(shù)比 n 還大，此時(shí)的 n 可能在第 middle 組也可能比 middle 組還小

(3) n > sum 代表前 middle 組總數(shù)比 n 還小，此時(shí)的 n 一定至少在第 middle +1 組或之後

(情形一) 如果 head 等於 end (仔細(xì)看迴圈條件)，此時(shí) middle 也與 head、end 相同

(1)若 n < sum，end 變成 middle -1而後離開迴圈，因?yàn)槎炙褜ぶ鸩娇s小上下限，依照前提當(dāng)離開迴

圈時(shí) n 一定在第 middle 組，middle 又等於 head，因此 n 在第 head 組，與結(jié)論相同

(2)若 n > sum，代表 n 在第 middle +1 組之後，但是情形一 head 等於 end 等於 middle，n 的位置超

過了上限，顯然是不可能產(chǎn)生這情況的

(情形二) 如果 head +1 等於 end，根據(jù)程式的整數(shù)計(jì)算此時(shí) middle 等於 head

( 例 head = 10，end = 11，則 middle = 10 )

(1)若 n < sum，end 變成 middle -1 (10-1)，因?yàn)?middle == head 所以 end 為 head -1 (=9)，由前提可

知 n 在第 middle 組也同時(shí)在第 head 組，與結(jié)論相同

(2)若 n > sum，head 變成 middle +1 (10+1)，因?yàn)?middle == head 所以在執(zhí)行完這一行後 head 就等

於 end 了，此時(shí)變成情形一再照上面判斷

(情形三) 如果 head +2 = end，根據(jù)程式的整數(shù)計(jì)算此時(shí) middle 等於 head +1 等於 end -1

( 例 head = 10，end = 12，則 middle = 11 )

(1)若 n < sum，end 變成 middle -1 (11-1)，那麼 head 就等於 end ( =10)，回到情形一

(2)若 n > sum，head 變成 middle +1 (11+1)，那麼 head 就等於 end ( =12)，回到情形一

(情形四) 如果 head +3 = end，根據(jù)程式的整數(shù)計(jì)算此時(shí) middle 等於 head +1

( 例 head = 10，end = 13，則 middle = 11 )

(1)若 n < sum，end 變成 middle -1 (11-1)，那麼 head 就等於 end ( =10)，回到情形一

(2)若 n > sum，head 變成 middle +1 (11+1)，那麼 head+1 就等於 end (12+1=13)，回到情形二

(情形五) 如果 head +4 = end

( 例 head = 10，end = 14，則 middle = 12 )

(1)若 n < sum，end 變成 middle -1 (12-1)，那麼 head+1 就等於 end (10+1=11)，回到情形二

(2)若 n > sum，head 變成 middle +1 (12+1)，那麼 head+1 就等於 end (13+1=14)，回到情形二

所有可能基本上都會(huì)變成情形一或情形二，可以自己多舉幾個(gè)例子或是寫程式看過程，總之最後得知 n 在第 head 組，而前 end 組共有 S = end * (end+1) /2 個(gè)數(shù)字，n 減去 S 就是 n 在這組的位置設(shè)為 k，所以第 n 項(xiàng)數(shù)字為 k / (head-k+1) 或 (head-k+1) / k，當(dāng) head 是偶數(shù)答案是前者， head 是奇數(shù)答案是後者，(如果不知道為什麼可以往上看那張數(shù)列的圖片，至於 head-k+1 這個(gè)加一的原因是分子分母和等於所屬組數(shù)加一)，求出第 n 項(xiàng)後記得依照要求輸出正確答案。

以上就是本題的個(gè)人思路歷程。