资源预览内容
亲,该文档总共2页全部预览完了,如果喜欢就下载吧!
资源描述
康托展开和康托展开的逆运算By_scy 2010-4-8 八数码问题不用康托展开判断重复8s,用康托展开判断重复30MS 。康托展开最大 最明显的作用就是在判断状态是否重复方面了,其实属于hash 的一个技巧。一、康托展开【问题背景】对于一个有n 个不同元素的集合 1,2,3,4,.,n的从小到大排序(从大 到小 同理)的全排列显然它有 n!项。如 n=4,那么就有 4!=4321=24项。与自然数 1,2,3,4,-n!与之一一对应。比如 1 4 四个数的全排列按字典序 如下: 1234:第一个 1243:第二个 1324:第三个 1342:第四个 1423:第五个 1432:第六个2134:第七个 2143:第八个 2314:第九个 2341:第十个 2413:第 11 个 2431:第 12 个3124:第 13 个 3142:第 14 个 3214:第 15 个 3241:第 16 个 3412:第 17 个 3421:第 18 个4123:第 19 个 4132:第 20 个 4213:第 21 个 4231:第 22 个 4312:第 23 个 4321:第 24 个【主要问题】例 1:求 4132 是第几个排列?看上面就知道答案就是:20。 那么是怎么算的呢?解:总共 4 个数,所以 n=4.ans:=0; 第一个数是 4,研究比 4 小的并且还没有出现过的数有3 个:1,2,3。那么 ans:=ans+ 3*(n-1)! 所以 ans:= ans+ 3* 3*2*1 =18 第二个数是 1, 研究比 1小的并且还没有出现过的数为 0 个。 那么 ans:=ans+ 0 * (n-2)!, 那么 ans 不变。第三个数是 3,研究比 3 小的并且还没有出现过的数为1 个:1,2。那么 ans:=ans+ 1* (n-3)!,那么 ans:=18+1* 1=19 第四个数是 2,研究比 2 小的并且还没有出现过的数为0 个。那么 ans 不变。其实最后 一个可以不研究了,比它大和比它小的全都出现过了。最后 ans 怎么等于 19啊?代 表它前面有 19 个排列嘛,那么 4132 自己就是第 20 个罗( 最后 ans:=ans+1)例 2:问 45231 是第几个排列?4 5 2 3 1ans:= 3*4! + 3*3! + 1*2! + 1*1! + 0*0! + 1 =94 练习第一题:找出 35142 在 15 从小到大全排序中的位置?第二题:找出 6482731在 18 从小到大全排列中的位置?第三题:找出 35142 在 15 从大到小全排序中的位置?第四题:找出 6482731在 18 从大到小全排列中的位置?二、康托展开的逆运算例 3:15 从小到大全排列中,找出第96 个排列?解:首先设 x1x2x3x4x5, (x1等于?不知道 ) ,用 96-1 得到 95,表示 x1x2x3x4x5 前面 有 95 个序列。第一个数 x1,假设 x1 目前有 k 个比 x1 小的并且还没有出现过的数,那么k:= 95 div (n-1)! = 95 div 24=3, 也就是有 3 个比 x1 小并且没有出现过的数,那么 x1=4. 95 变成 95-324=23 第二个数 x2,假设 x2 目前有 k 个比 x2 小的并且还没有出现过的数,那么k:= 23 div (n-2)! = 23 div 6 = 3, 也就是有 3 个比 x2 小并且没有出现过的数,那 么 x2=5.(有 3 个数比它小的数是4,但 4 已经在之前出现过了,所以是5)23 变成 23 3 * 6 = 5 第三个数用 23 去除 3! 得到 3 余 5 第四个数用 5 去除 2! 得到 2 余 1 第五个数就是最后还没有出现的那个。所以这个数是 45321 练习:第五题: 8 个数从小到大排序,求第28017个排列?第六题: 8 个数从大到小排序,求第14302个排列?注意 8 != 42320 http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1038 noip2004 普及火星人http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1148 8 数码问题http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1209魔板 ioi96 http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1212巧妙取量
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号