序贯奖励点的算法

Question

我想写一个算法来找到连续的奖励点。邀请者每次确认邀请都会得到( 1/2 )^k分，其中k是邀请的级别:0级(直接邀请的人)会得到1分，1级(由原始客户邀请的人邀请的人)会得到1/2分，2级邀请(由1级的人邀请的人)会得到1/4分，依此类推。只有第一个邀请才算数:向同一个人发送多个邀请不会产生任何进一步的积分，即使它们来自不同的邀请者并且只有第一个邀请算数。例如：

输入：

A recommends B
B accepts
B recommends C
C accepts
C recommends D
B recommends D
D accepts

计算如下:A从B的推荐中获得1分，B从C的推荐中获得0.5分，C的推荐中获得另外的0.25分。A的总分为1.75分。

B从C的推荐中获得1分，从C的D推荐中获得0.5分。B从D的推荐中得不到任何分数，因为D之前是由C邀请的。B总分1.5分。

C从D的推荐中得到1分。C总分为1分。

输出：{ “A”: 1.75, “B”: 1.5, “C”: 1 }

这个问题的算法应该是什么？我认为这里必须使用动态编程。

Answer 1

这只是一个祖先在树中的搜索。通过跟踪深度，您可以知道要奖励多少分。

伪码

def add_points(accepter):
    depth = 0
    while accepter has an inviter:
        accepter.inviter.points += (0.5)^depth
        accepter = accepter.inviter
        depth += 1

这个算法是O(父代的数量)，因为你需要遍历所有的父代来更新，你知道你不能在复杂度方面做得更好。