92 lines
1.9 KiB
C++
92 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
//是否已经出现过非零数字
|
||
bool flag = false;
|
||
|
||
//数位分离递归版本[朴素版本]
|
||
void inv0(int n) {
|
||
//递归出口为当前数字n=0
|
||
if (n == 0) {
|
||
printf("\n");
|
||
return;
|
||
}
|
||
//当前位数字
|
||
int m = n % 10;
|
||
printf("%d", m);
|
||
//递归
|
||
inv0(n / 10);
|
||
}
|
||
|
||
//数位分离递归版本[朴素版本+标志优化]
|
||
void inv1(int n) {
|
||
//递归出口为当前数字n=0
|
||
if (n == 0) {
|
||
printf("\n");
|
||
return;
|
||
}
|
||
//当前位数字
|
||
int m = n % 10;
|
||
if (!flag && !m) {//没有出现过非零数字，并且，当前的数字还是0，也是不输出的
|
||
|
||
} else {//其它情况都应该输出
|
||
printf("%d", m);
|
||
flag = true;//修改标识
|
||
}
|
||
//等价变形
|
||
/*if(flag || m){
|
||
printf("%d", m);
|
||
flag = true;//修改标识
|
||
}*/
|
||
//不管当前位置数字什么情况，都要尝试下一个位置递归
|
||
inv1(n / 10);
|
||
}
|
||
|
||
//最大公约数
|
||
int gcd(int a, int b) {
|
||
if (!b) return a;
|
||
return gcd(b, a % b);
|
||
}
|
||
|
||
|
||
//斐波那契数列[画二叉树说明]
|
||
LL fib(int n) {
|
||
if (n == 1) return 1;
|
||
if (n == 2) return 1;
|
||
return fib(n - 1) + fib(n - 2);
|
||
}
|
||
|
||
//斐波那契记化搜索+递归版本
|
||
const int N = 110;
|
||
int s[N];
|
||
|
||
LL fib2(int n) {
|
||
if (n == 1) return 1;
|
||
if (n == 2) return 1;
|
||
if (!s[n - 1]) s[n - 1] = fib2(n - 1);
|
||
if (!s[n - 2]) s[n - 2] = fib2(n - 2);
|
||
return s[n - 1] + s[n - 2];
|
||
}
|
||
|
||
|
||
int main() {
|
||
//朴素版本
|
||
inv0(100);
|
||
inv0(12340567);
|
||
|
||
//朴素版本+标志优化
|
||
inv1(100);
|
||
inv1(12340567);
|
||
|
||
//测试最大公约数
|
||
cout << gcd(4, 6) << endl;
|
||
|
||
//测试斐波那契数列
|
||
cout << fib(20) << endl;
|
||
|
||
//测试斐波那契数列(记忆化搜索+递归版本)
|
||
cout << fib2(20) << endl;
|
||
return 0;
|
||
} |