算法目录合集
该地址指向所有由本人自己所经历的算法习题(也有可能仅仅是一个入门的案例或者是经典案例)，仅仅为我做过而且比较有意思的，也许还会有一些我自己想出来的，出于兴趣写在这里,具体格式我会在下面列明，总目录也会在这里出现，方便查阅以及自己进行复习回顾。
做这个图形首先要先找到数字之间的规律，然后再画个等腰三角形，相信等腰三角形家都会画，所以我着重说一下找规律的方法。 这个题有多种思路可以解决，在这里我提供两种思路供大家参考：
第一种思路非常简单，就是跟着这个三角形的规律走，也即是杨辉三角所发现的规律：一个数字为他的两肩之和，即：第三行的第二个数字为第二行的第一个和第二个数字的和；第八行的第五个数字，为第七行的第四个和第五个数字之和，发现规律没？第n行的第m个数字，就是第（n-1）行的第（m-1）和第m个数字的和，于是我们就可以规定好第一行与第二行的数字（都是1），以及大三角形两腰的数字（都是1），然后按照既定的规律来寻迹了。这便得到了我们的核心代码：
for (int row = 0; row < 总层数; row++) { triangles[row][0] = 1; triangles[row][row] = 1; for (int seat = 1; seat < row; ++seat) { triangles[row][seat] = triangles[row - 1][seat - 1] + triangles[row - 1][seat]; } }其中:
triangles[row][0] = 1; triangles[row][row] = 1;就是来为特殊情况（每条边）进行赋值为1 的。而：
for (int seat = 1; seat < row; ++seat) { triangles[row][seat] = triangles[row - 1][seat - 1] + triangles[row - 1][seat]; }就是实现第n行的第m个数字，就是第（n-1）行的第（m-1）和第m个数字的和的操作。于是就可以得到了我们所需要的数组，画出来即可。（具体代码以及结果参见下面的代码实现——方式一）
这个思路不太容易想到，不过我给大家提个醒，在高中的时候，老师教的二项式定理大家有没有还给老师啊？😀😀😀😀这里就要用到相关的知识： 二项式定理的表现形式如下：
( x + y ) n = C n 0 x n y 0 + C n 1 x n − 1 y 1 + C n 2 x n − 2 y 2 + … … + C n n − 1 x 1 y n − 1 + C n n x 0 y n (x+y)^n =C_{n}^{0} x^ny^0+C_{n}^{1} x^{n-1}y^1+C_{n}^{2} x^{n-2}y^2+……+C_{n}^{n-1} x^1y^{n-1}+C_{n}^{n} x^0y^n (x+y)n=Cn0xny0+Cn1xn−1y1+Cn2xn−2y2+……+Cnn−1x1yn−1+Cnnx0yn
这里我们要用到的就是他们的常数项，即： C n 0 C_{n}^{0} Cn0、 C n 1 C_{n}^{1} Cn1、 C n 2 C_{n}^{2} Cn2 …… C n n − 1 C_{n}^{n-1} Cnn−1、 C n n C_{n}^{n} Cnn这些数，大家可以随意给n赋值，看看有什么结果？
n数列31、3、3、161、6、15、20、15、6、191、9、36、84、126、126、84、36、9、1…………n C n 0 C_{n}^{0} Cn0、 C n 1 C_{n}^{1} Cn1、 C n 2 C_{n}^{2} Cn2 …… C n n − 1 C_{n}^{n-1} Cnn−1、 C n n C_{n}^{n} Cnn是否很神奇呢？根据二项式推出来的常数项的值，好巧不巧，与杨辉三角的相对应的层数的数列是完全一样的。那还不手到擒来？我们只需要把这个数学语言转化为计算机语言就行了，计算机怎么找出一行中的数字规律？他不行，得我们来，我们让计算机按照我们给出的值去计算就可以了，那么，当给定了第一个值 C n 0 C_{n}^{0} Cn0如何让他计算出 C n 1 C_{n}^{1} Cn1呢？给出了 C n n − 1 C_{n}^{n-1} Cnn−1又如何去找出 C n n C_{n}^{n} Cnn呢？我们不如随便假设一个数字 C n r C_{n}^{r} Cnr，看看他与他之后的一位 C n r + 1 C_{n}^{r+1} Cnr+1的关系，并根据此做出一个推定，再去验证：
C n r = n ! r ! ( n − r ) ! C_{n}^{r} = \dfrac{n!}{r! (n-r)!} Cnr=r!(n−r)!n!
= n × ( n − 1 ) × … … × 2 × 1 r × ( r − 1 ) × … … × 2 × 1 × ( n − r ) × ( n − r − 1 ) × … … × 2 × 1 = \dfrac{n\times(n-1)\times……\times2\times1}{r\times(r-1)\times……\times2\times1 \times (n-r)\times(n-r-1)\times……\times2\times1} =r×(r−1)×……×2×1×(n−r)×(n−r−1)×……×2×1n×(n−1)×……×2×1
= n × ( n − 1 ) × … … × ( n − r + 2 ) × ( n − r + 1 ) r × ( r − 1 ) × … … × 2 × 1 = \dfrac{n\times(n-1)\times……\times(n-r+2)\times(n-r+1)}{r\times(r-1)\times……\times2\times1} =r×(r−1)×……×2×1n×(n−1)×……×(n−r+2)×(n−r+1)
所以同理可以得出：
C n r + 1 = n ! ( r + 1 ) ! [ n − ( r + 1 ) ] ! C_{n}^{r+1} = \dfrac{n!}{(r+1)! [n-(r+1)]!} Cnr+1=(r+1)![n−(r+1)]!n!
= n × ( n − 1 ) × … … × ( n − r + 1 ) × ( n − r ) ( r + 1 ) × r × ( r − 1 ) × … … × 2 × 1 = \dfrac{n\times(n-1)\times……\times(n-r+1)\times(n-r)}{(r+1)\times r\times(r-1)\times……\times2\times1} =(r+1)×r×(r−1)×……×2×1n×(n−1)×……×(n−r+1)×(n−r)
于是很容易找出在每一行中，后一项是前一项的 k k k倍：
k = C n r + 1 C n r = n × ( n − 1 ) × … … × ( n − r + 1 ) × ( n − r ) ( r + 1 ) × r × ( r − 1 ) × … … × 2 × 1 × r × ( r − 1 ) × … … × 2 × 1 n × ( n − 1 ) × … … × ( n − r + 2 ) × ( n − r + 1 ) k=\dfrac{C_{n}^{r+1}}{C_{n}^{r} }= \dfrac{n\times(n-1)\times……\times(n-r+1)\times(n-r)}{(r+1)\times r\times(r-1)\times……\times2\times1} \times \dfrac{r\times(r-1)\times……\times2\times1}{n\times(n-1)\times……\times(n-r+2)\times(n-r+1)} k=CnrCnr+1=(r+1)×r×(r−1)×……×2×1n×(n−1)×……×(n−r+1)×(n−r)×n×(n−1)×……×(n−r+2)×(n−r+1)r×(r−1)×……×2×1
验证一下，n=5，r=3，可以得出 C 5 3 = 10 C_{5}^{3} = 10 C53=10， C 5 4 = 5 C_{5}^{4} = 5 C54=5，而且 C 5 4 C 5 3 = 1 2 = ( 5 − 3 ) ( 3 + 1 ) \dfrac{C_{5}^{4}}{C_{5}^{3} }= \dfrac{1}{2}= \dfrac{(5-3)}{(3+1)} C53C54=21=(3+1)(5−3),推广到r=n-1，也是没有问题的，所以这就是我们要找的规律了： ( n − r ) ( r + 1 ) \dfrac{(n-r)}{(r+1)} (r+1)(n−r)😀😀😀😀，还原成计算机语言的时候注意计算机是从0开始数数的，就好了：于是得到了我们的核心代码：
for (int row = 0; row < triangles.length; row++) { //每层的第一个数字 int member = 1; //对每层数值单独操作 for (int seat = 0; seat < triangles[row].length; seat++) { //每层的其余数字 triangles[row][seat] = member; member = member * (row - (seat + 1) + 1) / (seat + 1); } }初始化第一个数字为1，然后赋值给数组triangles[row][]的0号索引位置，然后对初始化值member进行规律变化，再赋值给第二个……以此类推，得到全数组，然后画出来即可。（具体代码以及结果参见下面的代码实现——方式二）
结果演示
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1结果演示
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 1 10 45 120 210 252 210 120 45 10 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1这两个力扣的杨辉三角的题都是非常基础的，在这里就不做过多的计算了，大家看看就可以了，我的leetcode也不收录这俩题了，没啥意思，链接给你们，自己去看，可以练练手，118.杨辉三角、119.杨辉三角II（不过那里面用其他方式的解题思路大家可以看看，学习学习，思路学会了真的很重要）。
如下图，黑球为游戏用球，白色圆球为障碍物，小黑球落下后与白色球碰撞后，假设落到两侧的几率是完全一样的并且只能落在相邻的两个空格内。那么，小黑球落在E格中的概率一定是最大的，店主放在那里的奖品也一定是最差的。我们不难对这种游戏进行数学还原：从该图中不难发现，各区域的概率与杨辉三角形有密切联系，我们可以直接利用杨辉三角的性质得出小球落到每个区域的概率。 对于每个格子小黑球落入的概率分析如下（分析过程略，概率学初级知识，随便可以查查😎😎😎😎），对于这个图，我们要得到的ABCDEFGHI的概率如下图所示的： 1 256 \dfrac{1}{256} 2561、 1 32 \dfrac{1}{32} 321、 7 64 \dfrac{7}{64} 647、 7 32 \dfrac{7}{32} 327、 35 128 \dfrac{35}{128} 12835、 7 32 \dfrac{7}{32} 327、 7 64 \dfrac{7}{64} 647、 1 32 \dfrac{1}{32} 321、 1 256 \dfrac{1}{256} 2561。 那么多加两层呢？我们难道要去一点一点写出来吗？明显是不可能的，那么我们就要找到他的普遍规律，这组数据不太方便看，那么我把它复原一下，不再进行约分： 熟悉了吧？分子就是杨辉三角，分母就是2的层数次方（ 2 层 数 2^{层数} 2层数），在数学上的表达就是：F格子的概率为 C 8 5 2 8 = 56 256 = 7 32 \dfrac{C_{8}^{5}}{2^8}=\dfrac{56}{256}=\dfrac{7}{32} 28C85=25656=327 ；那么第m行的第n个格子的概率就是 C m n − 1 2 m \dfrac{C_{m}^{n-1}}{2^m} 2mCmn−1。 数学规律找到了，那么实现代码也就很容易了，这里我采用横向寻踪的方式，分母直接采用控制台用户输入的数据，分子通过杨辉三角数组进行查询，代码如下：
package com.interest.test; import java.util.Scanner; /** * com.interest.test * * @author g55zhw * @create 2020-09-06-11-06 */ public class ParkBall { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String define = null; String exit = "exit"; while (!exit.equals(define)) { System.out.println("请输入游戏障碍物的层数"); String piles = sc.next(); System.out.println("请输入需要查询的格子（需要小于您输入的层数+2，否则无法查询）"); String seat = sc.next(); int sum = (int) Math.pow(2, Double.parseDouble(piles)); int[][] parkBall = setTriangle(Integer.parseInt(piles)); try { int gcd = getGCD(parkBall[Integer.parseInt(piles)][Integer.parseInt(seat) - 1], sum); System.out.println(gcd); int pilesGCD = parkBall[Integer.parseInt(piles)][Integer.parseInt(seat) - 1] / gcd; int sumGCD = sum / gcd; System.out.println("分子为：" + parkBall[Integer.parseInt(piles)][Integer.parseInt(seat) - 1] + "，分母为：" + sum + ",落入第" + piles + "行第" + seat + "个格子的概率为：" + pilesGCD + "/" + sumGCD); } catch (ArrayIndexOutOfBoundsException e) { System.out.println("输入错误"); } System.out.println("是否继续?(输入“exit”退出，输入任意值继续)"); define = sc.next(); } System.out.println("感谢您的使用"); } /** * 返回传入参数的最大公约数 * @param a 参数 * @param b 参数 * @return a 与 b 的最大公约数 */ public static int getGCD(int a, int b) { int min = Math.min(a, b); int gcd = -1; for (int i = min; i >= 1; i--) { if (a % i == 0 && b % i == 0) { gcd = i; break; } } return gcd; } /** * 返回杨辉三角数组 * @param plies 层数 * @return int[][] 表示杨辉三角的数组 */ public static int[][] setTriangle(int plies) { int[][] triangles = new int[plies + 1][]; for (int i = 0; i <= plies; i++) { triangles[i] = new int[i + 1]; } for (int row = 0; row < triangles.length; row++) { int member = 1; for (int seat = 0; seat < triangles[row].length; seat++) { triangles[row][seat] = member; member = member * (row - (seat + 1) + 1) / (seat + 1); } } return triangles; } }测试结果
请输入游戏障碍物的层数 8 请输入需要查询的格子（需要小于您输入的层数+2，否则无法查询） 6 8 分子为：56，分母为：256,落入第8行第6个格子的概率为：7/32 是否继续?(输入“exit”退出，输入任意值继续) yyy 请输入游戏障碍物的层数 9 请输入需要查询的格子（需要小于您输入的层数+2，否则无法查询） 3 4 分子为：36，分母为：512,落入第9行第3个格子的概率为：9/128 是否继续?(输入“exit”退出，输入任意值继续) exit 感谢您的使用成功😄😄😄😄
具体还是参见第62题：不同路径(中等难度)——如何学以致用
原答案有出入，我稍微调了一下，对于结果是没有影响的。
#include <stdio.h> #define N 12 long combi(int n, int r){ int i; long p = 1; for(i = 1; i <= r; i++) p = p * (n-i+1) / i; return p; } int main(void) { int n, r, t; for(n = 0; n <= N; n++) { for(r = 0; r <= n; r++) { int i;/* 排版设定开始 */ if(r == 0) { for(i = 0; i <= (N-n); i++) printf(" "); }else { printf(" "); } /* 排版设定结束 */ printf("%3d", combi(n, r)); } printf("\n"); } }将杨辉三角依次下降，成如图所示排列，将同一行的数加起来，即得一数列1、1、2、3、5、8、…… 公式表示如下：
f(1) = C 0 0 C_{0}^{0} C00 = 1 f(2) = C 1 0 C_{1}^{0} C10 = 1 f(3) = C 2 0 C_{2}^{0} C20 + C 1 1 C_{1}^{1} C11 = 1+1 = 2 f(4) = C 3 0 C_{3}^{0} C30 + C 2 1 C_{2}^{1} C21 = 1+2 = 3 f(5) = C 4 0 C_{4}^{0} C40 + C 3 1 C_{3}^{1} C31 + C 2 2 C_{2}^{2} C22 = 1+3+1 = 5 f(6) = C 5 0 C_{5}^{0} C50 + C 4 1 C_{4}^{1} C41 + C 3 2 C_{3}^{2} C32 = 1+4+3 = 8 f(7) = C 6 0 C_{6}^{0} C60 + C 5 1 C_{5}^{1} C51 + C 4 2 C_{4}^{2} C42 + C 3 3 C_{3}^{3} C33 = 1+5+6+1 = 13 f(8) = C 7 0 C_{7}^{0} C70 + C 6 1 C_{6}^{1} C61 + C 5 2 C_{5}^{2} C52 + C 4 3 C_{4}^{3} C43 = 1+6+10+4 = 21 …… f(n) = C n − 1 0 C_{n-1}^{0} Cn−10 + C n − 2 1 C_{n-2}^{1} Cn−21 + … + C n − 1 − m m C_{n-1-m}^{m} Cn−1−mm (m<=n-1-m)
