自定义函数库

求两点距离

double dis(double x1, double y1, double x2, double y2){
return sqrt(pow(x2-x1, 2)+pow(y2-y1, 2));
}

判断闰年

bool isLeapYear(int year){
return year%4==0 && year%100!=0 || year%400==0;
}

判断素数

bool isPrime(int num){
if(num<2) return false;
for(int i=2; i*i<=num; i++){
if(num%i == 0) return false; 
}
return true;
} 

埃氏筛素数

const int N=1e5+1;
bool is_prime[N];
void func(){
memset(is_prime, true, sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2; i*i<=N; i++){
if(is_prime[i]){
for(int j=i*i; j<=N; j=j+i){
is_prime[j]=false;
}
}
}
}

冒泡排序

const int N=101;
int n, arr[N];
void bubbleSort() {
for(int i=0; i<n-1; i++) {//比较趟数 
bool flag = 1;
for(int j=0; j<n-i-1; j++) { 
if(arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
flag = 0;
}
}
if(flag) break;
}
}

插入排序

const int N=101;
int n, arr[N];
void insertSort() {
for(int i=1; i<n; i++) {//arr[i]当前需要插入的元素
int base=arr[i], j; 
for(j=i-1; j>=0; j--) {
if(arr[j]>base) {
arr[j+1]=arr[j];
}else break;
}
arr[j+1]=base;
}
}

选择排序

const int N=101;
int n, arr[N];
void selectSort() {
for(int i=0; i<n-1; i++) {//i：当次排序元素应该在的位置 
int minIndex=i;
for(int j=i+1; j<n; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[minIndex], arr[i]);
}
}

归并排序

const int N=101;
int n, arr[N], tmp[N];
void mergeSort(int left, int right){
int mid=(left+right)/2;
if(left<mid) partition(left, mid);
if(mid+1<right) partition(mid+1, right);
int i=left, j=mid+1, t=0;
while(i<=mid && j<=right){
if(arr[i] < arr[j]) tmp[t++] = arr[i++];
else tmp[t++] = arr[j++];
}
while(i<=mid) tmp[t++] = arr[i++];
while(j<=right) tmp[t++] = arr[j++];
for(int i=0; i<t; i++) arr[i+left] = tmp[i];
}

快速排序

const int N=101;
int n, arr[N];
void quickSort(int left, int right){
int num = arr[left], i=left, j=right;
while(i<j){
while(i<j && arr[j]>=num)  j--;
arr[i]=arr[j];
while(i<j && arr[i]<=num)i++;
arr[j]=arr[i];
}
arr[i]=num;
if(left<i-1) quickSort(left, i-1);
if(i+1<right) quickSort(i+1, right); 
}

排列-n个数中抽m个进行全排列

const int N=10;
int n, m, arr[N], box[N]; 
bool vis[N];
void dfs(int pos){
if(pos==m){
for(int i=0; i<m; i++) cout<<box[i]<<" ";
cout<<endl;
return;
}
for(int i=0; i<n; i++){
if(!vis[i]){
vis[i]=true;
box[pos]=arr[i];
dfs(pos+1);
vis[i]=false;
}
}
}

组合-n个数中抽m个进行组合

const int N=10;
int n, m, arr[N], box[N]; 
bool vis[N];
void dfs(int idx, int pos){
if(pos==m){
for(int i=0; i<m; i++) cout<<box[i]<<" ";
cout<<endl;
return;
}
for(int i=idx; i<n; i++){
if(!vis[i]){
vis[i]=true;
box[pos]=arr[i];
dfs(i+1, pos+1);
vis[i]=false;
}
}
}

高精度数加法

string add(string a, string b) {
int lena=a.length(), lenb=b.length(), a1[1005]= {}, b1[1005]= {};
for(int i=0; i<lena; i++) a1[lena-1-i] = a[i]-'0';
for(int i=0; i<lenb; i++) b1[lenb-1-i] = b[i]-'0';
int lenc=lena>lenb?lena:lenb, c1[1005]= {}, carry=0;
for(int i=0; i<lenc; i++) {
c1[i]=a1[i]+b1[i]+carry;
carry=c1[i]/10;
c1[i]%=10;
}
if(carry>0) c1[lenc++]=carry;
string res="";
for(int i=lenc-1; i>=0; i--) res += c1[i]+'0';
return res;
}

高精度数减法

string sub(string a, string b) {
bool f=true; //标记a和b的大小关系，默认a大 
int lena=a.length(), lenb=b.length();
if(lena<lenb || lena==lenb && a<b){
f=false;
swap(a, b);
swap(lena, lenb);
} 
int a1[1005]= {}, b1[1005]= {};
for(int i=0; i<lena; i++) a1[lena-1-i] = a[i]-'0';
for(int i=0; i<lenb; i++) b1[lenb-1-i] = b[i]-'0';
int c1[1005]= {}, lenc=lena;
for(int i=0; i<lenc; i++) {
if(a1[i]<b1[i]){
a1[i+1]--;
a1[i]+=10;
} 
c1[i]=a1[i]-b1[i];
}
while(lenc>1 && c1[lenc-1]==0) lenc--; 
string res="";
if(f==false) res+='-';
for(int i=lenc-1; i>=0; i--) res += c1[i]+'0';
return res;
}

高精度数乘法，大数乘大数

string mul1(string a, string b) {
int lena=a.length(), lenb=b.length(), a1[1005]= {}, b1[1005]= {};
for(int i=0; i<lena; i++) a1[lena-1-i] = a[i]-'0';
for(int i=0; i<lenb; i++) b1[lenb-1-i] = b[i]-'0';
int lenc=lena+lenb, c1[2005]= {}, carry;
for(int i=0; i<lenb; i++) {
carry=0;
for(int j=0; j<lena; j++) {
c1[i+j]+=a1[j]*b1[i]+carry;
carry = c1[i+j]/10;
c1[i+j]%=10;
}
c1[i+lena]=carry;
}
while(lenc>1 && c1[lenc-1]==0) lenc--;
//保存运算结果
string res="";
for(int i=lenc-1; i>=0; i--) res += c1[i]+'0';
return res;
}

高精度数乘法，大数乘小数

string mul2(string a, int b){
    int lena=a.length(), a1[1005]={};
    for(int i=0; i<lena; i++) a1[lena-1-i]=a[i]-'0';
    int lenc=lena, c1[2005]={}, carry=0;
    for(int i=0; i<lenc; i++){
        c1[i] = a1[i]*b+carry;
        carry = c1[i]/10;
        c1[i] %= 10;
    }
    while(carry){
        c1[lenc++]=carry%10;
        carry/=10;
    }
string res="";
    for(int i=lenc-1; i>=0; i--) res+=c1[i]+'0';
    return res;
}

原文地址：https://blog.csdn.net/yuyanjingtao/article/details/144361351

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！