codeforces 392 c Yet Another Number Sequence

搜狗校招顺序随机整数编码

xhSong posted @ 2014年8月24日 11:42 in 数学 with tags 搜狗 校招 笔试 编码 顺序随机 K<=15*N , 8251 阅读

要准备找工作了,这几天在看july整理的面试题目,很全很强大。其中有个搜狗校招的笔试题目,觉得很有意思。思考了下,感觉相比给出的方法还有更好的方法。

题目

N个整数(数的大小为0-255)的序列,把它们加密为K个整数(数的大小为0-255).再将K个整数顺序随机打乱,使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法,且要求K<=15*N. 如果是:

1. N<=16,要求K<=16*N.
2. N<=16,要求K<=10*N.
3. N<=64,要求K<=15*N

第1、2问

因为N条件相同,所以第1问和第2问其实是同一个问题,解决了第2问也就搞定了第1问。

简单方法

原理

应题目要求,加密后的K个整数打乱顺序后还要能恢复原文,那么就需要将原文整数的位置信息也编码进密文。

一种简单的方法就是把密文的8位数分成3段

第1部分编码位置,N<=16的情况需要4位来表示
第2部分编码整数的第几位,000表示第0位,111表示第7位
第3部分编码某一位上的数值,如:0110 101 1表示,第6个数的第5位为1

原文整数范围[0-255]有8位,因此编码1个原文数字需要8个密文整数,即 K<=8N。已经可以满足第1、2问的要求了。

栗子

假设原文第6个整数为77,二进制表示为 01001101,那么可以编码成

0110 111 0
0110 110 1
0110 101 0
0110 100 0
0110 011 1
0110 010 1
0110 001 0
0110 000 1

好一点的方法

原理

这里我想到了一种更好一点的方法,可以使 K<=4N

首先,我们将原文整数写成4进制:x = a3 * 64 + a2 * 16 + a1 * 4 + a0(也就是将原文整数分为4段,每段2位),记系数为ai。由于i属于{0, 1, 2, 3}并且ai也属于{0, 1, 2, 3},因此我们考虑用2位编码i,2位编码ai。于是密文的数字就被分为了这么三段

第1部分依然编码位置
第2部分编码i
第3部分编码ai

这样只需要4个密文整数就可以编码一个原文整数了,即 K<=4N

栗子

假设原文第6个数字为77,二进制表示为 01001101,那么可以编码成

0110 11 01
0110 10 00
0110 01 11
0110 00 01

第三问

好一点的方法

原理

由于N<=64这样就必须用6位来编码位置,剩下只有2位来编码数值了。

继承第1、2问好一点的方法,我们用剩下的2位编码i,用出现的次数编码 ai。也就是ai等于多少对应的密文整数就出现多少次。由于i有4个,ai<=3,故每一个原文整数最多需要4*3=12个密文整数来编码,也就是 K<=12N

栗子

假设原文第6个数字为77,二进制表示为 01001101,那么可以编码成

000110 11
000110 01
000110 01
000110 01
000110 00

更好一点的方法

原理

假设每1个原文整数最多能使用 n 个密文整数来编码。

对于1个密文数字依然需要6位来编码位置,剩下2位来编码数值信息。2位对应4个状态(00, 01, 10, 11)。n 个密文整数分给4个状态,状态出现的次数可以位0,并且n可以不用完。相当于5个状态分n个整数,最后一个状态表示没有用完的整数。则一共有C(n+4, 4)种组合方式。

我们用1种组合方式编码1个数值,[0-255]共有256个数值。那么要求满足 C(n+4, 4) >= 256。求的当n=7时,C(n+4,4)=330 > 256。故这种编码方式可以使得 K<=7N。状态对应的表格在这里下载

栗子

假设原文第6个数字为77,二进制表示为 01001101,那么可以编码成

000110 10
000110 10
000110 01
000110 01
000110 00
000110 00

  • 无匹配
Avatar_small
陈磊 说:
2017年5月25日 08:34

佩服。貌似"第三问,好一点的方法"这里可以用剩下的2位编码ai,用出现的次数编码 i,这样可以更省一点空间,k<=10N

Avatar_small
li9.in 说:
2023年4月22日 14:14

Our reporting team intends to publish the Education & Recruitment Update for all age groups and present the true picture of the recent events with the inside coverage. Our objective would be to cater the requirements.. People of all age groups as we intend to publish news classified into General, Political, Crime, Sports, li9.in Entertainment, Education and World News.Our reporting team intends to publish the Education & Recruitment Update for all age groups and present the true picture of the recent events with the inside coverage. Our objective would be to cater the requirements.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter