该系列由以下定义 -f(0) = 0, f(1) = 1, f(n) = 2*f(n - 1) - 2*(n - 2) for all n > 1
我想在 python 中将其实现为一个函数,其中整数数组传递给函数,该函数将返回定义序列约束中的所有数字。
如何解决这个问题才能准确解决?
为了获得该系列的第 n 项,我实现了以下递归函数 -
result = {}
def find_nth_term(n):
if n == 0:
result[n] = 0
return 0
elif n == 1:
result[n] = 1
return 1
else:
val = 2*find_nth_term(n-1)-2*find_nth_term(n-2)
result[n] = val
return val
find_nth_term(10)
print(set(result.values()))
上面的程序对吗?下一步该怎么做?
我们知道:
f(n) = 2*[ f(n-1) - f(n-2)]---(1)
f(n-1) = 2*[ f(n-2) - f(n-3)]---(2)
f(n-2) = 2*[f(n-3) - f(n-4)]---(3)
将 f(n-1( 从 (2( 替换为 (1(:
f(n) = 2*2* f(n-2) - 2*2* f(n-3) - 2* f(n-2)
= 2*f(n-2) - 4*f(n-3) --- (4)
将 f(n-2( 从 (3( 替换为 (4(:
f(n) = 2*[2*f(n-3) - 2*f(n-4)] - 4*f(n-3)
f(n) = 4*f(n-3) - 4*f(n-4) -4*f(n-3)
f(n) = -4 *f(n-4)
通过扩展:
f(n) = (-4)^k * f(n- 4k)
也:
f(0)=0
f(1)=1
f(2)=2
f(3)=2
因此,任何 f(n( 都可以简化为以下形式之一:。
f(n) = (-4)^k * 0 OR (-4)^k * 1 OR (-4)^k * 2
对于 python 部分:
给定一个整数 (x( :if X==0: f(0( = 0
else:
检查它的形式是 ((-4(**k(*2 还是 (-4(**k,然后:
在 f(n( 中: n = a + 4k 其中:
a= 1如果形式为 (-4(**k a= 2如果形式为 (-4(**k
(*2
基于上述关系的序列变为:(对于前 10 个数字(
0, 1, -2, 6, -16, 44, -120, 328, -896, 2448......
此代码
def seq(n):
nxt = 0
seq = [0,1]
first, second = seq
for i in range(n-2):
nxt = 2*(first - second)
seq.append(nxt)
first = second
second = nxt
return seq
def numbers(array, seq):
int_in_seq = []
for i in array:
if i in seq:
int_in_seq.append(i)
return (f"numbers in seq:",int_in_seq)
如果这里的阿雷是:
array = [-2, 12, -16, 200, 328]
这给出了序列中数组的所有数字
输出
'numbers in seq:', [-2, -16, 328]