分类 linuxC 下的文章

深度优先搜索-八皇后(非递归)

#include <stdio.h>
#include <math.h>
#define N 8
/*八皇后问题是在8*8的棋盘上放置8枚皇后,使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后*/

int a[N] = {0}; //表示棋盘,若a[2]=2,则表示在第3行第2列放一个皇后,因为同一行不能放两个皇后,所以只需要1维数组就可以表示一个棋盘。

int solution = 0;//解的个数

int top = 0;

struct Node
{
    int row;
    int col;
} stack[512];

void push (struct Node p) {
    stack[top] = p;
    top++;
}

int is_empty(void) {
    return top == 0;
}

struct Node pop(void) {
    top--;
    return stack[top];
}

//row行,col列, 是否可以摆皇后
int IsOK(struct Node node)
{
    int i;
    for (i = 0; i < node.row; i++)
    {
        if (a[i] == node.col || (abs(a[i] - node.col) == node.row - i))
        {
            return 0;
        }
    }
    return 1;
}
 
//打印出所有解
void Print()
{
    printf("第%d种解:\n", ++solution);
    int i,j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (a[i] == j)
            {
                printf("%d", i);
            }
            else
            {
                printf("#");
            }
        }
        printf("\n");
    }
 
    printf("-----------------\n");
}
 
void DSF()
{
    struct Node node = {0,0};
    push(node);
    while(!is_empty())
    {
        //--find
        node = pop();
        while (node.col < N && !IsOK(node))
        {
            node.col++;
        }
        if (node.col < N)
        {
            //--forward
            if (node.row < N-1)
            {
                //把ok的节点放到当前层
                a[node.row] = node.col;
                push(node);
                
                //进入下一层的第一个节点
                node.row++;
                node.col = 0;
                push(node);
            }
            else
            {
                //--done
                a[node.row] = node.col;
                Print();
                
                //进入当前层的下一个结点
                //node = stack.top();
                node.col++;
                push(node);
            }
        }
        else
        {
            //--back
            node = pop();
            node.col++;
            push(node);
        }
    }
}
int main()
{
    DSF();
    return 0;
}


深度优先搜索-八皇后(递归)

#include <stdio.h>
#include <math.h>
#define N 8

/*八皇后问题是在8*8的棋盘上放置8枚皇后,使得棋盘中每个横向、纵向、左上至右下斜向、右上至左下斜向均只有一枚皇后。
求解出所有摆法,一共有92种摆法*/

int a[N] = {0}; //表示棋盘,若a[2]=2,则表示在第3行第2列放一个皇后,因为同一行不能放两个皇后,所以只需要1维数组就可以表示一个棋盘。
 
int solution = 0;//解的个数
 
//row行,col列, 是否可以摆皇后
int IsOK(int row, int col)
{
    int i;
    for (i = 0; i < row; i++)
    {
        if (a[i] == col || (abs(a[i] - col) == row - i))
        {
            return 0;
        }
    }
    return 1;
}
 
void Display()
{
    int i,j;
    printf("第%d种解:\n",++solution);
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (a[i] == j)
            {
                printf("%d", i);
            }
            else
            {
                printf("#");
            }
        }
        printf("\n");
    }
 
    printf("-----------------\n");
}
 
void DSF(int row)
{
    int col;
    for (col = 0; col < N; col++)
    {
        //find
        if (IsOK(row, col))
        {
            a[row] = col;
            //forward
            if (row != N -1)
            {
                DSF(row + 1);
            }
            else
            {
                //done
                Display();
            }
            
        }
    }
    //back
}
 
int main()
{
    DSF(0);
    return 0;
}

思维方法与编程思想

  1. 以概念为中心
  2. 组合规则
  3. 最少例外原则(Rule of Least Surprise)
  4. 不要把必要条件(Necessary Condition)当充分条件(Sufficient Condition)
  5. 封装成函数的基本步骤是:把语句放到函数体中,把变量改成函数的参数
  6. 递归
    • 随着函数调用的层层深入,存储空间的一端逐渐增长,然后随着函数的层层退出,存储空间的这一端又逐渐缩短,这是一种具有特定性质的数据结构。它的特性就是只能在某一端增长或缩短,并且每次访问参数和局部变量时只能访问这一末端的单元,而不能访问内部的单元
  7. 函数式编程(Functional Programming),命令式编程(Imperative Programming), 编程语言应该更多是在描述要做什么(Declarative)而不是描述具体一步一步怎么做(Imperative), 例如sql
  8. 迭代和增量式求解
  9. 抽象
    • '抽象'简单来说就是提取公因式
    • 组合使得系统可以任意复杂,而抽象使得系统的复杂性是可以控制的,任何改动都只局限在某一层,而不会波及整个系统
  10. 数据驱动的编程(Data-driven Programming),写代码最重要的是选择正确的数据结构来组织信息,设计控制流程和算法尚在其次,只要数据结构选择得正确,其它代码自然而然就变得容易理解和维护了
  11. 分而治之(归并排序)
  12. 折半求解(折半查找)
  13. 回溯(迷宫问题)

广度优先搜索 - 迷宫问题

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5

struct point {
    int row;
    int col;
    int predecessor; // 保存'前趋点'(出队点)在queue数组中的索引,即head-1
} queue[512];

int head = 0;
int tail = 0;

// 入队
void enqueue (struct point p) {
    queue[tail] = p;
    tail++;
}

// 出队
struct point dequeue (void) {
    head++;
    return queue[head-1];
}

// 判断队列是否为空
int is_empty (void) {
    return head == tail;
}

// 迷宫
int maze[MAX_ROW][MAX_COL] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

// visit
void visit (int row,int col) {
    maze[row][col] = 2;
    struct point p = {row,col,head-1};// head-1出队点所在queue的索引
    enqueue(p);
}

int main (void) {
    struct point p = {0,0,-1};
    maze[p.row][p.col] = 2;
    enqueue(p);

    while (!is_empty()) {
        p = dequeue();
        // 终点
        if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
            break;
        }
        // 上
        if (p.row-1 >=0 && maze[p.row-1][p.col] == 0) {
            visit(p.row-1,p.col);
        }
        // 右
        if (p.col+1 < MAX_COL && maze[p.row][p.col+1] == 0) {
            visit(p.row,p.col+1);
        }
        // 下
        if (p.row+1 < MAX_ROW && maze[p.row+1][p.col] == 0) {
            visit(p.row+1,p.col);
        }
        // 左
        if (p.col-1 >= 0 && maze[p.row][p.col-1] == 0) {
            visit(p.row,p.col-1);
        }
    }

    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
        printf("row:%d,col:%d\n",p.row,p.col);
        while (p.predecessor != -1) {
            p = queue[p.predecessor];
            printf("row:%d,col:%d\n",p.row,p.col);
        }
    } else {
        printf("找不到终点");
    }
}

深度优先搜索 - 迷宫问题

// 搜索算法的特点:每次取一个相邻的点走下去,一直走到无路可走了再退回来,取另一个相邻的点再走下去。这称为深度优先搜索(DFS,Depth First Search)

#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5

// 存放走过的点(用数组模拟栈)
struct point {
    int row;
    int col;
} stack[512];

int top = 0;

// 二维数组, 存放前趋点结构体, 比如 predecessor[4][4]存放{3,4},表示是从3,4到4,4
struct point predecessor[MAX_ROW][MAX_COL] = {
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
    {{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}}
};

// '迷宫', 0 表示可走, 1 表示不可走, 2 表示走过
int maze[MAX_ROW][MAX_COL] = {
    0,1,0,0,0,
    0,1,0,1,0,
    0,0,0,0,0,
    0,1,1,1,0,
    0,0,0,1,0,
};

// top总是指向栈顶元素的下一个元素 
// [ 栈低->栈顶 ]
void push (struct point p) {
    stack[top] = p;
    top++;
}

int is_empty(void) {
    return top == 0;
}

// pop其实并没有清除原来的栈顶元素,只是把top指针移动了一下,原来的栈顶元素仍然存在那里
// 下次Push操作就会覆盖它
struct point pop(void) {
    top--;
    return stack[top];
}

void visit (int row,int col,struct point p) {
    maze[row][col] = 2; // 走过的位置点设置为2
    predecessor[row][col] = p; // 保存走到此位置的'前趋点'
    struct point visit_point = {row,col}; // 走过的位置点入栈
    push(visit_point);
}

void main (void) {
    struct point p = {0,0};
    maze[p.row][p.col] = 2;
    push(p);
    while (!is_empty()) {
        p = pop();
        // 终点
        if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
            break;
        }
        // 上
        if (p.row-1 >=0 && maze[p.row-1][p.col] == 0) {
            visit(p.row-1,p.col,p);
        }
        // 右
        if (p.col+1 < MAX_COL && maze[p.row][p.col+1] == 0) {
            visit(p.row,p.col+1,p);
        }
        // 下
        if (p.row+1 < MAX_ROW && maze[p.row+1][p.col] == 0) {
            visit(p.row+1,p.col,p);
        }
        // 左
        if (p.col-1 >= 0 && maze[p.row][p.col-1] == 0) {
            visit(p.row,p.col-1,p);
        }
    }
    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
        // 走到终了
        printf("(%d, %d)\n", p.row, p.col);// 打印终点
        while (predecessor[p.row][p.col].row != -1) { // 是否有'前趋点'
            p = predecessor[p.row][p.col]; // 取出'前趋点'
            printf("(%d, %d)\n", p.row, p.col); // 打印'前趋点'
        }
    } else {
        printf("不能走到终点");
    }
}