試題 算法訓練 數字遊戲
資源限制
時間限制:1.0s 記憶體限制:256.0MB
問題描述
給定一個1~N的排列a[i],每次将相鄰兩個數相加,得到新序列,再對新序列重複這樣的操作,顯然每次得到的序列都比上一次的序列長度少1,最終隻剩一個數字。
例如:
3 1 2 4
4 3 6
7 9
16
現在如果知道N和最後得到的數字sum,請求出最初序列a[i],為1~N的一個排列。若有多種答案,則輸出字典序最小的那一個。資料保證有解。
輸入格式
第1行為兩個正整數n,sum
輸出格式
一個1~N的一個排列
樣例輸入
4 16
樣例輸出
3 1 2 4
資料規模和約定
0<n<=10
package 第九次模拟;
import java.util.Scanner;
public class 數字遊戲 {
static int sum;
static int N;
static int arr1[];
static boolean bool = true;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
N = input.nextInt();
sum = input.nextInt();
int array[] = new int[N];
int visit[] = new int[N + 1];
dfs(0, array, visit, bool);
}
public static void dfs(int step, int arr[], int vis[], Boolean b) {
if (step == N) {
int arr1[] = new int[N];
for (int i = 0; i < N; i++) {
arr1[i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N - i; j++) {
arr1[j] = arr1[j] + arr1[j + 1];
}
}
if (arr1[0] == sum) {
for (int x : arr) {
System.out.print(x + " ");
}
bool = false;
return;
} else
return;
}
if (bool == true) {
for (int i = 1; i <= N; i++) {
if (vis[i] == 0) {
arr[step] = i;
vis[i] = 1;
dfs(step + 1, arr, vis, bool);
vis[i] = 0;
}
}
}
return;
}
}