是基础算法！

WPY

发布于：2019年8月11日

C++学习

一些基础的算法。

最大公约数gcd

~~开挂法~~：__gcd(a,b);~~STL大法好！！！(震耳欲聋)~~

int gcd(int a,int b)
{
  	if(b==0) return a;
  	return gcd(b,a%b);
}

最大公约数与最小公倍数的关系gcd(a,b)*lcm(a,b)=ab

素数判断

简单法

暴力~~超时见祖宗~~

bool pand(int x) //x>=3
{
  	for(int i=2; i*i<=x; i++)
  			if(x%i==0) return 0;
  	return 1;
}

筛法

<1>取最小的素数2，筛去它的所有倍数

<2>取未被筛最小的数（一定是素数），再筛去它的所有倍数

<3>重复<2>直至全部都是素数（取最小数只需到 sqrt(n) ）

bool isprime[N]
int n,ans=0;
int main()
{
  	memset(isprime,1,sizeof(isprime));
  	cin>>n;
  	isprime[1]=0;
  	for(int i=2; i<=sqrt(n); i++) //生成
    		if(isprime[i]) for(int k=i*i; k<=n; k+=i) isprime[k]=0;
  	for(int i=2; i<=n; i++) //输出
      	if(isprime[i]) {ans++; cout<<i<<" ";}
    cout<<endl<<ans<<endl;
 		return 0;
}

排序

选择排序

for(int i=1; i<=n-1; i++)
 	 for(int j=i+1; j<=n; j++)
    	if(a[i]>a[j]) t=a[j],a[j]=a[i],a[i]=t;

冒泡排序

对于接近有序的数列，加标记可以缩短排序时间

for(int i=n-1; i>=1; i--){
  	int p=0;
  	for(int k=1; k<=i; k++)
      	if(d[k]>d[k+1]) swap(d[k+1],d[k]),p=1;
    if(!p) break;
}

插入排序

for(int i=2; i<=n; i++){
  	int p=a[i];
  	for(int k=i; k>1 && p<a[k-1]; k--) a[k]=a[k-1];
  	a[k]=p;
}

快排

sort(a+1,a+n+1,cmp);~~STL大法好！！！(再次破音)~~

//手写快排
void sort(int l,int r)
{
  	int x=l,y=r,mid=a[(l+r)/2]; //mid:取一个数
  	do{
    		while(a[i]<mid) x++; //左边起比mid小的数不动，x停在不比mid小的位子
      	while(mid<a[y]) y--; //右边起比mid大的数不动，y停在不比mid大的位子
      	if(x<=y) swap(a[x],a[y]),x++,y--; //如果x与y不交叉，交换x与y的数，x与y各再跳一步
  	}while(x<=y); //直至x与y交叉；mid已经在交叉的位置了
  	if(l<y) qsort(l,y); //左边还有数(l<y),递归
   	if(x<r) qsort(x,r); //右边还有数(x<r),递归
}

归并排序

把两个已经有序的序列，归并成一个有序的序列

归并排序不会像快排那样蜕化为o(n2),最好和最坏的情况都是o(nlog2n)

void merge_sort(int l,int r)
{
		if(l!=r){
    		int mid=(l+r)/2;
    		merge_sort(l,mid);
    		merge_sort(mid+1,r);
      	merge(l,mid,r);
  	}
}

void merge(int p,int q,int r)
{
  	int tt=p,tl=p,tr=q+1; //tt是tmp的指针，tl和tr是两个待合并有序序列的指针
  	while(tt<=r){
   	 		if(tl<=q && (tr>r || a[tl]<a[tr])) tmp[tt++]=a[tl++];  //tl还有元素，tr已经没有元素或tr指的元素较大
     		else tmp[tt++]=a[tr++]; //除上述情况的其他情况
    }
    for(int i=p;i<=r;i++) a[i]=tmp[i]; //在tmp[]合并好后要搬到a[]中
}

二分

a[ ]已经排序

递归算法

bool find(int x,int l,int r) //x为要查找的数
{
  	if(l>r) return 0;
  	int mid=(l+r)/2;
  	if(x==a[mid]) return 1;
  	if(x<a[mid]) return find(x,l,mid-1);
  	if(x>a[mid]) return find(x,mid+1,r);
}

非递归算法

bool find(int x,int l,int r)
{
  	while(l<=r){
    		int mid=(l+r)/2;
      	if(x==mid) return 1;
      	if(x<a[mid]) r=mid-1;
      	else l=mid+1;
  	}
}

快速幂

//输出：ans%p
ans=1,a%=p;
while(b){
  	if(b%2==1) ans=(ans*a)%p;
  	a=(a*a)%p;
  	b>>1;
}
cout<<ans<<endl;