C++算法

1 高精度

  • 使用字符型转整数数组实现防止long或者int这种数据类型的位数限制导致的精度丢失。

1.1 高精度加法

  • 基本逻辑实现原理
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
#include <iostream>
using namespace std;
int a[101],b[101],c[101];
string s1, s2;
/*高精度加法*/
void strtoint(string str,int dec[]) {
	//倒序
	for (int i = 0; i < str.size(); i++)
	{
		dec[str.size() - i-1] = str[i] - '0';
	}
}
int main() {
	while (true)
	{
		cin >> s1 >> s2;
		strtoint(s1, a);
		strtoint(s2, b);
		int la = s1.size();
		int lb = s2.size();
		int lc = max(la, lb) + 1;
		//对位相加
		for (int i = 0; i <= lc; i++)
		{
			c[i] = a[i] + b[i] + c[i];//
			c[i + 1] = c[i] / 10;
			c[i] = c[i] % 10;
		}
		//去除0
		while (lc > 1 && c[lc] == 0) lc--;
		//倒序打印
		for (int i = lc; i >= 0; i--)
		{
			cout << c[i];
		}
	}
	return 0;
}

1.2 高精度减法

  • 退位 + 负数
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
#include<iostream>
using namespace std;
//倒序 字符串转位整型数组
void strtoint(string str, int dec[]) {
		for (int i = 0; i < str.size(); i++)
		{
			dec[str.size() - i - 1] = str[i] - '0';
		}
}
//判断减数和被减数大小
bool cmpstr(string s1, string s2) {
	if (s1.size() > s2.size())
	{
		return true;
	}
	return s1 >= s2;
}
string s1, s2;
int a[101], b[101], c[101];
int main() {
	//4321
    //765
	//766
	cin >> s1 >> s2;
	//判断结果正负
	if (!cmpstr(s1, s2))
	{
		swap(s1, s2);//交换s1和s2
		cout << "-";
	}
	strtoint(s1, a);
	strtoint(s2, b);
	int lc = max(s1.size(), s2.size());
	for (int i = 0; i < lc; i++)
	{
		if (a[i] < b[i]) {
			a[i + 1]--;
			a[i] += 10;
		}
		c[i] = a[i] - b[i];
	}
	//去0
	while (c[lc]==0&&lc>1) lc--;
	for (int i = lc; i >= 0; i--) cout << c[i];
	
	return 0;
}

1.3 高精度乘法

  • 进位累加
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
#include<iostream>
using namespace std;
//倒序 字符串转位整型数组
static void strtoint(string str, int *dec) {
		for (int i = 0; i < str.size(); i++)
		{
			dec[str.size() - i] = str[i] - '0';
		}
}
string s1, s2;
int a[101], b[101], c[101];
int main() {
	//  1234 ai
	//    56 bj
	//  7404
	// 6170
	//c[i+j-1] = a[i]*b[j]+a[i-1]b[j+1]
	cin >> s1 >> s2;
	strtoint(s1, a);
	strtoint(s2, b);
	int la = s1.size(), lb = s2.size();
	int lc = la + lb;
	for (int i = 1; i <= la; i++)
	{
		for (int j = 1; j <= lb; j++)
		{
			c[i + j - 1] += a[i] * b[j];
			c[i + j] += c[i + j - 1] / 10;
			c[i + j - 1] %= 10;
		}
	}
	//去0
	while (c[lc] == 0 && lc > 1) lc--;
	for (int i = lc; i >= 1; i--) cout << c[i];
	return 0;
}

1.4 高精度除法

1.4.1 高精度除低精度

  • 按位取余
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
#include<iostream>
using namespace std;
string s1;
long b;
int a[101], c[101];
int tmp;
static void strtoint(string str, int* dec) {
	for (int i = 0; i < str.size(); i++)
	{
		dec[i+1] = str[i] - '0';
	}
}
int main() {
	cin >> s1;
	cin >> b;
	int la = s1.size();
	strtoint(s1, a);
	for (int i = 1; i <= la; i++)
	{
		c[i] = (tmp*10 + a[i])/ b;
		tmp = (tmp * 10 + a[i]) % b;//余数
	}
	int lc=0;
	while (c[lc]==0&&lc<la) lc++;
	for (int i = lc; i <= la; i++) cout << c[i];
	cout << endl << "余数:" << tmp;
	return 0;
}

1.4.2 高精度除高精度

  • 利用减法，来做，除数-X个被减数补位后 记录X就是答案
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
79
80
81
82
83
#include<iostream>
using namespace std;
//倒序
void strtoint(string str,int dec[]) {
	dec[0] = str.size();//记录长度
	for (int i = 0; i < dec[0]; i++)
	{
		dec[str.size() - i] = str[i] - '0';
	}
}
//打印c
void printC(int *c) {	
	while (c[c[0]] == 0 && c[0] > 1) c[0]--;
	for (int i = c[0]; i >= 1; i--) cout << c[i];
	//除数比被除数大打印0
	if (c[0] <= 0)
	{
		cout << c[0];
	}
}
//交换数组
void swapIntList(int * a, int * b) {
	int temp= *a;
	*a = *b;
	*b = temp;
}
//补0  221 3
void numcpy(int p[],int q[],int len) {
	//将p数组移动len位到q数组  221 
	for (int i = 1; i <= p[0]; i++) {
		q[i +len-1] = p[i]; //50021
	}
	q[0] = p[0] + len;
}//判断a数组和b大小
int compare(int x[], int y[]) { //返回1 x>y 返回-1 x<y
	if (x[0] > y[0]) return 1;
	if (x[0] < y[0]) return -1;
	for (int i = x[0]; i > 0; i--)
	{
		if (x[i] > y[i]) return 1;
		if (x[i] < y[i]) return -1;
	}
	return 0;
}
//相减
void minu(int a[],int b[]) {
	for (int i = 1; i <= a[0]; i++)
	{
		if (a[i] < b[i]) {
			a[i + 1]--;
			a[i] += 10;
		}
		a[i] -= b[i];
	}
	while (a[a[0]]==0 && a[0] >0)
	{
		a[0]--;
	}
}
int a[301], b[301], c[301];
int tmp[301];
string s1,s2;
int main() {
	cin >> s1 >> s2; //1234  12
	strtoint(s1,a); //44321
	strtoint(s2,b); //221
	c[0] = a[0] - b[0] + 1; //3
	
	for (int i = c[0]; i >=1; i--)
	{   
		memset(tmp, 0, sizeof(tmp)); //设置tmp元素全为0
		numcpy(b, tmp, i); //将b补0和tmp一样 tmp : 
		while (compare(a,tmp)>=0)
		{
			c[i]++;
			minu(a, tmp); //a-tmp
		}
	}
	printC(c);
	cout << endl;
	printC(a);
	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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<iostream>
using namespace std;
int a[300] = {}, b[300] = {}, c[300] = {}, tmp[300] = {};
//字符串倒序转整数数组
//数组
void strReverseToInt(string str,int dec[]) {
	dec[0] = str.size();//记录数字长度
	for (int i = 1; i <= str.size(); i++) {
		dec[dec[0]-i+1] = str[i-1]-'0';
	}
}
void printReverse(int *dec) {
	while (dec[0] > 0 && dec[dec[0]] == 0)
	{
		dec[0]--;
	}
	for (int i = dec[0]; i >= 1; i--)
	{
		cout << dec[i];
	}
}
int* addstring(string s1, string s2) {
	strReverseToInt(s1, a);
	strReverseToInt(s2, b);
	c[0] = max(a[0], b[0]) + 1;
	for (int i = 1; i <= c[0]; i++) {
		c[i] = a[i] + b[i] + c[i];
		c[i + 1] = c[i] / 10;
		c[i] %= 10;
	}
	return c;
}
//高精度减法
int* minu(string s1, string s2) {
	//判断s1-s2正负
	if (s1<s2)
	{
		s1.swap(s2);//交换s1 s2
		cout << "-";//加-号
	}
	strReverseToInt(s1, a);
	strReverseToInt(s2, b);
	c[0] = max(a[0],b[0]);
	for (int i = 1; i <= c[0]; i++)
	{
		if (a[i]<b[i] )
		{
			c[i] += 10;
			c[i + 1]--;
		}
		c[i] = a[i] - b[i];
	}
	return c;
}
//高精度乘法
int* multiply(string s1, string s2) {
	//1234 a4a3a2a1
	//0012 b2b1
	// 2468 c[i+j-1] += (a[i] * b[j]) % 10
	//12340
	//14808
	strReverseToInt(s1, a);
	strReverseToInt(s2, b);
	c[0] = a[0]+b[0];
	for (int i = 1; i <= a[0]; i++)
	{
		for (int j = 1;  j <= b[0];  j++)
		{
			c[i + j - 1] += (a[i] * b[j])%10;
			c[i + j] += c[i + j - 1] / 10;
			c[i + j - 1] %= 10;
		}
	}
	return c;
}
//补0
void numcpy(int p[],int q[],int num) {
	//p : 221
	//q : 40021
	q[0] = p[0] + num;
	for (int i = 1; i <=p[0]; i++)
	{
		q[i+num] = p[i]; 
	}
}
//比较数组大小
int compare(int x[], int y[]) { //返回1 x>y 返回-1 x<y
	if (x[0] > y[0]) return 1;
	if (x[0] < y[0]) return -1;
	for (int i = x[0]; i > 0; i--)
	{
		if (x[i] > y[i]) return 1;
		if (x[i] < y[i]) return -1;
	}
	return 0;
}
//数组相减
void minu(int a[], int b[]) {
	for (int i = 1; i <= a[0]; i++)
	{
		if (a[i] < b[i]) {
			a[i + 1]--;
			a[i] += 10;
		}
		a[i] -= b[i];
	}
	while (a[a[0]] == 0 && a[0] > 0)
	{
		a[0]--;
	}
}
//高精/高精
//4321
//12
//4321-c1200
int* divide(string s1, string s2) {
	strReverseToInt(s1, a);//1234
	strReverseToInt(s2, b);//12
	c[0] = a[0]-b[0]+1; //3
	for (int i = c[0]; i >= 1; i--)
	{
		numcpy(b, tmp, i - 1);//补0操作
		while (compare(a,tmp)>=0)//a>=tmp
		{
			minu(a, tmp);
			c[i]++;
		}
	}
	return c;
}
int main() {
	string s1, s2;
	cin >> s1 >> s2;
	//int *res = addstring(s1, s2); //加法
	//int* res = minu(s1, s2); //减法
	//int* res = multiply(s1, s2); //乘法
	//int* res = divide(s1, s2);
	//printReverse(res);
	return 0;
}

2 排序

2.1 冒泡排序

  • 冒泡原理就是沉底，是每轮排序将最大的值放到最后面
  • 遍历数组，从小到大，如果遇到后面的数比该数小，交换位置，这样每次可以将一个最大值放到最后。
  • 因为已经放了一个排好的最大值在最后了，所以第二次遍历的时候，就可以少遍历一位

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(int a[], int len) {
	int temp;
	bool res;
	for (int i = 0; i < len-1; i++)
	{
		res=true; //如果一轮啥变化也没有 说明已经拍好
		for (int j = 0; j < len-i-1; j++)
		{
			if (a[j] > a[j+1])
			{
				swap(a[j], a[j + 1]);
				res = false;
			}
		}
		if (res) break; //提前中断
	}
}

2.2 选择排序

  • 选择排序我看来是优化版的冒泡排序，选择排序解决了冒泡每轮都要交换顺序的过程
  • 找出一个最大值或者最小值，直接交换。再往后找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void selectSort(int a[],int len) {
	int temp,min,tmp;
	for (int i = 0; i < len; i++)
	{
		min = i;
		temp = a[i];
		for (int j = i + 1; j < len; j++)
		{
			if (temp > a[j])
			{
				temp = a[j];
				min = j;
			}
		}
		if (min != i)
		{
			tmp = a[i];
			a[i] = a[min];
			a[min] = tmp;
		}
	}
}

2.3 计数排序

  • 计数排序主要是用到了数组的下标 比如9出现在一次就在下标9的位置++。
  • 最后按小到大输出即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//计数排序
void countSort(int a[],int len) {
	int max = 0;
	int tmp[101] = {};
	for (int i = 0; i < len; i++)
	{
		if (max < a[i]) max = a[i];
	}
	for (int i = 0; i < len; i++)
	{
		tmp[a[i]]++;
	}
	for (int i = 0; i <= max; i++)
	{
		for (int j = 0; j < tmp[i]; ++j)
		{
			cout << i << " ";
		}
	}

2.4 桶排序

数据结构

栈（Stack）

1、顺序栈的定义

  • 堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈遵循“后进先出”（Last In First Out，LIFO）的原则，即最后一个被放入栈中的元素总是第一个被取出。
  • 先进入栈的元素在底部，接着进去的在底部上面一个位置，出栈的时候从栈顶取。类似于自动步枪的弹夹，最先进入弹匣的，是最后射出的。

2、栈的特点

  1. 栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的
  2. 栈有三个基础操作压入(push),弹出(pop),取数(getTop)操作都为 O(1)时间
  3. 栈有一个计数器 counter 或栈顶指针

3、栈的基本操作

  1. 建栈（init）：在使用栈之前，首先需要建立一个空栈，称建栈；

  2. 压栈（push）：往栈顶加入一个新元素，称进栈（压栈）；

  3. 出栈（pop）：删除栈顶元素，称出栈（退栈、弹出）；

  4. 取栈顶（gettop）：查看当前的栈顶元素，称读栈；

  5. 测试栈（empty）在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试 栈；

  6. 显示栈（display）：输出栈的所有元素；

  7. 释放栈（setnull）：清空栈；

4、栈的操作代码

初始化、入栈、出栈、显示栈！

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
#include <iostream> 
#define size 3//常量：栈的长度
using namespace std;
int stack[size];//数组模拟栈 int top = -1;//初始化栈指针
//入栈
void push(int value){
    if(top == MAXN - 1){
    	cout<<"栈满"<<endl;
        return;
    }
    top++;
    stack[top] = value;
}
//出栈
int pop(){
    if(top == -1){
        cout<<"栈空！"<<endl;
        return;
    }
    top--;
}

//显示栈
void display(){
    int i;
    for(i = top;i >= 0;i--){
    	cout<<stack[i]<<" ";
    }
    cout<<endl;
}

int main(){
    int order;//指令 int x,t;
    cout<<"输入指令："; 
    while(1 == 1){
        cout<<"1:入栈,2:出栈,3:显示栈!"<<endl; cin>>order;
        if(order == 1){
            cin>>x;
            push(x);
            display();
        }else if(order == 2){
            t = pop();
            if(t != -1){
                cout<<t<<"出栈!"<<endl; display();
            }
        }else if(order == 3){
            display();
        }
	}
	return 0; 
}