香槟塔（简易版）

EvanTheGreat 2022-01-02 原文

这里记录的香槟塔算法笔记是简易版的，最初时，香槟塔中的每个杯子都是空的，没有倒酒。从塔顶的杯子开始倒酒，给定一个倒酒的杯数（次数），然后查找某一行某一列杯子的乘酒量（小数表示，例如1.0表示满；0.5表示一半满）

对于特定行特定列的杯子，我们在这里用一个二维数组来存储，既存储位置，也存储乘酒量。然后，我们给第一个杯子（即塔顶杯子赋初值），接着可以用一个双重for循环遍历数组，我们查找当前位置的酒杯的存酒量。如何查找？可以将其与1进行对比，如果大于1，那就说明这个杯子肯定会溢出，那么我们就把溢出的酒量均分给它下面那一行地两个杯子。如果小于1那就是还没满，不用做处理。

当然，我们这里存储都是没有考虑杯子容量的，因此若直接返回查找位置的杯子容量，极有可能会出现大于1的情况。这个时候我们就要把结果与1比较，取二者的较小值，这样才是最终结果。

 1 package com.hw.list0710;
 2 
 3 import java.util.Scanner;
 4 
 5 public class Champagne {
 6     private static double getNum(int poured, int row, int col) {
 7         double[][] storage = new double[100][100];
 8         storage[0][0] = poured;  //初始倒了几杯酒
 9         for(int i = 0; i < row; ++i) {
10             for(int j = 0; j <= i; ++j) {
11                 double d = (storage[i][j] - 1.0) / 2;  //当前杯子。大于0即溢出了，否则还没满
12                 if(d > 0){  //所以这里只考虑溢出的情况
13                     storage[i+1][j] += d;
14                     storage[i+1][j+1] += d;
15                 }
16             }
17         }
18         return Math.min(1, storage[row][col]);//大于1那就是1了，因为大于1就满了，满了就要往下溢出
19     }
20 
21     public static void main(String[] args) {
22         Scanner s = new Scanner(System.in);
23         System.out.println("输入已倒杯数:");
24         int poured = s.nextInt();
25         System.out.println("输入查找的行:");
26         int row = s.nextInt();
27         System.out.println("输入查找的列:");
28         int col = s.nextInt();
29         s.close();
30         double res = getNum(poured, row-1, col-1);
31         System.out.println(res);
32     }
33 }