问题描述
背景
在古代中国,《三字经》、《百家姓》、《千字文》被合称为三、百、千,都是非常重要的启蒙教育课本,广为流传。而其中问世最早的《千字文》更凭借其优美的文字、华丽的辞藻成为中华传统文化的一个重要组成部分,得到了人们的普遍重视和喜爱。
《千字文》的作者,是梁武帝时代官拜散骑员外郎的周兴嗣。历来在正史上的记载,就这样一笔带过,但据私家笔记的野史记载,内容不是这样简单了。周兴嗣同梁武帝本来便是文字之交的朋友,在萧齐时代,还在朝廷上有过同僚之谊。到了梁武帝当了皇帝,那就变成君臣的关系。由朋友变君臣,说是关系不错,其实,伴君如伴虎,反是最糟糕的事,周兴嗣有一次不小心得罪了梁武帝,梁武帝一怒之下,想杀他或很严厉地处分他,到底还是于心不忍,只好下令把先关起来再说。但梁武帝又说了一句话,你不是文才很好吗?你能在一夜之间,把一千个不同的字,写一篇好文章,就赦你无罪。因此,周兴嗣就在一夜之间,挖空心思,写了这篇《千字文》。文章写好了,可是在一夜之间,头发、眉毛、胡子也都白了!大家要注意,用一千个不同的中文字,一夜之间,写出有关宇宙、物理、人情、世故的文间,等于写了一篇非常精简的“中国文化纲领要点”,虽然,只写到南北时期的梁朝为止,实在也太难了。梁武帝本人,才华文学都自命不凡,看了周兴嗣一夜之间之间所写的《千字文》,也不能不佩服。周兴嗣因此得到宽恕,而且还特加赏赐。
——摘自南怀瑾《原本大学微言》
现代人,一生中有机会通读千字文的机会是非常少的,很多理工科的大学生,完全没有听说过这篇神奇的文章,自然也会抱着“怀疑一切”的态度问,真的有这么神吗,真的一个重复的字都没有吗?耳听为虚,眼见为实,我们就来检验一下千字文中是不是真的没有重复的字。
不过在动手之前,先让我们花上几分钟的时间,读读《千字文》吧:简体中文版、正体中文版。
任务
请编写一个程序,从输入中读取一篇中文文章,并统计出该文章中 ASCII 字符以外的重复出现的每一个字重复出现的次数。
文章使用 UTF-8 编码,可能会出现任何可以用 UTF-8 编码表示的字符(不限于中文)。
文章中所有的字符在 UCS-2 能够表示的范围内,即字符的 Unicode 值用两个字节就可以表示。
输入
一篇文章,总字数不限、每行字符数不限。每个字重复出现的次数不超过 60000 次。
输出
按照 Unicode 编码从小到大的顺序,输出文章中 ASCII (0~127) 字符以外的每一个重复出现过的字重复出现的次数。每行包含三项内容,首先是重复的字符(以 UTF-8 编码输出),然后是该字符的 Unicode 编码值(十六进制输出,字母均使用小写,长度不足4位数的用0补齐),最后输出该字符的重复次数。
如果文章中没有出现重复的字,则输出“No repeat!”。
测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
---|---|---|---|---|---|
测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 1024KB | 0 |
测试用例 2 | 以文本方式显示
| 以文本方式显示
| 1秒 | 1024KB | 0 |
大体思路:
主要就是数据的读入和输出,进行UTF-8和unicodo以及十进制之间的转换,转换完成进行计数然后输出。其实题目的主体并不难,难的是数据的读入和输出。但是需要判断一下这个字符是用几个字节表示的,如果读入的值在0~127之间说明是用一个字节表示的,如果在192~223之间就表示是用两个字节表示的,根据题意,其他的情况就是用三个字节表示的。
具体实现:
输入用getchar()读入,然后结束的标记就用!=255,因为getchar()是一个字节一个字节读的,而UTF-8刚好又是以字节的形式存储的,所以正好搭配。
至于运用位运算还不是很熟练,所以就先不说位运算那种方法了,说一下一个暴力计算Unicode的方法:对于一个字节表示的字符其UTF-8的表示方式是0×××××××;对于两个字节表示的字符其表示方式是110××××× 10××××××;对于三个字节表示的字符其表示方式就是1110×××× 10×××××× 10××××××;依次类推。然后Unicode就是将上面的×号所在的位上的0或1字串链接起来所得到的一个大的二进制串的值。下面就是计算了,可以这样运用纯数学的方式计算。比如说对于二进制的符号来说假设第一个字节表示的数是a,第二个字节表示的数是b,那么将后面的×号所在位上的数字链接起来所得到的二进制字符串的十进制表示就是(a-2^7-2^6)*2^6+(b-2^7)这个主要就是运用了二进制与十进制的转化。计算出字符相应的Unicode值之后就把其作为计数数组的下标,然后进行计数,这样也省去了最后字符要按Unicode的大小进行输出时的排序那一步。三个字节的计算方法和两个字节的计算方法一样就不再说了。然后就是输出汉字,输出的时候需要判断一下Unicode的值以确定该字符是用三个字节表示的还是用两个字节表示的,两个字节可以表示的范围是128~2047,输出的时候可以采用这样的输出方式(“%c%c”,a,b)a,b,就是前面我们读入时的a,b的值。这里那,对于啊a,b可以有两种方式来计算,第一种就是在最开始计算的时候就把每一个字符所用的字节表示的数给记录下来;第二种就是再将Unicode的十进制形式转换为UTF-8以字节表示的形式,具体转换时这样的,假设Unicode的值是t(对于两个字节表示的字符来说),那么b=t%2^6+2^8,a=t/2^6+2^6+2^7,这样也可以计算出来啊a,b的值。这样一个汉字就输出来了,剩下的就是输出其十六进制表示就用printf("0x%04x",unicode);然后再输出大于1的字符的个数就好。
实现代码
<span style="font-family:Microsoft YaHei;font-size:14px;">#include<stdio.h>
#include<string.h>
int main()
{
// freopen("C:\\Users\\LL\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\LL\\Desktop\\out.txt","w",stdout);
unsigned char ch,ch1,ch2;
int t,t1,t2,m1,m2,m3,m=0;
long a[65536];
long n,i;
memset(a,0,sizeof(a));
while((ch=getchar())!=255)
{
t=ch;
if(t<128)
{
;
}
else if(t>191&&t<224)
{
ch1=getchar();
t1=ch1;
n=64*t+t1-12416;
a[n]++;
}
else
{
ch1=getchar();
t1=ch1;
ch2=getchar();
t2=ch2;
n=4096*t+64*t1+t2-925824;
a[n]++;
}
}
for(i=0;i<65536;i++)
{
if(a[i]>1)
{
m=1;
break;
}
}
if(m==1)
{
for(i=128;i<65536;i++)
{
if(i>=128&&i<=2047)
{
if(a[i]>1)
{
m2=i%64+128;
m1=i/64+192;
printf("%c%c",m1,m2);
printf(" 0x%04x",i);
printf(" %ld\n",a[i]);
}
else
{
;
}
}
else
{
if(a[i]>1)
{
m3=i%64+128;
m2=(i/64)%64+128;
m1=i/4096+224;
printf("%c%c%c",m1,m2,m3);
printf(" 0x%04x",i);
printf(" %ld\n",a[i]);
}
}
}
}
else
{
printf("No repeat!\n");
}
return 0;
}</span>