| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 567 人关注过本帖
标题:请问这道题的输出怎么按字典序排列?
只看楼主 加入收藏
自学的数学
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:17
帖 子:603
专家分:2418
注 册:2017-11-15
  得分:4 
回复 9楼 青蝶
楼主的叙述没问题,主要是大家的理解的立场不一样,有所差别。楼主给定的数组是10个元素,要求的是这10个元素的和为给定的值。而不是一部分元素之和的值。
2018-06-21 17:13
青蝶
Rank: 2
等 级:论坛游民
帖 子:137
专家分:46
注 册:2018-2-4
  得分:0 
这个题。。时间限制是1秒,10重for循环,没超时,通过了。。
2018-06-21 20:57
青蝶
Rank: 2
等 级:论坛游民
帖 子:137
专家分:46
注 册:2018-2-4
  得分:0 
但是还是想知道为什么我写的程序,按字典序没排出来?
2018-06-21 20:58
书生牛犊
Rank: 13Rank: 13Rank: 13Rank: 13
来 自:星夜征程
等 级:蒙面侠
威 望:8
帖 子:1052
专家分:4993
注 册:2015-10-27
  得分: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},它是从前往后逐个字母比较大小,升序排列。楼主的代码我在本地运行了一下,次序差别很大。
另外,貌似程序要求先输出组合个数,然后输出各组合吧。。所以这代码不能直接作为成品提交。   楼主还得理解一下“字典序”的概念,然后自己写。

φ(゜▽゜*)♪
2018-06-21 22:29
书生牛犊
Rank: 13Rank: 13Rank: 13Rank: 13
来 自:星夜征程
等 级:蒙面侠
威 望:8
帖 子:1052
专家分:4993
注 册:2015-10-27
  得分: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()根本没作用

φ(゜▽゜*)♪
2018-06-21 22:36
lin5161678
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:9
帖 子:410
专家分:1476
注 册:2011-12-3
  得分:0 
回复 10楼 青蝶
if(strcmp(s0[t].s,s0[j].s)) t=j;

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

2018-06-21 23:25
lin5161678
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:9
帖 子:410
专家分:1476
注 册:2011-12-3
  得分:0 
看来看去还是三进制最帅
不接受反驳
2018-06-21 23:32
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:51
帖 子:4975
专家分:13940
注 册:2016-10-22
  得分:4 
就是最大目标值是30,其实可以先对某个数进行按字典序的整数分解,最多分解成10个(先不看数组的具体组成),然后再看看每个序列在数组里面有多少组数据能重复符合要求的~

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

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

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


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-22 11:11
青蝶
Rank: 2
等 级:论坛游民
帖 子:137
专家分:46
注 册:2018-2-4
  得分:0 
回复 16楼 lin5161678
把那一句改成  if(strcmp(s0[t].s,s0[j].s)>0) t=j;
还是不行
2018-06-22 20:20







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026686 second(s), 8 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved