目录

1. 算法问题的四种常用策略

2. 常见算法的时间复杂度

3. 分治法：假币问题

4. 回溯法：n-皇后问题

---

1. 算法问题的四种常用策略

分治法、动态规划、贪心算法和回溯法是解决算法问题的四种常见策略。每种策略都有其独特的应用场景和优缺点。

分治法 (Divide and Conquer)

分治法是一种递归策略，它将一个复杂的问题分解为两个或更多个相同或相似的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。这种策略通常用于解决可以自然划分为独立子问题的问题。

例子：归并排序、快速排序、二分搜索。

优点：通常容易理解和实现。

缺点：子问题之间可能有重叠，导致重复计算。

动态规划 (Dynamic Programming)

动态规划也是一种分治策略，但它试图解决分治法中可能存在的子问题重叠的问题。它通常用于优化递归问题，通过保存子问题的解来避免重复计算。

例子：背包问题、最长公共子序列、斐波那契数列。

优点：可以有效地解决具有重叠子问题和最优子结构特性的问题。

缺点：需要更多的空间来存储子问题的解。

贪心算法 (Greedy Algorithm)

贪心算法是一种在每一步选择中都采取当前情况下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

例子：霍夫曼编码、最小生成树（如Kruskal算法）、Dijkstra算法。

优点：简单、高效，适用于许多问题。

缺点：不能保证总是得到全局最优解，仅适用于具有贪心选择性质和最优子结构性质的问题。

回溯法 (Backtracking)

回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯法会通过在上一步进行一些变化来丢弃该解，即“回溯”。

例子：八皇后问题、图的着色问题、旅行商问题。

优点：可以找到所有解。

缺点：可能效率不高，因为它会探索所有可能的候选解。

选择哪种策略取决于问题的性质和你希望得到的解的类型（全局最优解、所有解等）。每种策略都有其适用的场景和限制，理解它们的特性和优缺点是有效解决问题的关键。

2. 常见算法的时间复杂度

根据代码判断算法的时间复杂度。以下面C代码为例，执行次数函数为：m+n+m*n ，则时间复杂度为O(m*n)

3. 分治法：假币问题

【说明】

假币问题：有n枚硬币，其中有一枚是假币，已知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。

【分析问题】

将n枚硬币分成相等的两部分：
(1)当n为偶数时，将前后两部分，即1～n/2和n/2+1～0,放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币。
(2)当n为奇数时，将前后两部分，即1～(n-1)/2和(n+1)/2+1～n,放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币；若两端重量相等，则中间的硬币，即第(n+1)/2枚硬币是假币。

【C代码】

下面是算法的C语言实现：

coins[]://硬币数组
first,last://当前考虑的硬币数组中的第一个和最后一个下标

#include <stdio.h>
int getCounterfeitCoin(int coins[],int first, int last)
{
    int firstsum = 0,lastsum = 0;
    int ì;
    if(first==last-1)
        {/*只剩两枚硬币*/
            if(coins[first] < coins[last])
                return first;
                return last;
        }
    if(last - first + 1)%2 ==0)
    { /*偶数枚硬币*/
        for(i= first;i < first+(last-first)/2+1 ;i++)
        {
            firstsum+= coins[i];
        }
        for(i=first +(last-first)/ 2 + 1;i< last +1;i++)
        {
            lastsum += coins[i];
        }    
        if(firstSum<lastSum)
        {
            Return getcounterfeitCoin(coins,first,first+(last-first)/2);
        }
        else
        {
            Return getCounterfeitCoin(coins,first+(last-first)/2+1,last);
        }
    }
    else
    { /*奇数枚硬币*/
        for(i=first;i<first+(last-first)/2;i++)
        {
            firstsum+=coins[i];
        }
        for(i=first+(last-first)/2+1;i<last+1;i++)
        {
            lastsum+=coins[i];
        }
        if(firstsum<lastsum)
        {
            return getCounterfeitCoin(coins,first,first+(last-first)/2-1);
        }
        else if(firstsum>lastsum)
        {
            return getCounterfeitCoin(coins,first+(last-first)/2-1,last);
        }
        else
        {
            return first+(last-first)/2;
        }
    }
}

4. 回溯法：n-皇后问题

 【说明】

n-皇后问题是在n行n列的棋盘上放置n个皇后，使得皇后彼此之间不受攻击，其规则是任意两个皇后不在同一行、同一列和相同的对角线上。

【分析】

拟采用以下思路解决 n-皇后问题：第i个皇后放在第i行。从第一个皇后开始，对每个皇后，从其对应行(第i个皇后对应第i行)的第一列开始尝试放置，若可以放置，确定该位置，考虑下一个皇后；若与之前的皇后冲突，则考虑下一列；若超出最后一列，则重新确定上一个皇后的位置。重复该过程，直到找到所有的放置方案。

【C代码】

下面是算法的C语言实现。

(1)常量和变量说明，
pos:一维数组，pos[i]表示第i个皇后放置在第i行的列位置。
count:统计放置方案数。
i,j,k:变量，
N:皇后数。

(2)C程序。

#include <stdio.h>
#include <math.h>
#define N 4
/*判断第 k个皇后目前放置位置是否与前面的皇后冲突*/
int isplace (int pos[], int k) {
    int i;
    for(i=1; i<k; i++) {
        if( pos[i] ==pos[k] || fabs(i-k) — fabs(pos[i] - pos[k])){ //同一列不能有多个皇后
            return 0;
        }
    }
    return 1;
}

int main(){
    int i,j,count=1;
    int pos[N+1];
    //初始化位置
    for(i=1; i<=N; i++){
        pos[i]=0;
        j=1; //初始化当前行为第一行
    }
    while(j>=1){
        pos[j]= pos[j]+1;
        /*尝试摆放第i个皇后*/
        while(pos[j]<=N && isplace(pos,j)==0){
        pos[j]= pos[j]+1;
        }
        /*得到一个摆放方案*/
        if(pos[j]<=N && j==N){
            printf("方案Sd:",count++);
            for(i=1; i<=N; i++){
                printf("sd",pos[i]);
                printf("\n");
            }
        }
        /*考虑下一个皇后*/
        if(pos[j]<=N && j<N ){
            j=j+1;
        } else{ //返回考虑上一个皇后
            pos[j]=0;
            j=j-1; //回溯到上一行，将当前行设为上一行
        }
    }
    return 1;
}

【问题1】(10分)
根据以上说明和C代码，填充C代码中的(1)～(5).
【问题2】(2分)
根据以上说明和C代码，算法采用了 回溯法 设计策略。从一条路往前走，能进则进，
不能进则退回来，换一条路再试，这就是回溯法的基本思想。
【问题3】(3分)
上述 C代码的输出为：
方案1:2 4 1 3
方案2:3 1 4 2