切換
舊版
前往
大廳
主題

ZeroJudge - e793: an easy gcd problem 解題心得

Not In My Back Yard | 2020-02-29 00:11:01 | 巴幣 0 | 人氣 162

題目連結:


題目大意:
輸入有多列,每列給定兩正整數 a 、 b (皆可用 long long 型態(64 位元整數)儲存,當 a = b = 0 時代表輸入結束),求 a 、 b 的最大公因數。

但是不得使用 if..else.., <cstdio>以外的函式庫, #define, &&, ||, /, while, do..while, goto, break, continue, for, 三元運算子, switch..case, operator。

以上這些比較針對 C/C++ ,對於其他語言有各自的對應,在此不贅述。



範例輸入:
1 1
923 1
6 3
0 0


範例輸出:
1
1
3


解題思維:
定義兩個函式 A(a, b) 、 B(a, b) ,A 只回傳參數 a 、B 則根據 a % b 的值來決定呼叫 A(b, a % b) 還是 B(b, a % b) 。雖然不能使用 if 等指令,但是可以使用 ! 運算子,將數字轉成 0 或是 1 。如果 n = 0 ,則 !n 為 1 ;反之,n ≠ 0 ,則 !n 為 0 。

將 A 、 B 放入陣列之中,並用函式指標去指向他們再搭配 ! 運算子就可以實現原本求最大公因數的輾轉相除法之遞迴。

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

創作回應

追蹤 創作集

作者相關創作

更多創作