可用分押宝游戏火热进行中...	专题改版：Java Web 专题

字母——数字密码

楼主Vo5（娜娜）2005-04-01 00:07:18 在 C/C++ / C语言提问

我们学校acm校内赛的训练题，我花了一个小时都没做完，哪位大侠能给我讲讲正确的算法吗？谢谢啦

如果用数字1——26代表英文字母a--z，即1--a,2--b,以此类推……26——z;
那么我们可以用数字来代表相应的单词。
但是一个数字排列有多种可能，
如123可能代表abc(1，2，3.),也可能代表lc(12，3),或者aw（1，23）
要求编一个程序，计算出从键盘输入的每串数字可能代表的字母串的个数,输入0则程序结束
如
input:
25114
1111111111
3333333333
0
output:
6
89
1

象这种题我们应该怎么入手？我通常都是凭直觉嘀……知识不成系统阿问题点数：50、回复次数：25Top

1 楼du51（郁郁思扬）回复于 2005-04-01 01:07:05 得分 0

大哥呀.传说中的非波那契呀..Top

2 楼MagicCarmack（MagiC++）回复于 2005-04-01 01:21:04 得分 0

楼上的能不能解释一下,我实在看不出是什么斐波那契数列

这个应该是个数学组合问题Top

3 楼KamofNUDT（）回复于 2005-04-01 01:35:47 得分 0

求解思路如下：
首先考虑没有两位数字的情况，这个简单，只有一种可能；
然后考虑有一个两位数字的情况，只要计算一个字符串中可能出现的两位数的个数就可以得到，也很容易，记为B_1；
然后考虑有两个两位数的情况，首先把第一个两位数从字符串中去掉，然后重复第二步的做法，得到结果C_1；再把原字符串中第二个两位数去掉，重复第二步的做法，得到结果C_2；依次下去，得到结果C_B_1；第三步的最后结果就是 C_1 + C_2 + ... + C_B_1
接下来是三个两位数，也是一样，去掉一个，然后重复上一步的做法，最后把结果累加起来
直到最后去掉 N 个两位数

编程实现的时候估计要考虑一下怎样实现Top

4 楼du51（郁郁思扬）回复于 2005-04-01 02:33:00 得分 0

#include<iostream>
using namespace std;
int f(int n)
{
if(n==1)return 1;
if(n==2)return 2;
return f(n-1)+f(n-2);
}
int make(char *str)
{
int count=1;
int len=strlen(str);
int i,j;
for(i=0,j=0;i<len;i++)
{
if(str[i]==49||str[i]==50)
{
j++;
if(i+1==len)count*=f(j);
continue;
}
if(str[i]>49&&str[i]<55)
{
j++;
count*=f(j);
j=0;
continue;
}
}
return count;
}
int main()
{
char *str[200];
for(int i=0;i<200;i++)str[i]=new char[200];
i=0;
cin>>str[i];
while(strcmp(str[i],"0"))cin>>str[++i];
i=0;
while(strcmp(str[i],"0"))cout<<make(str[i++])<<endl;
for(i=0;i<200;i++)delete str[i];
system("PAUSE");
return 0;
}Top

5 楼du51（郁郁思扬）回复于 2005-04-01 02:56:40 得分 20

以上程序在VC下可以.DEV下.把MAIN里面I的声明提到FOR外面即可.
*******************************************************************
1只有一种排法.
1:
1
12:
(1)+2 (这里面的1是只有一个1的时候)
因为12可组有.
(12)....................共二个.
121:
(1+2)+1 (这是只有12的时候的情况)
(12)+1 (这是只有12的时候的情况)
此时因为2与1可组.顾多出单独1的时候的情况.
(1)+21 (这里是1单独的时候的情况)...........共三.
1212:
(1+2+1)+2 (这是只有121的时候的情况)
(12+1)+2 (这是只有121的时候的情况)
(1+21)+2 (这是只有121的时候的情况)
此时因为1与2可组.顾多出单独12时候的情况.
(1+2)+12 (这是只有12的时候的情况)
(12)+12 (这是只有12的时候的情况)..........共五.
----------------------------------------
至此.后面递推.应是斐波那契数列........
================================================
再回到总体.假设有一个为:12312612
明眼人一看便知这个数列的总结果应为(123)(126)(12)三个单项的积....
原因很简单.
123的3与12的1没法组成有效数.被隔离了.而126与12同理被隔离了.
也就是三者个数取斐波那契之后相乖即可...........
Top

6 楼du51（郁郁思扬）回复于 2005-04-01 03:39:25 得分 20

不好意思呀.上面程序有问题.
#include<iostream>
using namespace std;
int f(int n)
{
if(n==1)return 1;
if(n==2)return 2;
return f(n-1)+f(n-2);
}
int make(char *str)
{
int count=1;
int len=strlen(str);
int i,j;
for(i=0,j=1;i<len;i++,j++)
{
if((str[i]==49||str[i]==50))
{
if(i+1==len)count*=f(j);
continue;
}
if(i-1>-1&&str[i]>54&&str[i-1]==50)j--;
count*=f(j);
j=0;
}
return count;
}
int main()
{
char *str[200];
int i;
for(i=0;i<200;i++)str[i]=new char[200];
i=0;
cin>>str[i];
while(strcmp(str[i],"0"))cin>>str[++i];
i=0;
while(strcmp(str[i],"0"))cout<<make(str[i++])<<endl;
for(i=0;i<200;i++)delete str[i];
system("PAUSE");
return 0;
}Top

7 楼wugaojun（）回复于 2005-04-01 15:26:44 得分 0

思路完全是正确的.其实跟知识体系应该没什么关系,有直觉就行.然后慢慢理清思路并把一些边界情况考虑清楚就行了Top

8 楼pcboyxhy（-273.15℃）回复于 2005-04-01 15:33:54 得分 0

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char *argv[])
{
char str[10000];
int a, b, len, t, i;
while(cin>>str)
{
a=1; b=1;
if(str[0]=='0') return 0;
len=strlen(str);
for(i=1; i<len; ++i)
if(str[i]=='0'||str[i-1]=='0') b=a;
else if(str[i]<'7' && str[i-1]=='2' || str[i-1]=='1') {t=b; b+=a; a=t;}
else a=b;
cout<<b<<endl;
}
return 0;
}
Top

9 楼Vo5（娜娜）回复于 2005-04-01 16:52:11 得分 0

to 郁郁思扬，
谢谢你提供的思路，我做出来了！！（哈哈哈哈哈笑一笑祝贺一下先~~~~~~~）谢谢！！！
p.s

你的程序中 system("PAUSE"); 这句是什么意思？有什么作用？
Top

10 楼Vo5（娜娜）回复于 2005-04-01 17:01:36 得分 0

还有还有……
if(i-1>-1&&str[i]>54&&str[i-1]==50)j--;
这个语句中i-1>-1 是什么意思？
Top

11 楼du51（郁郁思扬）回复于 2005-04-01 17:14:35 得分 0

i-1>-1是防止越界.......
system("PAUSE");是使程序暂停.使你可能看结果,而不是一闪就没有了.Top

12 楼shine51151（美丽心情）回复于 2005-04-01 17:22:03 得分 0

system("PAUSE");
这里是让程序在执行完暂停一下，不用也可以。

i-1>-1
实际上就是判断i是不是大于0，如果i小于0条件就为假。
Top

13 楼Vo5（娜娜）回复于 2005-04-01 17:35:52 得分 0

我用的是tc3.0
system("PAUSE");过不了编译……Top

14 楼xjp6688（大平/要做必须最好）回复于 2005-04-01 17:36:28 得分 0

你的程序中 system("PAUSE"); 这句是什么意思？有什么作用？
------------
是暂停程序Top

15 楼du51（郁郁思扬）回复于 2005-04-01 17:49:55 得分 0

换成getchar();Top

16 楼du51（郁郁思扬）回复于 2005-04-01 17:53:57 得分 0

#include<iostream.h>
#include<string.h>
int f(int n)
{
if(n==1)return 1;
if(n==2)return 2;
return f(n-1)+f(n-2);
}
int make(char *str)
{
int count=1;
int len=strlen(str);
int i,j;
for(i=0,j=1;i<len;i++,j++)
{
if((str[i]==49||str[i]==50))
{
if(i+1==len)count*=f(j);
continue;
}
if(i>0&&str[i]>54&&str[i-1]==50)j--;
count*=f(j);
j=0;
}
return count;
}
int main()
{
char *str[200];
int i;
for(i=0;i<200;i++)str[i]=new char[200];
i=0;
cin>>str[i];
while(strcmp(str[i],"0"))cin>>str[++i];
i=0;
while(strcmp(str[i],"0"))cout<<make(str[i++])<<endl;
for(i=0;i<200;i++)delete str[i];
cin.get();
return 0;
}
Top

17 楼yuanyou（元友）回复于 2005-04-01 18:06:05 得分 0

学习！！Top

18 楼syun0（@）回复于 2005-04-01 19:37:39 得分 5

char str[100];
int func(char str[], int start, int *c)
{
if (str[start] == '\0')
(*c) ++;
else
{
func(str, start+1, c);
if (str[start+1] != '\0' && (str[start]-'0')*10+(str[start+1]-'0') <= 26)
func(str, start+2, c);
}
return 0;
}

int main()
{
int i = 0, count = 0;
printf("input:");
while ((str[i++]=getchar()) != '\n');
str[i-1] = '\0';
func(str, 0, &count);
printf("%d\n", count);
return 0;
}Top

19 楼pcboyxhy（-273.15℃）回复于 2005-04-01 19:59:14 得分 5

做ACM练习题就不要用TC了
还没听说过有比赛用这个的Top

20 楼cdlqfayx（）回复于 2005-04-02 11:37:49 得分 0

to du51(郁郁思扬) : 小弟拜服!
看到题目偶只有朦胧的思路,不如你的清晰.
向你学习!Top

21 楼lihuanzhong（紫色枫叶）回复于 2005-04-02 12:37:30 得分 0

有点思路了我做作看
Top

22 楼Vo5（娜娜）回复于 2005-04-02 18:58:28 得分 0

我学到了很多呢……谢谢！！Top

23 楼du51（郁郁思扬）回复于 2005-04-03 00:23:01 得分 0

别光谢呀.给分呀.呵呵....Top

24 楼Meteorlet（http://smartdict.cn）回复于 2005-04-03 10:47:28 得分 0

回复人：syun0(@) ( ) 正解Top

25 楼Vo5（娜娜）回复于 2005-04-03 21:26:01 得分 0

接吧
^_^Top