切換
舊版
前往
大廳
主題

ZeroJudge - d663: 11730 - Number Transformation 解題心得

Not In My Back Yard | 2018-10-23 20:40:12 | 巴幣 0 | 人氣 205

題目連結:


題目大意:
給定兩正整數S(1 ≦ S ≦ 100)、T(1 ≦ T ≦ 1, 000),求S轉換成T的最少次數。

轉換的方法為:有一正整數A可變成B,而B又可變為C。其中A加上A的質因數變為B,而B加上B自己的質因數(而不是A的)變成了C。此即為A轉換為C的一種方法。

如果S無法轉換成T,輸出-1。(注意:對於本題來說,A的質因數不包括自己。)

當S = T = 0 時,請停止程式。

註:原題敘述比較會讓人誤會,因此引入C(原本只有A和B的敘述)。



範例輸入:
6 12
6 13
0 0



範例輸出:
Case 1: 2
Case 2: -1
 


解題思維:
因為S可能經由很多個數字變成T,而中間的數字又有各自的質因數。因此,這題要採取廣度優先搜尋(BFS)的策略。

一開始先判斷S有哪些質因數,把它們加上S並放進陣列或佇列裡存起來。

然後對於那些數字再各自找它們的質因數,得到一些新的數字,然後判斷新的數字是否有出現在陣列裡過。有的話,就不用再放進去了,因為已經做過了(或是正要搜尋)。

倘若新的數字超過T了,也不用繼續搜尋這個數字。搜尋直到碰到了T才停止。

以上若以S=10、T=18為例,則如下圖:
然後記得把轉換的次數存起來,最後要輸出。




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

創作回應

更多創作