7C00.ME/houmu 2012-01-05

一则算法题的解题报告:手机键盘

考完试后心血来潮,打算研究一些数据结构和算法方面的问题,发现了博客园里面的这篇文章《算法竞赛专题集合》(网址),里面给出了不少有用的资料。随便挑出了其中的一个来看,有一道关于手机键盘的题目(网址),感觉比较有意思,难度也不是太大,特意拿出来做了一下。简单说明一下我的做法。

题目要求,参见网址

在看文章给出的结题思路之前,自己的想法是这样的。首先从数字上找规律,对于字符a到r而言,按键次数就是相对值(字符ch和‘a’的距离,就是ch-‘a’)模3加1,但是7和9每个键包含4个字符,打破了这个规律,那就单独考虑。总共就8个字符,就用查表法了。代码如下:

#include<stdio.h>
int main()
{
	char w[300];
	int i =0;
	int t =1;
	int ts[8] = {4,1,2,3,1,2,3,4};
	scanf("%s",&w);
	while(w[i] != '\0')
	{
		if(w[i] >= 's')
			t = ts[(w[i]-'s')];
		else
			t = (w[i]-'a') % 3 + 1;
		printf("%c%d",w[i],t);
		i+=1;
	}
	return 0;
}

然后,学习一下人家的思路。他(她)首先考虑的也是查表法,但是接着在空间复杂度上否定了这个思路。然后,做了一种改进,在我看来是查表法的一种变种或优化吧。我对他的算法的一种实现,代码如下:

#include<stdio.h>
int main()
{
	char w[300];
	char l[10] = "adgjmptw{";
	int i=0,j=0;
	scanf("%s",&w);
	while(w[i] != '\0')
	{
		j=0;
		while(w[i] >= l[j+1]) j++;
		printf("%c%d",w[i],w[i]-l[j]+1);
		i++;
	}
	return 0;
}

特别注意到一个字符‘{’是ascii表后紧随着‘z’的,用来判断边界。第二种方法感觉比第一种方法要好一点。