实验一

二分查找

#include<iostream>
using namespace std;
int a[10000+10];
bool BinarySearch(int s,int e,int v);
int main(){
	int n,m,v;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>v;
		if(BinarySearch(0,n-1,v))cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}
bool BinarySearch(int s,int e,int v){
	if(s==e){
		return a[s]==v;
	}
	else{
		int mid=(s+e)/2;
		if(a[mid]==v)return true;
		else if(a[mid]<v)return BinarySearch(mid+1,e,v);
		else if(a[mid]>v)return BinarySearch(s,mid,v);
	}
}

归并排序

#include<iostream>
using namespace std;
int a[10000+10],b[10000+10];
void MergeSort(int s,int e);
void Merge(int s,int m,int e);
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	MergeSort(0,n-1);
	for(int i=0;i<n;i++){
		cout<<a[i]<<endl;
	}
	return 0;
}
void Merge(int s,int m,int e){
	int i=s,j=m,k=s;
	while(i<m&&j<=e){
		while(a[i]<=a[j]&&i<m&&j<=e){
			b[k++]=a[i++];
		}
		while(a[j]<=a[i]&&i<m&&j<=e){
			b[k++]=a[j++];
		} 
	}
	while(i<m){
		b[k++]=a[i++];
	}
	while(j<=e){
		b[k++]=a[j++];
	}
	for(int r=s;r<=e;r++){
		a[r]=b[r];
	}
}
void MergeSort(int s,int e){
	if(s==e)return;
	else{
		int mid=(s+e)/2;
		MergeSort(s,mid);
		MergeSort(mid+1,e);
		Merge(s,mid+1,e);
	}
}

快速排序

#include<iostream>
using namespace std;
int a[10000+10];
void Qsort(int s,int e);
int divide(int s,int e);
void Swap(int& a,int& b);
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	Qsort(0,n-1);
	for(int i=0;i<n;i++){
		cout<<a[i]<<endl;
	}
	return 0;
}
void Swap(int& a,int& b){
	int t=a;a=b;b=t;
}
int divide(int s,int e){
	int v=a[s],i=s+1,j=e;
	while(i<j){
		while(i<j&&a[i]<=v){
			i++;
		}
		while(i<j&&a[j]>=v){
			j--;
		}
		Swap(a[i],a[j]);
	}
	if(a[i]<=v){
		Swap(a[i],a[s]);
		return i;
	}
	else{
		Swap(a[i-1],a[s]);
		return i-1;
	} 
}
void Qsort(int s,int e){
	if(s>=e)return;
	else{
		int q=divide(s,e);
		Qsort(s,q-1);
		Qsort(q+1,e);
	}
}

穷举n位二进制数

#include<iostream>
using namespace std;
int n;
int a[25];
void make(int m);
int main(){
	cin>>n;
	make(0);
	return 0;
}
void make(int m){//已经填了m位，也就是下标为m-1的地方填好了，要填m位 
	if(m==n){
		for(int i=0;i<n;i++){
			cout<<a[i];
		}
		cout<<endl;
	}
	else{
		for(int i=0;i<=1;i++){
			a[m]=i;
			make(m+1); 
		}
	}
}

穷举所有排列（交换法）

#include<iostream>
using namespace std;
int n;
int a[15]; 
void Swap(int& a,int& b);
void make(int m);
int main(){
	cin>>n;
	for(int i=0;i<n;i++)a[i]=i;
	make(0);
	return 0;
}
void Swap(int& a,int& b){
	int t=a;a=b;b=t;
}
void make(int m){//已经填了m个字母也就是说下标为m-1已经填好了，要填第m个 
	if((m+1)==n){
		for(int i=0;i<n;i++){
			cout<<char('a'+a[i]);
		}
		cout<<endl;
	}
	else{
		for(int i=m;i<n;i++){
			Swap(a[i],a[m]);
			make(m+1);
			Swap(a[i],a[m]);
		}
	}
}

穷举所有排列

#include<iostream>
using namespace std;
int n;
int a[15]; 
void make(int m);
int main(){
	cin>>n;
	make(0);
	return 0;
}
void make(int m){//已经填了m个字母也就是说下标为m-1已经填好了，要填第m个 
	if(m==n){
		for(int i=0;i<n;i++){
			cout<<char('a'+a[i]);
		}
		cout<<endl;
	}
	else{
		for(int i=0;i<n;i++){
			int flag=1;
			for(int j=0;j<m;j++){
				if(a[j]==i){
					flag=0;
					break;
				}
			}
			if(flag){
				a[m]=i;
				make(m+1);
			}
		}
	}
}

求第k小数

#include<iostream>
using namespace std;
int a[10000+10];
int search(int s,int e,int k);
int divide(int s,int e);
void Swap(int& a,int& b);
int main(){
	int n,k;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cin>>k;
	cout<<search(0,n-1,k)<<endl;
	return 0;
}
void Swap(int & a,int & b){
	int t=a;a=b;b=t;
}
int divide(int s,int e){
	int v=a[s],i=s+1,j=e;
	while(i<j){
		while(i<j&&a[i]<=v){
			i++;
		}
		while(i<j&&a[j]>=v){
			j--;
		}
		Swap(a[i],a[j]);
	}
	if(a[i]<=v){
		Swap(a[i],a[s]);
		return i;
	}
	else if(a[i]>v){
		Swap(a[i-1],a[s]);
		return i-1;
	}
}
int search(int s,int e,int k){
	if(s==e)return a[s];
	else{
		int q=divide(s,e);
		if(q-s+1==k)return a[q];
		else if(q-s+1>k)return search(s,q-1,k);
		else if(q-s+1<k)return search(q+1,e,k-(q-s+1));
	}
}

循环赛日程表

#include<iostream>
using namespace std;
int a[128+10][128+10];
void bmake(int s,int e);
int main(){
	int n;
	cin>>n;
	n=1<<n;
	for(int i=1;i<=n;i++){
		a[i][1]=i;
	}
	bmake(1,n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++){
			cout<<a[i][j]<<' ';
		}
		cout<<a[i][n]<<endl;
	}
	return 0;
}
void bmake(int s,int e){
	if(s+1==e){
		a[s][2]=e;
		a[e][2]=s;
	}
	else{
		int m=(s+e)/2;
		bmake(s,m);
		bmake(m+1,e);
		for(int i=0;i<=m-s;i++){
			for(int j=0;j<=m-s;j++){
				a[m+1+i][2+m-s+j]=a[s+i][1+j];
				a[s+i][2+m-s+j]=a[m+1+i][1+j];
			}
		}
	}
}

走迷宫

#include<iostream>
using namespace std;
int a[25][25];
int m,n;
int s,t,c,d;
void dfs(int x,int y){
	a[x][y]=-1;
	if(x==c&&y==d){
		cout<<"Yes"<<endl;
		return;
	}
	else{
		if(x-1>=0&&a[x-1][y]!=1&&a[x-1][y]!=-1){
			dfs(x-1,y);
		}
		if(y+1<n&&a[x][y+1]!=1&&a[x][y+1]!=-1){
			dfs(x,y+1);
		}
		if(x+1<m&&a[x+1][y]!=1&&a[x+1][y]!=-1){
			dfs(x+1,y);
		}
		if(y-1>=0&&a[x][y-1]!=1&&a[x][y-1]!=-1){
			dfs(x,y-1);
		}
	}
}
int main(){
	cin>>m>>n;
	cin>>s>>t>>c>>d;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	dfs(s,t);
	if(a[c][d]!=-1)cout<<"No"<<endl;
	return 0;
}