基本算法

1.欧里几德算法求最大公约数(辗转相除法)

include<bits/stdc++.h>

using namespace std;
int a,b,c;//求a,b的最大公约数

int main()
{
    cin>>a>>b;//可以直接使用__gcd(a,b)求出a,b的最大公约数
    while(b>0)
    {
        c=a%b;
        a=b;
        b=c;
    }
    cout<<a;
}

2.筛选法求素数

#include<bits/stdc++.h>

using namespace std;
int n,a[100010];//筛选法求出1,n之间的所有素数

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) a[i]=1;
    a[0]=a[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(a[i]==1)
        {
            for(int j=i*2;j<=n;j+=i) a[j]=0;
        }
    }
    for(int i=0;i<=n;i++)
    {
        if(a[i]==1) cout<<i<<" ";
    }
    return 0;
}

3.康托展开

//给出一个1~n的全排列中的某一个，求它是按字典序排列的第几个。
#include<bits/stdc++.h>

using namespace std;
int n,t,ans,vis[21],p[21]={1,1};

int main()
{
    for(int i=2;i<=20;i++) p[i]=p[i-1]*i;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t;
        vis[t]=1;
        int k=0;
        for(int j=1;j<t;j++)
        {
            if(vis[j]==0) k++;
        }
        ans+=k*p[n-i];
    }
    cout<<ans+1<<endl;
    return 0;
}

4.逆康托展开

int  fac[] = {1,1,2,6,24,120,720,5040,40320};
//康托展开的逆运算,{1...n}的全排列，中的第k个数为s[]
void reverse_kangtuo(int n,int k,char s[])
{
    int i, j, t, vst[8]={0};
    --k;
    for (i=0; i<n; i++)
    {
        t = k/fac[n-i-1];
        for (j=1; j<=n; j++)
            if (!vst[j])
            {
                if (t == 0) break;
                --t;
            }
        s[i] = '0'+j;
        vst[j] = 1;
        k %= fac[n-i-1];
    }
}

5.同余定理

1)a≡a(mod d)

2)a≡b(mod d)→b≡a(mod d)

3)(a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),b≡m(mod d),则

4)a+b≡x+m （mod d）

5)a-b≡x-m (mod d)

6)a*b≡x*m (mod d )

7）当d为素数时 若ab≡0 mod(d) 则有 a or b≡0 mod(d)

6.次方求模

1）将幂拆解为多个底数的平方次的积；

2）如果指数为偶数，把指数除以2，并让底数的平方次取余；

3）如果指数为奇数，就把多出来的底数记录下来，再执行偶数次操作。

int PowerMod(int a,int b,int c)//a的b次方对c取模
{
    int ans=1;
    a=a%c;
    while(b>0)
    {
        if(b%2==1) ans=(ans*a)%c;
        b=b/2;
        a=(a*a)%c;
    }
    ans%=c;
    return ans;
}

7.三角形面积

//海伦公式(注意S和p都用double)
//三角形三边为a,b,c,p=1.0/2*(a+b+c)[半周长],S为面积
//S=sqrt(p*(p-a)*(p-b)*(p-c))

#include<bits/stdc++.h>

using namespace std;
int a,b,c;
double p,S;

int main()
{
    cin>>a>>b>>c;
    p=(a+b+c)/2.0;
    S=sqrt(p*(p-a)*(p-b)*(p-c));
    cout<<S<<endl;
    return 0;
}

8.三点顺序(顺时针or逆时针)

//利用矢量叉积右手定理
//1.四指指向a向量方向（右手垂直于平面）
//2.四指朝向b向量弯曲（注意弯曲方向的夹角要小于180°）
//3.大拇指指向为a*b的方向
//即叉积向上>0为逆时针，向下<0为顺时针

#include<bits/stdc++.h>

using namespace std;
int x1,y1,x2,y2,x3,y3;

int main()
{
    while(cin>>x1>>y1>>x2>>y2>>x3>>y3)
    {
        if(x1==0&&y1==0&&x2==0&&y2==0&&x3==0&&y3==0) break;
        int A=x2-x1;
        int B=y2-y1;
        int C=x3-x1;
        int D=y3-y1;
        if(A*D-B*C>0) cout<<"逆时针"<<endl;
        else cout<<"顺时针"<<endl;
    }
    return 0;
}

9.二分查找

//在a[]中查找key所在的位置
#include<bits/stdc++.h>

using namespace std;

int BinSearch(int a[],int len,int key)
{
    int low=0;
    int high=len-1;
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(key==a[mid]) return mid;
        else if(key>a[mid]) low=mid+1;
        else high=mid-1;
    }
    return -1;
}

int main()
{
    int key;
    cin>>key;
    int a[]={1,2,3,4,5,6,7,8,9,10,11};
    int len=sizeof(a)/sizeof(a[0]);
    int ans=BinSearch(a,len,key);
    cout<<ans;
    return 0;
}

10.冒泡排序

#include<bits/stdc++.h>

using namespace std;

void bubble_sort(int a[],int n)
{
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<n-i-1;j++)
            if(a[j]>a[j+1])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
    }
}

int main()
{
    int a[10];
    for(int i=0;i<10;i++) cin>>a[i];
    bubble_sort(a,10);
    for(int i=0;i<10;i++) cout<<a[i]<<" ";
    return 0;
}

11.插入排序

#include<bits/stdc++.h>

using namespace std;

void insert_sort(int a[],int n)
{
    int i,j;
    for(i=1;i<n;i++)
    {
        for(j=i-1;j>=0;j--)
            if(a[i]>a[j]) break;
        if(j!=i-1)
        {
            int temp=a[i];
            for(int k=i-1;k>j;k--) a[k+1]=a[k];
            a[j+1] =temp;
        }
    }
}

int main()
{
    int a[10];
    for(int i=0;i<10;i++) cin>>a[i];
    insert_sort(a,10);
    for(int i=0;i<10;i++) cout<<a[i]<<" ";
    return 0;
}