欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法题解之容斥原理

程序员文章站 2024-02-11 13:24:22
...

        我们有时候在解题的时候,将问题分成几个子问题,然后叠加,但是答案中有重复解,也就是这些子问题相互具有重叠的部分,如果不分成子问题那么无疑会使解题过程变得更加麻烦。这时候容斥原理可以帮助解决这一难题。容斥原理就是先将子集问题的解相加,然后减去重复的解,再加上减的过程中重复减的部分,依次递推。

1.何谓容斥原理

 在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。
        如果被计数的事物有A、B、C三类,那么,A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数-既是A类又是C类的元素个数-既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。(A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C)。因为当A+B+C之后,相当于把A和B的公共部分加了两次,所以需要减去,同理也将B和C的公共部分加了两次,A和C的公共部分加了两次,所以需要减去。但是在减的过程中多减了ABC的公共部分,所以需要加上,从而得到最终解。
        根据以上推理,将公式推导到一般化,公式如下:
                       算法题解之容斥原理

        

2.例题讲解

   2、3、5、7的倍数
                                                                算法题解之容斥原理
        题目大致意思是求求1-N中有多少个不是2或3或5或7的倍数。我们可以先解其反命题,即有多少个是2或3或5或7的倍数,最后用N相减即可。
        根据容斥原理:首先,我们先将问题转化为四个子命题,即2的倍数、3的倍数、5的倍数和7的倍数四个子命题,各自的结果就是N/2、N/3、N/5、N/7。但是2的倍数和3的倍数这两个解有重复的部分,那就是减去其两者相乘得到的数的倍数即可,同理其它任意两个数同理;然后加上任意三个乘积的倍数;接着减去四个数乘积的倍数即可。最后再用N减去前面求到的结果。
代码如下:
import java.util.*;
public class Main {
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int total=(n/2+n/3+n/5+n/7)-(n/6+n/10+n/14+n/15+n/21+n/35)+(n/30+n/42+n/70+n/105)-n/210;
		int ans=n-total;
		System.out.println(ans);
	}

}





相关标签: 容斥原理