任何一個大于1的自然數n，總可以拆分成若干個小于n的自然數之和， 當n=7共14種拆分方法：
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
輸入格式:
輸入n， 1<n<20，
輸出格式:
按字典序輸出具體的方案，
輸入樣例:
在這里給出一組輸入，例如：
7
輸出樣例:
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
這里我們同樣采用回溯法；每個結點優先從1開始減去當前剩余數，減數優先級遞減直到n-1結束；隨后判斷是否可減；當出現余數既不為0又小于當前減數時則判斷不可減，減去當前分支；具體演算法如下：
package 宿題;
import java.io.*;
public class PTASplittingNumbers {
static int A;
public static void main(String args[])throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
A=(int)in.nval;
String s=""+A+"=";//初始化字串s;
Split(A,1,s);
}
private static void Split(int a,int n,String s){
if(a==0){//當前余數為0，到達最底層；
s=s.substring(0, s.length()-1);//將字串最后一個字符“+”舍去；
System.out.println(s);
}else{
for(int i=n;i<A;i++){
if(a-i>=i||a-i==0)//判斷是否可減，否則剪枝；
Cut(a-i,i,s+i+"+");
}
}
}
該演算法最壞情況下的時間復雜度為O((n-1)^n)，
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121144.html
標籤：其他