【校課筆記】演算法設計與分析

09-13

【校課筆記】演算法設計與分析

來自專欄一隻怪猴的的研究報告

實驗一

1、棋盤覆蓋問題

在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用4種不同形態的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。

#include <iostream>
#include <stdio.h>
using namespace std;

int Board[100][100];
int tile = 1;
void ChessBoard(int tr, int tc, int dr, int dc, int size)//trtc左上角方格 drdc特殊方格
{
if(size == 1) return;
int t = tile ++, s = size / 2;
//覆蓋左上角棋盤
if(dr < tr + s && dc < tc + s)//特殊方格在此棋盤中
ChessBoard(tr, tc, dr, dc, s);
else {//此棋盤中無特殊方格

Board[tr + s - 1][tc + s - 1] = t;
ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
}
//右上角
if(dr < tr + s && dc >= tc + s)
ChessBoard(tr, tc + s, dr, dc, s);
else {
Board[tr + s - 1][tc + s] = t;
ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
}

//左下角
if(dr >= tr + s && dc < tc + s)
ChessBoard(tr + s,tc, dr, dc, s);
else {
Board[tr+s][tc+s-1] = t;
ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
}
//右下角
if(dr >= tr + s && dc >= tc + s)
ChessBoard(tr + s,tc + s, dr, dc, s);

else {
Board[tr+s][tc+s] = t;
ChessBoard(tr + s, tc + s, tr + s ,tc + s, s);
}
}
int main()
{
int x, y, size;
cin>>size>>x>>y;
Board[x][y] = 0;

ChessBoard(1, 1, x, y, size);
for(int i = 1;i <= size;i ++)
{
for(int j = 1;j <= size; j++)
{
printf("%2d ",Board[i][j]);
}
cout<<endl;
}
return 0;

}

2、合併排序問題

對n個元素組成的序列進行排序。

基本思想：將待排序元素分成大小大致相同的兩個子集合，分別對兩個集合進行排序，最終將排序好的子集合合併成所要求的排好序的集合。

#include <iostream>
#include <stdio.h>
using namespace std;
int b[100];
void Merge(int c[], int d[], int l, int m, int r)//合併到d
{
int i = l, j = m + 1, k = 1;

while((i <= m) && (j <= r))
if(c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
if(i > m)
for(int q = j; q <= r; q++)
d[k++] = c[q];
else
for (int q = i;q <= m; q++)
d[k++] = c[q];
}

void Copy(int a[], int b[], int left, int right)
{
int j=1;
for(int i = left; i<= right;i ++) {
a[i]= b[j];
j++;
}
}
void MergeSort(int a[], int left, int right)
{

if(left < right) {
int i = (left + right) / 2;
MergeSort(a, left, i);
MergeSort(a, i + 1, right);
Merge(a, b, left, i, right);
Copy(a, b, left, right);
}
}
int main()
{
int n, a[100],b[100];
cin>>n;
for(int i = 1;i <= n; i ++)
{
cin>>a[i];
}
MergeSort(a, 1, n);
for(int j = 1;j <= n;j ++)
{
printf("%d ",a[j]);
}
return 0;
}

3、集合最大元問題

在規模為n的數據元素集合中找出最大元。當n=2時，一次比較就可以找出兩個數據元素的最大元和最小元。當n>2時，可以把n個數據元素分為大致相等的兩半，一半有n/2個數據元素，而另一半有n/2個數據元素。先分別找出各自組中的最大元，然後將兩個最大元進行比較，就可得n個元素的最大元。

#include <iostream>
using namespace std;
int max(int a,int b){
return (a>b) ? a:b ;
}
int findMax(int a[],int l,int r){
int max1=0, max2=0;
if(l==r)
return a[l];//返回a[r]一樣
if(l==r-1)
return max(a[l],a[r]);
else{
int i=(l+r)/2;
max1= findMax(a,l,i);
max2= findMax(a,i+1,r);
return max(max1,max2);
}
}
int main()
{
int n, a[100];
cin>>n;
for(int i = 0;i < n; i ++)
cin>>a[i];
cout<<findMax(a,0,n-1);
return 0;
}