传球法解计数问题

接力传球题目
题目：接力传球
n个小朋友在玩传球。

小朋友们用1到n的正整数编号。

每个小朋友有一个固定的传球对象，第i个小朋友在接到球后会将球传给第ai个小朋友，并且第i个小朋友与第ai个小朋友之间的距离为di。

一次传球接力是这样进行的：由一个小朋友发球，将球传给他的传球对象，之后接到球的小朋友再将球传给自己的传球对象，如此传球若干次后停止。

期间，包括发球者在内，每个小朋友至多只能拿到球一次。

一次传球接力的总距离是每次传球的距离的总和。

小朋友们想进行一次总距离最长的传球接力，现在需要你帮助他们求出满足上述要求的传球接力的最长总距离。

输入：
输入的第1行包含1个整数n。

接下来的n行，第i行包含两个整数ai和di，意义如题目中所述，两个数间用一个空格隔开。

输出：
输出包含1个数，表示传球接力总距离的最大值。

示例：
输入：
3
1 2
2 3
3 1
输出：
5
解释：
在这个例子中，我们有3个小朋友，编号为1，2和3。

小朋友1的传球对象是2，距离为2；小朋友2的传球对象是3，距离为3；小朋友3的传球对象是1，距离为1。

最长的传球接力路径是1 -> 2 -> 3 -> 1，总距离为2+3+1=6。

因此，答案是6。

传球法公式好的，以下是为您生成的关于“传球法公式”的文章：咱今天就来聊聊这个听起来有点神秘的“传球法公式”。

还记得我上高中那会，我们班有个特别痴迷数学的同学小李。

有一次数学课上，老师讲到了传球法公式，小李那叫一个兴奋，眼睛瞪得圆圆的，手里的笔不停地在本子上比划着。

这传球法公式啊，在数学里可是个有趣的家伙。

它主要是用来解决一些关于物品或者信息传递的问题。

比如说，有几个小伙伴站成一圈传球，经过一定的次数后，想知道球在谁手里，这时候传球法公式就派上用场啦。

举个简单的例子，假设 A、B、C 三个人围成一圈传球，从 A 开始传，每次只能传给相邻的人。

经过 5 次传球后，球在谁手里呢？这时候我们就可以用传球法公式来算一算。

传球法公式的核心思路就是通过建立数学模型，把复杂的传球过程转化为可以计算的数学式子。

它可不是那种让人一看就头疼的复杂公式，其实只要理解了其中的逻辑，还是挺简单易懂的。

咱们再回到刚才说的小李。

下课后，小李还拉着我，非要给我再讲讲这个公式。

他在黑板上画了好多图，边画边解释：“你看啊，如果有n 个人传球，传了 m 次，那么第 m 次传球后球在第 k 个人手里的情况，就可以通过特定的计算得出。

”我当时听得云里雾里的，心里想这小李也太较真了。

不过后来做作业的时候，我发现还真用上了这个传球法公式。

有一道题是这样的：五个同学围成一圈传球，经过 8 次传球，球回到最初发球同学的手里，问有多少种不同的传球方式？我一开始有点懵，但是静下心来，按照传球法公式一步步算，嘿，还真给算出来了。

随着学习的深入，我发现传球法公式不仅仅能解决这种简单的传球问题。

比如在一些复杂的网络信息传递中，它也能发挥作用。

就像我们在互联网上分享消息，从一个人传到另一个人，经过多次传播后，想要知道消息的传播路径和最终的覆盖范围，都可以借助传球法公式的思路来分析。

总之啊，这传球法公式虽然不是那种天天能用到的，但一旦遇到相关的问题，它可就是我们的解题神器。

传球问题的探究性学习一问题背景三人相互传球，由甲开始发球，并作为第一次传球，经过5次传球后，球仍回到甲手中，则不同的传球方法的种数是（）(A) 6 （B） 8 （C）10 （D）16本题主要考查排列组合中的计数问题，当时我校学生的得分情况并不理想：笔者所任教班级为实验班（学生的成绩普遍较好），但是选择正确答案（C）的仅为30%，其余选项基本平均！进一步调查发现，大多数同学没有明确的解题思路：有的根本就不理解题意；有的只会使用列举法进行直观列举，但不能按一定顺序将所有情况一一穷尽，有遗漏现象；选（C）的同学中也有是蒙对的，其实并不真正理解题意；绝大多数同学没有转化问题的意识，不能通过联想已经解决的熟悉问题来建立数学模型求解，表现出抽象思维的贫乏与薄弱。

事实上，对这种似乎是非常规性的问题，往往难以用常规题型的通常解法去顺利解答；我们有些老师做起来也不容易尽快找到切入点，评讲时就难以点拨到位.我感觉这是一道极具思维训练价值的好题，值得深入研究，于是组织学生进行研究性学习。

二分组讨论多向求解师（简要介绍做题情况与试题特点后）这真是一道难题吗？同学们能用所学过的相关知识与方法来求解吗？（留给学生充分独立思考、探索和自由交流讨论的时空）将学生讨论的结果归类如下：1．将传球路线一一列举，进行直观求解：生1 考虑传球次数不多，可用枚举法画出详细树状图（图1），甲先传球给乙（上面的一条道路）到最后回到甲手中，共有五种传球方法；同理甲先传球给丙，由对称性可知也有五种传球方法；故共有10种传球方法.生2 由于球开始和结束都在甲手中，因此球第一次传出后及最后一次传出前必须不在甲手中，不妨把乙、丙统称为“非”（意为非甲），故只要确定中间几次传球的情况即可.传球线路如图2，图中“→”表示传球方向，“→”之上所附数字表示对应于此步的传球方法数.所以，本题传球的不同方法数是11212⨯⨯⨯⨯+11112⨯⨯⨯⨯+12112⨯⨯⨯⨯=10.2．与已有知识结构联系，广泛联想与想象，进行发散思维，建模求解：生3 联想到2003年新课程卷文科高考试题第16题：将3种作物种植在并排的5块试验田里，每块种植一种作物且相邻的试验田不能种植同一作物，不同的种植方法共有种.可以将本题进行等价转化为涂色模型：相当于给图3六个方格涂红、黄、蓝三种颜色，要求第1、6两格涂红色，每个方格涂一种颜色，并且相邻的两个方格针对红色还可涂在（1）若22A种方法，而两色之一，有1A种方法，由乘法原理知有2A12A=4种方法；（2）若4种方法；（3则只能在选涂一种颜色，在有22A种方法；综上，共有222A12A+22A=2⨯4+2=10种方法.生4 改变问题的叙述形式，就成为很熟悉的排数模型：用1、2、3三个数字排成6位整数，要求首位和末位排1，且任意相邻的两个数码不甲非12甲甲甲非非非非22111111图2甲乙…丙甲甲甲丙乙乙丙丙乙乙丙图1丙3 431 2 5 6相同，可以得到多少个不同的6位整数？（解略）三 进一步探究师 上述4位同学的4种解法都具有一定的代表性，如何将问题及其解答向一般情况推广，来进一步揭示问题的规律，认识问题的本质呢？生5 将此问题向一般情况引申，有推广 1 甲乙丙三个人相互传球，由甲开始发球，并作为第一次传球，经过n 次传球后，球又回到甲手中，则不同的传球方法有多少种？问题一经引向一般，上述4种具体解法就难以完全套用！但是可以受其方法的启发----引导学生发现问题背后的规律：生6 设经过n 次传球后，球在甲手中的不同方法有n a 种，球不在甲手中的不同方法有n b 种，则有：①01=a ，经过n 次传球后共有n2种不同的传球方法；②经过n 次传球后球要么在甲手中，要么不在，可得n 2=n a +n b ；③第1-n 次传球后，球在甲手中，则下一次必不在甲手中（甲传出去有两种可能）；第1-n 次传球后，球不在甲手中，则下一次可以传到甲手中（乙可以传给甲或丙，丙可以传给甲或乙，各有两种可能）；④经过n 次传球后，球在甲手中有n a 种方法，等于第1-n 次传球后球不在甲手中的方法数1-n b ，即n a =1-n b ，且1112---=+n n n b a .所以112---=n n n a a （i ）。

计数问题·排列组合试题与解答1.【题目】从1～2004这2004个自然数中，共有多少个数与四位数8866相加时，至少发生一次进位。

【解答】这个题如果顺向思考，就特别复杂，我们逆向思考，把不能进位的个数找出来，我们再从2004个数中减少这么多个，就是满足条件的了。

8866加一个数，如果不发生进位，千位上只能是0和1，百位上也只能是0和1，十位上只能是0～3，个位也是0～3，所有不进位的情况共有2×2×4×4－1＝63种，为什么减去1呢，因为四位数字都选0时的0000这个数不存在。

所以至少发生一次进位的数有2004－63＝1941个数。

2.【题目】五位同学扮成奥运会吉祥物福娃贝贝、晶晶、欢欢、迎迎和妮妮，排成一排表演节目。

如果贝贝和妮妮不相邻，共有多少种不同的排法。

【解答】这个题的基本思想是从总的排列中去掉相邻的排列就行了。

五个同学共有5×4×3×2×1＝120种排法其中两人相邻的共有4×3×2×1＝24种排法则其中两人不相邻的排法共有120－24＝96种。

3.【题目】甲乙丙丁四个同学排成一排，从左到右数，如果甲不排第一个位置上，乙不排第二个位置上，丙不排第三个位置上，丁不排第四个位置上，那么不同的排法共有多少种？【解答】此题方法很多，谈谈分类讨论。

甲不排第一个位置，则第一个位置可以是乙、丙、丁当乙排第一个位置时有以下3种排法：乙甲丁丙，乙丙丁甲，乙丁甲丙当丙和丁排第一个位置时同样分别有3种排法，因此共有3×3＝9种不同的排法。

4.【题目】高速公路入口处的收费站有1号、2号、3号、4号共四个收费窗口，有A、B、C三辆轿车要通过收费窗口购票进入高速公路。

那么三辆轿车共有多少种不同的购票次序？【解答】A轿车进入高速公路时，有4种情况；B轿车进入时，除了每个入口有一种外，和A同进一个入口时，有在A 前和A后两种情况，因此B轿车进入时，对应有5种情况；C轿车进入时，分成两类来分析：如果A和B分别从不同的入口进入的，则C进入时，可以从两个入口和A前A后，B前B后，共6种进入方式。