全排列代码问题

a327904410

问题描述
　　给定一个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

帮我看下代码为什么输出不是最小字典序，在十次测试中两个出现问题，不知道为什么，求大佬帮我看看哪里出了问题

1. #include<stdio.h>
   
2. #include<string.h>
   
3. 
   
4. // a[]是原数组，b[]是计算并判断是否等于sum，c[]保存最小字典排序
   
5. // n是数组长度，sum是数组里的数累加后的最终结果
   
6. // flag 一是判断有没有能计算出sum的数组，二是保存第一个数组c[]
   
7. int a[11], b[11], c[11], n, sum, flag = 1;
   
8. 
   
9. void swap(int a[], int i, int j) {
   
10.         int temp = a[i];
    
11.         a[i] = a[j];
    
12.         a[j] = temp;
    
13. }
    
14. 
    
15. void perm(int a[], int l, int r) {
    
16.         int i, j;
    
17.         if (l == r) {    // 排完序
    
18.                 for (i = 0; i < n; i++) {  // 将a[]复制进b[]
    
19.                         b[i] = a[i];
    
20.                 }
    
21.                 j = n;   // j表示b[]数组计算长度，长度递减
    
22.                 while (j) {
    
23.                         for (i = 1; i < j; i++) {
    
24.                                 b[i - 1] += b[i];
    
25.                         }
    
26.                         j--;
    
27.                 }
    
28.                 if (b[0] == sum) {    // 如果最终计算出等于sum
    
29.                         if (flag) {       // 将第一次得到的数组保存在c[]
    
30.                                 for (i = 0; i < n; i++) {
    
31.                                         c[i] = a[i];
    
32.                                 }
    
33.                                 flag = 0;
    
34.                         }
    
35.                         else {       // 第二次得到能计算出sum的数组
    
36.                                 int ret = memcmp(a, c, n);    // 比较大小，取最小数组
    
37.                                 if (ret < 0) {
    
38.                                         for (i = 0; i < n; i++) {
    
39.                                                 c[i] = a[i];    // 最小数组给c[]
    
40.                                         }
    
41.                                 }
    
42.                         }
    
43.                        
    
44.                 }
    
45.         }
    
46.         else {
    
47.                 for (i = l; i <= r; i++) {   // 全排列，递归
    
48.                         swap(a, l, i);
    
49.                         perm(a, l + 1, r);
    
50.                         swap(a, l, i);
    
51.                 }
    
52.         }
    
53. }
    
54. 
    
55. int main() {
    
56.         scanf("%d%d", &n, &sum);
    
57.         int i;
    
58.         for (i = 0; i < n; i++) {
    
59.                 a[i] = i + 1;
    
60.         }
    
61.         perm(a, 0, n - 1);
    
62.         if (flag) {    // 若没找到数组，则返回空
    
63.                 printf("");
    
64.         }
    
65.         else {
    
66.                 for (i = 0; i < n; i++) {
    
67.                         printf("%d ", c[i]);
    
68.                 }
    
69.         }
    
70.         return 0;
    
71. }

复制代码

input6.txt (6 Bytes, 下载次数: 1)

2022-3-28 23:50 上传

点击文件名下载附件

output6.txt (18 Bytes, 下载次数: 0)

2022-3-28 23:50 上传

点击文件名下载附件

a327904410

代码可能有点混乱，没整理好，不要见怪

a327904410

我打印了a[]所有数组，发现有最小字典序的，但没能复制到c[]，不知道为啥

a327904410

放假回来看了下，问题已解决，貌似删不了帖子。