切換
舊版
前往
大廳
主題

ZeroJudge - d468: 簡單求冪題(求冪系列題3) 解題心得

Not In My Back Yard | 2018-11-04 13:36:08 | 巴幣 0 | 人氣 174

題目連結:


題目大意:
給定兩正整數 a 、 n ( -2 ^ 63 ≦ a ^ n ≦ 2 ^ 63 - 1 ),求 a ^ n 的值。

當 a = n = 「0」時,程式停止,並輸出「All Over.」。

註: a 、 n 要剛好各是 1 個「0」才停止。如果像是 a = 「00」、 n = 「0」,此時要輸出「0」,而程式要繼續執行。



範例輸入:
6 5
567 3
0 012
2 25
0 0



範例輸出:
7776
182284263
0
33554432
All Over.



解題思維:
一開始用字串讀入兩個數字字串,判斷是否剛好都為 "0" ,如果是就停止程式。

反之,就要把數字字串轉為一般數字。轉成數字的方法如下:

假設字串為 "48763"  ,一開始有一個變數 X = 0,而我們要讓 X = 48763 :
從字串最左邊開始跑,讀到 '4' ,把 X 乘以 10 ,再加上 4 。現 X = 4 。
讀到 '8' ,把 X 乘以 10 ,再加上 8 。現 X = 48 。
讀到 '7' ,把 X 乘以 10 ,再加上 7 。現 X = 487。
讀到 '6' ,把 X 乘以 10 ,再加上 6 。現 X = 4876 。
最後讀到 '3' ,把 X 乘以 10 ,再加上 3 。現 X = 48763 。
這樣便使得 X = 48763 了。

但是要小心字串有可能以負號('-')開頭,要預先處理。


把字串轉成數字後,判斷是否皆為 0 ,如果是就輸出 0 。

不然,再判斷 a 或 n 是否為 0 。如果 a 是 0 ,則輸出 0 ( 0 的任一次方為 0 );如果 n 是 0 ,則輸出 1 (任意數字的 0 次方為 1 )。

如果皆非,再判斷 a 是否是 1 ,如果是輸出 1 ;否則判斷 a 是否等於 -1 ,如果是還要再判斷 n 的奇偶性。 n 是偶數,輸出 1 ; n 是奇數,輸出 -1 。

排除了以上的特例之後,就可以直接運算 a ^ n 了。不過當然不能直接乘,要使用到以前提到的快速冪。先做 a ^ 2 、 a ^ 4 、 a ^ 8 等等,然後看 n 的二進位表示法,把相應次方的再乘起來。

最後輸出即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作