前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >小朋友学奥数(21):康托展开

小朋友学奥数(21):康托展开

作者头像
海天一树
发布2018-11-23 13:48:39
5680
发布2018-11-23 13:48:39
举报
文章被收录于专栏:海天一树

一、康托展开运算

把一个整数X展开成如下形式: X = an * (n - 1)! + an-1 * (n - 2)! + … + ai * (i - 1)! + … + a2 * 1! + a1 * 0! 其中,ai为整数,并且0 <= ai < i,1 <= i <= n)。 ai表示原数的第i位在当前未出现的元素中是排在第几个。

康托展开的最基本应用就是求一个排列(按字典序)的序号(即第几个)。而其逆运算就是求序号对应的排列。

二、例子

例1:n = 3时,即三位数字的全排列,321的序号是多少?

方法一: 1 2 3这三个数按字典序来进行排列,得:

代码语言:javascript
复制
123
132
213
213
312
321

这里可以看出321是第6个数。

方法二: 321的第一位是3,则第一位小于3的数一定排在321的后面,这样的排列有22!个。 321的第二位是2,则第一位等于3第二位小于2的数一定排在321的后面,这样的排列有11!个。 321的第三位是1,则第一位为3第二位为2第3位小于1的数一定排在321的后面,这样的排列有0个。 所以排在321前面的数有2 * 2! + 1 * 1! = 5个。321是第5 + 1 = 6个数。

例2:对于n = 3的全排列,第6个数是多少?

分析: 现将序号减去1,为5。 5/2!=2余1,说明比第一位数小的数有2个,那么第一位肯定为3。 上一步的余数/1! = 1/1!=1余0,说明比第二位小的数有1个,那么第二位肯定是2。 第三为只能为1了。 所以第6个数是321。

例3:n = 4的全排列中,1324是第几个数?

1324的第一位是1,小于1的数有0个,所以总共有 0 * 3! = 0个。 1324的第二位是3,小于3的数有1和2,但1已经在第一位了,所以只有一个数2。再考虑第三位和第四位的排列数为2!,所以共有 12! = 2个。 1324的第三位是2,小于2的数是1,但1已经排在第一位了,所以有0个数 。 01! = 0。 所以比1324小的排列有0 * 3! + 1 * 2! + 0 * 1! = 2个。 综上,1324是的序号为2 + 1 = 3。

例4:对于n = 6的全排列,153426的序号是多少?再往后数200个,得到的数是多少?

① 153426的第一位数是1,比1小的数有0个,共有0 * 5!= 0个。 153426的第二位数是5,比5小的数有4个,但是1已经出现在首位了,所以只有2,3,4这三个。共有3 * 4!= 72个。 153426的第三位数是3,比3小的数有2个,但是1已经出现在首位了,所以只有2这1个。共有1 * 3!= 6个。 153426的第四位数是4,比4小的数有3个,但是1和3已经出现在首位和第三位了,所以只有2这1个。共有1 * 2!= 2个。 153426的第五位数是2,比2小的数有1个,但是1已经出现在首位了,所以共有0 * 1!= 0个。 153426的第六位数是6,比6小的数有5个,但是这5个数已经被前五位数占了,所以共有0 * 0!= 0个。 综上,153426排在第72 + 6 + 2 + 1 = 81个。

② 第81个再往后数200个,就是第281个。 首先将281减去1,即280。 第一位为280 / 5! = 2余40,说明比第一位数小的数有2个,则第一位数必为3 上一步的余数 / 4! = 40 / 4! = 1余16,说明比第二位数小的数有1个,第二位数必为2。 上一步的余数 / 3! = 16 / 3!= 2余4,说明比第三位数小的数有2个。在前两位数是3和2的前提下,第三位只能为5,这样比它小的两个数为1或4。 上一步的余数为 4/ 2! = 2余0 ,说明比第四位数小的数有2个。因为前三位数分别为3、2、5,则第四位数必为6。 上一步的余数为 0/1! = 0余0 ,说明比第五位数小的数有0个,则第五位数必为1。 剩下一位数为4。 综上,153426往后数的第200个数是325614。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-10-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 KidsCode少儿编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、康托展开运算
  • 二、例子
    • 例1:n = 3时,即三位数字的全排列,321的序号是多少?
      • 例2:对于n = 3的全排列,第6个数是多少?
        • 例3:n = 4的全排列中,1324是第几个数?
          • 例4:对于n = 6的全排列,153426的序号是多少?再往后数200个,得到的数是多少?
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档