每日一道算法題數(shù)字游戲（藍橋杯練習系統(tǒng)）全排列問題-創(chuàng)新互聯(lián)
資源限制
內(nèi)存限制：256.0MB C/C++時間限制：1.0s Java時間限制：3.0s Python時間限制：5.0s
問題描述
給定一個1～N的排列a[i]，每次將相鄰兩個數(shù)相加，得到新序列，再對新序列重復這樣的操作，顯然每次得到的序列都比上一次的序列長度少1，最終只剩一個數(shù)字。
例如:
3 1 2 4
4 3 6
7 9
16
現(xiàn)在如果知道N和最后得到的數(shù)字sum，請求出最初序列a[i]，為1～N的一個排列。若有多種答案，則輸出字典序最小的那一個。數(shù)據(jù)保證有解。
輸入格式
第1行為兩個正整數(shù)n，sum
輸出格式
一個1～N的一個排列
樣例輸入
4 16
樣例輸出
3 1 2 4
數(shù)據(jù)規(guī)模和約定
0
import java.util.Arrays;
import java.util.Scanner;
public class Main{static int n=0;
static int sum=0;
static int[] used=new int[11];//用來標記是否使用
static int[] dp=new int[11];//用來存儲每個位置的數(shù)字
public static void main(String[] args){Scanner in=new Scanner(System.in);
n=in.nextInt();
sum=in.nextInt();
Arrays.fill(used,0);
DFS(1);
}
public static void DFS(int step){if(step==n+1){//說明已經(jīng)列滿n個數(shù)了，這個時候需要判斷和是否為sum
int s[] =new int[n+1];//防止破壞dp數(shù)組里的數(shù)，因為如果滿足條件需要輸出dp數(shù)組的內(nèi)容
for(int i=1;i<=n;i++){s[i]=dp[i];
}
for(int i=1;i//總共加n-1次
for(int j=1;j<=n-i;j++){//把數(shù)組的和全加到j=1的位置上去
s[j]+=s[j+1];
}
}
if(s[1]==sum)//滿足條件，輸出
{for(int i=1;i<=n;i++){System.out.print(dp[i]);
if(ireturn;
}
}
for(int i=1;i<=n;i++){if(used[i]==0){used[i]=1;
dp[step]=i;
DFS(step+1);
used[i]=0;
}
}
}
} 你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
分享題目：每日一道算法題數(shù)字游戲（藍橋杯練習系統(tǒng)）全排列問題-創(chuàng)新互聯(lián)
URL地址：http://m.jiaotiyi.com/article/djjgjo.html