知识点:迭代加深
所谓迭代加深,也是深度优先搜索,但是与普通深度优先搜索不同的是,每次深搜都会有搜索的最大深度限制,如果没有找到解,就增大深度,再进行深搜,如此循环指导找到解为止,这样可以找到最浅层的解。
迭代加深适用于某些分支很深,搜索空间大,但问题的答案却位于浅层的这类问题。
本题的剪枝思路:(1)从大到小枚举下一个数;(2)判重。
import java.util.*;
public class Main
{
static int N = 110, n;
static int[] path = new int[N];
public static boolean dfs(int u, int k)
{
if(u == k) return path[u - 1] == n;
boolean[] st = new boolean[N]; // 这里的st数组用于判重,对应剪枝思路(2)
for(int i = u - 1; i >= 0; i --)
for(int j = i; j >= 0; j --) // 这里两个for循环的循环顺序对应剪枝思路(1)
{
int s = path[i] + path[j];
if(s <= path[u - 1]) return false; // 由于是按照从大到小枚举的,若当前的s小于等于path[u-1],后面的也必然这样,故直接返回false
if(s > n || st[s]) continue;
st[s] = true;
path[u] = s;
if(dfs(u + 1, k)) return true;
}
return false;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
n = sc.nextInt();
if(n == 0) break;
path[0] = 1;
// 迭代加深
int k = 1;
while(!dfs(1, k)) k ++;
// 输出结果
for(int i = 0; i < k; i ++) System.out.print(path[i] + " ");
System.out.println();
}
}
}