#23023: 解題紀錄


waynebox01 (麻糬)

School : 國立高雄大學
ID : 130336
IP address : [218.35.40.37]
Last Login :
2020-10-20 23:47:17
b893. 勘根定理 -- 板橋高中教學題 | From: [218.35.40.37] | Post Date : 2020-10-18 00:40

  其實是寫給自己看的紀錄,避免往後忘記為何如此寫程式碼......

1. 根據討論的內容,其中一項條件 -2,147,483,647 <= x^6 <= 2,147,483,647

  使得 x = 36 時, x^6 會超標,所以 表示 -35 <= x <= 35

2. 根據另一討論的內容,關於 #8 和 #9 的結果

  本人也一直跑出 OLE 的結果,其 輸出為 34 35

  在付出不少次 WA 後,一樣取得了 #8 和 #9 的測資......

  #8 : -40 -40 -40 -40 -40 39

  #9 :  40  40  40  40  40 39

  可知 問題應該是出在 "溢位" 上,

  以 #9 的測資為例:

  當 x 為 34 時, f(x) 為 1,872,490,199 ; 當 x 為 35 時, f(x) 為 -2,132,301,857

  因 x = 35 時,出現了 溢位 ,使得程式誤判在 34 ~ 35 區間有 奇數 個 根

 

  解決方法很簡單,最簡便的就是 使用 long long int 來進行計算了。

3. 接下來的問題,是關於 long long int 的計算問題,

  本人在程式碼中使用了 long long int 紀錄數字,但跑程式出來結果,卻還是會有 "溢位" 的問題產生

  去網路上查了一些資料之後,有成功克服這個問題了,一併紀錄下來供後續參考:

  假設 程式碼 : long long int value = 2,147,483,647+1;

  計算後輸出 的 value 仍舊等於 -2,147,483,648,

  其原因在於 雖然程式碼經編譯後,會由電腦自行幫忙 將 資料型態不符 的 資料進行轉型,

  但上述式子,電腦的轉型過程為:因 2,147,483,647 及 1 皆為 int,故無 轉型動作 直接計算,得結果 -1

  long long int value = -1 ,此時為了將 資料 -1 指定給 value ,才將 -1 強制轉型成 long long int 再 指定給 value

  

  因此 想要程式碼正確 應該 如下述這樣改:

  long long int value = (long long int) 2,147,483,647 + 1;

  計算 (long long int) 2,147,483,647 + 1 時,因 運算元 + 號 的左右兩端 型態不同,於是將 1 轉型成 long long int 進行計算,

  得 2,147,483,648 ,再將此結果 指定給 value

 

  懶人包:

  運算元 兩端 的資料型態 至少需有一項為 long long int ,才可避免 " 運算後 有 溢位 的錯誤資料 被轉型成 long long int 再 指定給 變數 "。

 

  另附上,研究 long long int 溢位 時看到解說比較詳盡的網頁:

  https://ithelp.ithome.com.tw/articles/10230507

 
ZeroJudge Forum