《编程思维与实践》1002.神秘信息

题目

思路

由相同的符号表示相同的数码，不同的符号表示不同的数码可以知道： 如果神秘信息中有 n 个不同的字符，那么至少是 n 进制的 ( 像两个字符至少要用 1 和 0 表示 ) 那么不难知道当 n 进制时，表示的整数才可能是最小的 同时，要想使表示的整数最小那越靠前的字符表示的数应该越小 但应注意第一个字符不能表示为 0 ，如 : c a t s 的四进制最小表示为 1023 进制转换 N = k n R n + k n − 1 R n − 1 + . . . + k 1 R + k 0 可以通过迭代来计算： N = ( k n R n − 1 + k n − 1 R n − 2 + . . . + k 1 ) R + k 0 也就是说可以先求出 k n R 再乘上 R 加上 k n − 1 一直如此操作直到加到 k 0 由相同的符号表示相同的数码，不同的符号表示不同的数码可以知道：\\ 如果神秘信息中有n个不同的字符，那么至少是n进制的(像两个字符至少要用1和0表示) \\ 那么不难知道当n进制时，表示的整数才可能是最小的\\ 同时，要想使表示的整数最小那越靠前的字符表示的数应该越小\\ 但应注意第一个字符不能表示为0，如:cats的四进制最小表示为1023\\ 进制转换\quad N=k_nR^n+k_{n-1}R^{n-1}+...+k_1R+k_0 \\ 可以通过迭代来计算：N=(k_nR^{n-1}+k_{n-1}R^{n-2}+...+k1)R+k_0\\ 也就是说可以先求出k_nR \quad 再乘上R加上k_{n-1} \quad 一直如此操作直到加到k_0 由相同的符号表示相同的数码，不同的符号表示不同的数码可以知道：如果神秘信息中有n个不同的字符，那么至少是n进制的(像两个字符至少要用1和0表示)那么不难知道当n进制时，表示的整数才可能是最小的同时，要想使表示的整数最小那越靠前的字符表示的数应该越小但应注意第一个字符不能表示为0，如:cats的四进制最小表示为1023进制转换N=kn​Rn+kn−1​Rn−1+...+k1​R+k0​可以通过迭代来计算：N=(kn​Rn−1+kn−1​Rn−2+...+k1)R+k0​也就是说可以先求出kn​R再乘上R加上kn−1​一直如此操作直到加到k0​

代码

#include<stdio.h>
int main()
{
	int T;
	scanf("%d",&T);     
	for(int i=0;i<T;i++)
	{
        char s[61];        //字符串长度最多为60 数组应该开61
		scanf("%s",s);
		int a[128];    //相同的符号表示相同的数可以利用ASCII码表的对应关系
		
        for(int j=0;j<128;j++)
		{
			a[j]=-1;              //用数组来存储每个位置的数字 
		}
        
        char *p=s;
        a[*p]=1;        //先将最特殊的第一个赋值（断点），之后对第二个以后的处理
        int digit=0;   //赋值
        int number=1;  //统计不同元素个数，也就是最小的进制数
        
		while(*(++p)!='\0')
		{
			if(a[*p]==-1)  //为-1表示判断未赋过值，也就是新元素
			{	
                a[*p]=digit;
                digit=digit?digit+1:2;   //digit为0时digit的值为2 否则为digit+1  （如1023） 
				number++;
			}
		}
        
		if(number<2)  //没有一进制 
		{
			number=2;
		}
        
		p=s;
        long long count=0;  //计算最小的十进制数
        
		while(*p!='\0')
		{
			count=count*number+a[*p];   //number为进制数
			p++;
		}
      
        printf("case #%d:\n",i);
		printf("%lld\n",count);
	}	
	return 0;
}