递推与递归

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.递推求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() ...