这是一种计算数组中有多少数字大于 0 的复杂方法。如果您尝试在编译器中运行它,则返回值为 1,因为数组中唯一大于 0 的数字是 3.1。
第一次运行时:
{-1.5, 3.1, -5.2, 0.0}
0 1 2 3
L H
然后自从L=0
and H=3
, M = (0+3)/2 = 3/2 = 1
当你到达g(A, L, M) + g(A, M+1, H)
,你分成两个:
{-1.5, 3.1, -5.2, 0.0}
0 1 2 3
L H
L1 H1 L2 H2
让我们做左边的部分g(A, L1, H1) = g(A, 0, 1)
first:
{-1.5, 3.1, -5.2, 0.0}
0 1 2 3
L H
L1 H1 L2 H2
^^^^^^^
再次因为L1=0
, H1=1
, 所以M1 = (0+1)/2 = 1/2 = 0
然后你又分成两部分g(A, 0, 0)
and g(A, 1, 1)
:
{-1.5, 3.1, -5.2, 0.0}
0 1 2 3
L H
L1 H1 L2 H2
L11,H11 L12,H12
在左边部分,因为-1.5 <= 0
所以g(A, L11, H11) = g(A, 0, 0) = 0
,在右侧部分,因为3.1 > 0
所以g(A, L12, H12) = g(A, 1, 1) = 1
.
所以因此g(A, 0, 1) = g(A, 0, 0) + g(A, 1, 1) = 1
.
做同样的事情g(A, L2, H2)
,你就明白了g(A, L, H) = g(A, L1, H1) + g(A, L2, H2) = 1 + 0 = 1
.
@Nawaz 有一个好主意,将其可视化为二叉树,基本上从树的根部开始:
{-1.5, 3.1, -5.2, 0.0}
在迭代的第二层,将数组分成两部分:
{-1.5, 3.1, -5.2, 0.0}
/ \
/ \
/ \
/ \
{-1.5, 3.1} {-5.2, 0.0}
在第三层,你再次分裂:
{-1.5, 3.1, -5.2, 0.0}
/ \
/ \
/ \
/ \
{-1.5, 3.1} {-5.2, 0.0}
/ \ / \
/ \ / \
{-1.5} {3.1} {-5.2} {0.0}
在此刻L==H
因此,我们可以评估节点:
{-1.5, 3.1, -5.2, 0.0}
/ \
/ \
/ \
/ \
{-1.5, 3.1} {-5.2, 0.0}
/ \ / \
/ \ / \
{-1.5} {3.1} {-5.2} {0.0}
| | | |
0 1 0 0
为了找到返回值,我们总结:
{-1.5, 3.1, -5.2, 0.0}
/ \
/ \
/ \
/ \
{-1.5, 3.1} {-5.2, 0.0}
0+1=1 0+0=0
最后
{-1.5, 3.1, -5.2, 0.0}
1+0=1