包含排斥原理.doc

1、包含排斥原理(1)某系的100名学生中,《离散数学》的选修学生有50人,《数据库原理》54人,同时选修这三门课有7人,同时选修《离散数学》与《计算理论基础》有20人,同时选修《计算理论基础》与《数据库原理》有10人,同时选修《离散数学》与《数据库原理》有21人,每个学生至少选修这三门课中的某一门,请先写出3个集合的基于包含排斥原理的计算方法,再计算《计算理论基础》的选修学生是多少?只选一门课的学生是多少?(2)某学院对本年度200名学生进行调查发现:67人选修程序设计,47选修了中国文学欣赏,有95人选修股票投资,有26人同时选修了程序设计与中国文学欣赏,有28人同时选修了中国文学与股票投资,有27选修了程序设计与股票投资,有50人没有选修这三门课,请先出包含排斥原理,再利用此原理计算出同时选修了这三门课的人数,并画出其文氏图,在其中填入各部分的数字以验证。(3)求1到1000之间不能同时被3,5,8整除数的个数,并画出其文氏图,在其中填入各部分的数字以验证。(4)写出包含排斥原理,并求1-160之间素数的个数。(5)请写出包含排斥原理,并求20-160之间素数的个数。(6)请写出包含排斥原理,请计算50-500之间素数的个数。(7)请计算1-500之间能被3或5或7整除的整数的个数。(8)请计算20-400之间能被3或5或7整除的整数的个数。(9)计算[100,1000]中,能被3或5或7或11整除的整数的个数。(10)计算50-500之间能被3或5或7整除的整数的个数。(11)计算1-400之间能被2或3或5或9整除的数个数;(12)计算[1000]中,不能被2整除,也不能不能被3整除,也不能被5整除的整数的个数。2、等价关系(1)设集合A={1,2,3,4,5},关系R={<1,1>,<1,3>,<2,3>,<2,5>,<3,3>,<4,5>,<5,1>},利用关系矩阵求出其自反闭包、对称闭包、可传递闭包。(2)设集合A={a,b,c,d,e},关系R={<c,c>,<a,c>,<b,c>,<e,a>,<b,b>,<d,e>,<e,b>},利用关系矩阵求出其自反闭包、对称闭包、可传递闭包。(3)设集合A={1,2,3,4,5,6},R={<1,6>,<1,5>,<5,2>,<4,5>,<3,1>,<3,3>},利用warshall算法求其传递闭包,并且画出其关系图,用虚线标出求t(R)过程中所加入的新序偶。(4)写出求传递闭包的warshall算法,某关系的序偶为R={<1,2>,<1,4>,<2,1>,<2,3>,<3,4>,<3,5>,<4,1>,<4,3>,<5,4>,<5,2>},求传递闭包与对称递包,必须给出步骤,再用t(R)=RÈR2È...Rn求传递闭包(5)写出求传递闭包的warshall算法,某关系的序偶为R={<a,b>,<a,d>,<a,c>,<b,a>,<b,c>,<c,d>,<b,e>,<d,a>,<d,b>,<e,c>,<e,a>,<e,c>},求此关系的传递闭包与对称递包,必须给出计算步骤,最后再用t(R)=RÈR2È...ÈRn求传递闭包(6)写出求传递闭包的warshall算法,某关系的序偶为R={<1,2>,<1,4>,<1,5>,<2,1>,<2,3>,<3,4>,<3,5>,<4,1>,<4,3>,<