时间戳

首页 > 解决方案 > 向后递归

javascript - 向后递归

问题描述

有一个任务：有几个男孩想打架，如果人数是偶数，他们分成两组，输了的人 - 回家。他们分成两对，打架，然后有人回家，直到他们得到奇数的人。当最后奇数人离开时 - 每个人都与每一个可能的敌人战斗。公式如下：n(n-1)/2。例如 5 个人 - 10 场战斗。

如果从一开始的人的数量是奇数 - 相同的计数方式：n（n-1）/ 2。

我写了一个脚本来计算所有可能的战斗次数，就像这样：

function qwe(number) {
        if(number % 2) {
            return number = number*(number-1)/2
        } else {
            number = number / 2; 
            return number + qwe(number)
        }
    }
    
console.log(qwe(6));

但是，如果我知道战斗次数并且想知道这场战斗我需要多少人怎么办？如何以相反的方式执行此功能？

标签： javascriptalgorithmrecursion

解决方案

你不能轻易地逆转这个功能，至少不能完全逆转。

有了三个战士，就会有3 * (3 - 1) / 2，或3打架。有四个战士，第一轮会有2战斗，然后1是第二轮，为3战斗。所以如果我们知道有三场战斗，我们不知道是三场还是四场。同样，qwe (10)is15和 so is qwe (16)。

有可能——事实上，从我的测试（最多）看来n，1000000最多有两个输入可以产生任何给定的输出。

我们可以通过详尽的搜索找到它们，因为很容易证明它qwe (n)总是至少n - 1，所以如果我们检查所有值的答案，最多比我们的目标值大一，我们将找到所有达到目标的值。但是由于功能如此混乱，我很难看到如何改进这种详尽的搜索。我们可以很容易地测试奇数结果，因为qwe (n) = n * (n - 1) / 2通过一些简单的代数，我们可以证明 if qwe (n) == t, then n = (1 + sqrt (1 + 8 * t)) / 2，但是测试递归步骤似乎更有问题。

推荐阅读