博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
插板法
阅读量:5218 次
发布时间:2019-06-14

本文共 1053 字,大约阅读时间需要 3 分钟。

(文章原出处)

三道题,诠释“插板法”精髓。(核心是可以将求n个数和为m的方案数转化为m+n个物体分成n堆,每堆至少一个的问题,从而使用插板法)

【1】、10个相同的糖果,分给3个孩子A、B、C,每个孩子至少一个,有多少种不同的分法?

【2】、10个相同的糖果,分给3个孩子A、B、C,有多少种不同的分法?

【3】、10个相同的糖果,分给3个孩子A、B、C,每个孩子至少2个,有多少种不同的分法?

【4】、10个相同的糖果,分给3个孩子A、B、C,A至少一个,B至少2个,C可以没有,有多少种不同的分法?

======先思考再看答案哦=========

【答案在此】

插板法的应用主要在于,相同元素,非空分组。

通俗点讲就是一些相同的东西,进行分组,每组至少为1个的情况。

【1】、10个糖果9个空,分成三组插两块板,第一块板有9中插法,第二块板有8种插法,第一第二块板没有顺序要求,所以共有9×8÷(2×1)=36(种)分法。

【2】、与第一题不同,这里没有限制孩子获得的数量,意味着有些孩子可以分到0个。那么这时候就不能直接用插板法了,必须转化成每个孩子至少得到1个。怎么转化呢?

很简单,分这10个糖果之前就给每个小朋友1个糖果,这样就保证分的时候每个小朋友至少分一个了,就可以用插板法了,只不过这时的题就变成了“10+3=13个相同的糖果,分给3个孩子A、B、C,每个孩子至少一个,有多少种不同的分法?”.

13个糖果12个空,分成三组插两块板,第一块板有12中插法,第二块板有11种插法,第一第二块板没有顺序要求,所以共有12×11÷(2×1)=66(种)分法。

【3】.不能直接插板,将至少三个转化成至少一个,咋转化?先给每人1个,剩下的至少没人一个就搞定啦!题目变为“10-1×3=7个相同的糖果,分给3个孩子A、B、C,每个孩子至少一个,有多少种不同的分法?”

7个糖果6个空,分成三组插两块板,第一块板有6中插法,第二块板有5种插法,第一第二块板没有顺序要求,所以共有6×5÷(2×1)=15(种)分法。

【4】、此题综合了这几类题型,还是转化:A满足不用管;B至少2个,需要先分掉1个;C可以不分,那就借一个给他。 10-1+1=10,题目变成第一小题了,答案还是36.

【练一题】一个三位数,各位数字均不为0,且数字和是9,请问这样的数有多少个?(可以为0又怎样?)

 

转载于:https://www.cnblogs.com/MekakuCityActor/p/8611427.html

你可能感兴趣的文章
PAT B1018.锤子剪刀布(20)
查看>>
Extjs控件之 grid打印功能
查看>>
枚举类型(不常用)递归
查看>>
ETL
查看>>
Tomcat源码分析(六)--日志记录器和国际化
查看>>
minggw 安装
查看>>
Jquery操作cookie,实现简单的记住用户名的操作
查看>>
[BZOJ1196][HNOI2006]公路修建问题 二分答案+最小生成树
查看>>
PHP基础入门(二)
查看>>
[Luogu P3119] [USACO15JAN]草鉴定Grass Cownoisseur (缩点+图上DP)
查看>>
【原创】大数据基础之Zookeeper(4)应用场景
查看>>
18款在线代码片段测试工具
查看>>
20.C++- &&,||逻辑重载操作符的缺陷、,逗号重载操作符的分析
查看>>
静态变量数组实现LRU算法
查看>>
在SQL中怎么把一列字符串拆分为多列
查看>>
中文系统 上传file的input显示英文
查看>>
css样式写一个三角形
查看>>
比callback更简洁的链式执行promise
查看>>
android permission
查看>>
【译】在Asp.Net中操作PDF - iTextSharp - 使用字体
查看>>