題目連結:
題目大意:
給定兩正整數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為例,則如下圖:
然後記得把轉換的次數存起來,最後要輸出。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。