【问题】传球问题 【问题】传球问题 2009年12月20日 cui 评论 29 条评论 10,051 人阅读 有a,b,c,d,四个人 互相传球 从a开始传出 经过5次传球后 球回到a的手里 算总共有多少种传球的方法 (转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途) 相关文章如何调试bash脚本程序员的八个级别面向对象的Shell脚本给老婆普及计算机知识【原创】SQL栏目树的代码碰触,合作和团队绩效 (9 人打了分,平均分: 3.22 )Loading...
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 >>> 回复
//将上面的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; } 回复
前面四次总共有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 回复
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”; ?> ~ 回复
$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”; ?> 回复
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)); } } 回复
容斥原理,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了! 回复
“`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 种 回复
《【问题】传球问题》的相关评论
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 种