爬楼梯（小数据方式+大数据方式）

先给一个链接爬楼梯–leetcode

1.解题思路

1. 第一层楼梯有一种方式，即走一个格子
2. 第二层楼梯有两种方式，第一种方式是走两个一层阶梯，第二种方案是一次走两层
3. 从第三层开始，走到第n层的方案数等于走到前一层的方案数+走到前两层的方案数

2.当n很小的时候的代码

#include
using namespace std;
const int N=55;
int f[N];

int main()
{	
	int n;
	cin>>n;
	if(n==1)  //特判1
	{
		cout<<1;
		return 0;
	}
	if(n==2)  //特判2
	{
		cout<<2;
		return 0;
	}
	f[1]=1,f[2]=2;   //初始化条件一定要准确
	for(int i=3;i<=n;i++)
	{
		f[i]=f[i-1]+f[i-2];  //第i层的方案数等于第i-1层的方案数加上第i-2层的方案数
	}
	cout<<f[n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

实际上，可以发现，f数组有序的数据永远是f[i-1]和f[i-2]。那么可以考虑节省一点空间。

#include
using namespace std;
int f[2];

int main()
{	
	int n;
	cin>>n;
	if(n==1)  //特判1
	{
		cout<<1;
		return 0;
	}
	if(n==2)  //特判2
	{
		cout<<2;
		return 0;
	}
	f[0]=1,f[1]=2;   //初始化条件一定要准确
	for(int i=2;i<n;i++)
	{
		f[i%2]=f[(i-1)%2]+f[(i-2)%2];  //第i层的方案数等于第i-1层的方案数加上第i-2层的方案数
	}
	cout<<f[(n-1)%2];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.当n很大的时候的代码

由于当n数据很大的时候，代码会报错，原因是int类型存储的数据不够大。所以使用高精度加法。
先写一个高精度模板

#include
#include
#include
using namespace std;

//高精度加法
const int N = 10000;
char a[N];
char b[N];
char c[N];

int count(char* p)
{
	int sum = 0;
	while (*p != '\0')
	{
		sum++;
		p++;
	}	
	return sum;
}

void add(char *a,char *b,int n)
{
	int toNext = 0;  //进入下一位的数（比如8+9=17，进1到下一位）
	int i;
	for (i = 0; i < n; i++)
	{
		c[i] = (a[i] + b[i] + toNext) % 10;
		toNext = (a[i] + b[i] + toNext) / 10;
		
	}
	//注意一下，可能会有进位
	if (toNext > 0)
		c[i++]=toNext;
	cout << "输出c:";
	for (int j = i-1;j>=0; j--)  //逆序输出
	{
		printf("%d", c[j]);
	}
}


int main()
{
	cout << "输入两个数相加：";
	cin >> a >> b;
	//字符串要翻转一下，低位在前面
	//判断一下a，b哪个大，哪个大那个放上面
	int na = count(a);   //计算a的长度
	int nb = count(b);   //计算b的长度
	for (int i = 0; i < na / 2; i++)   //翻转字符串，顺便将字符变成数字，但是注意当字符串是奇数的时候中间的字符没有变成数字
	{
		int temp = a[i]-'0';
		a[i] = a[na - i-1] - '0';
		a[na - i-1] = temp;
	}
	if (na % 2)
		a[na / 2] -= '0';
	for (int i = 0; i < nb / 2; i++)
	{
		int temp =b[i] - '0';
		b[i] = b[nb - i - 1] - '0';
		b[nb - i - 1] = temp;
	}
	if (nb % 2)
		b[nb / 2] -= '0';
	if (na >= nb)
		add(a, b,na);
	else
		add(b, a,nb);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

上面的模板只是一个思路，其实实际使用的时候可以简单一点
结合题目：

#include
#include
using namespace std;

const int N = 100000;

int a[N];
int b[N];
int c[N];
int f[N];
int Maxlen = 1;
void add(int* a, int* b,int *c)
{
	//位数长度永远满足a>b
	//Maxlen保留最长长度
	int i;
	int toNext = 0;
	for (i = 1; i <= Maxlen; i++)
	{
		c[i] = (a[i] + b[i] + toNext) % 10;
		toNext = (a[i] + b[i] + toNext) / 10;
	}
	if (toNext > 0)
		c[i++] = toNext;
	Maxlen = i-1;
}

int main()
{
	int n;
	cin >> n;
	if (n == 1)
	{
		cout << 1;
		return 0;
	}
	if (n == 2)
	{
		cout << 2;
		return 0;
	}
	a[1] = 1;  //表示前i-2层的方案数
	b[1] = 2; //表示前i-1层的方案数
	for (int i = 3; i <= n; i++) //a b c a b c 
	{
		if (i % 3 == 0)
			add(b,a,c);
		if (i % 3 == 1)
			add(c,b,a);
		if (i % 3 == 2)
			add(a,c,b);
	}
	cout << "高精度：";
	if (n % 3 == 0)
	{
		for (int i = Maxlen; i >= 1; i--)
			cout << c[i];
	}
	if (n % 3 == 1)
	{
		for (int i = Maxlen; i >= 1; i--)
			cout << a[i];
	}
	if (n % 3 == 2)
	{
		for (int i = Maxlen; i >= 1; i--)
			cout << b[i];
	}

	cout << endl<<endl;
	cout << "低精度：";
	f[1] = 1;
	f[2] = 2;
	for (int i = 3; i <= n; i++)
		f[i] = f[i - 1] + f[i - 2];
	cout << f[n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78