【BT的课堂作业~】

1、完成以下C语言代码，贴在自己的博客。

a、写一个插入排序的函数，即输入一个数组，完成排序；

b、完成一个函数，输入值为整数，输出该值的二进制。

c、完成一个判断整数是否素数的函数，即，输入一个整数，判断其是否素数。

d、编辑一个数学公式：a的立方 + b的立方 = c的立方

1.a、写一个插入排序的函数，即输入一个数组，完成排序

#include<iostream>
using namespace std;
#include<vector>

template<typename T>
vector<T>MyArraySort(vector<T>& lst, bool (*match)(const T& A,const T& B) = nullptr, bool reverse = false) {//可以放入match函数A<B返回真则获得升序。默认升序
	//二分排序
	vector<T>rst;
	vector<vector<int>>stk;//stack的意思，作为栈临时存储
	stk.push_back(vector<int>());
	for (auto i = lst.size(); i--;)//初始化stk。直接储存T的话，复制之类的操作代价有些大，所以存储索引
		stk.back().push_back(i);

	auto Match = [&match,&lst,&reverse](int a, int b)->bool{//为了方便，写一个比较函数，lst[a]小于lst[b]则返回真^reverse
		if (match == nullptr ? (lst[a] <= lst[b]) : (match(lst[a], lst[b]))) {
			if (match == nullptr ? (lst[b] <= lst[a]) : (match(lst[b], lst[a])))
				return false;
			return true ^ reverse;
		}
		return false ^ reverse;
	};

	int isMiddle = 1;//判断stk.back()装的数是不是中间数的。当这值为0时为中间数。每次将数组二分，或者成功装入中间数数组后，isMiddle会赋予1的值。在消耗长度小于2的非中间数数组时isMiddle会减1
	while (stk.empty() == false) {
		auto curr = stk.back();//获取要二分的数组
		stk.pop_back();
		if (isMiddle == 0) {
			for (auto i = curr.size(); i--;)
				rst.push_back(lst[curr[0]]);
			isMiddle = 2;//重新装填
			continue;
		}
		if (curr.size() <= 2) {//如果该数组不足3，那就单独处理
			if (curr.size() == 1) //长度1直接压入
				rst.push_back(lst[curr[0]]);
			else if(curr.size()==2){//长度2比较后压入
				if (Match(curr[0], curr[1])) {
					rst.push_back(lst[curr[0]]);
					rst.push_back(lst[curr[1]]);
				}
				else {
					rst.push_back(lst[curr[1]]);
					rst.push_back(lst[curr[0]]);
				}
			}
			--isMiddle;
		}
		else {//数组长度3以上，二分处理
			auto mid = curr[int(curr.size() / 2)];//选一个中间数
			vector<int> left;
			vector<int>middle;
			vector<int>right;
			for (auto ptr = curr.begin(); ptr != curr.end();++ptr) {
				if (Match(*ptr,mid))
					left.push_back(*ptr);
				else if (lst[mid]==lst[*ptr])
					middle.push_back(*ptr);
				else
					right.push_back(*ptr);
			}
			stk.push_back(right);
			stk.push_back(middle);
			stk.push_back(left);
			isMiddle = 1;//装填1
		}
	}
	return rst;
}

int main() {
	vector<int> lst{1,2,3,4,3,2,3,4,5,6,7,6,5,4,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1};//初始化
	auto rst = MyArraySort<int>(lst, [](const int& a,const int& b)->bool {return a >= b; },true);
	for (auto i = rst.begin(); i != rst.end(); ++i)
		cout << *i;//输出结果：11222333334444455556666777889
	return 0;
}

2.b、完成一个函数，输入值为整数，输出该值的二进制。

#include<iostream>
using namespace std;
#include<string>

string Int_BCD(unsigned num) {
	string rst;
	while (num != 0) {
		rst.push_back(num&1?'1':'0');
		num >>= 1;
	}
	return string(rst.rbegin(),rst.rend());
}

int main() {
	cout << Int_BCD(12345);//输出结果：11000000111001
	return 0;
}

c、完成一个判断整数是否素数的函数，即，输入一个整数，判断其是否素数。

#include<iostream>
using namespace std;
#include<vector>

bool IsPrime(unsigned num) {
	static vector<unsigned> Index{2};
	static unsigned Pointer = 3;

	if (num == 1)//另类首先排除掉
		return false;
	unsigned border = sqrt(num);
	for (; Pointer <= border;++Pointer) {//补充Pointer~border之间的质数
		bool flag = true;
		for (auto i = Index.begin(); i != Index.end(); ++i) {
			if (Pointer % *i == 0) {
				flag = false;
				break;
			}
		}
		if (flag) 
			Index.push_back(Pointer);
	}
	for (auto i = Index.begin(); i != Index.end(); ++i) {
		if (num == *i)
			return true;
		if (num%*i==0)
			return false;
	}
	return true;
}


int main() {
	for (int i = 0; i < 100; ++i) {
		if (IsPrime(i))
			cout << i <<' ';//输出结果：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
	}
	return 0;
}

d、编辑一个数学公式：a的立方 + b的立方 = c的立方

//题目意义不详，pass