アルゴリズム分析と設計試験アルゴリズム

≪分治｜Division｜Eas≫-≪クイック・ソート｜Quick Sort｜Eas≫

#include
#include
#include
using namespace std;
const int N=1e5+10;
int tmp[N];
int n;
void quick_sort(int l,int r)
{
     
	if(l>=r) return;
	int mod=tmp[l+r>>1],i=l-1,j=r+1;
	while(i<j)
	{
     
		do i++;while(tmp[i]<mod);
		do j--;while(tmp[j]>mod);
		if(i<j) swap(tmp[i],tmp[j]);
	}
	quick_sort(l,j);
	quick_sort(j+1,r);
}
int main()
{
     
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&tmp[i]);
	quick_sort(0,n-1);
	for(int i=0;i<n;i++) printf("%d ",tmp[i]);
	
	return 0;
}
/*
5
1 3 2 5 4
*/

分割-集計ソート

#include
#include
#include
using namespace std;
const int N=1e5+10;
int tmp[N];
int q[N];
void merge(int l,int r)
{
     
	if(l>=r) return;
	int mod=l+r>>1;
	merge(l,mod);
	merge(mod+1,r);
	int i=l,j=mod+1,k=0;
	while(i<=mod&&j<=r)
		if(tmp[i]<=tmp[j]) q[k++]=tmp[i++];
		else q[k++]=tmp[j++];
	while(i<=mod) q[k++]=tmp[i++];
	while(j<=r) q[k++]=tmp[j++];
	for(int i=0,j=l;i<k;i++,j++) tmp[j]=q[i];
}
int main()
{
     
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&tmp[i]);
	merge(0,n-1);
	for(int i=0;i<n;i++) printf("%d ",tmp[i]);
	return 0;
}

動的計画——数塔

#include
#include
#include
using namespace std;
const int N=1e3+10;
int q[N][N];
int n;
int main()
{
     
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&q[i][j]);
	for(int i=n-1;i>=1;i--)
		for(int j=1;j<=i;j++)
			q[i][j]=max(q[i+1][j],q[i+1][j+1])+q[i][j];
	printf("%d
",q[1][1]);
	
	return 0;
}
/*
5
1 
2 3
3 4 5
4 5 6 7
4 6 8 2 10
*/

再帰-ハノタ

#include
#include
#include
using namespace std;
void move(int n,char A,char B,char C)
{
     
	if(n==1)
		printf("%c-->%c
",A,C);
	else 
	{
     
		move(n-1,A,C,B);
		printf("%c-->%c
",A,C);
		move(n-1,B,A,C);
		printf("%c-->%c
",A,C);
	}
}
int main()
{
     
	int n;
	scanf("%d",&n);
	move(n,'A','B','C');
	
	return 0;
}

再帰-最大公約数の最小公倍数は最大公約数から求めることができる

#include
#include
#include
using namespace std;
//   a,b     ， ab
int gcd(int a,int b)
{
     
	return b?gcd(b,a%b):a;//       ，  b!=0
}
int main()
{
     
	int a,b;
	scanf("%d %d",&a,&b);
	printf("%d
",gcd(a,b));
	return 0;
}
/*
2 4
3 5
2 8
8 10
*/

フィボナッチ数を再帰的に求める

#include
#include
#include
using namespace std;
int f(int n)
{
     
	if(n==1||n==2)
		return 1;
	else return f(n-1)+f(n-2);
}
int main()
{
     
	int n;
	scanf("%d",&n);
	printf("%d
",f(n));
	return 0;
}
//1 1 2 3 5 8 13 21

非再帰的なフィボナッチフィボナッチ数は90回目のときに1 0 18 10^{18}1018を超えるので、l o n g l o n g longlong longタイプで結果を保存し、前90項を求める.

#include
#include
#include
using namespace std;
typedef long long ll;
const int N=100;
ll f[N];
void init()
{
     
	f[1]=1;
	f[2]=1;
	for(int i=3;i<=90;i++) f[i]=f[i-1]+f[i-2];
}
int main()
{
     
	int n;
	init();
	scanf("%d",&n);
	printf("%lld
",f[n]);
	return 0;
}

貪欲-両替問題では、両替額が前に最小2倍の関係があることが要求されます.そうしないと、完全なリュックサック問題コードに変換されます.

#include
#include
#include
using namespace std;
int q[10]={
     100,50,20,10,5,1};//     
int f[10];//          ，     ，   0 
int main()
{
     
	int n;
	int ant=0;
	scanf("%d",&n);//     
	for(int i=0;i<6;i++)
		while(n>=q[i])
		{
     
			n-=q[i];
			f[i]++;
			ant++;
		 }
	printf("    %d
",ant);
	for(int i=0;i<6;i++)
		for(int j=f[i];j>0;j--)
			printf("%d ",q[i]); 
	return 0;
 } 
/*
620
60
74
*/

#include
#include
#include
using namespace std;
int q[10]={
     100,50,20,10,5,2,1};
int f[10];//          ，     ，   0 
int main()
{
     
	int n;
	int ant=0;
	scanf("%d",&n);//     
	for(int i=0;i<=6;i++)
	{
     
		f[i]=n/q[i];//    ，    
		ant+=f[i];
		n=n-n/q[i]*q[i];
	}
	printf("    %d
",ant);
	for(int i=0;i<=6;i++)
		for(int j=f[i];j>0;j--)
			printf("%d ",q[i]); 
	return 0;
 }