Java编程题:年会抽奖(错排问题) |
您所在的位置:网站首页 › 某部门举行年会抽奖活动英语翻译 › Java编程题:年会抽奖(错排问题) |
年会抽奖
今年公司年会的奖品特别给力,但获奖的规矩却很奇葩: 首先,所有人员都将一张写有自己名字的字条放入抽奖箱中;待所有字条加入完毕,每人从箱中取一个字条;如果抽到的字条上写的就是自己的名字,那么“恭喜你,中奖了!” 现在告诉你参加晚会的人数,请你计算有多少概率会出现无人获奖?输入描述: 输入包含多组数据,每组数据包含一个正整数n(2≤n≤20)。 输出描述: 对应每一组数据,以“xx.xx%”的格式输出发生无人获奖的概率。 示例1 输入 2 输出 50.00% 解析: 本题求解需要求出所有可能的抽奖情况,及所有人都不中奖时的情况,两者相除即为所得。这里主要牵扯到了一个错排问题。 错排问题: n个有序的元素应有n!个不同的排列,如若一个排列使得所有的元素不在原来的位置上,则称这个排列为错排;有的叫重排。 求错排问题的递推关系,分两步走: 第一步,考虑第n个元素,把它放在某一个位置,比如位置k,一共有n-1种放法; 第二步,考虑第k个元素,这时有两种情况: (1)把它放到位置n,那么对于除n以外的n-1个元素,由于第k个元素放到了位置n,所以剩下n-2个元素的错排即可,有Dn-2种放法; (2)第k个元素不放到位置n,这时剩下的这n-1个元素错排就好了,有Dn-1种放法。(如果位置n不放第k个元素,那么我们就可以把第k个元素当作是原来的第n个元素,相当于n-1个元素错排) 综上得到: 来源:牛客网 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |