主題

【zerojudge】c031. 00264 - Count on Cantor

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

根據題目的規則，數字的排列模式如下圖所示

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

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

首先依題目規律第一組有一個數字、第二組有兩個數字、第三組有三個數字...... ，則前 k 組一共有 1+2+3+...+k = k * (k+1) / 2 個數字，為了包含所有測資，前 k 組的數字要超過 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 代表搜尋上下限，然後進入迴圈求中間組 middle，算出前 middle 組共有 sum 個數字，與測資 n 比較，如果 n 等於 sum 代表 n 恰好是第 middle 組的最後一個數字，就可以先離開程式去求答案，而如果 n 小於 sum 則讓 end 設成 middle -1，如果 n 大於 sum 則讓 head 設成 middle +1，一般而言絕大部分的 n 都不會等於 sum，最後都會因為條件不符才離開迴圈，此時 n 一定會在第 head 組，第 end 組則是比第 head 組少一組 ( end = head - 1 )，以下是詳細的解釋 :

(前提)

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

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

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

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

(1)若 n < sum，end 變成 middle -1而後離開迴圈，因為二分搜尋逐步縮小上下限，依照前提當離開迴

圈時 n 一定在第 middle 組，middle 又等於 head，因此 n 在第 head 組，與結論相同

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

過了上限，顯然是不可能產生這情況的

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

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

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

知 n 在第 middle 組也同時在第 head 組，與結論相同

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

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

(情形三) 如果 head +2 = end，根據程式的整數計算此時 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，根據程式的整數計算此時 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)，回到情形二

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

以上就是本題的個人思路歷程。