经验总结

  1. 首页 > 生活 > >

Bob 的生存概率问题

生活百科

Bob 的生存概率问题作者：Grey
原文地址：
博客园：Bob 的生存概率问题
CSDN：Bob 的生存概率问题
题目描述给定五个参数 n , m , i , j , k ， 表示在一个 n*m 的区域 ， Bob 处在 (i,j) 点 ， 每次 Bob 等概率的向上、 下、左、右四个方向移动一步 ， Bob 必须走 k 步 。如果走完之后 ， Bob 还停留在这个区域上 ，  就算 Bob 存活 ， 否则就算 Bob 死亡 。请求解 Bob 的生存概率 ， 返回字符串表示分数的方式 。
题目链接：牛客-Bob的生存概率
暴力解法由于 Bob 可以向四个方向任意一个方向走 k 步 ， 所以 ， Bob 可以选择走的路线总数是：4^k ， 即：4 的 k 次方 。
接下来就是要求在 4 ^ k 总数中 ， 哪些是存活下来的路线 ， 定义如下递归函数
long process(int i, int j, int k, int n, int m)递归含义表示：目前在 (i ， j) 位置 ， 还有 k 步要走 ， 走完了如果还在棋盘中就获得1个生存点 ， 返回总的生存点数 。
接下来是 base case ， 如果越界了 ， 直接返回 0 ， 
【Bob 的生存概率问题】if (i < 0 || i == n || j < 0 || j == m) {return 0;}表示没有生存机会 ， 
如果没有越界 ， 但是此时正好 k == 0 ， 说明已经有一种存活路线了 ， 返回 1 ， 表示一种有效路线 。
if (i < 0 || i == n || j < 0 || j == m) {return 0;}// 没有越界 ， 说明还在棋盘中 ， 没有步数了 ， 直接返回一种有效路线 。if (k == 0) {return 1;}接下来是普遍情况 ，  Bob 在棋盘中 ， 可以往四面八方走 ， 即
long up = process(i - 1, j, k - 1, n, m);long down = process(i + 1, j, k - 1, n, m);long left = process(i, j - 1, k - 1, n, m);long right = process(i, j + 1, k - 1, n, m);上述表示四面八方走返回的有效路线 ， 四个方向的有效路线之和 ， 就是答案 ， 即
return up + down + left + right;递归函数的完整代码如下
public static long process(int i, int j, int k, int n, int m) {if (i < 0 || i == n || j < 0 || j == m) {return 0;}// 还在棋盘中！if (k == 0) {return 1;}// 还在棋盘中！还有步数要走long up = process(i - 1, j, k - 1, n, m);long down = process(i + 1, j, k - 1, n, m);long left = process(i, j - 1, k - 1, n, m);long right = process(i, j + 1, k - 1, n, m);return up + down + left + right;}由于最后的结果要返回最简的分数形式 ， 所以假设有效路线是 X 种 ， 所有可能的走法是 Y 种 ， 那么返回的字符串是如下形式
return (X/gcd(X,Y)) + "/" + (Y/gcd(X,Y))其中 gcd(X,Y) 就是利用辗转相除法得到 X ， Y 的最大公约数
public static long gcd(long m, long n) {return n == 0 ? m : gcd(n, m % n);}暴力解法的完整代码如下
import java.util.Scanner;public class Main {public static String livePossibility1(int i, int j, int k, int n, int m) {return buildExp(process(i, j, k, n, m), (long) Math.pow(4, k));}// 目前在i ， j位置 ， 还有k步要走 ， 走完了如果还在棋盘中就获得1个生存点 ， 返回总的生存点数public static long process(int i, int j, int k, int n, int m) {if (i < 0 || i == n || j < 0 || j == m) {return 0;}// 还在棋盘中！if (k == 0) {return 1;}// 还在棋盘中！还有步数要走long up = process(i - 1, j, k - 1, n, m);long down = process(i + 1, j, k - 1, n, m);long left = process(i, j - 1, k - 1, n, m);long right = process(i, j + 1, k - 1, n, m);return up + down + left + right;}public static String buildExp(long m, long n) {return m / gcd(m, n) + "/" + n / gcd(m, n);}public static long gcd(long m, long n) {return n == 0 ? m : gcd(n, m % n);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int i = sc.nextInt();int j = sc.nextInt();int k = sc.nextInt();System.out.println(livePossibility1(i, j, k, n, m));sc.close();}}

经验总结扩展阅读


上一篇：妻子旺自己事业的八字 财星官星命理特征

下一篇：什么星座得到人却得不得心