错位排序
发布日期:2022-02-08 04:20:48
浏览次数:4
分类:技术文章
本文共 1277 字,大约阅读时间需要 4 分钟。
错位全排列归纳:
1、常见例题:信封装错问题,抽奖问题(可以衍生概率问题)。排列出现完全错误,一个也不对等问题的的个数和出现的概率等。 2、可以转化为数学模型:已知一个长度为n的有序序列{a1,a2,a3,…,an},打乱其顺序,使得每一个元素都不在原位置上,则一共可以产生多少种新的排列? 可以先找出第一个,第二个的特例,从第三个开始递推。 3、错位排列公式:f(n) = (n-1)*(f(n-1)+f(n-2)) 公式解释:f(n)代表n个数的错位全排列,设有n个数,第n-1个数的错位全排列为f(n-1),将第n个数取出,可以放在之前的n-1个数的位子上,所以有n-1种情况,假设被替换掉的数是i,当将i放在n的位子上时,刚好形成错位,则将其余的n-2个数全排列即可,有f(n-2)种可能性,当不把i放在n的位子上时,只能够保证an放在i的位子上错位一个,所以,要将剩下的n-1个数进行错位全排列。所以递归的代码如下
int recursive(int n){ if (n==1) return 0; if (n==2) return 1; return (n-1)*(recursive(n-2)+recursive(n-1));}
省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做”考新郎”,具体的操作是这样的:
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个. 最后,揭开盖头,如果找错了对象就要当众跪搓衣板…看来做新郎也不是容易的事情…
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input 输入数据的第一行是一个整数C,表示测试实例的个数,然后是C行数据,每行包含两个整数N和M#includeusing namespace std;int main(){ long long n,m,i,sum,ch,b[21] = {0,0,1,2},sum1,sum2; int c; cin>>c; for(i=4;i<=20;i++) { b[i] = (i-1)*(b[i-1] + b[i-2]); } while(c--) { sum1 = 1; sum2 = 1; cin>>n>>m; ch = n - m; for(i=1;i<=ch;i++) { sum1 = sum1 *= n; n--; } for(i=1;i<=ch;i++) { sum2 = sum2 *= i; } cout<
转载地址:https://blog.csdn.net/weixin_38960774/article/details/79410463 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月13日 05时41分32秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
福利来袭,免费获取 Android 开发资料以及直播课程
2019-04-26
优势丧失
2019-04-26
【上市啦】“Python 之父” 力荐的蓝皮书,你知道是哪本吗?
2019-04-26
Python 爬虫面试题 170 道:2019 版
2019-04-26
歪门邪道
2019-04-26
我的前六年程序生涯
2019-04-26
知识地图
2019-04-26
罗马总会建成
2019-04-26
程序通过技术赚钱的八个途径
2019-04-26
我在爬坡阶段
2019-04-26
大疆机甲大师教育机器人Python开发:中文命名变量初尝试
2019-04-26
大疆机甲大师教育机器人Python开发:API中文化初尝试
2019-04-26
大疆机甲大师Python开发: 两只老虎
2019-04-26
大疆机甲大师教育机器人Python API中文化之一:枪亮枪暗
2019-04-26
大疆机甲大师教育机器人Python API中文化之二:LED闪烁
2019-04-26
大疆 RoboMaster 机甲大师官方刚刚开通”机甲小 S 实验室”知乎专栏
2019-04-26
大疆机甲大师教育机器人Python API中文化之三:底盘灯效
2019-04-26
大疆机甲大师教育机器人Python API中文化之四五:云台灯效,指定序号
2019-04-26
大疆机甲大师教育机器人Python API中文化之六:关灯
2021-06-29
“中文编程”知乎专栏两岁了——山雨欲来风满楼
2021-06-29