这个问题是在论坛上问的。有什么建议么？
有一个金字塔，第 1 层有 1 个杯子，第 2 层有 2 个，第 3 层有 3 个，依此类推。它看起来像这样
1 2 3 4 5 6
每个杯子的容量为 C。你从顶部倒 L 升水。当杯子 1 装满时，它会均匀地溢出到杯子 2,3，当它们装满时，杯子 4 和 6 只从 2 和 3 分别得到水，但 5 会从两个杯子中取水，依此类推。现在给定 C 和 L。找出第 i 杯中的水量？
问问题
4181 次
6 回答
9
每个玻璃杯都有一个流入流，玻璃杯中的水量，可能还有一些流出流（溢出）。
如果每个玻璃杯可以装 1 个单位的水，而你倒了 15 个单位的水，你会得到以下结果（括号中的溢出量）：
Incoming flow = 15, capacity = 1
Level 1: 1(14)
Level 2: 1(6) 1(6)
Level 3: 1(2) 1(5) 1(2)
Level 4: 1(1) 1(2.5) 1(2.5) 1(1)
Level 5: 1 1(0.75) 1(1.5) 1(0.75) 1
Level 6: 0 0.375 1(0.125) 1(0.125) 0.375 0
Level 7: 0 0 0.0625 0.125 0.0625 0 0
到第一层的流入流量为 L。来自一层玻璃的流入流量为，可写为：crFin(c, r)
Fin(0, r) = 0
Fin(r+1, r) = 0
Fin(1, 1) = L
Fin(c, r) = Fout(c - 1, r - 1)/2 + Fout(c, r - 1)/2
该玻璃杯中的水量为：
A(c, r) = Min(C, Fin(c, r))
流出的流量是：
Fout(c, r) = Max(0, Fin(c, r) - C)
A(c, r)如果不递归地进行评估，我看不到任何明显的公式。
要从索引到行和玻璃位置，您可以执行以下操作：
index = r*(r-1)/2 + c
r = floor((1 + sqrt(8*index - 7))/2)
c = index - r*(r-1)/2
(indexes start with 1)
于 2012-08-01T19:07:24.653 回答
0
一些想法：（1）重要的是知道哪两个杯子是第 i 个杯子的输入。(2) 重要的是要知道从左侧为您提供水的最小 Lleft 以及从右侧为您提供水的 Lright 的高度 (3) 所以您需要知道哪些杯子为第 i 个杯子提供水。如果你从 0 开始编号，这更容易，思考得更快。第 i 个杯子将填充 (i-1)*2+1 和 i*2，这意味着第 k 个杯子将从 (for k%2=1) ( k-1)/2 和 (k+1)/2 (对于 k%2=0) k/2 和 k/2+1 (4) 你应该检查一下对于任何 L 你将计算 L- Lleft 和 L-Lright。当为正时，提供的水是计算出的差除以 2^n 的结果，其中 n 是杯子的高度。
于 2012-08-01T18:42:04.587 回答
0
如果将金字塔建模为图形，则问题将转换为广度优先搜索。当您遍历每个节点时，获取其邻居并存储它们的溢出量。如果一个邻居已经被前一个节点检索到（这将在 5 个节点的情况下发生，因为节点 2 和节点 3 有一条边），您将必须根据其容量和已填充的内容更新溢出（通过节点 2；假设节点 2 在节点 3 之前被遍历）。
于 2012-08-02T06:37:17.053 回答
0
计算二项式系数的帕斯卡三角解可以用来解决这个问题。我们只需要稍微调整算法，而不是计算二项式系数，而是计算水位。给定第 i 个杯子，我们计算水平和指数以找出杯子在三角形中的位置。
杯子被建模为
0 Level 1
1 2 Level 2
3 4 5 Level 3
getIndex() 和 getLevel() 返回索引和级别。索引和级别从 1 开始。
public static int getIndex(int i) {
int totalNodes = i + 1;
double d = (-3 + Math.sqrt(9 - 8*(1-totalNodes)))/2;
int level = (int)Math.floor(d);
int total = ((level+1)*(level+2))/2;
int index = 0;
if(total==totalNodes) index = level;
else{
level++;
index = totalNodes - total - 1;
}
return ++index;
}
public static int getLevel(int i) {
int totalNodes = i + 1;
double d = (-3 + Math.sqrt(9 - 8*(1-totalNodes)))/2;
int level = (int)Math.floor(d);
int total = ((level+1)*(level+2))/2;
int index = 0;
if(total==totalNodes) index = level;
else{
level++;
index = totalNodes - total - 1;
}
return ++level;
}
k 是从 0 开始的第 k 个杯子。C 是杯子容量，L 是总水量。
public static double getWaterLevel(double C, double L, int k) {
int n = getLevel(k);
int index = getIndex(k);
double[] water = new double[index+1];
water[1] = L;
for(int i = 2; i <= n; i++)
{
boolean overflowed = false;
for(int j = Math.min(i, index); j > 0; j--) {
double over = 0;
if(water[j]>C) over = (water[j]-C)/2;
if(water[j-1]>C) over += (water[j-1]-C)/2;
water[j] = over;
if(!overflowed && over!=0) overflowed=true;
}
if(!overflowed) break; // no more overflow. stop
}
return water[index] > C ? C : water[index];
}
于 2013-11-26T04:03:51.433 回答
0
这是另一种简单的解决方案，只需将水倒入当前的玻璃杯中，然后检查是否有多余的水，然后流到下一个水平。在这里，我使用了 2D Mat 来倒水。然后我将 2D 垫子转换为 1D 尺寸等于第 i 个元素/玻璃，我们需要返回并返回它。实施明智，这是一个非常简单的解决方案。
private double fillWaterInGlasses(double capacity, double water , int glassToFind) {
int maxLevel = (int)(water/capacity)/2 + 1;
double[][] glasses = new double[maxLevel][maxLevel];
// Pour total water in top glass initially.
glasses[0][0] = water;
int level=0;
boolean waterInLevel = true;
while(waterInLevel) {
waterInLevel = false;
// For each glass in the level.
for(int j=0; j<=level; j++) {
// If the glass has more liquid then it can store then pour it to glasses under it.
if(glasses[level][j] > capacity) {
double extraWater = glasses[level][j] - capacity;
glasses[level][j] = capacity;
glasses[level+1][j] += extraWater / 2;
glasses[level+1][j+1] += extraWater / 2;
waterInLevel = true;
}
}
level++;
}
double res[] = new double[glassToFind];
int k =0;
for (int i = 0; i < glasses.length; i++) {
for (int j = 0; j <= i; j++) {
res[k] = glasses[i][j];
if (k == glassToFind-1){
return res[glassToFind-1];
}
k++;
}
}
return res[glassToFind-1];
}
于 2020-02-15T05:25:13.133 回答
-1
这是一个简单易懂的实现：
public class main {
static float total_water = 50;
static int N = 20;
static glass[][] pyramid = new glass[N][N];
public static void main(String[] args) {
build_pyramid();
pour_water(0, 0, total_water);
print_pyramid();
print_total_water_stored();
}
private static void print_total_water_stored() {
float total = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++)
total += pyramid[i][j].filled;
}
System.out.println("total water stored= " + total);
}
private static void pour_water(int row, int col, float water) {
if (water >= (pyramid[row][col].capacity - pyramid[row][col].filled)) {
water -= (pyramid[row][col].capacity - pyramid[row][col].filled);
pyramid[row][col].filled = pyramid[row][col].capacity;
pour_water(row + 1, col, water / 2);
pour_water(row + 1, col + 1, water / 2);
} else {
pyramid[row][col].filled += water;
}
}
public static void build_pyramid() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
pyramid[i][j] = new glass(1);
}
}
public static void print_pyramid() {
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++)
System.out.print(pyramid[i][j].filled + " ");
System.out.println();
}
}
}
class glass {
float capacity;
float filled;
glass(float cap) {
capacity = cap;
filled = 0;
}
}
于 2014-01-08T10:33:29.910 回答