解题思路:
首先我们以题目的三人传球为例,每个人只能传给自己左右的人,如下图所示:
在编程的时候,我们把学生序列存储为数组,小蛮在第一个,也就是0位置,数组形式的传球如下图所示:
每轮传球,球传到序号x的学生手中的可能应该是上一轮传球中他左、右两侧同学拥有球的可能性之和,以3人为例就如下图所示:
这部分图解还是看不懂的同学,可以再查阅一下“动态规划”的讲解
代码实现:
题目给的n表示学生数量,m表示轮数
但在构建二维数组的时候,应该构建的事a[m+1][n],因为初始状态不算在传递轮数中
然后就是a[i][j]等于多少了,这里要分情况讨论:
我们把圈拆成了数组,因此首、尾需要不同的处理方式表示其左右的同学,具体详见如下代码:
for(int i=1;i<m;i++) { for(int j=0;j<n;j++) { if(j==0) //第一个同学 { a[i][j]=a[i-1][1]+a[i-1][n-1]; } else if(j==n-1) //最后一个同学 { a[i][j]=a[i-1][0]+a[i-1][n-2]; } else //中间的同学 { a[i][j]=a[i-1][j-1]+a[i-1][j+1]; } } }
参考代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n=scan.nextInt(); int m=scan.nextInt(); m++; int [][]a=new int[m][n]; //存储第m轮各同学拿到球的可能性 for(int i=1;i<m;i++) //二维数组初始化 { for(int j=0;j<n;j++) { a[i][j]=0; } } a[0][0]=1; //小蛮初始就拿到了球 for(int i=1;i<m;i++) { for(int j=0;j<n;j++) { if(j==0) //第一个同学 { a[i][j]=a[i-1][1]+a[i-1][n-1]; } else if(j==n-1) //最后一个同学 { a[i][j]=a[i-1][0]+a[i-1][n-2]; } else //中间的同学 { a[i][j]=a[i-1][j-1]+a[i-1][j+1]; } } } System.out.println(a[m-1][0]); //小蛮 } }
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:927 |
C语言训练-大、小写问题 (C语言代码)浏览:2349 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:859 |
【明明的随机数】 (C++代码)浏览:779 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:1419 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:850 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:603 |
IP判断 (C语言描述,蓝桥杯)浏览:1094 |
字符逆序 (C语言代码)浏览:609 |
sizeof的大作用 (C语言代码)浏览:1448 |