算法竞赛中的组合数问题计算入门经典
计算组合数
编写函数,参数是两个非负整数n和m,返回组合数
其中m<=n<=25。例如,n=25,m=12时的答案为5200300。
代码及算法分析
程序4-1 组合数(有问题)
#include <stdio.h>
long long factorial(int n)
{
long long m=1;
//不要忘记初始化,不然的出来的结果惊人。
for(int i=1;i<=n;i++)
{
m*=i;
}
return m;
}
int main ()
{
int n,m;
scanf("%d %d",&n,&m);
printf("%lld",factorial(n)/(factorial(m)*factorial(n-m)));
return 0;
}
这个代码的问题显而易见,阶乘容易溢出,所以不可取。
所以,套用刘汝佳老师的一句话:”即使最终答案在所选择的数据类型范围之内,计算的中间结果仍然可能溢出“。
汝佳老师也给出了相应的解决方案,虽然不能完全避免中间结果溢出,但是对于题目给出的范围已经可以保证得到正确的结果了。
先来分析一下组合数的公式:
n!
————
m!(n-m)!
展开之后:
n *(n-1) *(n-2)……3 *2 *1
—————————————————————————————(1)
m *(m-1) *(m-2)……3 *2 *1 *(n-m) *(n-m-1) *(n-m-2)…… *3 *2 *1
因为n>=m,所以m在1~n之间,这样可以把n!除以m!约分:
n *(n-1) *(n-2)……(m+2) *(m+1)
————————————————(2)
(n-m) *(n-m-1) *(n-m-2)…… *3 *2 *1
然后汝佳老师给了一道思考题:为什么当m<n-m时要把m变成n-m?
移项之后得到:m<n/2,先列一个数轴:
|————————————————————>
0 1 2 3 ……m……n/2……M……(n-1) n
为了不把变换后的m与变换前的m弄混,把变化后的m记为M。因为组合数的公式,分子是大于分母的,所以分子的乘积比较大,容易溢出,要想优化,就得让分子乘积变小。
M=n-m带入组合式公式之后就是:
n!
————————————————(3)
M!(n-M)!=(n-m)!(n-(n-m))!=(n-m)!m!
所以式子并没有变化,同样可以进行约分得到(2)式的变式:
n *(n-1) *(n-2)……(M+2) *(M+1)
————————————————(4)
(n-M) *(n-M-1) *(n-M-2)…… *3 *2 *1
相当于将数轴
|————————————————————>
0 1 2 3 ……m ……n/2……M ……(n-1) n
标出的部分直接干掉了。
由于M是大于m的,所以分子的乘积缩小,溢出问题得到缓解,注意,是缓解不是解决,如果n和m的值很大的话还是会溢出。
分析之后就可以把程序4-1升级为程序4-2了:
#include <stdio.h>
long long c(int n,int m)
{
if(m<n-m)
{
m=n-m;
}
long long ans=1;
for(int i=m+1;i<=n;i++)
{
ans*=i;
}
for(int i=1;i<=n-m;i++)
{
ans/=i;
}
return ans;
}
int main ()
{
int n,m;
scanf("%d %d",&n,&m);
printf("%lld",c(n,m));
return 0;
}
汝佳老师提示
“对复杂的表达式进行化简有时不仅能减少计算量,还能减少甚至避免中间结果的溢出。”
上一篇: C++ 组合实施
推荐阅读
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
算法竞赛中的组合数问题计算入门经典
-
动态规划算法的两种经典解决方式:最优子结构和DP数组的使用解析-动态规划算法问题 什么叫作最优子结构? 和动态规划有什么关系? 为什么动态规划遍历DP数组的方式有正着遍历,有倒着遍历,有斜着遍历? 最优子结构 最优子结构是某些问题的一种特定的性质,并不是动态规划问题所特有的. 很多问题都具有最优子结构,但是其中大部分不具有重叠子问题,所以不会归为动态规划系列的问题 最优子结构: 可以从子问题的最优结果推导出更大规模问题的最优结果 子问题之间必须相互独立 通过改造问题来优化由于子问题之间不独立而导致的最优子结构失效的情况: 问题: 假设学校有10个班,已知每个班的最高分与最低分差值的最大分数差,需要计算全校学生中的最大分数差 分析: 这样的问题就无法通过这10个班的最大分数差来推导出来,因为这10个班的最大分数差不一定就包含全校学生的最大分数差.比如全校的最大分数差可能是由8班的最高分和6班的最低分的分数差而得.这样就导致子问题之间不是互相独立的 改造问题: 直接进行问题改造 int result = 0; for (Student a : school) { for (Student b : school) { if (a is b) { continue; } result = max(result, |a.score - b.score|) } } return result; 改造问题就是将问题等价转化: 最大分数差就等价于最高分数与最低分数的差 那么就是要求最高和最低分数 求最高分数是具备最优子结构的,求最低分数也是具有最优子结构的 这样就样一个不具备最优子结构的问题转化为具备最优子结构的子问题 借助最优子结构解决最值问题,再解决最大分数差问题 题目: 求一棵二叉树的最大值,假设节点中的值都为非负数 int maxVal(TreeNode root) { if (root == null) { return -1; } int left = maxVal(root.left); int right = maxVal(root.right); return max(root.val, left, right); }