顺序奖励积分的算法 [英] Algorithm for sequential reward points

问题描述

我想编写一种算法来查找顺序奖励点。
每次确认的邀请，邀请者都获得（1/2）^ k分，其中k是邀请的级别：级别0
（直接邀请的人）产生1分，级别1（受邀请的人）
给予1/2点，第2级邀请（第1级有人邀请的人）奖励1/4点，依此类推。
只有第一个邀请才算：发送给同一个人的多个邀请不会产生任何其他积分，
即使来自不同邀请者，也只有第一个邀请才算。
例如：

I want to write an algorithm to find the sequential reward points. The inviter gets (1/2)^k points for each confirmed invitation, where k is the level of the invitation: level 0 (people directly invited) yields 1 point, level 1 (people invited by someone invited by the original customer) gives 1/2 points, level 2 invitations (people invited by someone on level 1) awards 1/4 points and so on. Only the first invitation counts: multiple invites sent to the same person don't produce any further points, even if they come from different inviters and only the first invitation counts. For instance:

输入：

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的D推荐又获得0.25分。A的总得分为1.75分。

would calculate as: A receives 1 Point from the recommendation of B, 0.5 Point from the recommendation of C by B and another 0.25 Point by the recommendation of D by C. A gets a total score of 1.75 Points.

B从C的推荐中获得1分，从C的推荐中获得0.5分。 C提出的D的推荐。由于D之前是C提出的邀请，因此B没有从D的推荐中获得任何积分。 B获得1.5分。

B receives 1 Point from the recommendation of C and 0.5 Point from the recommendation of D by C. B receives no Points from the recommendation of D because D was invited by C before. B gets a total score of 1.5 Points.

C从D的推荐中获得1分。C获得1分。

C receives 1 Point from the recommendation of D. C gets a total score of 1 Point.

输出：
{ A：1.75， B：1.5， C：1}

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

What should be the algorithm for that? I think Dynamic Programing has to be use here.

推荐答案

这只是在树上搜索祖先。通过跟踪深度，您知道要奖励多少分。

This is simply an ancestors search in a tree. By keeping track of the depth, you know how many points to award.

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

此算法为 O（
，并且由于您需要遍历所有父母进行更新，因此您知道无法在复杂性方面做得更好。

This algorithm is O(number of parents) and since you need to traverse all parents to update, you know you can't do any better complexity-wise.

这篇关于顺序奖励积分的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！