计算问题的最优解

Question

这是问题->

​

​

输入是2 6 10。输出应该是41。

以下是对输出的解释：

​

​

我的代码给出了正确的输出，但随着数字的增加而变得更慢。我的代码如下。

def findMinGameCycle(e, n, m_0):
    r_total=2**(n-1)*(e+1)
    rest=0
    cycle=n
    m_total=m_0
    while m_total<=r_total:
        rest+=1
        cycle+=rest+1
        m_0+=1
        m_total+=m_0
    return cycle

Answer 1

科学计算入门:首先，试着用数学来解决这个问题。这个问题有一个封闭形式的解决方案，它只需要查看模式和二次公式。

让e, n, m_0如上所述。

在周期0，有e+1的敌人。在周期1，有2(e+1)。在周期2，有4(e+1)。推断，似乎在循环n-1 (它们停止复制的地方)，有2^(n-1)(e+1)的敌人。

在周期n处，有m_0的跟班。在cycle n+2 (他不得不等了一会儿)，有m_0 + (m_0 + 1)。在cycle n+5 (他不得不等待两个回合)，有m_0 + (m_0+1) + (m_0+2)。正在重新排列，在cycle n+5上有3m_0 + (1+2)的跟班。在周期n+9有4m_0 + (1+2+3)的爪牙，在周期n+14有5m_0 + (1+2+3+4)的爪子。推断一下，在cycle n+k(k+1)/2-1 (参见下面的链接)，有km_0 + (1+2+3+....(k-1))的附庸。右边的和是equal to k(k-1)/2。

我们想知道什么时候跟班人数超过了敌人。如果这些数字是连续的，那么当一个数字超过另一个数字时，它们是相等的。

即2^(n-1)(e+1) == km_0 + k(k-1)/2

这是k中的二次方程(回想一下，n,m_0,e是固定和给定的)。

使用我们得到的方便的quadratic formula解决k：

k = (1/2-m0) + sqrt((m0-1/2)^2+2^n*(e+1))

请注意，在我们的问题中，k不是连续的，因此我们必须在这一点上使其积分。如果k是一个小数，我们必须向上舍入到下一个整数，因为在下一个整数向下，没有足够的小数。

一旦我们对k进行舍入，我们就可以使用它来找到由上面的公式n+k(k+1)/2-1给出的循环。

以下是python中的所有逻辑：

import math

def turns(e,n,m0):
    k = (1/2-m0) + ((m0-1/2)**2+2**n*(e+1))**0.5
    k = math.ceil(k)
    return n + k*(k+1)/2 - 1

>>> turns(2,6,10)
41.0

由于我们花了一些时间做一些数学计算，所以没有循环，我们有一个恒定的时间解决方案。