| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
大量收QQ微信精准粉/交友粉,非诚勿扰千里之行 始于足下
共有 352 人关注过本帖
标题:字符串的题,帮忙看一下为什么不对?
只看楼主 加入收藏
青蝶
Rank: 2
等 级:论坛游民
帖 子:142
专家分:51
注 册:2018-2-4
结帖率:92.68%
  已结贴   问题点数:20  回复次数:7   
字符串的题,帮忙看一下为什么不对?
题目描述
设有n个正整数(n≤20) ,将它们联接成一排,组成一个最大的多位整数。
例如:
n=3 时,3 个整数13,312 ,343 联接成的最大整数为:34331213
又如:n=4 时,4 个整数7 ,13 ,4,246 联接成的最大整数为:7424613

输入输出格式
输入格式:
第一行,一个正整数 n 。
第二行,n 个正整数。
输出格式:
一个正整数,表示最大的整数。

我想用dfs做,程序运行出来不对,求帮忙看一下怎么回事?

代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

struct str{
    char s[100];
}a[25];

int n,visited[25];
char m[1000]={'\0'},temp0[1000]={'\0'};

void dfs(int step,char *ss){
    int i;
    char temp[1000];
    strcpy(temp,ss);
    if(step==21){
      if(strcmp(ss,m)>0) strcpy(m,ss);
      return;
  }
    for(i=1;i<=n;i++){
        if(visited[i]==0){
            strcat(ss,a[i].s);
            visited[i]=1;
            dfs(step+1,ss);
            strcpy(ss,temp);
            visited[i]=0;
        }
    }
}

int main(void){
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%s",a[i].s);
    memset(visited,0,sizeof(visited));
    dfs(1,temp0);
    printf("%s\n",m);
    return 0;
}
   
   
2018-07-20 20:02
zbjzbj
Rank: 9Rank: 9Rank: 9
来 自:郑州
等 级:贵宾
威 望:12
帖 子:267
专家分:1318
注 册:2011-4-22
  得分:10 
我跑了一下你这程序,穷举,递归,复杂,细节看不懂。
一个思路:把所有数据(字符串数组)“左对齐”排成一列,然后挑一个最大的出来(从左至右逐位比较)输出,然后数组中减去这个元素,继续在数组中在挑出最大的元素出来(递归)。
特殊情况处理:7,712,比较第一位,7和712并列,比较第二位,7没有第二位,按位数短的胜出。

或者直接从上到下排序完成,然后连接输出。
2018-07-20 23:23
青蝶
Rank: 2
等 级:论坛游民
帖 子:142
专家分:51
注 册:2018-2-4
  得分:0 
回复 2楼 zbjzbj
不知道我理解的对不对,是先判断数位是否一样,输出少的,再判断数的大小,输出大的么?
如果是这样,有些数据结果不对。
比如输入:
32 407 135 13 217
应该输出:
4073221713513

按照数位短的,应该先输出13,再输出135。
2018-07-20 23:37
青蝶
Rank: 2
等 级:论坛游民
帖 子:142
专家分:51
注 册:2018-2-4
  得分:0 
回复 2楼 zbjzbj
我的那个程序思路就是直接用深度优先搜索,遍历所有情况,更新最大值。
不知道哪里出了问题,运行不出来。
之前写过找规律先排序再输出,但是总有数据结果不对,后来找不到适用于所有情况的规律,改用暴力的。。
2018-07-20 23:41
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:266
帖 子:5829
专家分:33315
注 册:2011-1-18
  得分:5 
排序一下就行了
以你用的C++语言为例,一句话就行了
sort( begin(arr), end(arr), [](const string& a,const string& b){return a+b>b+a;} );
2018-07-21 01:20
zbjzbj
Rank: 9Rank: 9Rank: 9
来 自:郑州
等 级:贵宾
威 望:12
帖 子:267
专家分:1318
注 册:2011-4-22
  得分:0 
回复 3楼 青蝶
输出尾数短的不妥,后来我意识到这个问题了。应该是第一位和缺位的下一位比较,大者生出。比如,2351和23,首位2和缺位后的一位5比较,2351胜出。又如,23和23117,首位2和第三位1比较,23胜出。
2018-07-21 09:10
lin5161678
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:10
帖 子:410
专家分:1476
注 册:2011-12-3
  得分:5 
直接字符串比较排序
2018-07-21 09:45
青蝶
Rank: 2
等 级:论坛游民
帖 子:142
专家分:51
注 册:2018-2-4
  得分:0 
直接排序就好了,谢谢大佬们。
2018-07-21 10:56







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

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