字典序問題

        問題描述：在資料加密和資料壓縮中需要對特殊的字元串進行編碼。給定的字母表由26個小寫字母組成。該字母表産生的升序字元串是指字元串中字母從左到右出現的次序與字母在字母表中出現的次序相同，且每個字元最多出現1次。例如，a,b,ab,bc,xyz等都是升序字元串。現在對字母表中産生的所有長度不超過6的升序字元串按照字典序排列并編碼如下：

1	2	...	26	27	28	...
a	b	...	z	ab	ac	...

    對于任意長度不超過6的升序字元中，迅速計算出它在上述字典中的編碼。

    任務：對于給定的長度不超過6的升序字元串，程式設計計算它在上述字典中的編碼。

    解題思路：本題的關鍵之處在于正确了解題目描述中給出的字典序，其關鍵之處在于首先出現長度為1的字元串，然後是長度為2的字元串、……。而在相同長度的字元串中，按照字典序進行。例如，對字元串cfkp這個長度為4的字元串來講，如果能夠計算出排在它前面的字元串數目，加1就得到該字元串的編碼。排列在該字元串前的字元串可以如下分析：

    （1）長度為1的字元串、長度為2的字元串、長度為3的字元串；

     (2）在以字母c打頭的長度為4的字元串中，以cd、ce打頭、長度為4的字元串同樣排列在該字元串前面；而在以cf打頭的長度為4的字元串中，以cfg、cfh、cfi、cfj打頭的長度為4的字元串排列在該字元串前面；在以cfk打頭的字元串中，以cfkl、cfkm、cfkn、cfko打頭的長度為4的字元串同樣在它前面。

    對第（2）種情況進行分析，可以分為如下幾種情況：

    以cd和ce打頭、長度為4的字元串數目與以d、e打頭、長度為3的字元串數目相同；其他情況可以描述為：以g、h、i、j打頭，長度為2的字元串數目；以l、m、n、o打頭、長度為1的字元串數目。

    分析上述情況，對其中的規律進行總結，需要計算的字元串數目可以分為兩類：

   （1）長度為k的字元串數目，用g(k)表示；

   （2）以字元ch打頭，長度為k的字元串數目，用f(ch,i)表示。

    顯然，有

              g(k)=sum_{ch=1}^26 f(ch,k)

    同樣，有如下規律可以發現：

              f(ch,1)=1

              f(ch,k)=sum_{i=ch+1}^26 f(i,k-1)           

    在此基礎上，可以計算出每個字元串的編碼。

參考程式：

#include <stdio.h>
#include <string.h>

//計算以i打頭長度不超過k的升序字元串的個數
int f(int i,int k) 
{
	if (k==1)
		return 1;
	else
	{
		int sum=0;
		int j;
		for(j=i+1;j<=26;j++)
			sum+=f(j,k-1);
		return sum;
	}
}

//計算長度不超過k的升序字元串總個數
int g(int k)
{
	int sum=0;
	for(int i=1;i<=26;i++)
		sum+=f(i,k);
	return sum;
}

//進行單個字元到整數的轉換，這裡的整數是1~26
int change(char ch)
{
	return ch-'a'+1;
}

void main()
{
	char *str="a";
	
	//printf("the length of the string is %d.\n",strlen(str));
	int i,j;
	int pos=0;
	
	//首先處理長度小于本串長度的情況，涉及g函數
	for(i=1;i<strlen(str);i++)
		pos+=g(i);

	//處理首字元的情況
	for(i=1;i<change(str[0]);i++)
	{
		pos+=f(i,strlen(str)-1);
	}
	
	//處理後續字元的情況
	for(i=1;i<strlen(str);i++)
	{
		int temp=change(str[i-1]);
		int t=change(str[i]);
		int length=strlen(str)-i;
		
		for(j=temp+1;j<t;j++)
			pos+=f(j,length);
	}

	printf("the position of the string is %d.\n", pos+1);
}