アルゴリズムの問題の解題報告:携帯電話のキーボード

試験が終わった後、心血が流れて、いくつかのデータ構造とアルゴリズムの方面の問題を研究しようとして、ブログ園の中のこの文章《アルゴリズムコンテストの特別テーマの集合》(Webサイト)を発見して、中は多くの役に立つ資料を提供しました.そのうちの1つを適当に選んでみると、携帯電話のキーボードに関する問題(Webサイト)があって、面白そうで、難易度もあまり大きくないので、わざわざ出してみました.私のやり方を簡単に説明します.
タイトルの要件は、Webサイトを参照してください.
文章の出した問題の構想を見る前に、自分の考えはこうだった.まず、数字から法則を探します.文字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;

}

特に、1つの文字「{」はasciiテーブルの後ろに「z」が付いていることに気づき、境界を判断します.2つ目の方法は、1つ目の方法よりも良い感じがします.