0826-C01递归递推

1. 进制转换问题

#if 0
13
32 16 8 4 2 1
#endif

#include <bits/stdc++.h>
#include <stack>
using namespace std;

int main(){
	int n; cin >> n;
	stack<int> stk;
	
	while (n){
		stk.push(n%2);
		n /= 2;
	} 
	
	while (stk.size()) {
		cout<<stk.top();
		stk.pop();
	}
	
	return 0; 
}

#if 0
int main() {
	int i=1, a[1005] = {};
	int n; cin>>n;
	
	while (n){
		a[i++] = n%2;
		n/=2;
	} 
	for(--i; i>=1; i--) cout<<a[i]; 

	return 0;
}
#endif
	

递归方法

#include <bits/stdc++.h>
#include<stack>
using namespace std;
void f(int x)
{
	if(x==0) return;
	f(x/2);
	cout<<x%2;
}
int main()
{
	int n;
	cin>>n;
	f(n);
	return 0;
}

2. 递归

#include <bits/stdc++.h>
using namespace std;

void f(int x){
	if(x>1000) return;	//1递归出口 

	f(x+1); 			//2.递归表达式 
	cout << x << ' ';		
} 

int main() {
	f(1); 

	return 0;
}

#if 0

f(x) = 
1.递归出口(最简单的时候)
f(1) = 1 

2.递归表达式

f(5)
=5*f(4) 
=5*4*f(3)
=5*4*3*f(2)
=5*4*3*2*f(1)
=5*4*3*2*1
=5*4*3*2
=5*4*6
=5*24
=120
#endif 

3. 欧几里得算法

#include <bits/stdc++.h>
using namespace std;

int main() {
	cout << __gcd(104, 80) << endl; 
	

	return 0;
}

#if 0
欧几里得算法(辗转相除法)
求GCD(最大公约数)

104 80
104 / 80 = 1 ... 24
80 / 24 = 3 ... 8
24 / 8 = 3 ... 0
gcd = 8; 

将较大数字除以较小数字, 若余数为0 ,则除数为最大公约数
不为0则继续按照以规则相除:
将原来的除数变为被除数,余数变为除数,继续相除法,
直到余数为0, 则除数为最大公约数. 
#endif 

4. 格式化输入输出

#include <bits/stdc++.h>
using namespace std;

/*
1999:10:1
2009:10:1
*/
int main() {
	
	int y, m, d;
	scanf("%d:%d:%d", &y, &m, &d);
	printf("年份:%d\n月份:%d\n,天数:%d\n", y, m, d); 
	
//	int n; 
//	cin >> n;
//	cout << n << endl;
//	
//	scanf("%d", &n);	//&取地址
//	printf("这个数字是%c!\n输出完毕!", n);	//格式化输出 

	return 0;
}


#if 0
	转义字符,改变原来的含义
	\n, 换行
	\t, tab, 制表符
	\a, 响铃 
	\r, return, 1234\r56 
	\\
	\"

	ASCII, 
	American Standard Code for Information Interchange，
	美国信息交换标准代码
	'a' = 97
	'A' = 65
	'0' = 48
	' ' = 32 

	C语言格式化输入输出 
	 
	占位符 %d(int); %c(char); %lf(double); %f(float), %lld(long long) 
	scanf();
	printf()
#endif 

#include <bits/stdc++.h>
using namespace std;

int main() {
	
	cout << (int)'w' << endl; 
	
	cout << "老师说:\"下课了!\"" << endl; 
	
	cout << "\\\\\\" << endl;

	return 0;
}

5. 汉诺塔1

#include <bits/stdc++.h>
using namespace std;

//将n个圆盘从a柱借助b柱移动到c柱 
void hanoi(int n, char a, char b, char c) {
	//1.递归出口
	if (1 == n) {
		printf("%c -> %c\n", a, c); 
		return ;
	}
	 
	//2.递归表达式 
	hanoi(n-1, a, c, b);
	printf("%c -> %c\n", a, c);
	hanoi(n-1, b, a, c); 
}

int main() {
	int n; cin >> n;
	hanoi(n, 'A', 'B', 'C');
	
	return 0;
}

6. 汉诺塔2

	#include <bits/stdc++.h>
	using namespace std;
	
	//将n个圆盘从a柱借助c柱移动到b柱 
	void hanoi(int n, char a, char b, char c) {
		//1.递归出口
		if (1 == n) {
			printf("%c->%d->%c\n", a, n, b); 		//直接从a, b 
			return ;
		}
		 
		//2.递归表达式 
		hanoi(n-1, a, c, b);		//n 
		printf("%c->%d->%c\n", a, n, b);
		hanoi(n-1, c, b, a); 
	}
	
	int main() {
		int n; 
		char a, b, c;
		cin >> n >> a >> b >> c; 
		hanoi(n, a, b, c);
		
		return 0;
	}

https://www.acgo.cn/problemset/info/452

7. 递归与递推的区别

/*
递归:大量的重复计算,导致效率极低，时间复杂度较大
递推: 使用数组存储已经计算的结果, 大大减少了计算的时间

2^31 - 1 (int)
2^63 - 1 (long long)
*/

#include <bits/stdc++.h>
using namespace std;

long long dp[100005] = {0, 1, 1}; 

long long f(int x){
	if(1==x || 2==x) return 1;
	return f(x-1) + f(x-2); 
} 

int main() {
	
	for (int i=3; ;i++){
//		printf("第%d项: %lld\n", i, f(i)); 
		
		dp[i] = dp[i-1] + dp[i-2]; 
		printf("第%d项: %lld\n", i, dp[i]); 
	} 
	return 0;
}