算法笔记 01_字典序问题


★问题描述:

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26 个小写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同,且每个字符最多出现1次。例如,a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序字符串按照字典序排列并编码如下:

12...2728...
ab...abac...

对于任意长度不超过6 的升序字符串,迅速计算出它在上述字典中的编码。


★源程序(C++):

#include<string>  
#include<iostream>   
using namespace std;   
int f[26][10];   
int g[10];   
int zidianxu(string t)   
{   
 int sum=0;   
 int len=t.length();   
 if (len==1)   
 return t[0]-'a'+1;   
 for (int j=0;j<len;j++) sum+=g[j];   
 for (int i=0;i<t[0]-'a';i++) sum+=f[i][len-1];   
 int k=1;   
 while(k<len)   
 {   
  if(t[k]<=t[k-1])   
  return 0;   
  if (k+1==len) sum++;   
  for(int p=t[k-1]-'a'+1;p<t[k]-'a';p++) sum+=f[p][t.length()-k-1];   
  k++;   
 }   
 return sum;   
}   
  
int main()   
{   
 int n,i;   
 string str[1000];  
 cin>>n;   
 g[0]=0;   
 g[1]=26;   
 for(i=0;i<26;i++)   
 {   
  f[i][0]=1;   
 }   
 for(int j=1;j<10;j++)   
 {   
  for(i=0;i<26;i++)   
  {   
   for(int k=i+1;k<26;k++) f[i][j]+=f[k][j-1];   
  }   
  for(i=0;i<26;i++) g[j+1]+=f[i][j];   
 }   
 for(i=0;i<n;i++) cin>>str[i];  
 for(i=0;i<n;i++) cout<<zidianxu(str[i])<<endl;  
 return 0;  
}


★输出:比如在这里输入4,然后需要手动输入四个字符串,回车

happysneaker.com


上面的太难,下面的简单版字典序帮助理解


像abcd, 我们给他们编上位置代号:1234,在1的位置进制是26,在2的位置进制是25,以此递减,而且在2的位置少了a, 在3的位置少了a, b,以此类减。可以看出进制和字母在各个位置上的实际大小跟位置有关。这样就可以做了,先求出最后面字母的大小(因为不用乘上进制),再求前面的字母大小。(重要就是逆着求),代码如下:

// zidianxu.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include<iostream>
using namespace std;

void main() {
	char a[6];
	cout << "请输入字母的个数(下标从0开始,0代表一个字母):" << endl;
	int i;
	cin >> i;
	cout << "请输入字母:" << endl;
	for (int j = 0; j <= i; j++) {
		cin >> a[j];
	}
	int sum = 0;
	sum = a[i] - 96 - i;// 结果即最后一个字母的大小,都不用乘上进制。
	//最后一个字母的大小都求出来了,那么接下来只要依次把之前的加上即可。下面的循环是从头开始计算。
	for(int k=0;k<=i-1;k++){ // i为0的情况下,此语句不执行,直接输入真实的大小。
		sum += (a[k] - 96 - k)*(26 - k);// 比如a为26,b为25,c为24...这样累加起来就行了
	}

	cout << "该序列的大小为:" << sum << endl;
	system("pause");
}

happysneaker.com

运行结果

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论