算法Studying

C++算法

1 高精度

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

1.1 高精度加法

• 基本逻辑实现原理

#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 高精度减法

• 退位 + 负数

#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 高精度乘法

• 进位累加

#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 高精度除低精度

• 按位取余

#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就是答案

#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;;
}

总结

• 高精度运算其实就是按照字符串到数组的逻辑，按位次求出。四种运算逻辑略有不同，万变不离其宗。

高精度四种运算总和

#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 冒泡排序

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

代码如下:

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 选择排序

• 选择排序我看来是优化版的冒泡排序，选择排序解决了冒泡每轮都要交换顺序的过程
• 找出一个最大值或者最小值，直接交换。再往后找

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的位置++。
• 最后按小到大输出即可。

//计数排序
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 桶排序