Message Decoding UVA - 213
题目链接:https://vjudge.net/problem/UVA-213题目大意:
考虑下面的01串序列:
0,00,01,10,000,001,010,011,100,101,110,0000,0001,…,1101,1110,00000,…
首先是长度为1的串,然后是长度为2的串,以此类推。如果看成二进制,相同长读的后一个串等于前一个串加1.注意上述序列中不存在全为1的串。
你的任务是编写一个解码程序。首先输入一个编码头(例如 AB#TANCnrtXc),则上述序列的每个串依此对应编码头的每个字符。例如,0对应A,00对应B,01对应#…,110对应X,0000对应c。接下来是编码文本(有可能有多行组成)。编码文本由多个小节组成,每个小节的前3个数字代表小节中每个编码的长度(用二进制表示,例如010表示长度2),然后是各个字符的编码,以全1结束(例如,编码长度为2的小节以11结束)。编码文本以编码长度为000的小节结束。
例如,编码头为$#**\,编码文本为0100000101101100011100101000,应该这样解码:010(编码长度为2)00(#)00(#)10(*)11(小节结束)011(编码长度为3)000(\)111(小节结束)001(编码长度为1)0($)1(小节结束)000(编码结束)。
用一个二维数组来表示编码(len,value),len是编码长度,value是编码对应的二进制值。
边读取数据边处理数据,要注意换行符的处理且换行符有两个’\n’,’\r’。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int codes[8][(1<<8)-1];
int Get() {
memset(codes, 0, sizeof(codes));
//第一个要判断回车
while(1) {
char ch = getchar();
if(ch!='\n' && ch!='\r') {
codes[1][0] = ch;
break;
}
}
for(int i = 2; i <= 7; i++) {
for(int j = 0; j < (1<<i)-1; j++) {
char ch = getchar();
//结束程序
if(ch == EOF) return 0;
if(ch=='\n' || ch=='\r') return 1;
codes[i][j] = ch;
}
}
return 1;
}
int Read(int n) {
int sum = 0;
while(n--) {
char ch = getchar();
if(ch=='\n' || ch=='\r') n++;
else sum = sum*2 + (ch-'0');
}
return sum;
}
int main()
{
freopen("i.txt","r",stdin);
int flag ,len;
while(Get()) {
while(1) {
len = Read(3);
//printf("++++%d++++\n",len);
if(!len) break;
while(1) {
flag = Read(len);
//printf("\n***%d***\n",flag);
if(flag==(1<<len)-1) break;
putchar(codes[len][flag]);
}
}
putchar('\n');
}
return 0;
}