c 网站开发工程师招聘,网站建设有前景吗,网站手机端跳转页面模板,兰州传诚网络科技有限公司现在有28个小朋友#xff0c;每个人手上有一把钥匙#xff0c;每一个钥匙都只能打开自己的房间门#xff0c;现在将所有钥匙都收上来#xff0c;然后再随机打乱分给每个小朋友#xff0c;也就是有28#xff01;的分法#xff0c;请问现在其中14个小朋友的钥匙能恰好打开… 现在有28个小朋友每个人手上有一把钥匙每一个钥匙都只能打开自己的房间门现在将所有钥匙都收上来然后再随机打乱分给每个小朋友也就是有28的分法请问现在其中14个小朋友的钥匙能恰好打开自己的房间门其他14个小朋友不能打开自己的房间门的情况有多少钟答案直接返回一个结果数。
首先看到14个小朋友可以开自己的门那么其实这就是组合问题也就是C1428然后14个小朋友不是对应的钥匙则是一个错排问题
假设错排函数是An表示的含义是n个人都不对应自己的钥匙则现在拿出其中一个小朋友i单独讨论假设已经确定i选择了3号的钥匙那么对于3号小朋友来说如果他选择占用i的钥匙那么剩下的n-2把钥匙又就行An-2的讨论如果他不选择占用i的位置那么问题就等同于1不拿1的钥匙2不拿2的钥匙3不拿i的钥匙4不拿4的钥匙以此类推也就是An-1。
用这个推理可以知道
An C1,n-1*(An-2An-1);
那么综合起来就是C1428*A14。
现在问题来了要是我们按照组合的定义来实现C1428则一定会在算的过程中爆掉因为28的阶乘很大然后我发现在这个题不知道是不是特意设置的数边乘边除居然可以算出来了但是不建议这样去写玩意有数据改了中间会出现除不尽的结果那么组合数就会出错
最后就是把这两个算法实现了代码很简单就不打了写一个求组合数的正确写法
for(int i0;i28;i){for(int j0;ji;j){if(j0)c[i][j]1;elsec[i][j] c[i-1][j]c[i-1][j-1];}
}//c[28][14]就是组合数结果
