Board logo

标题: 一道巨混乱的机经题 [打印本页]

作者: 壳    时间: 2008-5-21 17:27     标题: 一道巨混乱的机经题

一个密码由1-20的任意数组成,数字排序相同算一个密码,一共有多少种可能?
作者: alamutu    时间: 2008-5-22 07:17

这题头疼,转一哥们的解答供参考:

首先要明确的问题,就是数字间是否允许0得出现,应该是20的0肯定允许,但对于个位数1,不会有01的存在吧?按题目来看应该是这个意思

如果这样的话,再按照楼主理解的排序相同的概念,那没有几个排序相同的数
因为所有连续的号码,只能是1组成的,
不会有0,因为没有01、02等数
不会有2或者更大的数,因为不会有20(这个结合上面的条件),以及21等更大的数

这样我们只要算出所有的可能再减去,重复数的可能,即可得出答案
所有的可能20*20*20

在计算连续的1,为了说明方便,我定义一个不显示的0为a,即数字1,表示为a1(实际是01,为了不和20中的0混淆,写作a1),
再定义任意出现的个位数字为y,任意出现两位为xx

第一步计算两个连续的1出现,即11,这样,可能出现11,并重复的密码为(上下为一组重复的数)
a1 1y xx  或者 xx a1 1y
11 ay xx      xx 11 ay
其中由于只有连续两个1出现,排除连续三个1出现,所以y={2,3,...,9},(y也不可能=0,因为没有如05这样的数出现),共8个数
xx={2,3,...19,20},共19个数

这样可能重复的数为8*19*2

第二本计算连续三个1,即111出现的并重复的密码可能:
a1 11 xx  或者 xx a1 11
11 a1 xx      xx 11 a1
11 1y xx      xx y1 11

先计算a1 11 xx  或者 xx a1 11这一组重复的数就是19*2个
      11 a1 xx      xx 11 a1
xx={2,3,...19,20},共19个数,就是19*2个

再计算a1 11 xx  这一组重复的数
      11 1y xx     
这里的y={2,3,...,9},而且xx只能为除了0、1的个位数,也是1个数
所以可能为8*8个

最后再看 xx a1 11 这一组重复的数
        xx y1 11
由于最大的数为20,所以不可能有y1这种数的存在,所以排除这一组数的可能

第三步在计算连续四个1,即1111出现的并重复的密码可能
只有一种 11 11 ay
        a1 11 1y
y={2,3,...,9},共8种

还有最后一种可能,即所有的数均为1组成,可能有1111,和11111两种,
第一种为 11 a1 a1  2个重复的数
        a1 11 a1
        a1 a1 11
第二种为 a1 11 11  也是2个重复的数
        11 a1 11
        11 11 a1

应该在没有别的重复的可能了,所以答案是
20*20*20-8*19*2-19*2-8*8-8-2-2

由于解法有些繁琐,不知有没有落下什么,大家帮忙看看有没有考虑不周全的地方吧,或者有更简便的算法。。。


作者: shelleyzhdai    时间: 2008-5-23 14:37

也许题目错了
作者: seinfeld0923    时间: 2008-5-31 08:24

QUOTE:
以下是引用alamutu在2008-5-22 7:17:00的发言:

这题头疼,转一哥们的解答供参考:

首先要明确的问题,就是数字间是否允许0得出现,应该是20的0肯定允许,但对于个位数1,不会有01的存在吧?按题目来看应该是这个意思

如果这样的话,再按照楼主理解的排序相同的概念,那没有几个排序相同的数
因为所有连续的号码,只能是1组成的,
不会有0,因为没有01、02等数
不会有2或者更大的数,因为不会有20(这个结合上面的条件),以及21等更大的数

这样我们只要算出所有的可能再减去,重复数的可能,即可得出答案
所有的可能20*20*20

在计算连续的1,为了说明方便,我定义一个不显示的0为a,即数字1,表示为a1(实际是01,为了不和20中的0混淆,写作a1),
再定义任意出现的个位数字为y,任意出现两位为xx

第一步计算两个连续的1出现,即11,这样,可能出现11,并重复的密码为(上下为一组重复的数)
a1 1y xx  或者 xx a1 1y
11 ay xx      xx 11 ay
其中由于只有连续两个1出现,排除连续三个1出现,所以y={2,3,...,9},(y也不可能=0,因为没有如05这样的数出现),共8个数
xx={2,3,...19,20},共19个数

这样可能重复的数为8*19*2

第二本计算连续三个1,即111出现的并重复的密码可能:
a1 11 xx  或者 xx a1 11
11 a1 xx      xx 11 a1
11 1y xx      xx y1 11

先计算a1 11 xx  或者 xx a1 11这一组重复的数就是19*2个
      11 a1 xx      xx 11 a1
xx={2,3,...19,20},共19个数,就是19*2个

再计算a1 11 xx  这一组重复的数
      11 1y xx     
这里的y={2,3,...,9},而且xx只能为除了0、1的个位数,也是1个数
所以可能为8*8个

最后再看 xx a1 11 这一组重复的数
        xx y1 11
由于最大的数为20,所以不可能有y1这种数的存在,所以排除这一组数的可能

第三步在计算连续四个1,即1111出现的并重复的密码可能
只有一种 11 11 ay
        a1 11 1y
y={2,3,...,9},共8种

还有最后一种可能,即所有的数均为1组成,可能有1111,和11111两种,
第一种为 11 a1 a1  2个重复的数
        a1 11 a1
        a1 a1 11
第二种为 a1 11 11  也是2个重复的数
        11 a1 11
        11 11 a1

应该在没有别的重复的可能了,所以答案是
20*20*20-8*19*2-19*2-8*8-8-2-2

由于解法有些繁琐,不知有没有落下什么,大家帮忙看看有没有考虑不周全的地方吧,或者有更简便的算法。。。

服了!好有耐心阿


作者: beerbuggys    时间: 2008-6-6 08:29

考试的时候碰到这题,直接放弃




欢迎光临 国际顶尖MBA申请交流平台--TOPWAY MBA (http://forum.topway.org/) Powered by Discuz! 7.2