请问这道题的输出怎么按字典序排列？ - C语言论坛

第 11 楼

得分:4

回复 9楼青蝶

楼主的叙述没问题，主要是大家的理解的立场不一样，有所差别。楼主给定的数组是10个元素，要求的是这10个元素的和为给定的值。而不是一部分元素之和的值。

第 12 楼

得分:0

这个题。。时间限制是1秒，10重for循环，没超时，通过了。。

第 13 楼

得分:0

但是还是想知道为什么我写的程序，按字典序没排出来?

第 14 楼

得分:0

审题不认真，连题目需求都没理解对....

程序代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int a[11]= {0},Totol=0;

void print() {
    Totol++;
    printf("%d",a[0]);
    for(int i=1; i<10; i++)printf(" %d",a[i]);
    printf("\n");
}
void dfs(int x,int remain) {
    if(x==9) {//迭代到第九个数就可以判断出结果了。
        if(remain>0&&remain<4) {
            a[9]=remain;
            print();
        }
        return;
    }
    if(remain<=0)return;//还没到第九个数，和已大于等于n,剩下的也不用测试了

    for(int j=1; j<4; j++) {
        a[x]=j;
        dfs(x+1,remain-j);
    }

}

int main(void) {
    int n,i,j;
    scanf("%d",&n);
    if(n<10 || n>30) {
        printf("0\n");
        exit(0);
    }

    dfs(0,n);
    printf("共计%d组\n",Totol);
    return 0;
}

这应该就是楼主要的字典序了。字典序应该是形如{aaa,aaaaa,aaaab,aaab,aaaba}，它是从前往后逐个字母比较大小，升序排列。楼主的代码我在本地运行了一下，次序差别很大。
另外，貌似程序要求先输出组合个数，然后输出各组合吧。。所以这代码不能直接作为成品提交。楼主还得理解一下“字典序”的概念，然后自己写。

φ(゜▽゜*)♪

第 15 楼

得分:0

以下是引用青蝶在2018-6-21 17:09:10的发言：

我改成字符数组存储了，把所有结果存起来以后按字典序排序，用的strcmp函数，但是输出没变，怎么回事？
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

int a[11],k=0;

struct str{
    char s[12];
}s0[10000];

void dfs(int x,int remain){
    int i;
    if(x==0){
      if(remain!=0)
        return;
    }
    if(remain==0){
        for(i=1;i<=10;i++) s0[k].s=a+'0';
        k++;
        return;
    }
    if(a[x]==1){
        a[x]=2;
        dfs(x,remain-1);
        a[x]=1;
        dfs(x-1,remain);
    }
    if(a[x]==2){
        a[x]=3;
        dfs(x-1,remain-1);
        a[x]=2;
        dfs(x-1,remain);
    }
}

int main(void){
    int n,i,j,t;
    struct str temp;
    scanf("%d",&n);
    if(n<10 || n>30){
        printf("0\n");
        exit(0);
    }
    for(i=0;i<11;i++) a=1;
    dfs(10,n-10);
    printf("%d\n",k);
    for(i=0;i<k-1;i++){            //按字典序排序
        t=i;
        for(j=i+1;j<k;j++){
            if(strcmp(s0[t].s,s0[j].s)) t=j;
        }
        if(t!=i){
            temp=s0;
            s0=s0[t];
            s0[t]=temp;
        }
    }
    for(i=0;i<k;i++){
      for(j=1;j<=9;j++){
          printf("%c ",s0.s[j]);
    }
      printf("%c\n",s0.s[10]);
}
    return 0;
}

strcmp()只是对某一次的组合进行快速排序而已。。。。题目的关键还是要把所有的组合按照字典序进行排列。你得把每一个组合看作一个字符串，然后使用字符串排序函数去做，结果才是对的。by the way,由于你所写的代码的特性，其实每一次的组合里的元素本身就已经是非递减序列了，是否使用strcmp（）根本没作用

φ(゜▽゜*)♪

第 16 楼

得分:0

回复 10楼青蝶

 if(strcmp(s0[t].s,s0[j].s)) t=j;

strcmp 返回值你没理解好
比较结果A大于B 正数
比较结果A小于B 负数
不管是正数还是负数都会执行t = j
于是只要不相等就触发交换
这显然没有排序的效果了

https://zh.

第 17 楼

得分:0

看来看去还是三进制最帅
不接受反驳

https://zh.

第 18 楼

得分:4

就是最大目标值是30,其实可以先对某个数进行按字典序的整数分解,最多分解成10个(先不看数组的具体组成),然后再看看每个序列在数组里面有多少组数据能重复符合要求的~

其实只要记录10个数里面1,2,3分别有多少个就可以了,好像可以用简单的排列组合公式~
然后改进一下可以根据1,2,3的数字有没有超出数组个数来进行剪枝,这样应该可以实现~

10个数的所有组合共有2^10=1024种情况,看出来也可以对所有组合进行枚举的

没多想,或者有说得不到位的地方,不要见笑就是了

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 19 楼

得分:0

回复 16楼 lin5161678

把那一句改成 if(strcmp(s0[t].s,s0[j].s)>0) t=j;
还是不行