离散上机.docx
- 文档编号:15104018
- 上传时间:2023-06-30
- 格式:DOCX
- 页数:21
- 大小:220.38KB
离散上机.docx
《离散上机.docx》由会员分享,可在线阅读,更多相关《离散上机.docx(21页珍藏版)》请在冰点文库上搜索。
离散上机
1.快速排序及其排序次数比较
(1)源程序:
#include
usingnamespacestd;
#include
voidRandomProduce(inta[10][1611])
{
inti,j;
for(i=0;i<8;i++)
{
for(j=0;j<1611;j++)
{
a[i][j]=rand()%(40000);
}
}
for(j=0;j<1611;j++)
{
a[8][j]=j+1;
}
for(j=0;j<1611;j++)
{
a[9][j]=1611-j;
}
}
intFastSort(inta[10][1611],intlow,inthigh,inti,int&k)
{
intpivotkey;
intt;
t=a[i][(high+low)/2];
a[i][(high+low)/2]=a[i][low];
a[i][low]=t;
pivotkey=a[i][low];
while(low { while(low { high--; k++; } a[i][low]=a[i][high]; while(low { low++; K++; } a[i][high]=a[i][low]; k++; } a[i][low]=a[i][0]; returnlow; } voidQSort(inta[10][1611],intlow,inthigh,inti,int&k) { intpivotloc; if(low { pivotloc=FastSort(a,low,high,i,k); QSort(a,low,pivotloc-1,i,k); QSort(a,pivotloc+1,high,i,k); } } intmain() { inti,j,k=0; intsum=0; intave; inta[10][1611]; RandomProduce(a); for(i=0;i<10;i++) { QSort(a,0,1611,i,k); cout<<"第”< "< sum+=k; k=0; } ave=sum/10; cout<<"平均的排序次数是"< return0; } (2)程序运行截图 复杂度 K 1 2 3 4 5 6 7 8 9 10 T(n) 19796 42502 68929 96230 120867 148212 174726 205053 238423 261763 下界 18658 41768 66566 92457 119161 146514 174406 202759 231519 260636 上界 19965 44382 70484 97681 125692 154351 183550 213211 243275 273699 由图可得下表: 2.归并排序 k 10 11 12 13 14 15 16 17 18 19 W(n) 9217 20481 45057 98305 212993 458753 983041 2097153 4456449 9437185 快速排序(下界) 10936 24698 55060 121461 265619 576646 1244124 2669932 5703250 12133293 3.城市最优回路 #ifndefPARKGUIDE_H//定义头文件 #definePARKGUIDE_H #include usingnamespacestd; constintMaxSize=12;//图中最多顶点个数 template classParkGuide { public: ParkGuide(int*a,T*v,intn);//构造函数,初始化具有n个顶点的图 ~ParkGuide(){}//析构函数 voidDijkstra(intv,intendv);//最小距离 voidPutOutArcInfo();//输出路径 voidTSP(intv);//求最优路径 private: Tvertex[MaxSize];//存放图中顶点的数组 intarc[MaxSize][MaxSize];//存放图中边的数组 intvertexNum;//图的顶点数和边数 }; #endif #include #include #include"ParkGuide.h"//引入头文件 usingnamespacestd; template voidParkGuide : TSP(intv)//求最优旅游路线,从V点出发,最后回到V点 { intpathsum=0;//用于存放路径和 intmax=10000;//代表无穷大 intminpath;//用于存放当前找到的最小路径 intvisited[12]={1};//记录顶点的访问情况: visited[d]=0表示d点未访问,visited[d]=1表示d点已被访问 intj=0;//临时存放顶点编号,以便传递给顶点v //让所有点都记录为未访问。 visited[c]=0. for(intd=1;d visited[d]=0; //最佳旅游路线算法开始 for(intflat=0;flat! =vertexNum;) { minpath=10000; for(intk=0;k<8;k++)//依次读取与v相邻的路径,取未被访问的最小路径 { if(minpath>arc[v][k]&&visited[k]==0) //相邻的两个点进行路径大小比较,求出最小路径: 逐一比较,保证minpath值为最小值 { minpath=arc[v][k]; j=k; } } if(minpath 记录已访问点的个数。 visited[j]设为1,表示j点已被访问 { flat++; visited[j]=1; pathsum=pathsum+minpath;//更新最短路径长度 v=j;//将点交还给v,以便进行下一次循环: 即让现在所在的点成为下一次循环的出发点 cout<<"->("< } if(flat==vertexNum-1)//当已经访问了所有点,把出发点的visited设为0,即表示未访问,以便寻找并返回正门 { visited[0]=0; } if(flat==vertexNum)//返回始发点,输入路径长度 {cout< } cout<<"┏━━━┓"< cout<<"┃小贴士┃这条精品游览路线可以让您一次不重复的游览国内所有的城市! "< cout<<"┗━━━┛"< cout<<"**************祝您旅途愉快************"< } //程序名称: ParkGuide.cpp #include #include #include"ParkGuide.h"//引入头文件 usingnamespacestd; template ParkGuide : ParkGuide(int*a,T*v,intn)//构造图 { inti,j; vertexNum=n;//顶点数 for(i=0;i for(j=0;j arc[i][j]=10000; for(i=0;i vertex[i]=v[i];//存储顶点信息 for(i=0;i for(j=0;j arc[i][j]=*(a+i*n+j); inttt=0; } template voidParkGuide : PutOutArcInfo()//输出图中所有的路径 { inti=0;//假设源点是第0个顶点,即顶点序号是0 intj=0; if(i>vertexNum||j>vertexNum)throw"位置";//错误抛出异常 else {for(i=0;i {//输出任意两点之间的路径 for(j=0;j { if(arc[i][j]<10000)//两点之间存在路径 cout<<"从"< "< } } } } template voidParkGuide : Dijkstra(intv,intendv)//求从v顶点到endv点的最短路径 { if(v>vertexNum)throw"位置";//v顶点或endv顶点输出不正确则抛出异常 intnumv=vertexNum;//顶点数 intdist[MaxSize];//最短长度 intpath[MaxSize];//当前找到的最短路径 ints[MaxSize];//存放源点和已生成的终点的集合 intmax=10000;//代表无穷大 inti,j,k,wm; for(i=0;i { dist[i]=arc[v][i]; if(i! =v&&dist[i] path[i]=v;//当前找到的最短路径为v else path[i]=-1;//否则v与i顶点不存在路径 s[i]=0;//给s集合确定初值0 } s[v]=1;dist[v]=0;//将顶点v本身排除在外 for(k=0;k { wm=max;j=v;//确定当前最短路径wm及顶点的序号j for(i=0;i { if(! s[i]&&dist[i] { j=i; wm=dist[i];//把当前找到的路径确定为最大值 } } s[j]=1; for(i=0;i { if(! s[i]&&dist[j]+arc[j][i] { dist[i]=dist[j]+arc[j][i];path[i]=j;//dist[i]取最小值 } } } if(endv { stringmmm="";//初始化字符串 intj=endv; while(j>-1) { stringnnn=vertex[j];//依次把顶点存放在nnn字符串中 nnn+=mmm; mmm=""+nnn; j=path[j]; } cout<<"从"< "< "< //输出从v点到endv点的最短路径 } else//endv点不存在 for(i=0;i { stringmmm="";//初始化字符串 intj=i; while(j>-1) { stringnnn=vertex[j];//依次把顶点存放在nnn字符串中 nnn+=mmm; mmm=""+nnn; j=path[j]; } cout<<"从"< "< "< //输出从v点到任意点的最短路径 } } #include #include #include"ParkGuide.cpp"//引用ParkGuide.cpp文件 #include"TSP.cpp"//引用解决最佳旅游路线的TSP文件 usingnamespacestd; intmain(intargc,char*argv[]) { inti,j; constintnumv=50;//顶点数 intcontrol=1;//控制 intwhich;//功能选择变量 stringname;//插入顶点的值 intborder[numv][numv]={ {1005,100,2000,200,907,1009,987,566,421,6578,985,124,653,487,568,214,578,1256,1034,245,654,635,128,148,987,354,126,846,139,210,354,678,458,698,1268,1456,10358,54,128,644,345,578,698,1256,1564,1987,1354,1546,1458,1534}, {156,1054,1000,456,845,54,1047,105,456,125,1234,1985,1675,456,1564,1354,1896,1354,1625,125,364,985,126,345,50,164,1245,236,1489,1987,235,246,258,124,1236,210,325,349,856,945,961,837,246,125,245,345,368,987,246,479}, {263,548,657,985,123,456,987,159,347,357,126,324,156,148,189,387,654,1125,164,1984,265,356,565,58,459,57,468,106,98,96,157,349,56,125,349,1168,1578,1945,1684,1931,2654,1987,2456,2846,12369,3015,3645,1268,1975,1657}, {125,1235,1456,985,961,2546,2589,2465,654,125,364,786,5489,3245,1684,1023,236,156,985,654,756,156,945,324,587,689,50,56,98,102,165,489,354,168,195,324,165,987,3456,1698,156,423,1696,456,168,354,369,1684,4568,1235}, {102,4568,2354,1658,4569,2354,1659,1598,465,165,56,98,90,102,165,568,785,465,986,1023,1654,489,654,1236,546,875,168,4952,466,954,962,156,486,168,148,985,164,168,654,512,587,536,469,646,159,479,264,1023,654,569}, {0,0,0,0,0,156,145,687,546,235,135,1456,986,930,1567,2495,1346,987,1568,452,357,694,512,1354,2641,2579,1365,154,256,684,579,986,865,756,654,326,632,651,456,845,125,354,168,176,133,568,459,682,459,684}, {0,0,0,0,0,0,456,468,984,657,1236,466,657,1234,120,56,98,1325,4652,486,135,486,368,126,2684,2456,1265,1354,245,987,965,248,654,753,1254,168,1259,98,90,980,960,966,842,108,106,546,358,7695,1256,1896}, {0,0,0,0,0,0,0,486,987,125,1235,1658,4569,368,475,136,486,201,201,546,785,654,984,1256,232,1560,248,962,125,654,1235,356,845,9820,156,90,108,168,564,265,984,1256,321,50,60,58,978,456,157,654}, {0,0,0,0,0,0,0,0,456,87,964,523,156,120,103,980,56,98,156,147,864,256,982,568,157,489,684,153,249,685,156,579,631,2156,410,216,357,986,1235,453,862,657,451,235,123,458,154,658,458,961}, {0,0,0,0,0,0,0,0,0,123,455,486,579,123,458,698,487,1532,1654,980,2456,103,256,489,687,452,366,597,152,165,985,962,1523,1268,1456,1258,2134,206,983,964,765,784,916,664,125,854,657,1203,654,846}, {0,0,0,0,0,0,0,0,0,0,1546,875,456,2654,1206,1645,1654,856,954,963,154,2245,2687,456,846,916,98,102,50,68,476,153,246,589,648,152,364,651,632,649,852,103,567,486,153,124,689,133,468,138}, {0,0,0,0,0,0,0,0,0,0,0,154,162,158,687,486,984,687,168,536,459,856,157,324,986,458,126,102,50,68,980,654,126,856,145,869,126,478,654,1369,564,982,476,135,697,1206,2254,2346,1129,354}, {0,0,0,0,0,0,0,0,0,0,0,0,124,354,687,495,456,980,50,68,753,1256,1456,953,652,1230,980,564,753,1569,421,684,523,1567,1486,2549,246,123,587,456,128,56,964,346,754,156,492,1347,156,476}, {0,0,0,0,0,0,0,0,0,0,0,0,0,154,687,462,154,987,452,315,684,256,143,697,1256,364,102,50,983,786,842,751,354,712,756,761,365,2245,2641,2830,1465,249,365,148,90,546,56,1478,322,456}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,154,234,685,1254,368,145,50,684,511,398,156,1364,1265,1458,980,654,267,153,98,998,152,1347,654,852,741,963,123,456,789,951,357,126,984,756,102,358}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,154,488,698,154,687,1656,321,1265,1468,980,50,649,354,126,587,456,321,569,153,1025,4523,126,698,124,980,65,874,256,154,862,168,1423,2486,2256,123}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1546,1265,354,156,488,346,1359,1545,356,486,951,652,147,563,156,984,567,126,486,355,458,624,1586,1486,150,60,50,98,415,324,685,1236,142,65}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,45,265,452,418,87,546,123,654,162,1878,1316,16
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 上机