Backtracking

Integer Transformation Problem

Description

整數變換問題。關於整數 i 的變換 f 和 g 定義如下：f(i)=3i；g(i)=i/2 (向下取整)。試設計一個算法，對於給定的 2 個整數 n 和 m，用最少的 f 和 g 變換次數將 n 變換為 m。例如，可以將整數 15 用 4 次變換將它變換為整數 4：4=gfgg(15)。當整數 n 不可能變換為整數 m 時，算法應如何處理?

Input

由文件 input.txt 給出輸入數據。第一行有 2 個正整數 n 和 m。

Output

將計算出的最少變換次數以及相應的變換序列輸出到文件 output.txt。文件的第一行是最少變換次數。文件的第 2 行是相應的變換序列。

Sample

輸入文件示例

input.txt

15 4

輸出文件示例

output.txt 4 gfgg

Analysis

DFS

定義 轉變函數 (Transformation Function) $f(x)$ 和 $g(x)$

由於需要求出，對於給定輸入整數n，是否可以 某種轉變函數序列來 轉變到 整數m

我們不妨首先考慮使用 Brute-Force Method來處理該問題。

因為存在2種轉變方式，所以我們定義的遞歸是 2路遞歸。

換句話說，這個 遞歸方法產生的 解空間樹是一顆 二叉樹

同時，我們通過題意可知，遞歸次數的下界為 0，但 遞歸次數的上界未知。

我們做一個 猜測：如果 遞歸次數超過 整數n，則 不太可能 存在解。

於是，對於該方法，我們會按照 深度優先搜索的順序來訪問 解空間樹

假設我們已知擁有了 整顆解空間樹 (二叉樹)。則實際上，我們會直觀地發現，

我們會從 樹根節點開始，沿著一條 路徑做 深度搜索，直到抵達 我們設定的最大層次（也就是我們預測的遞歸次數的上界），再進行 回溯。（這個過程產生的方案是： $f \rightarrow ff \rightarrow fff \cdots \rightarrow \underbrace{f\cdots f}_{我們設定的遞歸的最大深度}$
graph TD;
root((root)) --> f((f));
style f fill:pink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:pink,stroke:#333,stroke-width:4px
f --> fg((g));
g --> gf((f));
g --> gg((g));
ff --> fff((f));
style fff fill:pink,stroke:#333,stroke-width:4px
ff --> ffg((g));
fg --> fgf((f));
fg --> fgg((g));
gf --> gff((f));
gf --> gfg((g));
gg --> ggf((f));
gg --> ggg((g));
fff --> ffff((f));
style ffff fill:pink,stroke:#333,stroke-width:4px
fff --> fffg((g));
ffg --> ffgf((f));
ffg --> ffgg((g));
fgf --> fgff((f));
fgf --> fgfg((g));
fgg --> fggf((f));
fgg --> fggg((g));
gff --> gfff((f));
gff --> gffg((g));
gfg --> gfgf((f));
gfg --> gfgg((g));
ggf --> ggff((f));
ggf --> ggfg((g));
ggg --> gggf((f));
ggg --> gggg((g));
當然，如果說，在 沿著當前路徑 抵達人為設定的遞歸的最大深度之前，我們 幸運地發現，已經找到了 解。

但是請註意：這個 解並不一定是 最優解，因為我們實際上進行的是 深度優先搜索。

這個解只不過是 當前搜索路徑上的 最優解：因為在 當前搜索路徑上，該解是 第一個被發現的解。

根據題目的性質，我們可以知道，在該條路徑上的後續發現的解 並不會 優於 在該條路徑上被發現的第一個解。

如果，我們 十分不幸運，在 沿著該條深度優先搜索路徑 抵達我們人為設定的最大遞歸深度時，仍然 未發現解，

則此時我們方法會見 回溯1步： $f\cdots fff \rightarrow f \cdots ffg$
graph TD;
root((root)) --> f((f));
style f fill:pink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:pink,stroke:#333,stroke-width:4px
f --> fg((g));
g --> gf((f));
g --> gg((g));
ff --> fff((f));
style fff fill:pink,stroke:#333,stroke-width:4px
ff --> ffg((g));
fg --> fgf((f));
fg --> fgg((g));
gf --> gff((f));
gf --> gfg((g));
gg --> ggf((f));
gg --> ggg((g));
fff --> ffff((f));
fff --> fffg((g));
style fffg fill:pink,stroke:#333,stroke-width:4px
ffg --> ffgf((f));
ffg --> ffgg((g));
fgf --> fgff((f));
fgf --> fgfg((g));
fgg --> fggf((f));
fgg --> fggg((g));
gff --> gfff((f));
gff --> gffg((g));
gfg --> gfgf((f));
gfg --> gfgg((g));
ggf --> ggff((f));
ggf --> ggfg((g));
ggg --> gggf((f));
ggg --> gggg((g));
如果此時還 未發現解，則 再回溯1步： $f\cdots ffg \rightarrow f\cdots fgf$
graph TD;
root((root)) --> f((f));
style f fill:pink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:pink,stroke:#333,stroke-width:4px
f --> fg((g));
g --> gf((f));
g --> gg((g));
ff --> fff((f));
ff --> ffg((g));
style ffg fill:pink,stroke:#333,stroke-width:4px
fg --> fgf((f));
fg --> fgg((g));
gf --> gff((f));
gf --> gfg((g));
gg --> ggf((f));
gg --> ggg((g));
fff --> ffff((f));
fff --> fffg((g));
ffg --> ffgf((f));
style ffgf fill:pink,stroke:#333,stroke-width:4px
ffg --> ffgg((g));
fgf --> fgff((f));
fgf --> fgfg((g));
fgg --> fggf((f));
fgg --> fggg((g));
gff --> gfff((f));
gff --> gffg((g));
gfg --> gfgf((f));
gfg --> gfgg((g));
ggf --> ggff((f));
ggf --> ggfg((g));
ggg --> gggf((f));
ggg --> gggg((g));
如果仍然 未發現解，則 再回溯一步： $f\cdots fgf \rightarrow f\cdots fgg$
graph TD;
root((root)) --> f((f));
style f fill:pink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:pink,stroke:#333,stroke-width:4px
f --> fg((g));
g --> gf((f));
g --> gg((g));
ff --> fff((f));
ff --> ffg((g));
style ffg fill:pink,stroke:#333,stroke-width:4px
fg --> fgf((f));
fg --> fgg((g));
gf --> gff((f));
gf --> gfg((g));
gg --> ggf((f));
gg --> ggg((g));
fff --> ffff((f));
fff --> fffg((g));
ffg --> ffgf((f));
ffg --> ffgg((g));
style ffgg fill:pink,stroke:#333,stroke-width:4px
fgf --> fgff((f));
fgf --> fgfg((g));
fgg --> fggf((f));
fgg --> fggg((g));
gff --> gfff((f));
gff --> gffg((g));
gfg --> gfgf((f));
gfg --> gfgg((g));
ggf --> ggff((f));
ggf --> ggfg((g));
ggg --> gggf((f));
ggg --> gggg((g));

對此，我們發現一個 比較嚴重的問題。

我們觀察到，該 深度優先搜索方法在 每一個遞歸層次都會 按順序執行 $f(x)$ 和 $g(x)$ ，

所以，它會先 沿著一條路徑不斷下降到 $f \cdots fff$

graph TD;
root((root)) --> f((f));
style f fill:pink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:pink,stroke:#333,stroke-width:4px
f --> fg((g));
g --> gf((f));
g --> gg((g));
ff --> fff((f));
style fff fill:pink,stroke:#333,stroke-width:4px
ff --> ffg((g));
fg --> fgf((f));
fg --> fgg((g));
gf --> gff((f));
gf --> gfg((g));
gg --> ggf((f));
gg --> ggg((g));
fff --> ffff((f));
style ffff fill:pink,stroke:#333,stroke-width:4px
fff --> fffg((g));
ffg --> ffgf((f));
ffg --> ffgg((g));
fgf --> fgff((f));
fgf --> fgfg((g));
fgg --> fggf((f));
fgg --> fggg((g));
gff --> gfff((f));
gff --> gffg((g));
gfg --> gfgf((f));
gfg --> gfgg((g));
ggf --> ggff((f));
ggf --> ggfg((g));
ggg --> gggf((f));
ggg --> gggg((g));

如果，我們要尋找的 最優解它不是以 $f$ 作為前綴的，

那麽，我們對 這整條深度優先搜索路徑所做的搜索的工作 都是浪費的！

更極端地，如果 最優解是 $g \cdots ggg$ ，那麽，我們 所做的絕大部分搜索都將是 無用的

graph TD;
root((root)) --> f((f));
root((root)) --> g((g));
style g fill:lightgreen,stroke:#333,stroke-width:4px
f --> ff((f));
f --> fg((g));
g --> gf((f));
g --> gg((g));
style gg fill:lightgreen,stroke:#333,stroke-width:4px
ff --> fff((f));
ff --> ffg((g));
fg --> fgf((f));
fg --> fgg((g));
gf --> gff((f));
gf --> gfg((g));
gg --> ggf((f));
gg --> ggg((g));
style ggg fill:lightgreen,stroke:#333,stroke-width:4px
fff --> ffff((f));
fff --> fffg((g));
ffg --> ffgf((f));
ffg --> ffgg((g));
fgf --> fgff((f));
fgf --> fgfg((g));
fgg --> fggf((f));
fgg --> fggg((g));
gff --> gfff((f));
gff --> gffg((g));
gfg --> gfgf((f));
gfg --> gfgg((g));
ggf --> ggff((f));
ggf --> ggfg((g));
ggg --> gggf((f));
ggg --> gggg((g));
style gggg fill:lightgreen,stroke:#333,stroke-width:4px

不妨再考慮一個 不幸運的情況：最優解 如果是 以g作為前綴，但 它的長度卻比較小。

那麽我們也會做 大部分沒有意義的搜索，因為該 算法不管 最優解的長度有多麽小，都要按 深度優先搜索的方式，不斷下降（使轉變函數序列的長度增長），不斷 下降和 回溯 尋求解。(如果在 下降過程沒有發現解，那麽就只能通過 回溯後接著 下降，再繼續尋找解)

Iterative-Deepening DFS

首先，我們解決一下 這個不幸運的情況：如果 最優解它足夠短，我們希望 搜索算法不要 下降到我們設定的最大深度，然後通過 逐步回溯來發現這個 長度較短的最優解。而是說，我們希望讓 搜索算法盡量找找看，有沒有 長度較短的解，如果 長度較短的解 的確找不到，那麽我們再 尋找長度較長的解

實際上，根據這道題目的性質。我們也不應該采用 深度優先搜索。

因此，我們可以使用 叠代加深搜索 (Iterative-Deepening DFS)：

在 深度為1的解空間樹中進行 搜索，若找到 解則立即返回。
在 深度為2的解空間樹中進行 搜索，若找到 解則立即返回。
$\cdots$
在 深度為k的解空間樹 中進行 搜索，若找到 解則立即返回。
在 深度為k以內的解空間樹中 無解！

graph TD;
root((root)) --> f((f));
style f fill:lightpink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:lightgray,stroke:#333,stroke-width:4px
f --> fg((g));
style fg fill:lightgray,stroke:#333,stroke-width:4px
g --> gf((f));
style gf fill:lightgray,stroke:#333,stroke-width:4px
g --> gg((g));
style gg fill:lightgray,stroke:#333,stroke-width:4px
ff --> fff((f));
style fff fill:lightgray,stroke:#333,stroke-width:4px
ff --> ffg((g));
style ffg fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgf((f));
style fgf fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgg((g));
style fgg fill:lightgray,stroke:#333,stroke-width:4px
gf --> gff((f));
style gff fill:lightgray,stroke:#333,stroke-width:4px
gf --> gfg((g));
style gfg fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggf((f));
style ggf fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggg((g));
style ggg fill:lightgray,stroke:#333,stroke-width:4px
fff --> ffff((f));
style ffff fill:lightgray,stroke:#333,stroke-width:4px
fff --> fffg((g));
style fffg fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgf((f));
style ffgf fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgg((g));
style ffgg fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgff((f));
style fgff fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgfg((g));
style fgfg fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggf((f));
style fggf fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggg((g));
style fggg fill:lightgray,stroke:#333,stroke-width:4px
gff --> gfff((f));
style gfff fill:lightgray,stroke:#333,stroke-width:4px
gff --> gffg((g));
style gffg fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgf((f));
style gfgf fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgg((g));
style gfgg fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggff((f));
style ggff fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggfg((g));
style ggfg fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggf((f));
style gggf fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggg((g));
style gggg fill:lightgray,stroke:#333,stroke-width:4px

graph TD;
root((root)) --> f((f));
root((root)) --> g((g));
style g fill:lightpink,stroke:#333,stroke-width:4px
f --> ff((f));
style ff fill:lightgray,stroke:#333,stroke-width:4px
f --> fg((g));
style fg fill:lightgray,stroke:#333,stroke-width:4px
g --> gf((f));
style gf fill:lightgray,stroke:#333,stroke-width:4px
g --> gg((g));
style gg fill:lightgray,stroke:#333,stroke-width:4px
ff --> fff((f));
style fff fill:lightgray,stroke:#333,stroke-width:4px
ff --> ffg((g));
style ffg fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgf((f));
style fgf fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgg((g));
style fgg fill:lightgray,stroke:#333,stroke-width:4px
gf --> gff((f));
style gff fill:lightgray,stroke:#333,stroke-width:4px
gf --> gfg((g));
style gfg fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggf((f));
style ggf fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggg((g));
style ggg fill:lightgray,stroke:#333,stroke-width:4px
fff --> ffff((f));
style ffff fill:lightgray,stroke:#333,stroke-width:4px
fff --> fffg((g));
style fffg fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgf((f));
style ffgf fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgg((g));
style ffgg fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgff((f));
style fgff fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgfg((g));
style fgfg fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggf((f));
style fggf fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggg((g));
style fggg fill:lightgray,stroke:#333,stroke-width:4px
gff --> gfff((f));
style gfff fill:lightgray,stroke:#333,stroke-width:4px
gff --> gffg((g));
style gffg fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgf((f));
style gfgf fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgg((g));
style gfgg fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggff((f));
style ggff fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggfg((g));
style ggfg fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggf((f));
style gggf fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggg((g));
style gggg fill:lightgray,stroke:#333,stroke-width:4px

graph TD;
root((root)) --> f((f));
style f fill:lightpink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
style ff fill:lightpink,stroke:#333,stroke-width:4px
f --> fg((g));
g --> gf((f));
g --> gg((g));
ff --> fff((f));
style fff fill:lightgray,stroke:#333,stroke-width:4px
ff --> ffg((g));
style ffg fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgf((f));
style fgf fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgg((g));
style fgg fill:lightgray,stroke:#333,stroke-width:4px
gf --> gff((f));
style gff fill:lightgray,stroke:#333,stroke-width:4px
gf --> gfg((g));
style gfg fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggf((f));
style ggf fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggg((g));
style ggg fill:lightgray,stroke:#333,stroke-width:4px
fff --> ffff((f));
style ffff fill:lightgray,stroke:#333,stroke-width:4px
fff --> fffg((g));
style fffg fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgf((f));
style ffgf fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgg((g));
style ffgg fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgff((f));
style fgff fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgfg((g));
style fgfg fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggf((f));
style fggf fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggg((g));
style fggg fill:lightgray,stroke:#333,stroke-width:4px
gff --> gfff((f));
style gfff fill:lightgray,stroke:#333,stroke-width:4px
gff --> gffg((g));
style gffg fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgf((f));
style gfgf fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgg((g));
style gfgg fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggff((f));
style ggff fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggfg((g));
style ggfg fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggf((f));
style gggf fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggg((g));
style gggg fill:lightgray,stroke:#333,stroke-width:4px

graph TD;
root((root)) --> f((f));
style f fill:lightpink,stroke:#333,stroke-width:4px
root((root)) --> g((g));
f --> ff((f));
f --> fg((g));
style fg fill:lightpink,stroke:#333,stroke-width:4px
g --> gf((f));
g --> gg((g));
ff --> fff((f));
style fff fill:lightgray,stroke:#333,stroke-width:4px
ff --> ffg((g));
style ffg fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgf((f));
style fgf fill:lightgray,stroke:#333,stroke-width:4px
fg --> fgg((g));
style fgg fill:lightgray,stroke:#333,stroke-width:4px
gf --> gff((f));
style gff fill:lightgray,stroke:#333,stroke-width:4px
gf --> gfg((g));
style gfg fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggf((f));
style ggf fill:lightgray,stroke:#333,stroke-width:4px
gg --> ggg((g));
style ggg fill:lightgray,stroke:#333,stroke-width:4px
fff --> ffff((f));
style ffff fill:lightgray,stroke:#333,stroke-width:4px
fff --> fffg((g));
style fffg fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgf((f));
style ffgf fill:lightgray,stroke:#333,stroke-width:4px
ffg --> ffgg((g));
style ffgg fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgff((f));
style fgff fill:lightgray,stroke:#333,stroke-width:4px
fgf --> fgfg((g));
style fgfg fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggf((f));
style fggf fill:lightgray,stroke:#333,stroke-width:4px
fgg --> fggg((g));
style fggg fill:lightgray,stroke:#333,stroke-width:4px
gff --> gfff((f));
style gfff fill:lightgray,stroke:#333,stroke-width:4px
gff --> gffg((g));
style gffg fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgf((f));
style gfgf fill:lightgray,stroke:#333,stroke-width:4px
gfg --> gfgg((g));
style gfgg fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggff((f));
style ggff fill:lightgray,stroke:#333,stroke-width:4px
ggf --> ggfg((g));
style ggfg fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggf((f));
style gggf fill:lightgray,stroke:#333,stroke-width:4px
ggg --> gggg((g));
style gggg fill:lightgray,stroke:#333,stroke-width:4px

$\cdots$

註意兩點：

我們可以 立即返回是因為：根據 題目性質，要求求解 最短/最小的解

算法最終 報告無解並不一定表示 原問題無解：這取決於 我們設定的最大遞歸深度 $k$

最大深度 $k$ 的設定需要我們根據題目分析得到，它可以是 靜態的，也可以是 動態的。

它可以是 不確切的上界，但至少我們希望 要保證k足夠大，使得不會遺漏解

於是，我們需要做下面這些工作：

定義 遞歸次數的上界估計函數 (價值函數) $\implies \text{estimate(args) -> int k }$

在 DFS Method中，我們並沒有定義這個 上界估計函數，

因為~~我們偷偷看了輸入數據~~ 如果 k的上界非常大的話，對於 DFS Method方法是 沒有意義的，

因為根據 DFS和 該問題的特性，所產生的DFS樹會 迅速膨脹到 我們無法在規定時間內求得解，而這個 非常大的k值也 根本不會被觸碰到

對於 IDDFS，我們可以根據 題目性質 設置 合適的上界估計函數。

但要註意，如果 最優解的 深度確實很大，那麽 IDDFS也會面臨 DFS樹 迅速膨脹 的 困境

不過，IDDFS對於 最優解的深度較小的情況是非常適合的。
根據 題目性質為 遞歸方法 定義 所需的全局變量
我們當然可以使用 遞歸方法所屬的方法棧的局部內存來存儲 所需要的變量
- 但是，這往往會導致 重復拷貝和傳遞相同的參數和 產生大量結構高度相似的冗余信息
這不僅僅是 空間上的問題，還包括做這些工作所用的 時間

如果你使用的是 C/C++等提供 指針/引用的 編程語言，可能會有些 奇怪的想法。

但請重新考慮一下：一個4字節的指針並不會比 一個4字節的整數更節約空間。

一般來說，每個遞歸方法的一個幀棧如果 只做一個選擇，那麽我們實際上只需要 保存所做的選擇和 當前深度即可。

比如說，要求 每一個遞歸方法的函數調用幀棧 進行 選擇一個數字，選擇一個轉變函數等等。
- 使用 遞歸函數的函數調用幀棧但 僅保存必要信息
該方法可行，但 回溯時會稍微麻煩一些，仍然不如直接使用 全局變量
按k遞增方式執行k次 DFS $\implies \text{search(k) -> bool found}$

之所以能夠在 第一次發現解後 判定該解就是最優解並 終止算法是取決於 題目性質

如果 題目所求的最優解 與 遞歸的深度（也就是最優解和長度無關）無關，那麽 IDDFS可能並不會更有效。
若第一次發現任何解則 立即終止搜索並 返回該解 ，否則報告 無解

Solution

DFS

Source

    public static int f(int i) {
        return 3 * i;
    }

    public static int g(int i) {
        return i / 2;
    }
    
    public static String ans_string;
    
    public static void solve(int n, int m, int limit, String ops) {
    
        // Base Case
        if ((n == m) || (n == 0) || (m == 0) || (ops.length() > ans_string.length()) || limit >= 30) {
            if (n == m) {
                if (ops.length() < ans_string.length()) {
                    ans_string = ops;
                }
            }
            return;
        }
    
        // Recursion Case
        solve(f(n), m, limit + 1, "f" + ops);
        solve(g(n), m, limit + 1, "g" + ops);
    }

Benchmark

-----------------------------------------------------
Current Case: FUNC0.in & FUNC0.out
Expected  Input: [15 4]
Expected Output: [4, gfgg]
Your     Output: [4, gfgg]
Time Cost: 157.343000 ms (157343000 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC1.in & FUNC1.out
Expected  Input: [115 8]
Expected Output: [9, gggggggff]
Your     Output: [9, gggggggff]
Time Cost: 3852.005300 ms (3852005300 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC10.in & FUNC10.out
Expected  Input: [11838 127878]
Expected Output: [25, ggffffggggfgggfffffgggggf]
Your     Output: [25, ggffffggggfgggfffffgggggf]
Time Cost: 15302.874100 ms (15302874100 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC2.in & FUNC2.out
Expected  Input: [82 54]
Expected Output: [8, fffggggg]
Your     Output: [8, fffggggg]
Time Cost: 295.231800 ms (295231800 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC3.in & FUNC3.out
Expected  Input: [56 125]
Expected Output: [22, ggggggffffffgggggggfff]
Your     Output: [22, ggggggffffffgggggggfff]
Time Cost: 3743.782100 ms (3743782100 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC4.in & FUNC4.out
Expected  Input: [115 111]
Expected Output: [18, fgfgfgggggfffggggf]
Your     Output: [18, fgfgfgggggfffggggf]
Time Cost: 13528.005700 ms (13528005700 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC5.in & FUNC5.out
Expected  Input: [210 24907]
Expected Output: [24, gffgggggfffffffffggggggf]
Your     Output: [24, gffgggggfffffffffggggggf]
Time Cost: 14796.151600 ms (14796151600 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC6.in & FUNC6.out
Expected  Input: [50961 91791]
Expected Output: [25, fggffffgggggggggggggfffff]
Your     Output: [25, fggffffgggggggggggggfffff]
Time Cost: 2660.372100 ms (2660372100 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC7.in & FUNC7.out
Expected  Input: [59338 486]
Expected Output: [22, fffffggggggggggggggggf]
Your     Output: [22, fffffggggggggggggggggf]
Time Cost: 2700.998700 ms (2700998700 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC8.in & FUNC8.out
Expected  Input: [53530 750062539]
Expected Output: [25, gfgfgfffffffffggfgggggfff]
Your     Output: [25, gfgfgfffffffffggfgggggfff]
Time Cost: 5185.903400 ms (5185903400 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC9.in & FUNC9.out
Expected  Input: [96418 37529284]
Expected Output: [25, gffffffgggggggggggfffffff]
Your     Output: [25, gffffffgggggggggggfffffff]
Time Cost: 2065.022700 ms (2065022700 ns)
Accepted.
-----------------------------------------------------
Result Statistics: √ √ √ √ √ √ √ √ √ √ √

Iterative Deepening DFS

Source

    public static int f(int i) {
        return 3 * i;
    }

    public static int g(int i) {
        return i / 2;
    }
    
    /* Global Variable */
    private static int n;
    private static int m;
    private static int k;
    private static boolean[] performF;
    
    public static int estimate(int n, int m) {
        return n;
    }
    
    public static boolean found() {
        int value = n;
        for (int i = 0; i < k; i++) {
            if (performF[i]) {
                value = f(value);
            } else value = g(value);
        }
        return value == m;
    }
    
    public static void printCurrentPlan() {
        for (int i = k - 1; i >= 0; i--) {
            System.out.print(performF[i] ? "f" : "g");
        }
    
    }
    
    public static boolean search(int depth) {
    
        /* Base Case */
        if (depth >= k) {
            return found();
        }
    
        /* Recursion Case */
        // At any depth, we can have 2 choices:
    
        /* Perform f */
        performF[depth] = true;
        if (search(depth + 1)) {
            return true;
        }
    
        /* Perform g */
        performF[depth] = false;
        if (search(depth + 1)) {
            return true;
        }
    
        // If we can't perform either f or g, we backtrack
        return false;
    }
    
    public static void solve(Scanner scanner) {
        n = scanner.nextInt();
        m = scanner.nextInt();
        int estimate = estimate(n, m);
        performF = new boolean[estimate + 1];
    
        /* K-Search */
        // k means perform tiems
        for (k = 0; k <= estimate; k++) {
            if (search(0)) {
                System.out.println(k);
                printCurrentPlan();
                break;
            }
        }
    }

Benchmark

-----------------------------------------------------
Current Case: FUNC0.in & FUNC0.out
Expected  Input: [15 4]
Expected Output: [4, gfgg]
Your     Output: [4, gfgg]
Time Cost: 3.844700 ms (3844700 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC1.in & FUNC1.out
Expected  Input: [115 8]
Expected Output: [9, gggggggff]
Your     Output: [9, gggggggff]
Time Cost: 1.549000 ms (1549000 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC10.in & FUNC10.out
Expected  Input: [11838 127878]
Expected Output: [25, ggffffggggfgggfffffgggggf]
Your     Output: [25, ggffffggggfgggfffffgggggf]
Time Cost: 2137.224700 ms (2137224700 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC2.in & FUNC2.out
Expected  Input: [82 54]
Expected Output: [8, fffggggg]
Your     Output: [8, fffggggg]
Time Cost: 0.945200 ms (945200 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC3.in & FUNC3.out
Expected  Input: [56 125]
Expected Output: [22, ggggggffffffgggggggfff]
Your     Output: [22, ggggggffffffgggggggfff]
Time Cost: 193.517300 ms (193517300 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC4.in & FUNC4.out
Expected  Input: [115 111]
Expected Output: [18, fgfgfgggggfffggggf]
Your     Output: [18, fgfgfgggggfffggggf]
Time Cost: 16.105000 ms (16105000 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC5.in & FUNC5.out
Expected  Input: [210 24907]
Expected Output: [24, gffgggggfffffffffggggggf]
Your     Output: [24, gffgggggfffffffffggggggf]
Time Cost: 1017.764000 ms (1017764000 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC6.in & FUNC6.out
Expected  Input: [50961 91791]
Expected Output: [25, fggffffgggggggggggggfffff]
Your     Output: [25, fggffffgggggggggggggfffff]
Time Cost: 1749.323400 ms (1749323400 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC7.in & FUNC7.out
Expected  Input: [59338 486]
Expected Output: [22, fffffggggggggggggggggf]
Your     Output: [22, fffffggggggggggggggggf]
Time Cost: 256.666400 ms (256666400 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC8.in & FUNC8.out
Expected  Input: [53530 750062539]
Expected Output: [25, gfgfgfffffffffggfgggggfff]
Your     Output: [25, gfgfgfffffffffggfgggggfff]
Time Cost: 1587.514600 ms (1587514600 ns)
Accepted.
-----------------------------------------------------
Current Case: FUNC9.in & FUNC9.out
Expected  Input: [96418 37529284]
Expected Output: [25, gffffffgggggggggggfffffff]
Your     Output: [25, gffffffgggggggggggfffffff]
Time Cost: 1395.128700 ms (1395128700 ns)
Accepted.
-----------------------------------------------------
Result Statistics: √ √ √ √ √ √ √ √ √ √ √

Computation without Priority Problem

Description

給定 n 個正整數和 4 個運算符＋、－、∗、/，且運算符無優先級，如 2+3∗5=25。對於任意給定的整數 m，試設計一個算法，用以上給出的 n 個數和 4 個運算符，產生整數 m，且用的運算次數最少。給出的 n 個數中每個數最多只能用 1 次，但每種運算符可以任意使用。

Input

對於給定的 n 個正整數，設計一個算法，用最少的無優先級運算次數產生整數 m。

Output

由文件 input.txt 給出輸入數據。第一行有 2 個正整數 n 和 m。第 2 行是給定的用於運算的 n 個正整數。

Sample

輸入文件示例

input.txt

5 25 5 2 3 6 7

輸出文件示例

output.txt

2 2+3*5

Analysis

DFS

我們給出該問題的 BFS Method，該解法使用 Token存儲 已使用的數字和 參與運算的運算符信息。

遞歸過程維護 Token的鏈表，通過 遍歷Token鏈表來獲得一個 運算方案。

IDDFS

不同於 Integer Transformation Problem的 遞歸過程：在 DFS樹的 每一層只需要選擇 轉變方法

Computation without Priority Problem的 遞歸過程：在 DFS樹的 每一層 不但要選擇 使用的數字，還要選擇 使用的運算符

不過，這並沒有什麽不同。因為，我們使用的是 回溯法。

我們只管 嘗試所有可能的選法，如果最終 發現確實 DFS樹的某層的選擇確實是錯的，

那麽我們進行 回溯即可！然後繼續尋找 問題的解

另外，這裏我們不討論 剪枝的問題，盡管使用 剪枝可以再進一步優化該方法。

Solution

BFS

Source

    enum Operators {
        ADDICTION("+"), SUBTRACTION("-"), MULTIPLICATION("*"), DIVISION("/"), NONE("");

        private final String operatorString;
    
        Operators(String operatorString) {
            this.operatorString = operatorString;
        }
    
        public String toString() {
            return this.operatorString;
        }
    }
    
    static class Token {
        public Token parent;
        public int value;
        public int operand;
        public String operator;
        public int length;
    
        public Token(Token parent, int value, int operand, String operator) {
            this.parent = parent;
            this.value = value;
            this.operand = operand;
            this.operator = operator;
            this.length = parent != null ? parent.length + 1 : 1;
        }
    
        public ArrayList<Integer> listUsedOperands() {
            ArrayList<Integer> operands = new ArrayList<>();
            Token current = this;
            while (current != null) {
                operands.add(current.operand);
                current = current.parent;
            }
            return operands;
        }
    
        public String getPath() {
            StringBuilder sb = new StringBuilder();
            getPath(sb, this);
            return sb.toString();
        }
    
        private void getPath(StringBuilder sb, Token currentToken) {
            if (currentToken != null) {
                getPath(sb, currentToken.parent);
                sb.append(currentToken.operator).append(currentToken.operand);
            }
        }
    
        @Override
        public String toString() {
            return this.getPath();
        }
    }


    /*
    Current Case: ARIT0.in & ARIT0.out
    Expected  Input: [5 25, 5 2 3 6 7]
    Expected Output: [2, 2+3*5]
    
    5 2 3 6 7
    0 0 0 0 0
    */
    public static Token solve(ArrayList<Integer> nums, int m) {
    
        /* Initialize the tokens */
        LinkedList<Token> tokens = new LinkedList<>();
        for (int num : nums) {
            // If we are lucky enough...
            if (num == m) return new Token(null, m, m, Operators.NONE.toString());
            tokens.add(new Token(null, num, num, Operators.NONE.toString()));
        }
    
        /* Brute-Force-Search */
        for (int level = 0; level < nums.size(); level++) {
    
            int SIZE = tokens.size();
            for (int amount = 0; amount < SIZE; amount++) {
    
                /* Get the first token */
                Token currentToken = tokens.poll();
    
                /* Generate tokens */
                // Get unused nums
                ArrayList<Integer> unusedNums = new ArrayList<>(nums);
                currentToken.listUsedOperands().forEach(unusedNums::remove);
    
                // Try all operators
                for (int num : unusedNums) {
    
                    for (Operators operator : Operators.values()) {
                        if (operator == Operators.NONE) continue;
    
                        int newValue;
                        switch (operator) {
                            case ADDICTION:
                                newValue = currentToken.value + num;
                                break;
                            case SUBTRACTION:
                                newValue = currentToken.value - num;
                                break;
                            case MULTIPLICATION:
                                newValue = currentToken.value * num;
                                break;
                            case DIVISION:
                                newValue = currentToken.value / num;
                                break;
                            default:
                                newValue = 0xdead;
                        }
    
                        /* Push */
                        Token newToken = new Token(currentToken, newValue, num, operator.toString());
    
                        /* Found ? */
                        if (newToken.value == m) {
                            return newToken;
                        } else tokens.add(newToken);
                    }
                }
            }
        }
        return null;
    }

Benchmark

-----------------------------------------------------
Current Case: ARIT0.in & ARIT0.out
Expected  Input: [5 25, 5 2 3 6 7]
Expected Output: [2, 2+3*5]
Your     Output: [2, 2+3*5]
Time Cost: 7.099500 ms (7099500 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT1.in & ARIT1.out
Expected  Input: [30 2894, 2 40 2 50 48 23 39 26 23 42 36 29 35 17 39 16 48 12 45 20 35 19 20 3 15 42 1 49 45 10 ]
Expected Output: [3, 40+39*36+50]
Your     Output: [3, 40+39*36+50]
Time Cost: 477.980500 ms (477980500 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT10.in & ARIT10.out
Expected  Input: [6 721, 1 2 3 4 5 6]
Expected Output: [5, 2*3*4*5*6+1]
Your     Output: [5, 2*3*4*5*6+1]
Time Cost: 38.360500 ms (38360500 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT2.in & ARIT2.out
Expected  Input: [21 11573, 16 17 3 12 24 49 25 18 28 5 38 8 22 3 11 11 16 21 4 11 32 ]
Expected Output: [4, 16+3*38*16+21]
Your     Output: [4, 16*17+32*38+21]
Time Cost: 7109.397600 ms (7109397600 ns)
Wrong Answer.
-----------------------------------------------------
Current Case: ARIT3.in & ARIT3.out
Expected  Input: [8 1554, 32 23 1 1 26 33 28 5 ]
Expected Output: [3, 33+28*26-32]
Your     Output: [3, 33+28*26-32]
Time Cost: 3.193600 ms (3193600 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT4.in & ARIT4.out
Expected  Input: [41 48, 34 44 38 38 28 38 39 45 34 19 13 4 36 41 32 30 8 31 10 15 32 27 34 38 4 42 35 49 23 27 18 30 9 6 2 47 47 16 48 9 17 ]
Expected Output: [0, 48]
Your     Output: [0, 48]
Time Cost: 1.859300 ms (1859300 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT5.in & ARIT5.out
Expected  Input: [17 11787, 3 9 37 7 7 11 32 48 34 3 31 20 27 38 19 27 17 ]
Expected Output: [3, 31*20*19+7]
Your     Output: [3, 31*20*19+7]
Time Cost: 47.619500 ms (47619500 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT6.in & ARIT6.out
Expected  Input: [4 24, 1 1 10 7]
Expected Output: [3, 1+1*7+10]
Your     Output: [3, 1+1*7+10]
Time Cost: 1.087000 ms (1087000 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT7.in & ARIT7.out
Expected  Input: [18 2553, 32 48 3 42 7 34 12 29 3 50 30 35 22 13 35 9 11 20 ]
Expected Output: [3, 32+29*42-9]
Your     Output: [3, 32+29*42-9]
Time Cost: 3.876700 ms (3876700 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT8.in & ARIT8.out
Expected  Input: [6 1234, 1 2 3 4 5 6]
Expected Output: [No Solution!]
Your     Output: [No Solution!]
Time Cost: 1250.530200 ms (1250530200 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT9.in & ARIT9.out
Expected  Input: [27 9546, 10 5 30 1 14 49 8 19 44 21 23 35 26 7 35 3 27 18 5 15 49 23 8 44 48 49 47 ]
Expected Output: [4, 10+14*19*21-30]
Your     Output: [4, 10*30-26*35-44]
Time Cost: 33963.559100 ms (33963559100 ns)
Wrong Answer.
-----------------------------------------------------
Result Statistics: √ √ √ × √ √ √ √ √ √ ×

Iterative-Deeping DFS

Source

    /* Global Variables */
    private enum Operators {
        ADDICTION("+"), SUBTRACTION("-"), MULTIPLICATION("*"), DIVISION("/");

        private final String operatorString;
    
        Operators(String operatorString) {
            this.operatorString = operatorString;
        }
    
        @Override
        public String toString() {
            return this.operatorString;
        }
    }
    
    private static int k;
    private static int n;
    private static int m;
    private static int[] nums;
    private static boolean[] used;
    private static int[] operands;
    private static int[] operators;
    
    public static void printCurrentPlan() {
        // for n numbers, we can use k \in {0, 1, 2, ..., n-1} operators
        // k = 0 means that we don't need to use any operators
        for (int i = 0; i <= k; i++) {
            if (i > 0) System.out.print(Operators.values()[operators[i - 1]]);
            System.out.print(operands[i]);
        }
    }
    
    public static boolean found() {
    
        int sum = 0xdead;
        // k means the number of operands
        for (int i = 0; i <= k; i++) {
            // Push the first operand
            if (i == 0) {
                sum = operands[0];
                continue;
            }
    
            // Actually, we won't use the last index of operator
            // And if we only have one operand, we won't need to calc any operators. (just ignore the only operator at index 0)
            int operator = operators[i - 1];
            int operand = operands[i];
    
            // Calculate
            switch (Operators.values()[operator]) {
                case ADDICTION:
                    sum += operand;
                    break;
                case SUBTRACTION:
                    sum -= operand;
                    break;
                case MULTIPLICATION:
                    sum *= operand;
                    break;
                case DIVISION:
                    sum /= operand;
                    break;
            }
    
        }
    
        return sum == m;
    }
    
    public static boolean search(int depth) {
    
        /* Base Case */
        if (depth > k) {
            return found();
        }
    
        /* Recursive Case */
    
        // We can choose any of the unused numbers !
        for (int i = 0; i < nums.length; i++) {
            // Skip the number if we have used it.
            if (used[i]) continue;
            else used[i] = true;
    
            // Use the number
            operands[depth] = nums[i];
    
            // Also, we can use any of the operators !
            for (int j = 0; j < Operators.values().length; j++) {
                // Use the operator
                operators[depth] = Operators.values()[j].ordinal();
    
                // Go !
                if (search(depth + 1)) {
                    // if not found, the recursion should go ahead
                    return true;
                }
            }
    
            // Free it !
            used[i] = false;
        }
    
        return false;
    }
    
    public static void solve(Scanner scanner) {
    
        /* Initialize */
        n = scanner.nextInt();
        nums = new int[n];
        used = new boolean[n];
        operands = new int[n];
        operators = new int[n];
    
        m = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
    
        /* k-search */
        // k is the number of operands
        // for n, k = 0, 1, 2, ..., n-1
        for (k = 0; k < nums.length; k++) {
            if (search(0)) {
                System.out.println(k);
                printCurrentPlan();
                return;
            }
        }
        System.out.println("No Solution!");
    }

Benchmark

-----------------------------------------------------
Current Case: ARIT0.in & ARIT0.out
Expected  Input: [5 25, 5 2 3 6 7]
Expected Output: [2, 2+3*5]
Your     Output: [2, 2+3*5]
Time Cost: 6.820100 ms (6820100 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT1.in & ARIT1.out
Expected  Input: [30 2894, 2 40 2 50 48 23 39 26 23 42 36 29 35 17 39 16 48 12 45 20 35 19 20 3 15 42 1 49 45 10 ]
Expected Output: [3, 40+39*36+50]
Your     Output: [3, 40+39*36+50]
Time Cost: 473.039600 ms (473039600 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT10.in & ARIT10.out
Expected  Input: [6 721, 1 2 3 4 5 6]
Expected Output: [5, 2*3*4*5*6+1]
Your     Output: [5, 2*3*4*5*6+1]
Time Cost: 266.458500 ms (266458500 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT2.in & ARIT2.out
Expected  Input: [21 11573, 16 17 3 12 24 49 25 18 28 5 38 8 22 3 11 11 16 21 4 11 32 ]
Expected Output: [4, 16+3*38*16+21]
Your     Output: [4, 16+3*38*16+21]
Time Cost: 2210.722500 ms (2210722500 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT3.in & ARIT3.out
Expected  Input: [8 1554, 32 23 1 1 26 33 28 5 ]
Expected Output: [3, 33+28*26-32]
Your     Output: [3, 33+28*26-32]
Time Cost: 17.388700 ms (17388700 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT4.in & ARIT4.out
Expected  Input: [41 48, 34 44 38 38 28 38 39 45 34 19 13 4 36 41 32 30 8 31 10 15 32 27 34 38 4 42 35 49 23 27 18 30 9 6 2 47 47 16 48 9 17 ]
Expected Output: [0, 48]
Your     Output: [0, 48]
Time Cost: 1.912900 ms (1912900 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT5.in & ARIT5.out
Expected  Input: [17 11787, 3 9 37 7 7 11 32 48 34 3 31 20 27 38 19 27 17 ]
Expected Output: [3, 31*20*19+7]
Your     Output: [3, 31*20*19+7]
Time Cost: 510.196400 ms (510196400 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT6.in & ARIT6.out
Expected  Input: [4 24, 1 1 10 7]
Expected Output: [3, 1+1*7+10]
Your     Output: [3, 1+1*7+10]
Time Cost: 1.734900 ms (1734900 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT7.in & ARIT7.out
Expected  Input: [18 2553, 32 48 3 42 7 34 12 29 3 50 30 35 22 13 35 9 11 20 ]
Expected Output: [3, 32+29*42-9]
Your     Output: [3, 32+29*42-9]
Time Cost: 17.189900 ms (17189900 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT8.in & ARIT8.out
Expected  Input: [6 1234, 1 2 3 4 5 6]
Expected Output: [No Solution!]
Your     Output: [No Solution!]
Time Cost: 293.963800 ms (293963800 ns)
Accepted.
-----------------------------------------------------
Current Case: ARIT9.in & ARIT9.out
Expected  Input: [27 9546, 10 5 30 1 14 49 8 19 44 21 23 35 26 7 35 3 27 18 5 15 49 23 8 44 48 49 47 ]
Expected Output: [4, 10+14*19*21-30]
Your     Output: [4, 10+14*19*21-30]
Time Cost: 5940.226300 ms (5940226300 ns)
Accepted.
-----------------------------------------------------
Result Statistics: √ √ √ √ √ √ √ √ √ √ √