| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2465 人关注过本帖, 2 人收藏
标题:求一个题目的答案,本人是菜鸟,想了很久没想出!
只看楼主 加入收藏
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
收藏
得分:0 
真帅,问题解决,TC下递归多次会自动退出,放个循环来控制调用递归就解决了。
最终代码:
程序代码:
#include <stdio.h>
#include <string.h>

int len,flag=0;
long sum=0,m;
char a[27],b[27];

int panduan(char *a)  /* 判断字符串是否为升序 */
{
 char *p=a;
 for(;*(p+1);p++)
   if(*p>=*(p+1)) return 1;

 p=a;
 while(*p)      /* 如有大写转成小写 */
   if(*p++<97) *(p-1)+=32;
 return 0;
}

int zifucmp(char *a,char *b)    /* 比较两字符 */
{
 int i=len-1;
 for(;i>=0;i--)
   if(a[i]!=b[i]) return 1;
 return 0;
}

void funsuan(int n)            /* 递归算法 */ 
{
 if((zifucmp(a,b))==0)
    return;
 if(n+1==len)
   {
    if(m==1000) {m=0;return;}
    if(len!=1)
      {
       if(a[n-1]!=b[n-1] || !flag)
     {
      flag=1;
      sum+='z'+1-b[n];
      b[n]+='z'+1-b[n];
     }
       else if(flag)
     {
      flag=0;
      sum+=a[n]-b[n];
      b[n]+=a[n]-b[n];
     }
      }
    else
      {
       sum+=a[0]-b[n];
       b[n]+=a[0]-b[n];
      }
    m++;
    if(b[n]>'z')
      {
       funsuan(n-1);
       b[n]=b[n-1]+1;
       funsuan(n);
      }
    else funsuan(n);
   }
 else
   {
    b[n]++;
    if(b[n]>=b[n+1]-1)
       {
        funsuan(n-1);
    b[n]=b[n-1]+1;
       }
   }
}

int main(void)
{
 int i;
 while(1)
   {
    gets(a);
    if(panduan(a))
      printf("input error!\n");
    else
     break;
   }
 len=strlen(a);
 for(i=0;i<len;i++)
   b[i]=96;
 b[i]=0;
 while(1)
   if(zifucmp(a,b)!=0)
     funsuan(len-1);
   else
     break;

 printf("%s=%ld\n\n",b,sum);
 getch();
 return 0;
}

更改:最坏情况输入最大abcdefghijklmnopqrstuvwxyz,原来是19秒左右出结果,现在6秒内出结果,唉,真得是慢慢改进。

[ 本帖最后由 UserYuH 于 2009-10-31 18:13 编辑 ]

努力—前进—变老—退休—入土
2009-10-31 14:41
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
请UserYuH做一下自己代码的效率分析

专心编程………
飞燕算法初级群:3996098
我的Blog
2009-10-31 15:38
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
收藏
得分:0 
StarWing83 嗯,一个个数过来的没效率,但这题就是慢慢数也很不好搞,很头疼,只有这样了,有待慢慢改进。

努力—前进—变老—退休—入土
2009-10-31 16:03
godbless
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:216
专家分:950
注 册:2009-7-24
收藏
得分:0 
其实我想过用一个数组num[26]存住a ab abc abcd abcde ....的值,这样输入字符串,判断字符串长度,
根据字符串长度选择数值num和起始的判断字符串,如输入amnpz就可以从abcde开始判断了,这样效率会高一点,但我懒得统计
数组num了...
2009-10-31 16:31
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
收藏
得分:0 
我就觉得这题头疼,谁觉得不头疼的就放个有效代码出来。
我开始的的算法是,26+25+24……+1+1=abc,   ab=26+1=27,   bc=27+25,  但这方法没能实现,要快度可以研究这方法。
怕我的代码出来了,没人继续了,这里说这话是激厉正在思考这题的朋友继续努力,我只是打个头阵,期待好的算法。

努力—前进—变老—退休—入土
2009-10-31 16:46
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
UserYuH:此题我已解决,提示:组合数。

我写了Python的代码,就不贴出来了,你再想想,如果需要,我翻译成C然后贴代码~~
另外,abcdefghijklmnopqrstuvwxyz的答案是:67108863

专心编程………
飞燕算法初级群:3996098
我的Blog
2009-11-01 09:55
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
收藏
得分:0 
abcdefghijklmnopqrstuvwxyz的答案是:67108863
这个结果和我的一样,我的代码昨天也改进了一点,修改在上面,不是原来的一步步算,是26为一步的算,你说的组合数是怎么说?
ab abc abcd abcde ……这样吗?

努力—前进—变老—退休—入土
2009-11-01 10:03
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
我贴出Python代码你分析一下吧:

程序代码:
def c(n, m):
    """
    计算组合数
    """
    list = [1] * (m + 1)
    for i in range(1, n + 1):
        list[0] = 1
        t1 = list[0]
        for j in range(1, min(i, m + 1)):
            t2 = list[j]
            list[j] += t1
            t1 = t2
    return list[m]
def get_ord2(str):
    res = 0
    for i in range(0, len(str)):
        res += c(26, i)
    nchr = lambda s: ord(s) - ord('a')
    pos = (lambda i:
            'a' if i == 0 else chr(ord(str[i - 1]) + 1))
    for i in range(0, len(str)):
        for j in range(26 - nchr(pos(i)) - 1,
                26 - nchr(str[i]) - 1, -1):
            res += c(j, len(str) - i - 1)
    return res
while True:
    print get_ord2(raw_input())


专心编程………
飞燕算法初级群:3996098
我的Blog
2009-11-01 10:12
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:15 
这个是C代码,如果要在TC下编译,请把int换成long:
程序代码:
#include <stdio.h>
#include <string.h>
#define N 27
int main(void)
{
    int dp[N][N];
    char str[N + 1];
    int i, j;
    for (i = 0; i <= 26; ++i)
    {
        dp[i][0] = dp[i][i] = 1;
        for (j = 1; j < i; ++j)
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    }
    while (scanf("%s", &str[1]) == 1)
    {
        int res = 0, len = strlen(&str[1]);
        str[0] = 'a' - 1;
        for (i = 0; i < len; ++i)
        {
            res += dp[26][i];
            for (j = str[i] + 1; j < str[i + 1]; ++j)
                res += dp[26 - (j - 'a') - 1][len - i - 1];
        }
        printf("%d\n", res);
    }
    return 0;
}


专心编程………
飞燕算法初级群:3996098
我的Blog
2009-11-01 10:39
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
收藏
得分:0 
好代码,等于26*26画个矩阵图,每行都有规律的递增,每列都有一个初值和一个基数,按这规律我也修改下我的代码,做到结果秒出。

[ 本帖最后由 UserYuH 于 2009-11-1 14:43 编辑 ]

努力—前进—变老—退休—入土
2009-11-01 11:09
快速回复:求一个题目的答案,本人是菜鸟,想了很久没想出!
数据加载中...
 
   



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

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