算法笔记 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


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