注册 登录
编程论坛 C语言论坛

请问这道题的输出怎么按字典序排列?

青蝶 发布于 2018-06-20 22:41, 3211 次点击
在a这个整型数组里有10个元素,大小为1,2或者3,下标从1到10。现在给出一个数,输出满足a中10个数之和为这个数的所有情况,按字典序输出。
没有满足条件的情况则输出0。

我的程序可以输出所有结果,但不是按字典序,想问一下应该怎么改?

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

int a[11],s[10000][11],k=0;


void dfs(int x,int remain){
    int i;
    if(x==0){
      if(remain!=0)
        return;
    }
    if(remain==0){
        for(i=1;i<=10;i++) s[k][i]=a[i];
        k++;
        return;
    }   
    if(a[x]==2){
        a[x]=3;
        dfs(x-1,remain-1);
        a[x]=2;
        dfs(x-1,remain);
    }
    if(a[x]==1){
        a[x]=2;
        dfs(x,remain-1);
        a[x]=1;
        dfs(x-1,remain);
    }
}
   
int main(void){
    int n,i,j;
    scanf("%d",&n);
    if(n<10 || n>30){
        printf("0\n");
        exit(0);
    }
    for(i=0;i<11;i++) a[i]=1;
    dfs(10,n-10);
    printf("%d\n",k);
    for(i=0;i<k;i++){
      for(j=1;j<=9;j++){
          printf("%d ",s[i][j]);
    }
      printf("%d\n",s[i][10]);
}
    return 0;
}
   
18 回复
#2
lin51616782018-06-20 23:13
最简单的是
10位三进制
#3
lin51616782018-06-21 00:24
程序代码:
#include <stdio.h>

void print(int* arr)
{
    for(int i=0; i<10; ++i)
    {
        printf("%4d", arr[i]+1);
    }
    puts("");
}

int checkNum(int n, int m)
{
    int sum = 0;
    int index = 10;
    int arr[10] = {0};
    while(n)
    {
        sum += n%3+1;
        arr[--index] = n%3;
        n /= 3;
    }   
    if(sum + index == m)
    {
        print(arr);
        return 1;
    }
    return 0;
}

int main(int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    int bfind = 0;
    for(int i=0; i<9*9*9*9*9; ++i)
    {
        if(checkNum(i, n))
            bfind = 1;
    }
   
    if(bfind == 0)
    {
        puts("0");
    }
    return 0;
}

#4
八画小子2018-06-21 01:37
我觉得你应该去C++版块
#5
书生牛犊2018-06-21 07:00
@青蝶     ,。
举个例子。数组【2,1,1,3,1,2】,输出和是3 的组合,顺序应如下:
2+1  2+1  2+1  1+1+1  1+2  1+2  3  1+2

这道题我认为不需要用到矩阵。题目之所以规定要求你按照字典序,主要还是希望你用递归迭代的方法来做
程序代码:
int KeySum;//指示要匹配的“和”
int a[10];
int func(int n,int sum){//n指示目前所找到的位置,sum指示已累计的和
for(int i=n+1;i<10;i++){
if(sum+a[i]==KeySum){print();//如何输出找到的组合可能需要引入额外的缓存数组,时间缘故我不展开}
else if(sum+a[i]<KeySum){func(i,sum+a[i]);}   }
return状态;//指示是否找到可行的组合方案
}
main(){if(func(-1,0)==没找到){printf("0");}}

赶着上班去,就只给思路了。
#6
lin51616782018-06-21 09:29
回复 5楼 书生牛犊
题目理解错了
10个数之和为这个数
10个元素都要加起来
不是选择一两个元素加起来
#7
星泪成寒2018-06-21 09:50
题目看不懂啊!!!
10个数加起来等于给定的数, 哪里来的多种情况?
#8
lin51616782018-06-21 10:07
回复 7楼 星泪成寒
比如给定 12
可以是
1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 2 2
这就是多种情况了
#9
青蝶2018-06-21 16:58
回复 5楼 书生牛犊
不好意思,题目描述地不是很清楚,就是6楼大佬的意思
#10
青蝶2018-06-21 17:09
我改成字符数组存储了,把所有结果存起来以后按字典序排序,用的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[i]=a[i]+'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[i]=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[i];
            s0[i]=s0[t];
            s0[t]=temp;
        }
    }
    for(i=0;i<k;i++){
      for(j=1;j<=9;j++){
          printf("%c ",s0[i].s[j]);
    }
      printf("%c\n",s0[i].s[10]);
}
    return 0;
}


[此贴子已经被作者于2018-6-21 17:11编辑过]

#11
自学的数学2018-06-21 17:13
回复 9楼 青蝶
楼主的叙述没问题,主要是大家的理解的立场不一样,有所差别。楼主给定的数组是10个元素,要求的是这10个元素的和为给定的值。而不是一部分元素之和的值。
#12
青蝶2018-06-21 20:57
这个题。。时间限制是1秒,10重for循环,没超时,通过了。。
#13
青蝶2018-06-21 20:58
但是还是想知道为什么我写的程序,按字典序没排出来?
#14
书生牛犊2018-06-21 22:29
审题不认真,连题目需求都没理解对....

程序代码:
#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
书生牛犊2018-06-21 22:36
以下是引用青蝶在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
lin51616782018-06-21 23:25
回复 10楼 青蝶
if(strcmp(s0[t].s,s0[j].s)) t=j;

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

#17
lin51616782018-06-21 23:32
看来看去还是三进制最帅
不接受反驳
#18
九转星河2018-06-22 11:11
就是最大目标值是30,其实可以先对某个数进行按字典序的整数分解,最多分解成10个(先不看数组的具体组成),然后再看看每个序列在数组里面有多少组数据能重复符合要求的~

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

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

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

#19
青蝶2018-06-22 20:20
回复 16楼 lin5161678
把那一句改成  if(strcmp(s0[t].s,s0[j].s)>0) t=j;
还是不行
1