演算法分析與設計考試演算法

分治—快速排序

#include<cstdio>
#include<algorithm>
#include<cstring>
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<cstdio>
#include<algorithm>
#include<cstring>
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<cstdio>
#include<algorithm>
#include<cstring>
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\n",q[1][1]);
	
	return 0;
}
/*
5
1 
2 3
3 4 5
4 5 6 7
4 6 8 2 10
*/

遞回—漢諾塔

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

遞回—最大公約數
最小公倍數可以由最大公約數來求得

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
//不用管a,b的大小關系，當a<b時，在下一次gcd時會將二者交換，使a>b
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\n",gcd(a,b));
	return 0;
}
/*
2 4
3 5
2 8
8 10
*/

遞回求斐波那契數

#include<cstdio>
#include<algorithm>
#include<cstring>
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\n",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 long\ long long long型別來存結果，求前90項，

#include<cstdio>
#include<algorithm>
#include<cstring>
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\n",f[n]);
	return 0;
}

貪心-換錢幣
換錢問題要求錢幣面值要之前存在最小2倍關系，否則則轉化為了完全背包問題
代碼如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
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\n",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<cstdio>
#include<algorithm>
#include<cstring>
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\n",ant);
	for(int i=0;i<=6;i++)
		for(int j=f[i];j>0;j--)
			printf("%d ",q[i]); 
	return 0;
 }