資源限制
內存限制：256.0MB C/C++時間限制：1.0s Java時間限制：3.0s Python時間限制：5.0s
問題描述
給定一個1～N的排列a[i]，每次將相鄰兩個數相加，得到新序列，再對新序列重復這樣的操作，顯然每次得到的序列都比上一次的序列長度少1，最終只剩一個數字。
例如:
3 1 2 4
4 3 6
7 9
16
現(xiàn)在如果知道N和最后得到的數字sum，請求出最初序列a[i]，為1～N的一個排列。若有多種答案，則輸出字典序最小的那一個。數據保證有解。
輸入格式
第1行為兩個正整數n，sum
輸出格式
一個1～N的一個排列
樣例輸入
4 16
樣例輸出
3 1 2 4
數據規(guī)模和約定
0解題思路:主要是1~N的整數要怎么排序才能符合這樣加起來的和能為sum，這就用到了全排列，而且今天學到了怎么把把數組加成這種階梯狀的值，只要s[j]+=s[j+1]，然后總共加n-1次，每次加n-i次，i從1到n

創(chuàng)新互聯(lián)公司為客戶提供專業(yè)的成都網站制作、網站建設、外貿網站建設、程序、域名、空間一條龍服務，提供基于WEB的系統(tǒng)開發(fā). 服務項目涵蓋了網頁設計、網站程序開發(fā)、WEB系統(tǒng)開發(fā)、微信二次開發(fā)、手機網站開發(fā)等網站方面業(yè)務。

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];//用來存儲每個位置的數字
    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){//說明已經列滿n個數了，這個時候需要判斷和是否為sum
            int s[] =new int[n+1];//防止破壞dp數組里的數，因為如果滿足條件需要輸出dp數組的內容
            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++){//把數組的和全加到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)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享題目：每日一道算法題數字游戲（藍橋杯練習系統(tǒng)）全排列問題-創(chuàng)新互聯(lián)
網頁地址：http://sd-ha.com/article20/djjgjo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供關鍵詞優(yōu)化、企業(yè)網站制作、網站導航、標簽優(yōu)化、微信小程序、網頁設計公司

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)