高效算法设计_递归与分治（棋盘覆盖问题，循环日程表，巨人与鬼）

递归与分治

棋盘覆盖问题

题目：有一个2^k*2^k的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖，且任意一个白色方格不能

同时被两个或更多牌覆盖。下面是L型牌的4种旋转方式。

[][]—— [][]—— []——— []
[] ———[]—— [][]— —[][]
(1)——(2) —— (3)—— (4)

思路：

分治：划分，递归求解（递归边界，k=1时一块牌就够了），合并。 (信了他的邪！)

---

左上角（r1,c1)
|——(r1+half_size-1,c1+half_size-1) |(r1+half_size,c1+half_size-1)
|——————————————中心点————————————
|——(r1+half_size,c1+half_size-1) | (r1+half_size,c1+half_size)

---

输入：

输出：

#include <stdio.h>

#define BOARD_SIZE 4
int board[BOARD_SIZE][BOARD_SIZE];
int g_domino_num;

// c1, r1: 棋盘左上角的行号和列号
// c2, r2: 特殊方格的行号和列号
// size = 2 ^ k
void chessboard(int r1, int c1, int r2, int c2, int size)//提前手算好要不要-1非常重要。
{
    if(1 == size) return;
    int half_size;
    int d = g_domino_num++;
    half_size = size / 2;

    if(r2 < r1 + half_size && c2 < c1 + half_size) //特殊方格在左上角子棋盘
    {
       chessboard(r1, c1, r2, c2, half_size);
    }
    else   // 不在此棋盘，将此棋盘右下角设为相应的骨牌号
    {
       board[r1 + half_size - 1][c1 + half_size - 1] = d;
       chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size);
    }

    if(r2 < r1 + half_size && c2 >= c1 + half_size) //特殊方格在右上角子棋盘
    {
       chessboard(r1, c1 + half_size, r2, c2, half_size);
    }
    else  // 不在此棋盘，将此棋盘左下角设为相应的骨牌号
    {
       board[r1 + half_size - 1][c1 + half_size] = d;
       chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size);
    }

    if(r2 >= r1 + half_size && c2 < c1 + half_size) //特殊方格在左下角子棋盘
    {
       chessboard(r1 + half_size, c1, r2, c2, half_size);
    }
    else  // 不在此棋盘，将此棋盘右上角设为相应的骨牌号
    {
       board[r1 + half_size][c1 + half_size - 1] = d;
       chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size - 1, half_size);
    }

    if(r2 >= r1 + half_size && c2 >= c1 + half_size) //特殊方格在右下角子棋盘
    {
       chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size);
    }
    else   // 不在此棋盘，将此棋盘左上角设为相应的骨牌号
    {
       board[r1 + half_size][c1 + half_size] = d;
       chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size);
    }
}

int main()
{
    int i, j;
    board[2][2] = 0;
    int iRow,iCol;
    while(EOF != scanf("%d %d",&iRow,&iCol))
    {
        g_domino_num = 1;
        board[iRow][iCol] = 0;
        chessboard(0, 0, iRow, iCol, BOARD_SIZE);
        for(i = 0; i < BOARD_SIZE; i++)
        {
            for(j = 0; j < BOARD_SIZE; j++)
            {
               printf("%-4d", board[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

循环日程表

题目： n=2^k个运动员进行网球循环赛，需要设计比赛日程表。每个选手必须与其他n-1选手各赛一次;每个选手一天只能赛一次;循环赛一共进行了n-1天，

按此要求设计一张比赛日程表，该表有n行和n-1列，第i行j列为第i个选手第j天遇到的选手。

思路：

• 当k=1时，共有2个球队参赛，一天就可以比完。
• 当k=2时，共有4个球队，需比赛3天。从2个球队的比赛安排表中可以看出，左上 角与右下角对称，左下角与右上角对称，左下角的值是由左上角值加n得到

输入：

4

输出：

1   2   3   4
2   1   4   3
3   4   1   2
4   3   2   1

#include <stdio.h>
#include<string.h>
int creatTable(int a[][1000],int n){
    if(n==1){
        a[1][1]=1;
        return 0;
    }
    else{
        creatTable(a,n/2);
        for(int i=1;i<=n/2;i++){
            for(int j=1;j<=n/2;j++){
                a[i][j+n/2]=a[i][j]+n/2;//右上
                a[i+n/2][j]=a[i][j+n/2];//左下
                a[i+n/2][j+n/2]=a[i][j];//右下
            }
        }
    }
}
int main() {
    int a[1000][1000];
    int n,i,j,k;
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    creatTable(a,n);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            printf("%-4d",a[i][j]);
        printf("\n");
    }
    return 0;
}

巨人与鬼

题目：一组n个巨人正与n个鬼进行战斗,每个巨人的武器是一个质子炮, 它可以把一串质子流射中鬼而把鬼消灭。

质子流沿直线行进,在击中鬼时就终止。巨人决定采取下述策略。他们寻找鬼配对,以形成n个巨人─鬼对。

然后每个巨人同时向他选取的鬼射出一串质子流。我们知道,让质子流互相交叉是很危险的。因此巨人选择的配对方式应该使质子流都不会交叉。

假定每个巨人和每个鬼的位置都是平面上的一个固定点,并且没有三个位置共线, 求一种配对方案。

hh，被题目吸引，我是不是有毒hhhh。

思路：

1. 先找左下角节点
2. 把其余点按其与左下角节点角度大小排序
3. 从小到大遍历，当一边的巨人与鬼的数量相同时(这里利用正负1相加为0判断)，储存答案，递归求解

输入：

1 1 1
1 0 1
0 1 2
0 2 2

输出：

4 3 2 1 

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef struct node{
    int id;
    int x;
    int y;
    int type;
    double angle;
}Node;
Node p[1000];//结构体数组，用来存储每个人的信息。
int ans[1000];
void sovel(int l,int r){//递归求解，分治思想
    Node t;
    if(l>=r) return;
    int pos=l;
    //step-1
    for(int i=l+1;i<=r;i++){//查找编号为l-r区域内左下角节点
        if(p[i].y<p[pos].y||(p[i].y==p[pos].y && p[i].x<p[pos].x)){
            pos=i;
        }
    }
    t=p[l];
    p[l]=p[pos];
    p[pos]=t;

    int cnt=p[l].type;
    //step-2
    for(int i=l+1;i<=r;i++)//计算与左下角的角度
        p[i].angle=atan2(p[i].y-p[l].y,p[i].x-p[l].x);
    for(int i=l+1;i<=r;i++){//按angle排序,冒泡排序
        for(int j=i;j<=r;j++){
            if(p[i].angle>p[j].angle){
                t=p[i];
                p[i]=p[j];
                p[j]=t;
            }
        }
    }
    //step-3
    for(int i=l+1;i<=r;i++){
        cnt+=p[i].type;
        if(cnt==0){
            ans[p[l].id]=p[i].id;//链接左下角点和当前点。
            ans[p[i].id]=p[l].id;
            sovel(l+1,i-1);//分治，递归求解左边区域
            sovel(i+1,r);//分治，递归求解右边区域
            break;
        }
    }
    return;
}

int main(){
    memset(ans,0,sizeof(ans));
    int x,y,t,len=1;
    while(scanf("%d%d%d",&t,&x,&y)!=EOF){
        p[len].x=x;
        p[len].y=y;
        p[len].id=len;
        if(t==1)
            p[len].type=1;//巨人
        else
            p[len].type=-1;//鬼
        len++;
    }
    len--;
    sovel(1,len);
    for(int i=1;i<len;i++)
        printf("%d ",ans[i]);
    return 0;
}