使用递归的数字序列
sequence of numbers using recursion
我想像这样计算数字序列:
n*(n-1)+n*(n-1)*(n-2)+n*(n-1)*(n-2)*(n-3)+n*(n-1)*(n-2)*(n-3)*(n-4)+...+n(n-1)...(n-n)
例如 n=5
总和等于 320
.
我有一个函数,计算一个元素:
int fac(int n, int s)
{
if (n > s)
return n*fac(n - 1, s);
return 1;
}
好的,没什么好写的。如果你想解决这个递归问题,我建议使用 2 种方法。 (由于 recrusiv faculty,复杂性一团糟,运行时间会随着大数而急剧增加!)
int func(int n){
return func(n, 2);
}
int func(int n, int i){
if (i < n){
return n*(fac(n-1,n-i)+func(n, i + 1));
}else return 0;
}
int fac(int i,int a){
if(i>a){
return i*fac(i-1, a);
}else return 1;
}
是这样的吗?
function fac(int n, int s)
{
if (n >= s)
return n * fac(n - 1, s);
return 1;
}
int sum = 0;
int s = 4;
n = 5;
while(s > 0)
{
sum += fac(n, s);
s--;
}
print sum; //320
无循环版本:
int fac(int n, int s)
{
if (n >= s)
return n * fac(n - 1, s);
return 1;
}
int compute(int n, int s, int sum = 0)
{
if(s > 0)
return compute(n, s - 1, sum + fac(n, s));
return sum;
}
print compute(5, 4); //320
为每个被加数重新计算阶乘非常浪费。相反,我建议使用记忆。如果您重新订购
n*(n-1) + n*(n-1)*(n-2) + n*(n-1)*(n-2)*(n-3) + n*(n-1)*(n-2)*(n-3)*...*1
你得到
n*(n-1)*(n-2)*(n-3)*...*1 + n*(n-1)*(n-2)*(n-3) + n*(n-1)*(n-2) + n*(n-1)
注意你是如何从 1..n 的乘积开始,然后加上 1..n 除以 1 的乘积,然后加上除以 1*2 的乘积,依此类推
我认为您的函数的更有效定义是(在 Python 中):
def f(n):
p = product(range(1, n+1))
sum_ = p
for i in range(1, n-1):
p /= i
sum_ += p
return sum_
这个定义的递归版本是:
def f(n):
def go(sum_, i):
if i >= n-1:
return sum_
return sum_ + go(sum_ / i, i+1)
return go(product(range(1, n+1)), 1)
最后但同样重要的是,您还可以通过使用 reduce
生成被加数列表来定义函数而无需任何显式递归(这更 'functional' -- 就像在函数式编程中一样 - - 样式):
def f(n):
summands, _ = reduce(lambda (lst, p), i: (lst + [p], p / i),
range(1, n),
([], product(range(1, n+1))))
return sum(summands)
这种风格在函数式编程语言如Haskell中非常简洁; Haskell 有一个函数调用 scanl
,它简化了加数的生成,因此定义只是:
f n = sum $ scanl (/) (product [1..n]) [1..(n-2)]
我想像这样计算数字序列:
n*(n-1)+n*(n-1)*(n-2)+n*(n-1)*(n-2)*(n-3)+n*(n-1)*(n-2)*(n-3)*(n-4)+...+n(n-1)...(n-n)
例如 n=5
总和等于 320
.
我有一个函数,计算一个元素:
int fac(int n, int s)
{
if (n > s)
return n*fac(n - 1, s);
return 1;
}
好的,没什么好写的。如果你想解决这个递归问题,我建议使用 2 种方法。 (由于 recrusiv faculty,复杂性一团糟,运行时间会随着大数而急剧增加!)
int func(int n){
return func(n, 2);
}
int func(int n, int i){
if (i < n){
return n*(fac(n-1,n-i)+func(n, i + 1));
}else return 0;
}
int fac(int i,int a){
if(i>a){
return i*fac(i-1, a);
}else return 1;
}
是这样的吗?
function fac(int n, int s)
{
if (n >= s)
return n * fac(n - 1, s);
return 1;
}
int sum = 0;
int s = 4;
n = 5;
while(s > 0)
{
sum += fac(n, s);
s--;
}
print sum; //320
无循环版本:
int fac(int n, int s)
{
if (n >= s)
return n * fac(n - 1, s);
return 1;
}
int compute(int n, int s, int sum = 0)
{
if(s > 0)
return compute(n, s - 1, sum + fac(n, s));
return sum;
}
print compute(5, 4); //320
为每个被加数重新计算阶乘非常浪费。相反,我建议使用记忆。如果您重新订购
n*(n-1) + n*(n-1)*(n-2) + n*(n-1)*(n-2)*(n-3) + n*(n-1)*(n-2)*(n-3)*...*1
你得到
n*(n-1)*(n-2)*(n-3)*...*1 + n*(n-1)*(n-2)*(n-3) + n*(n-1)*(n-2) + n*(n-1)
注意你是如何从 1..n 的乘积开始,然后加上 1..n 除以 1 的乘积,然后加上除以 1*2 的乘积,依此类推
我认为您的函数的更有效定义是(在 Python 中):
def f(n):
p = product(range(1, n+1))
sum_ = p
for i in range(1, n-1):
p /= i
sum_ += p
return sum_
这个定义的递归版本是:
def f(n):
def go(sum_, i):
if i >= n-1:
return sum_
return sum_ + go(sum_ / i, i+1)
return go(product(range(1, n+1)), 1)
最后但同样重要的是,您还可以通过使用 reduce
生成被加数列表来定义函数而无需任何显式递归(这更 'functional' -- 就像在函数式编程中一样 - - 样式):
def f(n):
summands, _ = reduce(lambda (lst, p), i: (lst + [p], p / i),
range(1, n),
([], product(range(1, n+1))))
return sum(summands)
这种风格在函数式编程语言如Haskell中非常简洁; Haskell 有一个函数调用 scanl
,它简化了加数的生成,因此定义只是:
f n = sum $ scanl (/) (product [1..n]) [1..(n-2)]