计算机软件基础作业

《计算机软件基础作业》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《软件技术基础》结课大作业姓名王家毅学号120611325日期2014.06.191利用减半递推技术，写出求长度为n的数组中最大元素的递归算法#includeusingnamespacestd;intmaxa(inta[],intm,intn){intd,d1,d2;if(m==n)return(a[m-1]);else{d1=maxa(a,m,(m+n)/2);//求数组中前半部分的最大值d2=maxa(a,(m+n)/2+1,n);}//求数组中后半部分的最大值if(d1>d2

2、)d=d1;elsed=d2;return(d);}2编写用回溯法求解n皇后的算法#include#includeboolplace(intk,int*X){        inti;        i=1;        while(i

3、

4、(abs(X[i]-X[k])==abs(i-k)))                  returnfalse;          

5、        i++;         }        returntrue;}voidNqueens(intn,int*X){       intk;       X[1]=0;k=1;       while(k>0)       {             X[k]=X[k]+1;//不断的在解空间里从小到大的试探              while((X[k]<=n)&&(!place(k,X)))                      X[k]=X[k]+1;           

6、          //不符合条件的马上再取解空间的下一个值来试探。              if(X[k]<=n)   //找到了一个位置，而且是合法的                  if(k==n)   //是不是最后一个皇后，若是则得出一个完整解                 {                          for(inti=1;i<=n;i++)                          cout<

7、       cout<<"";                   }                  else    //若不是最后一个皇后，则给下一个皇后找位置                 {                          k=k+1;                          X[k]=0;                 }               else      k=k-1;  //若是找了全部的列都无法放置某个皇后，则回溯到上一个k的情况，让

8、上一个k再往下试        } }3给定n个城市间的距离，求从一个城市0出发经过其他城市一次且一次的一条最短路径voidmain(){functionDijkstra(G,w,s)foreachvertexvinV[G]d[v]:=infinityprevious[v]:=undefined //对n个顶点进行初始化，显然是O(n)d[s]:=0S:=emptyset //O(1)V:=setofallvertices //n个顶点加入队列O(n)WhileVisnotanemptyset //从

9、这一行可以看出n遍循环，下面调用Extract_Min(v)，此过程需要搜寻整个数组，一次操作时间是O(n)，共O(n^2)u:=Extract_Min(v)S:=Sunion{u}foreachedge(u,v)outgoingfromu //拓展边（u,v），共E条边，因此是O(E)ifd[v]>d[u]+w(u,v)d[v]:=d[u]+w(u,v)previous[v]:=u //总共合起来是O（E+n^2）;所有步骤合起来就是O(n)+O(1)+O(n)+O(E+n^2),即O(n^2)。}

10、4将单链表看做二叉树，编写递归程序打印单链表#include #include #include #include typedefstructnode{charc;intcount;structnode*left,*right;}bnode;bnode*k,*m;//分别记录叶子链表的第一及当前结点的前驱bnode*creatree(bnode*ptr,charch)//建二叉树{intresult;bnode*p,*r;//p指向当前结点的最近的父结点