递推与递归

顺序表综合操作 线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储与计算机内， 要求设计一个算法完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相互交换，若找不到则将其插入表中并使表中元素仍然递增有序 1.二分查找递归12345678910111213141516171819202122232425#include "preset.h"//有序顺序表查找（二分查找）递归写法int binSearch(SqList sql, int target, int low, int high) { if (low > high) return -1; int mid = (low + high) / 2; cout << "low : " << low << " high : " << high << " mid : " << mid << endl; if (target == sql.elem[mid]) { return mid; } else if (target < sql.elem[mid]) { high = mid - 1; binSearch(sql, target, low, high); } else { low = mid + 1; binSearch(sql, target, low, high); }}int main() { SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7}; cout << "current List:" << endl; print(sql); int target; cin >> target; cout << binSearch(sql, target, 0 ...

爬楼梯 原题链接：https://leetcode.cn/problems/climbing-stairs/ 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 1.递推与递归==思路==：简单的递推问题（斐波那契数列） 到达第一阶梯的方法数为1 到达第二阶梯的方法数为1 到达第三阶梯的方法数为 第一阶梯的方法数 + 第二阶梯的方法数 …… 到达第n阶梯的方法数为 第 n - 1 阶梯的方法数 + 第 n - 2 阶梯的方法数 ans[i] = ans[i - 1] + ans[i - 2]; 1234567891011121314class Solution {public: int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; int ans[2] = {1, 2}; int a = 0, b = 1; for (int i = 3; i <= n; ++i) { ans[a] += ans[b]; swap(a, b); } return ans[b]; }};

onlineJ杨氏矩阵 原题链接：http://oj.haizeix.com/problem/600 题目描述 给定一个n行m列的二维矩阵和一个目标数t， 二维矩阵中对于每一行从左到右不下降(右边的数≥左边的数)，对于每一列从上到下不下降(下边的数≥上边的数)。 现要在数组中找到目标数t，并输出其所在位置的行数和列数。 输入 第一行两个整数n, m（1 ≤ n, m ≤ 3000） 接下来输入一个二维矩阵，矩阵内所有数均小于 200000。 最后输入一个整数t（1 ≤ t ≤ 200000） 输出 输出用空格隔开的数表示位置（从1开始计数），答案有唯一解。 123453 41 2 3 45 6 15 207 10 20 2515 12 3 1.暴力法：==思路==： 使用两个for循环对矩阵进行遍历操作，当遍历到target值时输出其行、列的下标值。 12345678910111213141516171819202122232425#include<iostream>using namespace std;int n, m, target;int num[3005][3005];int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &num[i][j]); } } scanf("%d", &target); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (num[i][j] == target) { printf("%d %d\n", i, j); return 0; ...

数塔问题 1.onlineJ43：数塔问题 原题链接：http://oj.haizeix.com/problem/43 有一个由数字组成的三角形数塔，站在上一层的某个点，只能到达其下方左右的两个点。现在请找到一条从上到下的路径，使得路径上所有数字相加之和最大 1.递推法从上向下求和 由数塔中到达任意一点的数字和sum = 左上方数字和suml or 右上方数字和sumr + 该数字数值num 知到达该点最大和为ans[x][y] = max(ans[x - 1][y - 1], ans[x - 1][y]) + num[x][y]==关键== 遍历最后一行，找出最大的数字即为结果 12345678910111213141516171819202122232425262728#include<iostream>#include<cstdio>using namespace std;int n;int num[1005][1005];int main(){ scanf("%d", &n); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ scanf("%d", &num[i][j]); } } //1.从两个方向取数值大的方向max(num[i - 1][j - 1], num[i - 1][j]); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ num[i][j] += max(num[i - 1][j - 1], num[i - 1][j]); } } int ans = 0; //2.遍历最后一行，找出最大的数字即为结果 for(int i = 1; i <= n; ++i){ ans = max(a ...

Lattice paths Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid? 1.递推法递推法：dp[x][y] = dp[x - 1][y] + dp[x][y - 1] 网格中到达任意一点的路径方案数 = 正上方方案数 + 正下方方案数:dp[x][y] = dp[x - 1][y] + dp[x][y - 1] 递推边界为左上角点（1，1）,结果为右下角点坐标（4，4） 定义循环(i, j)需要从点(1, 1)点开始 这样外边界有一圈保护0，不需要判断边界、不用考虑数组越界问题（数字0不会影响答案） 12345678910111213141516171819#include<iostream>using namespace std;long long ans[25][25];int main(){ for(int i = 1; i <= 21; ++i){ for(int j = 1; j <= 21; ++j){ //初始化左上角点的值为(1, 1) if(i == 1 && j == 1){ ans[i][j] = 1; continue; } ans[i][j] = ans[i - 1][j] + ans[i][j - 1]; } } cout << ans[21][21] << endl; return 0;} 2.组合问题123456789101112#include<iostream>using namespac ...

1000-digit Fibonacci number The Fibonacci sequence is defined by the recurrence relation：Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. Hence the first 12 terms will be: F1 = 1F2 = 1F3 = 2F4 = 3F5 = 5F6 = 8F7 = 13F8 = 21F9 = 34F10 = 55F11 = 89F12 = 144 The 12th term, F12, is the first term to contain three digits. What is the index of the first term in the Fibonacci sequence to contain 1000 digits? 1.大整数加法将两个数组循环相加——用指针将数组的地址作为函数参数传递到函数中，通过交换二维数组第一个下标交换数组地址 123456789101112131415161718192021222324252627282930313233343536373839404142/*思路：大整数加法 + 循环使用两个变量求fib数列1.将大整数加法封装在一个函数中2.循环使用两个变量(数组)求斐波那契数列项3.当出现某一项大于1000时，输出项数结束循环*/#include<iostream>using namespace std;//1.将大整数加法封装在一个函数中void func(int *n1, int *n2){ //注意：初始的n2可能比n1短，需要首先更新答案的长度 n2[0] = n1[0]; for(int i = 1; i <= n2[0]; ++i){ n2[i] += n1[i]; if(n2[i] > 9){ n2[i + 1] += n2[i] / 10; n2[i] %= ...

斐波那契数列的递推与递归求法 斐波那契数列求法：递推（从前向后计算）、递归（从后向前计算），递归由于重复计算导致计算速度很慢——记忆化数组解决 1.递推求Fibonacci：1234567891011121314#include<iostream>using namespace std;long long num[50] = {1, 1};int main(){ for(int i = 2; i < 50; ++i ){ num[i] = num[i - 1] + num[i - 2]; } for(int i = 1; i < 50; ++i){ cout << i << " : " << num[i] << endl; } return 0;} 2.递归求Fibonacci：1234567891011121314151617#include<iostream>using namespace std;long long func(int x){ if(x == 0 || x == 1){ return 1; } return func(x - 1) + func(x - 2);}int main(){ for(int i = 1; i < 50; ++i){ cout << i << " : " << func(i) << endl; } return 0;} 注意：可以看到这里利用递归法求斐波那契数列在进行到30项时，每一项的运算时间已经达到秒级 3.递归求Fibonacci（记忆化数组优化）： 递归法中存在的大量重复计算导致递归递归太深、运算速度降低，可以使用记忆数组优化程序 定义一个记忆化数组用于存储运算过程中的中间值 当发现数字没有计算过，将数字计算一遍并将其存入数组中 当发现数字 ...

Even Fibonacci numbers Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. 1.利用数组求fib数列 开一个足够大的数组，并初始化前两项1，2 通过递推法逐个将斐波那契数列的每一项存入数组 将所有为偶数的项的数字相加 1234567891011121314151617181920212223#include<iostream>using namespace std;long long num[4000005] = {1, 2};int main(){ long long sum = 0; int i = 2; //1.利用递推法求出斐波那契数列的每一项，并存入数组中 while(num[i - 1] <= 4000000){ num[i] = num[i - 1] + num[i - 2]; i++; } //2.对数组每一项进行判断，若为偶数将其加入sum中 for(int j = 0; j < i; j++){ if(num[j] % 2 == 0){ sum += num[j]; } } cout << sum; return 0;}//空间复杂度:O(n) 2.两个变量求fib数列 不需要定义数组，在运算的过程中就可以知道哪些项是偶数 计算过程中只保留两个数字：前一个数 和 后一个数，两个数循环相加即可 123 ...

Longest Collatz sequence The following iterative sequence is defined for the set of positive integers: n → n/2 (n is even)n → 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain? NOTE: Once the chain starts the terms are allowed to go above one million. 1.函数递归调用12345678910111213141516171819202122232425262728293031/*思路:简单递归1.if x == 1, return 1;2.if x == odd, return (3n + 1);3.if x == even, return (n / 2);*/#include<iostream>using namespace std;int func(int x){ if(x == 1){ return 1; } if(x % 2 == 0){ return func(x / 2) + 1; } return func(3 * x + 1) + 1; }int main() ...