杭州做网站哪里好,做网站路由器映射外网,手机域名注册被骗,做网站费用走什么科目递推算法及常见示例#xff08;C、Python实现#xff09; 递推算法是一种用若干步可重复运算来描述复杂问题的方法#xff0c;它是一种序列计算中的常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次…递推算法及常见示例C、Python实现 递推算法是一种用若干步可重复运算来描述复杂问题的方法它是一种序列计算中的常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复该算法利用了计算机速度快和不知疲倦的机器特点。递推关系通常表示为一种递推公式。
下面是一些常见的例子。
★斐波那契数列斐波那契数列指的是这样一个数列01123581321345589...
这个数列从第3项开始每一项都等于前两项之和。
斐波那契数列是一种经典的递推问题它的定义是f(0)0f(1)1f(n)f(n-1)f(n-2)。通过这个递推关系式可以求解斐波那契数列的第 n 项。
☆C实现
#include iostream
using namespace std; int main() { int n; cout 请输入项数 n 的值 ; cin n; if (n 1) { return n; } int f1 0, f2 1, fn; for (int i 2; i n; i) { fn f1 f2; f1 f2; f2 fn; } cout 斐波那契数列的第 n 项为 fn endl; return 0;
}下面改用使用自定义函数实现
#include iostream
using namespace std; int fibonacci(int n) { if (n 1) { return n; } int f1 0, f2 1, fn; for (int i 2; i n; i) { fn f1 f2; f1 f2; f2 fn; } return fn;
} int main() { int n; cout 请输入项数 n 的值 ; cin n; cout 斐波那契数列的第 n 项为 fibonacci(n) endl; return 0;
}☆Python实现
n int(input(请输入 n 的值))
if n 1: fn nf1, f2 0, 1 for i in range(2, n1): fn f1 f2 f1, f2 f2, fnprint(斐波那契数列的第 {} 项为{}.format(n, fn))下面改用使用自定义函数实现
def fibonacci(n): if n 1: return nf1, f2 0, 1 for i in range(2, n1): fn f1 f2 f1, f2 f2, fn return fn n int(input(请输入 n 的值))
print(斐波那契数列的第 {} 项为{}.format(n, fibonacci(n)))★等差数列求和 1, 3, 5, 7, 9 是一个公差为 2 的等差数列。等差数列的求和问题可以通过递推算法解决。设等差数列的首项为 a1公差为 d第 n 项为 an则 ana1(n-1)d。要求等差数列的前 n 项和可以递推得到Sna1a2...ann/2[2a1(n-1)d]。
☆C实现
#include iostream
using namespace std;int main() { int a1, d, n; cout 输入第一项、公差和项数; cin a1 d n; int sum 0; for (int i 1; i n; i) { sum a1 (i - 1) * d; } cout 等差数列的前 n 项和为 sum endl; return 0;
}☆Python实现
a1 int(input(输入第一项: ))
d int(input(输入公差: ))
n int(input(输入项数: ))
sum 0
for i in range(1, n1): sum a1 (i - 1) * dprint(等差数列的前 {} 项和为{}.format(n,sum)) ★等比数列求和1, 2, 4, 8, 16 是一个公比为 2 的等比数列。等比数列的求和问题也可以通过递推算法解决。设等比数列的首项为 a1公比为 r第 n 项为 an则 ana1r^(n-1)。要求等比数列的前 n 项和可以递推得到Sna1(1-r^n)/(1-r)。
☆C实现
#include iostream
#include cmath // 引入 pow()
using namespace std;int main() { double a1, r, n; cout 输入第一项、公比和项数; cin a1 r n; double sum 0; for (int i 1; i n; i) { sum a1 * pow(r, i - 1); } cout 等比数列的前 n 项和为 sum endl; return 0;
}☆Python实现
a1 float(input(输入第一项))
r float(input(输入公比))
n int(input(输入项数)) sum 0
for i in range(1, n 1): sum a1 * (r ** (i - 1)) print(等比数列的前 {} 项和为{}.format(n, sum))附、递推、递归和迭代区别
递推是通过已知序列元素来计算其他元素递归是函数调用自身迭代是通过重复执行操作来解决问题。
递归和迭代可参见https://blog.csdn.net/cnds123/article/details/132409886
