算法分析与设计考点.docx

算法分析与设计考点.docx

《算法分析与设计考点.docx》由会员分享，可在线阅读，更多相关《算法分析与设计考点.docx（9页珍藏版）》请在冰点文库上搜索。

算法分析与设计考点

回溯法排列：

n皇后，旅行商n！

子集背包2ⁿ，

迷宫2ⁿ，

m着色mⁿ

贪心算法Kruskal宗教问题,活动安排nlogn

动态规划矩阵连乘n²

最长公共子序列mn

prim最小生成树n²

分治法二路并归nlogn

標題:

算法分析大题答案

简答题：

1.见书P1

2.

3.

4分治法伪代码

#include

#include

intAR[]={1,3,4,62,70,23,120,34,2};

intmaxNum（intarrary[],intleft,intright）

{

intmaxLeft,maxRight;

if（left==right）

{

returnleft;

}

maxLeft=maxNum（arrary,left,（left+right）/2）;

maxRight=maxNum（arrary,（left+right）/2+1,right）;

if（arrary[maxLeft]>arrary[maxRight]）

{

returnmaxLeft;

}

else

{

returnmaxRight;

}

}

voidmain（）

{

intleftX=0;

leftX=maxNum（AR,0,9）;

printf（'maxNum:

%d\n',leftX）;

}

5.

设计题：

1.

#include

intf（intn）;

intmain（）

{

  intnum;

  printf（"输入楼梯的阶数（大于1）:

"）;

  scanf（"%d", 

  printf（"上%d阶楼梯有%d种方法.\n",num,f（num））;

  return0;

}

//f（）函数定义

intf（intn）

{   

  if（n==1）

  {

     return1;    

  }

  elseif（n==2）

  {

     return2;

  }

  else

  {

     returnf（n-1）+f（n-2）;

  }

}

/*程序头部注释开始（为避免提交博文中遇到的问题，将用于表明注释的斜杠删除了）   

2.

算法：

贪心法求解背包问题

输入：

背包的容量C,物品重量W[n]，物品价值V[n]

输出：

数组X[n]

1.改变数组W和V的排列顺序，使其按单位重量价值V[i]/W[i]降序排列；

2.将数组X[n]初始化为0；

3.i=0；

4.循环直到（W[i]>C）

  4.1  将第i个物品放入背包：

X[i]=1;

  4.2  C=C-W[i];

  4.3  i++;

1.X[i]=C/W[i]。

2.

3.代码实现

4.int KnapSack（int W[],int V[],int N,int C） 

5.{ 

6.   double X[7]={0}; //物品总数为7个。

7.   int maxValue=0; 

8.   for（int i=0;W[i]

9.   { 

10.       X[i]=1; 

11.       maxValue+=V[i]; 

12.       C=C-W[i]; 

13.         

14.   X[i]=（double）C/W[i]; 

15.   maxValue+=X[i]*V[i]; 

16.   return maxValue; 

17.   } 

18.}