【问题】传球问题
有a,b,c,d,四个人
互相传球
从a开始传出
经过5次传球后
球回到a的手里
算总共有多少种传球的方法
关注CoolShell微信公众账号和微信小程序
（转载本站文章请注明作者和出处 酷 壳 – CoolShell ，请勿用于任何商业用途）
——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
(9 人打了分，平均分： 3.22 )
Loading... (9 人打了分，平均分： 3.22 )Loading... (9 人打了分，平均分： 3.22 )Loading...
《【问题】传球问题》的相关评论
60吧？（3×3×3×3-（3×3+3×2×2））
60?
60 （星号代表b or c or d）
a -* -* -* -* -a 3*2*2*2 = 24
a -* -a -* -* -a 3*3*2 = 18
a -* -* -a -* -a 3*2*3 = 18
60
def chuanqiu(current,remain):
if remain==0:
if current==’A’:
return 1
else:
return 0
else:
return sum(chuanqiu(next,remain-1) for next in [‘A’,’B’,’C’,’D’] if next != current)
>>> chuanqiu(‘A’,5)
60
>>>
问题等价于经过4次传球后不在a手里, 总共有多少种传球的方法.
//将上面的Python用C再写了一遍
#include
int cb(char cu, int t)
{
char s[4] = {‘a’,’b’,’c’,’d’};
if (t == 0) {
if (cu == ‘a’)
return 1;
else
return 0;
}
else {
int co = 0;
char ccuu;
for (int i=0;i<4;i++) {
ccuu = s[i];
if(ccuu != cu)
co += cb(ccuu, t-1);
}
return co;
}
}
int main()
{
for(int i=1; i<10; i++){
printf("%d\n",cb('a',i));
}
return 0;
}
确实是60，赞楼上各种解法。。。
新作者？
前面四次总共有3*3*3*3种传法，但当第四次传到a手中时，第五次就肯定不在a手中，因为a不能传给a自己。所以第五次传给a的总数就是前面四次的总数减去第四次传给a的总数，这样就形成了一个递归。
假设f(i)为第i次传给a的传法总数，那么
f(i)=pow(3,i-1)-f(i-1) 且 f(1)=0
所以
f(5) = pow(3,4) – f(4) = 81 – (pow(3,3)-f(3)) = … = 60
好吧，那我直接给公式吧：m个人，传n次（m,n>=3）,方法共计((m-1)^n+(-1)^n*（m-1))/m.
都是牛人，学习了。
1 #!/usr/bin/php
2 “.$target;
10 $str = $str.” => $target”;
11 if( $index == 5 ) {
12 if( $target == $end ) {
13 $count++;
14 echo $str;
15 }
16 echo “\n”;
17 return;
18 }
19 foreach( $pArray as $p ) {
20 if( $target == $p ) continue;
21 pass_ball( $target , $p , $end , $index , $str );
22 }
23 }
24 foreach( $pArray as $p ) {
25 if( $p == “a” ) continue;
26 pass_ball( ‘a’ , $p , ‘a’ , 0 , “” );
27 }
28 echo $count.”\n”;
29 ?>
#!/usr/bin/php
“.$target;
$str = $str.” => $target”;
if( $index == 5 ) {
if( $target == $end ) {
$count++;
echo $str;
}
echo “\n”;
return;
}
foreach( $pArray as $p ) {
if( $target == $p ) continue;
pass_ball( $target , $p , $end , $index , $str );
}
}
foreach( $pArray as $p ) {
if( $p == “a” ) continue;
pass_ball( ‘a’ , $p , ‘a’ , 0 , “” );
}
echo $count.”\n”;
?>
~
#!/usr/bin/php
“.$target;
$pArray = array( ‘a’ , ‘b’ , ‘c’ , ‘d’ );
$count=0;
function pass_ball( $start , $target , $end , $index , $str ) {
global $pArray;
global $count;
$index = $index + 1;
if( $index == 1 ) $str = $start.” => “.$target;
$str = $str.” => $target”;
if( $index == 5 ) {
if( $target == $end ) {
$count++;
echo $str;
}
echo “\n”;
return;
}
foreach( $pArray as $p ) {
if( $target == $p ) continue;
pass_ball( $target , $p , $end , $index , $str );
}
}
foreach( $pArray as $p ) {
if( $p == “a” ) continue;
pass_ball( ‘a’ , $p , ‘a’ , 0 , “” );
}
echo $count.”\n”;
?>
妈的 php的标签头传不上去
10楼的loonsw，能解释一下这个公式吗？
3楼的jx_world，我和你的思路一样，不过你的答案可真简洁清晰
10楼的胡扯什么呢 写的什么东西
F(n) = 3^(n-1) – F(n-1)
初值：F（2）= 3
解得：F(n) = 3*( 3^(n-1) + (-1)^n) / 4; 其中n大于等于2
@sunshine
考公务员的都擅长这类公式的。。 我们码农自然不知道是什么东西
我的解法不佳啊
public class TT {
private static int NX(int N, int x) {
int result = 1;
while(x– > 0)
result *= N;
return result;
}
public static int NotA(int n) {
if(n == 0)
return 0;
return NX(3, n) – NotA(n – 1);
}
public static void main(String[] args) {
System.out.println(NotA(5 – 1));
}
}
192
54
@perrywky
赞成 厉害
容斥原理，a 3 3 3 3 a,(三种情况)，排除a 3 3 3 a a,多排除了a 3 3 a a a,以此类推，
3^4 – 3^3 + 3^2 – 3^1,
边界考虑：a 3 a时： 3^1 (不是3^1 – 3^0);
结果就是60了！
F(n) = 3F(n-2) + 2F(n-1)，其中F(0) = 1，F(1) = 0
前几年的NOIP普及组题目
“`python
>>> from numpy import *
>>> a = array([[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]])
>>> b = matrix_power(a, 5)
>>> b
array([[60, 61, 61, 61],
[61, 60, 61, 61],
[61, 61, 60, 61],
[61, 61, 61, 60]])
“`
60 种