我正在尝试解决下面描述的问题，
给定f（0）和k的值，它们是整数。
我需要找到f（T）的值。其中T <= 1010
递归函数是，
f(n) = 2*f(n-1) , if 4*f(n-1) <=k
k - ( 2*f(n-1) ) , if 4*f(n-1) > k
我的努力，
#include<iostream>
using namespace std;
int main(){
long k,f0,i;
cin>>k>>f0;
long operation ;
cin>>operation;
long answer=f0;
for(i=1;i<=operation;i++){
answer=(4*answer <= k )?(2*answer):(k-(2*answer));
}
cout<<answer;
return 0;
}
我的代码给了我正确的答案。但是，代码将在最坏的情况下运行1010次，这给了我超时限制。我需要更有效的解决方案来解决这个问题请帮我。我不知道正确的算法。
如果2f（0）<k，那么你可以在O（log n）时间内计算这个函数（通过用模k求平方来求幂）。
r = f(0) * 2^n mod k
return 2 * r >= k ? k - r : r
你可以通过归纳证明这一点。归纳假设是0 <= f（n）<k / 2，并且上述代码片段计算f（n）。
这是一个Python程序，它检查随机测试用例，比较天真的实现（f）和优化的实现（g）。
def f(n, k, z):
r = z
for _ in xrange(n):
if 4*r <= k:
r = 2 * r
else:
r = k - 2 * r
return r
def g(n, k, z):
r = (z * pow(2, n, k)) % k
if 2 * r >= k:
r = k - r
return r
import random
errs = 0
while errs < 20:
k = random.randrange(100, 10000000)
n = random.randrange(100000)
z = random.randrange(k//2)
a1 = f(n, k, z)
a2 = g(n, k, z)
if a1 != a2:
print n, k, z, a1, a2
errs += 1
print '.',
你能在编程和计算之前使用数学解决方案吗？
其实， f（n）= f0 * 2 ^（n-1），如果f（n-1）* 4 <= k k - f0 * 2 ^（n-1），如果f（n-1）* 4> k
因此，您的代码将像这样写：
condition = f0*pow(2, operation-2)
answer = condition*4 =< k? condition*2: k - condition*2
对于一个简单的循环，你的答案看起来非常紧张;一个人可以使用answer<<2而不是4*answer和answer<<1为2*answer优化一点，但很可能你的编译器已经这样做了。如果你正在浪费时间，可能有必要以某种方式减少循环本身。
我无法弄清楚@Shannon想要的数学模式，但我认为我们可以利用这个函数迟早会循环的事实。如果循环足够短，那么我们可以通过在循环中的同一点获得答案来缩短循环。
那么让我们以Brent's algorithm的形式得到一些循环检测设备，看看我们是否可以将循环切割到合理的水平。
def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Find the position of the first repetition of length λ
mu = 0
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.
# Next, the hare and tortoise move at same speed until they agree
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
f0 = 2
k = 198779
t = 10000000000
def f(x):
if 4 * x <= k:
return 2 * x
else:
return k - 2 * x
lam, mu = brent(f, f0)
t2 = t
if t >= mu + lam: # if T is past the cycle's first loop,
t2 = (t - mu) % lam + mu # find the equivalent place in the first loop
x = f0
for i in range(t2):
x = f(x)
print("Cycle start: %d; length: %d" % (mu, lam))
print("Equivalent result at index: %d" % t2)
print("Loop iterations skipped: %d" % (t - t2))
print("Result: %d" % x)
与其他提出的答案相反，这种方法实际上可以使用备忘录数组来加速该过程，因为函数的开始实际上是多次计算的（特别是在brent内），或者它可能是无关紧要的，这取决于如何这个周期恰好是。
您提出的算法已经有O（n）。为了提出更有效的算法，我们没有太多的方向可以解决。我们有一些典型的选择
1.减去线性项的系数（但我怀疑它会在这种情况下产生影响
2.改为O（Logn）（通常使用某种分治技巧）
3.改为O（1）
在这种情况下，我们可以做最后一个。递归函数是分段函数
f(n) = 2*f(n-1) , if 4*f(n-1) <=k
k - ( 2*f(n-1) ) , if 4*f(n-1) > k
让我们按案例解决它：
情况1：如果4 * f（n-1）<= k（1）（假设起始指数为零）这是一个明显的几何系列
a_n = 2 * a_n-1
因此，有了公式
Sn = 2 ^（n-1）f（0）----（）
情况2：如果4 * f（n-1）> k（2），我们有
a_n = -2a_n-1 + k
假设，a_j是序列中满足条件（2）的元素
嵌套地在公式的_1中，您将获得等式
an = k -2k + 4k -8k ... +（ - 2）^（n-j）* a_j
k -2k 4k -8 ...是另一个gemo系列
Sn = k *（1-2 ^（n-j））/（1-2）---具有起始值k和比率= -2的gemo级数和公式
因此，我们在案例2中有一个公式
an = k *（1-2 ^（n-j））/（1-2）+（ - 2）^（n-j）* a_j ----（**）
所有我们离开去找到一个只是不满足条件（1）并满足（2）的aj
这可以使用我们对案例1的公式再次在恒定时间内获得：
求n使得4 * an = 4 * Sn = 4 * 2 ^（n-1）* f（0）求解n：4 * 2 ^（n-1）* f（0）= k，如果n不是整数，取n的上限
在我第一次尝试解决这个问题时，我错误地认为序列的值是单调递增的，但实际上序列可能会在案例1和案例2之间跳转。因此，可能没有常数算法来解决问题。
但是，我们可以使用上面的结果来跳过迭代更新复杂性。
整体算法看起来像：
以T，K和f（0）开头
计算n使用（*）或（**）进行条件切换
用f（n）更新f（0），更新T - n
重复
当T-n = 0时终止（最后一次迭代可能超过计算导致T-n <0，因此，如果发生这种情况，你需要稍微回过头来）
创建一个可以存储结果的地图。在找到f（n）之前检查该地图，如果解决方案已经存在或不存在。如果存在，请使用该解决方案。否则找到它，存放以备将来使用。
对于C ++：
定义：
map<long,long>result;
插入：
result[key]=value
访问：
value=result[key];
检查：
map<long,long>::iterator it=result.find(key);
if(it==result.end())
{
//key was not found, find the solution and insert into result
}
else
{
return result[key];
}
使用上述技术可以获得更好的解