连续奖励积分的算法

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 的推荐中获得 0.5 点，并且经C推荐D再加0.25分，A总分1.75分。

B从C的推荐中获得1分，从C的推荐中获得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( parent 的数量)，因为你需要遍历所有 parent 来更新，你知道你不能在复杂性方面做得更好。