UVa 10023 Square Root http://www.tcgs.tc.edu.tw/~sagit/luckycat/q10023.htm 給你一個整數Y，請你求出根號Y的值。 Input : 第1列有一個整數 n，代表接下來有n列測試資料。 每列測試資料有一個正整數Y（1 <= Y <=10^1000）。 我們保證Y一定是某一個正整數的平方。 Output : 每一筆測試資料請輸出根號Y的值，測試資料之間請輸出一空白行。 //========== Sample input 3 1024 7206604678144 81　 //========== Sample Output 32 2684512 9 ------------------------------------ 資料結構上採用「DJWS的網路日誌」中所述方式，以陣列將數字反序儲存，網頁如下 http://www.csie.ntnu.edu.tw/~u91029/BigNumber.html 且只先用一格存一位數的方式 找平方根時採用直覺的直式開方法，唯獨在決定下一位數時先用前幾位去猜 想法舉例如下： 假設 num = (9876504321 * 9876504321) = 97545337602731671041 (20位數) 先取前幾位可以放的進int的部分，若num為偶數就取偶數位, 奇數就取奇數位 用普通的sqrt處理 得到 result = sqrt(97543376) = 9876 result^2 = 97535376 接下來將前幾位取下, 並且先減掉目前算出來的result^2 97545337 (dividend) -97535376 --------- 9961 再來每次往後拿兩位 //=== 以下重複直到算出square root的每一位數 === 996160 (dividend) 並且希望求出result的下一位:X, 此時由於 9876X * 9876X <= 9754533760 (result*10+X)(result*10+X) <= 9754533760 9754533760 - 100*result*result >= 20*result*X + X*X 所以我們知道 dividend >= 20*X*result 用這個去猜X X <= (dividend/result)/20 其中dividend和result皆為大數, 不能直接做除法, 因此試圖捨棄一些精確度轉成int 猜 X = (int(dividend)/int(result))/20 + 1 雖然不精確, 但應該相差不遠 然後用這個猜的X去試試看是否 X*X + 20*result <= dividend 如果不是就將X遞減, 然後重複測試 ----- 測了蠻多測資都是正確的, 不知道什麼情況下會錯誤 或是code的哪裡出了問題呢? http://codepad.org/OOwvk2RB --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 112.104.11.16 ※ 編輯: bc5678 來自: 112.104.11.16 (09/26 23:29)