算法设计与分析大作业报告

班级： 

学号： 

姓名： 

分治法大作业报告

问题陈述：

编程实现归并排序算法和快速排序算法，输出排序结果。输入10组相同的数据，验证排序结果和完成排序的比较次数。

分治法基本思想：

分治法的基本思想是将问题分解成若干个子问题，然后求解子问题。子问题较原问题要容易些， 先得出子问题的解，由此得出原问题的解，这就是所谓“分而治之”的思想。

算法描述：

  当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可求解的子问题，其中1 1.归并排序的思想：将A（1），……，A（N）分成两个集合，对每个集合单独分类，然后将已分类的两个序列归并成一个含N个元素分好类的元素

2.快速排序的思想：选取A的某个元素做为划分元素，然后将其他元素重新排列，使在划分元素以前出现的元素都 小于或等于它，在划分元素之后出现的划分元素都大于等于它。

程序代码：

#include

#include

#include

void MergeSort(int *data,int x,int y,int *temp)

{    int p,q,m,i=x;

if (y-x>1)

    {m = x+(y-x)/2;

        p = x;

        q = m;

        MergeSort(data,x,m,temp);

        MergeSort(data,m,y,temp);

     while(p        {

         if (q>=y||(p            {temp[i++] = data[p++];}

            else

            {temp[i++] = data[q++];}

        }

     for(i=x;i            data[i] = temp[i];    }

}

void HoareSort(int *data,int x,int y)

{   

    int p=x,q=y-1,temp;

while(p     while (q>p&&data[q]>=data[p])

            q--;

     if (q>p)

        {

            temp = data[p],data[p] = data[q],data[q] =temp;

            p++;

        }

     while(q>p&&data[p]<=data[q])

            p++;

     if (p        {

            temp = data[p],data[p] = data[q],data[q] =temp;

            q--;

        }

        if (p==q)        {

            HoareSort(data,x,p);

            HoareSort(data,p+1,y);

        }}}

int main()

{

    int data[10],i;

    int temp[10];

    srand(time(NULL));

for (i=0;i<10;i++)

    { data[i] = rand()%100;    }

    printf("未排序排序的数据为：\\n");

for (i=0;i<10;i++)

    {printf("%d ",data[i]);}

    printf("\\n");

    printf("归并排序的顺序为： \\n");

    MergeSort(data,0,10,temp);

for (i=0;i<10;i++)

    {printf("%d ",data[i]);    }

    printf("\\n");

    printf("快速排序的顺序为： \\n");

    HoareSort(data,0,10);

for (i=0;i<10;i++)

    {printf("%d ",data[i]);}

    printf("\\n");

    return 0;

}

运行结果：

结论分析：

归并排序和快速排序都是递归排序，但是归并排序是稳定的排序方法，快速排序是不稳定的排序方法。（1）此问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （2）利用该问题分解出的子问题的解可以合并为该问题的解； （3）该问题所分解出的各个子问题是相互的，即子问题之间不包含公共的子问题。

动态规划大作业报告

问题陈述：

      定义0-1背包问题为：。条件为：，且。和分别表示第i个物品的价值和重量，c为背包容量。

动态规划基本思想：

    动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

算法描述：

   刻画0-1背包问题的最优解的结构。

可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即xn=1，那么其余x1，x2，...，x(n-1)一定构成子问题1，2，...，n-1在容量W-wn时的最优解。如果这个最优解不包含物品n，即xn=0，那么其余x1，x2，...，x(n-1)一定构成子问题1，2，...，n-1在容量W时的最优解。递归定义最优解的值，根据上述分析的最优解的结构递归地定义问题最优解。设c[i,w]表示背包容量为w时，i个物品导致的最优解的总价值，得到下式。显然要求c[n,w]。

程序代码：

#include

using namespace std;

void Path(int n, int W, int c[][100], int *v, int *wei)

{

   memset(*c, 0, (W+1)*sizeof(int));

for (int i = 1; i <= n; i++)

    {

        c[i][0] = 0;

     for (int w = 1; w <= W; w++)

        {

         if (wei[i-1] > w)

            {

                c[i][w] = c[i-1][w];

            }

            else

            {

                int temp = c[i-1][w-wei[i-1]] + v[i-1];    

             if (c[i-1][w] > temp)

                {

                    c[i][w] = c[i-1][w];

                }

                else 

                    c[i][w] = temp;

            }}}}

void find(int c[][100], int *x, int *wei, int n, int W)

{    

    int w = W;

for (int i = n; i >= 2; i--)

    {

        if (c[i][w] == c[i-1][w])

        {

            x[i-1] = 0;

        }

        else

        {

            x[i-1] = 1;

            w = w - wei[i-1];

        }

    }

    if (c[1][w] == 0)

        x[0] = 0;

    else

        x[0] = 1;

}

int main()

{

    int n = 5;

    int W = 100;

    int w[] = {10,48,35,23,25,30};

    int v[] = {40,10,20,30,50};

    int c[6][100] = {0};

    Path(n, W, c, v, w);

cout<<"最优的总价值为：";

cout<    int x[5];

    find(c, x, w, n, W);

cout<<"用0表示不装入，1表示装入，情况如下："< for (int i = 1; i < n+1; i++)

{cout<<"第"< cout<    return 0;

}

运行结果：

结论分析：

上述代码的时间复杂度为O(nw)。能表示出装入或者不装入但计算出装入后的总价值有点问题，程序还不够完善有待改进。动态规划问题的的实质就是寻求一个最优解的过程， 实质就是为问题寻求一个 最优算法，这个最优算法解出来的值是运用所有算法中最接近实际值的解。 一般对一个问题，不会运用多种算法，而只会选取其中的一种来求解（但实际 问题中常常需要不同算法的结合，不过一般是处理不同方面的算法） 不同的算法对待不同的问题总是有利有弊。

贪心法大作业报告

问题陈述：

给定n种物品和一个背包.物品i的重量是Wi,其价值为Vi,背包的容量为C。在选择物品i装入背包时，可以选择物品i的一部分，1<= i <=n。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

贪心法基本思想：

贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：

1.整体的最优解可以通过局部的最优解来求出；

2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。

算法描述：

对于背包问题,若它的一个最优解包含物品j,则从该最优解中拿出所含的物品j的那部分重量w,剩余的将是n-1个原重物品1,2,…,j-1,j+1,…,n及重为Wj-W的物品j中可装入容量为c-w的背包且具有最大价值的物品。

程序代码：

#include

struct goodinfo

{

    float p; 

    float w; 

    float X; 

    int flag; 

};

void Insertionsort(goodinfo goods[],int n)

{

    int j,i;

for(j=2;j<=n;j++)

    {

        goods[0]=goods[j];

        i=j-1;

     while (goods[0].p>goods[i].p)

        {

            goods[i+1]=goods[i];

            i--;

        }

        goods[i+1]=goods[0];

    }

}

void bag(goodinfo goods[],float M,int n)

{ 

    float cu;

    int i,j;

for(i=1;i<=n;i++)

        goods[i].X=0;

    cu=M;  

for(i=1;i    {

     if(goods[i].w>cu)

            break;

        goods[i].X=1;

        cu=cu-goods[i].w;

    }

if(i<=n)

        goods[i].X=cu/goods[i].w;

for(j=2;j<=n;j++)

    {

        goods[0]=goods[j];

        i=j-1;

     while (goods[0].flag        {

            goods[i+1]=goods[i];

            i--;

        }

        goods[i+1]=goods[0];

    }

cout<<"最优解为:"< for(i=1;i<=n;i++)

    {

     cout<<"第"<     cout<}}

void main()

{ 

cout<<"运用贪心法解背包问题"<    int j;

    int n;

    float M;

    goodinfo *goods;

    while(j)

    {

     cout<<"请输入物品的总数量：";

     cin>>n;

        goods=new struct goodinfo [n+1];

     cout<<"请输入背包的最大容量：";

     cin>>M;

     cout<        int i;

     for(i=1;i<=n;i++)

        { goods[i].flag=i;

     cout<<"请输入第"<     cin>>goods[i].w;

     cout<<"请输入第"<     cin>>goods[i].p;

        goods[i].p=goods[i].p/goods[i].w;

     cout<        }

        Insertionsort(goods,n);

        bag(goods,M,n);

     cout<<"请问您还要继续运行此程序吗？请用Y或者N回答。"<     cin>>j;

        if(j=='N')

            break;

}}

运行结果：

结论分析：

程序较完整，算法复杂度为O（N*N）。但有一点点小小的不足并没有算出物品装入后的重量，也没有展示最优解的价值为多少。

回溯法大作业报告

问题陈述：

 在n×n格的棋盘上放置彼此不受攻击的n个皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。要求在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

回溯法基本思想：

从一条路往前走，能进则进，不能进则退回来，换一条路再试。

当我们遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。

算法描述：

解向量：(x1, x2, … , xn)

显约束：xi = 1,2, … ,n

隐约束：  1)不同列：xi != xj

           2)不处于同一正、反对角线：|i-j| != |x(i)-x(j)|

解空间：满N叉树

程序代码：

#include

#include

using namespace std;  

class queen 

{ 

    struct q_place { 

        int x; 

        int y; 

        q_place ()  

            : x(0),y(0)  

        {} 

    }; 

public: 

    queen(int qc)  

    : q_count (qc), sum_solution (0) { 

        curr_solution.resize (q_count); 

    } 

    void backtrack () { 

        __backtrack (0); 

    } 

private: 

    void __backtrack (int t) { 

if (t >= q_count) {

            ++ sum_solution ; 

for (size_t i = 0;i < curr_solution.size(); ++ i) {

cout << "x = " << curr_solution[i].x

<< " y = " << curr_solution[i].y << endl;

            } 

cout << "解决方案有" << sum_solution <<"个"<< endl;

        } 

        else { 

for (int i = 0;i < q_count; ++ i) {

                curr_solution[t].x = i; 

                curr_solution[t].y = t; 

                if (__place(t)) { 

                    __backtrack (t + 1); 

                } 

            } 

        } 

    }  

    bool __place (int k) { 

for (int i = 0; i < k; ++ i) {

            if ((abs(curr_solution[i].x - curr_solution[k].x)  

                == abs(curr_solution[i].y - curr_solution[k].y)) 

                || curr_solution[i].x == curr_solution[k].x) { 

                return false; 

            } 

        } 

        return true; 

    } 

private: 

vector curr_solution;

    const int q_count;              

    int sum_solution;               

};  

int main()  

{ 

    int i;

cout<<"请输入皇后的个数："< cin>>i;

    queen q(i); 

cout<<"各个皇后在不同位置时，对应的解决方案个数如下："<    q.backtrack (); 

    return 0; 

}

运行结果：

结论分析：

n后问题主要在于可行解，一个一个的试，（t）能走通就往(t+1)下走，走不通就倒回去(t-1)换条走，再不行再回走。就要不停的尝试，不停的回溯，直到找全可行解，或者一个也没有就停止。还有重要的事约束条件，两个皇后不能在同行同列或者斜线上。这题需要理解程序设计的顺序结构基本思想，掌握顺序结构语句特点。并且学会用算法分析问题，能够使用顺序结构编写简单的程序解决具体问题。