P17 香槟塔

青旅半醒 2022-08-29 10:11 5阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70_pic_center]

> 用二维数组记录每个杯子倒入的水量，若一开始倒入8杯香槟，则第一杯为8;  
> 每一杯由其头顶的杯子溢出的水量决定：  
> 若是第一列的杯子，头顶仅有一个杯子；所以 array\[ i \]\[ j \] = 溢水量(头顶杯子(array\[i-1\]\[0\])-1) / 2  
> 若是最后一列杯子，头顶也仅有一个杯子： 所以array\[ i \]\[ j \] = 溢水量(头顶杯子(array\[i-1\]\[-1\])-1) / 2  
> 否则为中间杯子，头顶两个杯子: 所以array\[ i \]\[ j \] = 溢水量(左头顶杯子(array\[i-1\]\[j-1\]) + (右头顶杯子(array\[i-1\]\[ j \]) - 2)) / 2

package main
    
    import (
    	"fmt"
    	"strconv"
    )
    
    func New2DArray(length int) [][]float64 { 
    	var array = make([][]float64, length)
    	for i := 0; i < length; i++ { 
    		array[i] = make([]float64, length)
    	}
    	return array
    }
    
    func ChampagneTower(cpus float64, length, row, column int) float64 { 
    	array2D := New2DArray(length)
    	array2D[0][0] = cpus // 第一位的被倒入的杯数
    
    	for i := 1; i < length; i++ {  // 行
    		for j := 0; j <= i; j++ {  // 列
    			if j == 0 && (array2D[i-1][0]-1)/2 > 0 {  // 最左边, 头顶杯子为[i-1][j]=[i-1][0], 给他杯子倒入量一半给我
    				array2D[i][j] = (array2D[i-1][0] - 1) / 2
    			}
    			if j == i && (array2D[i-1][i-1]-1)/2 > 0 {  // 最右边, 头顶杯子为[i-1][i-1], 给他杯子倒入量一半给我; 比如[11]头顶为[00],[22]头顶为[11]
    				array2D[i][j] = (array2D[i-1][i-1] - 1) / 2
    			}
    			if j != 0 && j != i && (array2D[i-1][j-1]+array2D[i-1][j]-2)/2 > 0 {  // 中间, 头顶杯子为[i-1][j-1];[i-1][j], 给他们两杯子倒入量一半给我
    				array2D[i][j] = (array2D[i-1][j-1] + array2D[i-1][j] - 2) / 2
    			}
    			if row == i+1 && column == j+1 { 
    				s := array2D[i][j]
    				if s > 1 { 
    					return 1
    				}
    				r, _ := strconv.ParseFloat(fmt.Sprintf("%.9g", s-float64(int(array2D[i][j]))), 64)
    				return r
    			}
    		}
    	}
    	fmt.Println("行列不匹配, 打印香槟塔:")
    	for i := 0; i < length; i++ { 
    		for j := 0; j <= i; j++ { 
    			fmt.Print(array2D[i][j], "\t")
    		}
    		fmt.Println()
    	}
    	return -1
    }
    
    func main() { 
    	fmt.Println("倒入8杯香槟,往5层高的被塔里, 求第3行第4列的杯子里的水:\n", ChampagneTower(8, 5, 3, 4))
    	fmt.Println("倒入8杯香槟,往5层高的被塔里, 求第4行第1列的杯子里的水:\n", ChampagneTower(8, 5, 4, 1))
    }

行列不匹配, 打印香槟塔:
    8
    3.5     3.5
    1.25    2.5     1.25
    0.125   0.875   0.875   0.125
    0       0       0       0       0
    倒入8杯香槟,往5层高的被塔里, 求第3行第4列的杯子里的水:
     -1
    倒入8杯香槟,往5层高的被塔里, 求第4行第1列的杯子里的水:
     0.125

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAwNTY1_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/2c6ee393495042c7abd5b8465859d766.png