基本算法
基本算法
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;
} 