广州建设六马路小学网站,o2o网站建设计划书,海南中小企业网站建设,HTMT超链接网站怎么做目录
一、前言
二、计数原理
1、加法原理
2、分割立方体#xff08;lanqiaoOJ题号1620#xff09;
3、乘法原理
4、挑选子串#xff08;lanqiaoOJ题号1621#xff09;
5、糊涂人寄信#xff08;lanqiaoOJ题号1622#xff09;
6、战斗吧N皇后#xff08;lanqiaoO…目录
一、前言
二、计数原理
1、加法原理
2、分割立方体lanqiaoOJ题号1620
3、乘法原理
4、挑选子串lanqiaoOJ题号1621
5、糊涂人寄信lanqiaoOJ题号1622
6、战斗吧N皇后lanqiaoOJ题号1623
三、鸽巢原理
1、鸽巢原理概念
2、小蓝吃糖果lanqiaoOJ题号1624
四、二项式定理与杨辉三角
1、概念
2、杨辉三角形2021年省赛lanqiaoOJ题号1457 一、前言
本文主要讲了计数原理、鸽巢原理、杨辉三角的概念与相关编程题。
二、计数原理
1、加法原理 加法原理集合 S 被分成两两不相交的部分 S1、S2、S3、..、Sm那么 S 的对象数目等于|S| |S1| |S2| |S3| ... |Sml例一个学生想学一门数学课一门文化课但不能同时选现在从 4 门数学课和 4 门文化课中选一共有 448 种方法选一门课。加法原理的关键是将计数分解为若干个独立不相容的部分保证既不重复也不遗漏地进行计数。2、分割立方体lanqiaoOJ题号1620 【题目描述】 一个立方体边长为 n分割成 n×n×n 个单位立方体。任意两个单位立方体或者有 2 个公共点或者有 4 个公共点或者没有公共点。请问没有公共点和有 2 个公共点的立方体共有多少对 【输入描述】 一个整数n 1n30 【思路】 反过来计算先算出有 4 个公共点的立方体有多少对然后用总对数减去。分几种情况讨论 1) 正方体和周围 3 个正方体相邻这种情况共有 8 个就是顶角上的 8 个总个数 3×8 2) 正方体和周围 4 个正方体相邻这种情况共有 (n-2)×12 个总个数 4×(n-2)×12 3) 正方体和周围 5 个正方体相邻这种情况共有 6×(n×n-4×n4) 个总个数 5×6×(n×n-4×n4) 4) 正方体和周围 6 个正方体相邻这种情况共有 (n×n×n-n×n×6n×12-8) 个总个数 6×(n×n×n-n×n×6n×12-8) 最后把这 4 个情况求和再除以 2。 正方体一共 n^3 个共有 n^3(n^3-1)/2 种关系。 nint(input())
if n1:print(0) #边长为1时特判
else:sumn*n*n*(n*n*n-1)//2 #总数edge38ans33*edge3edge4(n-2)*12ans44*edge4edge5n*n-4*n4ans55*6*edge5edge6n*n*n-n*n*6n*12-8ans66*edge6print(sum-(ans3ans4ans5ans6)//2)3、乘法原理 令 S 是对象的有序对 (a,b) 的集合其中第一个对象 a 来自大小为 p 的一个集合对于对象 a 的每个选择对象 b 有 q 个选择那么 S 的大小ISI-p×q例中性笔的长度有 3 种颜色有 4 种直径有 5 种。不同种类的中性笔有3×4×560 种。例3^4×5^5×7^2×11^3的正整数因子有多少? 答: 这是算数基本定理的概念。3 有 0-4 这 5 种选择5 有 6 个选择7 有 3 个选择11 有 4 个选择因子总数是 5×6×3×4360 种。【排列数】 排列是有序的。 不可重复排列数从 n 个不同的物品中取出 r 个排列数为P(n, r) n(n- 1)(n - 2)...(n-r1) n!/(n-r)!可重复排列数从 n 个不同的物品中可重复地取出 r 个的排列数为n^r【组合数】 排列是有序的组合是无序的。如果 S 中的元素都不相同组合数 4、挑选子串lanqiaoOJ题号1621 【题目描述】 有 n 个数和一个整数 n。从这 n 个数选出一个连续子串要求这个子串里面有 k 个数要大于等于 m。问一共能选出多少个子串。显然子串个数要大于等于 k 个。 【输入描述】 第一行是 3 个整数 n、m、k。第二行是 n 个整数 a1、a2、...、an表示序列。2n2000001kn/21m, ai10^9 【输出描述】 输出一个整数表示答案。 【思路】 一个个地输入 ai直到输入的数字里大于 m 的数够 k 个就可以开始统计了。 1若正好到 k 个数情况总数是第一个大于 m 的位置 i(之前)乘以 i(当前) 以后的个数相当于求出了这一段区间的总个数。 2大于 k 个后怎么求出以后的序列个数而且保证不重复呢从前往后推理用倒数第二个位置-倒数第一个位置的差乘上后面的个数。这句话需要自己琢磨一下讲得并不清晰最好能举一个具体的例子来说明一下 n,m,kmap(int,input().split())
a[0]list(map(int,input().split()))
sum0
d[0]*(n1)
t0
for i in range(n1):if a[i]m:t1d[t]i #d[]: 比m大的数字所在位置。这里的没有任何意义python并无自增和自减if tk: #首先统计出k个比m大的if tk:sumd[1]*(n-i1)else:sum(d[t-k1]-d[t-k])*(n-i1)
print(sum)5、糊涂人寄信lanqiaoOJ题号1622 【题目描述】 有一个糊涂人写了 n 封信和 n 个信封到了邮寄的时候把所有的信都装错了信封。求装错信封可能的种类数。 【输入描述】 每行输入一个正整数 n表示一种情况。(n20) 【输出描述】 输出相应的答案。 【思路】 题目建模为有 1~n 个数字分别放在 n 个位置问都放错的情况有多少种。 用 DP 来做定义 dp[]dp[i] 表示数字 1~i 都放错的种类数。dp[n] 是答案。 下面考虑状态转移方程从 1~i 递推到 i。 数字 i 如果放错有 i-1 个位置可以放假设其放在第 k 个位置。对于数字 k可以放在 i 位置也可以不放在 i 位置。 如果 k 放在 i 位置那么对于剩下 i-2 个数字放的次数就是 i-2 个数字都放错的方法数 dp[i-2]。 如果 k 不放在 i 位置和 i-1 个数字放错的情况相同为 dp[i-1]。 状态转移方程dp[i] (i-1)*(dp[i-1]dp[i-2]) 注意本题的输入没有明确终止第 6 行处理了这种情况。import sys
def f(n):if n0 or n1:return 0elif n2:return 1else:return (n-1)*(f(n-1)f(n-2))
for n in sys.stdin: #读入n,和C代码的while(cinn)功能一样nint(n)print(f(n))6、战斗吧N皇后lanqiaoOJ题号1623 【题目描述】 在一个 N*M 的棋盘中存在多少种方式使得两个皇后可以互相攻击。 【输入】 输入有若干行每行两个数 NM (1NM106) 【输出】 对于每组测试数据输出一行表示答案 【思路】 两个皇后如果能攻击位于同一行、同一列、同一对角线。 设矩阵为 n*m前 2 者的可能性是 (mn-2)*n*m。同一行n*m*(m-1)同一列m*n*(n-1) 其他情况请自己思考。对角线情况 注意本题的输入没有明确终止且每行读取 2 个数。第 2~4 行处理了这种输入的情况。
import sys
for line in sys.stdin: #读多个数和C的while(cinnm)功能一样nint(line.split()[0])mint(line.split()[1])if nm:n,mm,nif n1:print(m*(m-1))continueansm*n*(mn-2)ans2*(n-2)*(n-1)*(2*n-3)//3ans2*(m-n1)*n*(n-1)print(ans)三、鸽巢原理
1、鸽巢原理概念 鸽巢原理又称抽屉原理。 鸽巢原理把 n1 个物体放进 n 个盒子至少有一个盒子包含 2 个或更多的物体。 例在370人中至少有2人生日相同 答把365天看成365个抽屉。把365人放进365个抽屉不管怎么放抽屉里面都有人了。 例n个人互相握手一定有2个人握手次数相同 答每人跟其他人握手最少可以是 0 次最多可以是 n-1 次。 如果握手最少的是 0 次那么剩下的 n-1 人中握手最多的人不会超过 n-2 次。0~n-2 共 n-1 种情况。 如果握手最少的张三是 1 次那么剩下的 n-1 人中握手最多的李四除了跟张三握手一次跟其他 n-2 人最多握手 n-2 次李四最多握手 n-1 次。1~n-1 共 n-1 种情况。 如果握手最少的张三是 2 次那么剩下的 n-1 人中握手最多的李四除了跟张三握手一次跟其他 n-2 人最多握手 n-2 次李四最多握手 n-1 次。 2~n-1 共 n-2 种情况。 所以握手次数最多有 n-1 种情况最少只有 1 种情况。 把最多的 n-1 种情况看成 n-1 个抽屉n 个人放进这 n-1 个抽屉至少有一个抽屉里面有 2 人。 2、小蓝吃糖果lanqiaoOJ题号1624 【题目描述】 Gardon有 n 种糖果每种数量已知。Gardon 不喜欢连续 2 次吃同样的糖果。问有没有可行的吃糖方案。 【输入】 第一行是整数 NOn1000000第二行是 n 个数表示 n 种糖果的数量 mi0mi1000000 【输出】 输出一行包含一个 Yes 或 no。 【思路】 鸽巢原理用 “隔板法” 求解。 找出最多的一种糖果把它的数量 K 看成 K 个隔板隔成 K 个空间把每个隔板的右边看成一个空间其它所有糖果的数量为 S。 最多的一种糖果把它的数量 K 看成 K 个隔板隔成 K 个空间 (把每个隔板的右边看成一个空间)其它所有糖果的数量为 S。 1如果 SK-1把 S 个糖果放到隔板之间这 K 个隔板不够放必然至少有 2 个隔板之间没有糖果由于这 2 个隔板是同一种糖果所以无解。 2SK-1时肯定有解。其中一个解是把 S 个糖果排成一个长队其中同种类的糖果是挨在一起的然后每次取 K 个糖果按顺序一个一个地放进 K 个空间。由于隔板数量比每一种糖果的数量都多所以不可能有 2 个同样的糖果被放进一个空间里。把 S 个糖果放完就是一个解一些隔板里面可能放好几种糖果。 nint(input())
alist(map(int,input().split()))
if sum(a)-max(a)max(a)-1:print(No)
else:print(Yes)
四、二项式定理与杨辉三角
1、概念 杨辉三角排列成如下三角形的数字 每个数是它上面 2 个数的和。 求杨辉三角第 n 行的数字可以模拟这个推导过程逐级递推复杂度 O(n^2)。用数学公式计算可以直接得到结果这个公式是 (1 x)^n。 二项式系数就是 (1x)^n 展开后第 r 项的系数。 理解(1x)^n 的第 r 项就是从 n 个 x 中选出 r 个这就是组合数的定义 当 n 较大且需要取模时二项式系数有两种计算方法 1递推公式 公式是杨辉三角的定义即 “每个数是它上面 2 个数的和” 。计算复杂度是 O(n^2)。 2用逆直接计算因为输出取模那么不用递推公式直接用公式计算更快。不过由于除法不能直接取模需要用到逆。用逆计算二项式系数有 用逆计算二项式系数复杂度是 O(n) 的。 2、杨辉三角形2021年省赛lanqiaoOJ题号1457 【题目描述】 如果我们按从上到下、从左到右的顺序把杨辉三角形的所有数排成一列可以得到如下数列1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...。给定一个正整数 N请你输出数列中第一次出现 N 是在第几个数 【输入描述】 输入一个整数 N。 N1000000000 【输出描述】 输出一个整数表示答案。 直接计算杨辉三角的每个数然后推导出 N 的位置。上一行的 2 个数相加得下一行的一个数。例如上一行是 b[0]~b[k]下一行是 a[0]~a[k1]那么 a[i] b[i-1] b[i]。推算过程只用一个数组完成和 DP 的自我滚动数组的原理一样即 a[i] a[i-1] a[i]def f():nint(input())a[0]*100050sum0 #sum等于1~line行的数字个数line0sum,a[0]1,1if n1:print(1)returnfor line in range(1,50000): #line: 杨辉三角的第line行for i in range(line,0,-1): #倒过来循环和DP的自我滚动数组的原理一样a[i]a[i-1]a[i] #上一行的2个数相加得下一行的一个数if a[i]n:print(sumline-i1)returnsum(line1) #1~line行的数字个数。每行比上一行多一个累加
f()以上组合数学原理与例题
祝好
