算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告

計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

目錄HYPERLINK實(shí)驗(yàn)一 實(shí)驗(yàn)一[實(shí)驗(yàn)題目]2-7集合劃分問(wèn)題[問(wèn)題描述]n個(gè)元素的集合{1，2，…，n}可以劃分為若干非空子集。例如，當(dāng)n=4時(shí)，集合{1，2，3，4}可以劃分為15個(gè)不同的非空子集。[算法設(shè)計(jì)]給定正整數(shù)n，計(jì)算出n個(gè)元素的集合{1，2，…，n}可以劃分為多少個(gè)不同的非空子集。[算法分析]本算法實(shí)現(xiàn)采用分治法思想，F(xiàn)(n,m)=F(n-1,m-1)+m*F(n-1,m)。假設(shè)將m個(gè)元素分解到n

個(gè)集合中，首先考慮將(m

–

(n

-

1))個(gè)元素分到第一個(gè)集合中，將余下的(n

-

1)個(gè)元素分別分配到余下的(n

-

1)個(gè)集合中，然后再考慮將(m

–

(n

-

2))個(gè)元素分配到第一個(gè)集合中，將余下的(n

-

2)個(gè)元素分別分配到余下的(n

-

1)集合中，依此類(lèi)推，直到后面的有一個(gè)集合中的元素個(gè)數(shù)比第一個(gè)集合中的元素個(gè)數(shù)多為止。[源代碼]#include<iostream>usingnamespacestd;intcompute_bell(introw,intposition){if(row==1)return1;if(row==2&&position==1)return1;else{if(position==1)returncompute_bell(row-1,row-1);elsereturncompute_bell(row,position-1)+compute_bell(row-1,position-1);}}intmain(){intn=0;intm;cout<<"pleaseinputanumber."<<endl;cin>>n;m=compute_bell(n,n);cout<<"theresuleis"<<m<<endl;}[運(yùn)行結(jié)果]實(shí)驗(yàn)二[實(shí)驗(yàn)題目]3-1獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題[問(wèn)題描述]用2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)。設(shè)第i個(gè)作業(yè)交給機(jī)器A處理時(shí)需要時(shí)間ai，若由機(jī)器B來(lái)處理，則需要時(shí)間bi。由于各作業(yè)的特點(diǎn)和機(jī)器的性能關(guān)系，很可能對(duì)于某些i，有ai≥bi，而對(duì)于某些j,j≠i，有aj

<bj。既不能將一個(gè)作業(yè)分開(kāi)由2臺(tái)機(jī)器處理，也沒(méi)有一臺(tái)機(jī)器能同時(shí)處理2個(gè)作業(yè)。設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，使得這2臺(tái)機(jī)器處理完這n個(gè)作業(yè)的時(shí)間最短(從任何一臺(tái)機(jī)器開(kāi)工到最后一臺(tái)機(jī)器停工的總時(shí)間)。研究一個(gè)實(shí)例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。[算法設(shè)計(jì)]對(duì)于給定的2臺(tái)處理機(jī)A和B處理n個(gè)作業(yè)，找出一個(gè)最優(yōu)調(diào)度方案，使2臺(tái)機(jī)器處理完這n個(gè)作業(yè)的時(shí)間最短。[算法分析]當(dāng)完成k個(gè)作業(yè)，設(shè)機(jī)器A花費(fèi)了x時(shí)間，機(jī)器B所花費(fèi)時(shí)間的最小值肯定是x的一個(gè)函數(shù)，設(shè)F[k][x]表示機(jī)器B所花費(fèi)時(shí)間的最小值。則F[k][x]=Min{F[k-1][x]+b[k],F[k-1][x-a[k]]}；其中F[k-1][x]+b[k]表示第k個(gè)作業(yè)由機(jī)器B來(lái)處理（完成k-1個(gè)作業(yè)時(shí)機(jī)器A花費(fèi)的時(shí)間仍是x），F(xiàn)[k-1][x-a[k]]表示第k個(gè)作業(yè)由機(jī)器A處理（完成k-1個(gè)作業(yè)時(shí)機(jī)器A花費(fèi)的時(shí)間是x-a[k]）。

那么單個(gè)點(diǎn)對(duì)較大值Max(x,F[k][x])，表示此時(shí)（即機(jī)器A花費(fèi)x時(shí)間的情況下）所需要的總時(shí)間。而機(jī)器A花費(fèi)的時(shí)間x是變化的，即x=0,1,2……x(max)，由此構(gòu)成了點(diǎn)對(duì)較大值序列。要求整體時(shí)間最短，取這些點(diǎn)對(duì)較大值序列中最小的即可。[源代碼]#include<iostream>#include<fstream>#include<iomanip>usingnamespacestd;constintSIZE=50;constintMAXINT=999;intmain(){while(1){intN,a[SIZE],b[SIZE],SumA[SIZE],SumB[SIZE];inttempSumA,tempSumB,MinSum;inti=0,j,k;tempSumA=tempSumB=0;intdata;intoriData[SIZE];ifstreamifile;ifile.open("input.txt");if(ifile.eof()){cerr<<"Failtoopenthefileinput.txt"<<endl;return1;}while(ifile>>data){oriData[i++]=data;}N=(int)oriData[0];for(i=1;i<=N;i++){a[i]=oriData[i];tempSumA+=a[i];SumA[i]=tempSumA;}for(i=1,j=N+1;j<=2*N;j++,i++){b[i]=oriData[j];tempSumB+=b[i];SumB[i]=tempSumB;}cout<<"Input.txtData:"<<endl;cout<<oriData[0]<<endl;for(i=1;i<=2*N;){cout<<oriData[i]<<"";i++;cout<<oriData[i]<<endl;i++;}cout<<endl;ifile.close();MinSum=(tempSumB>tempSumA)?tempSumA:tempSumB;int*MaxTime=newint[MinSum+1];int**F=newint*[N+1];for(i=0;i<N+1;i++)F[i]=newint[MinSum+1];SumB[0]=0;for(i=0;i<=N;i++){F[i][0]=SumB[i];for(j=1;j<=MinSum;j++)F[i][j]=0;}inttemp;for(k=1;k<=N;k++){temp=(SumA[k]>SumB[k])?SumB[k]:SumA[k];for(i=1;i<=temp;i++){if(i>=a[k])F[k][i]=(F[k-1][i]+b[k]<F[k-1][i-a[k]])?F[k-1][i]+b[k]:F[k-1][i-a[k]];elseF[k][i]=F[k-1][i]+b[k];}}temp=MAXINT;for(i=0;i<=MinSum;i++){MaxTime[i]=(i>F[N][i])?i:F[N][i];if(temp>MaxTime[i])temp=MaxTime[i];}ofstreamofile;ofile.open("output.txt");ofile<<temp<<endl;ofile.close();cout<<"thebesttimeis"<<temp<<endl;while(1);}}[運(yùn)行結(jié)果]實(shí)驗(yàn)三[實(shí)驗(yàn)題目]4-9汽車(chē)加油問(wèn)題[問(wèn)題描述]一輛汽車(chē)加滿油后可行駛nkm。旅途中有若干加油站。設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在那些加油站?？考佑停寡赝炯佑痛螖?shù)最少。并證明算法能產(chǎn)生一個(gè)最優(yōu)解。[算法設(shè)計(jì)]對(duì)于給定的n和k個(gè)加油站位置，計(jì)算最少加油次數(shù)。[算法分析]將一輛汽車(chē)在出發(fā)地加滿油，每次加滿可行駛nkm，利用相鄰加油站之間距離d[]是否可行駛的距離，并利用貪心算法計(jì)算最優(yōu)解。[源代碼]#include<stdio.h>voidGreedy(intd[],intn,intk){intsum=0;inti=0;intj=0;for(i=0;i<k;i++){if(d[i]>n){printf("NoSolution\n");return;}}for(i=0,j=0;i<k;i++){j+=d[i];if(j>n){sum++;j=d[i];}}printf("minrefueltime:%d\n",sum);}intmain(){inti,n,k;intd[100];printf("inputthelength:\n");scanf("%d",&n);printf("inputthenumberofstations:\n");scanf("%d",&k);printf("inputthelengthoftwostation:\n");for(i=0;i<k+1;i++)scanf("%d",&d[i]);Greedy(d,n,k+1);return0;}[運(yùn)行結(jié)果]實(shí)驗(yàn)四[實(shí)驗(yàn)題目]最短加法鏈問(wèn)題[問(wèn)題描述]最優(yōu)求冪問(wèn)題：給定一個(gè)正整數(shù)n和一個(gè)實(shí)數(shù)x，如何用最少的乘法次數(shù)計(jì)算出xn。例如，可以用6次乘法逐步計(jì)算x23如下：x,x2,x3,x5,x10,x20,x23?？梢宰C明,計(jì)算x23的冪序列中各冪次組成正整數(shù)n的一個(gè)加法鏈：1=a0<a1<a2<…<ar=nar=aj+ak,k<=j<I,i=1,2,…,r上述最優(yōu)求冪問(wèn)題相應(yīng)于正整數(shù)n的最短加法鏈問(wèn)題，即求n的一個(gè)加法鏈?zhǔn)蛊溟L(zhǎng)度r達(dá)到最小。正整數(shù)n的最短加法鏈長(zhǎng)度記為l(n)。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第1行有1個(gè)正整數(shù)n。結(jié)果輸出：將計(jì)算的最短加法鏈長(zhǎng)度l(n)和相應(yīng)的最短加法鏈輸出到文件output.txt。[算法設(shè)計(jì)]對(duì)于給定的正整數(shù)n，計(jì)算相應(yīng)于正整數(shù)n的最短加法鏈。[算法分析]問(wèn)題的解空間是一棵排列數(shù)，元素的孩子數(shù)目是其祖先和自己的一個(gè)全排列。利用迭代回溯遍歷每個(gè)活結(jié)點(diǎn)，求出每個(gè)加法鏈的長(zhǎng)度并進(jìn)行比較，記錄最小值進(jìn)行輸出。[源代碼]#include<cstdlib>#include<stdio.h>#include<fstream>#include<iomanip>#include<iostream>usingnamespacestd;intminStep=INT_MAX;inta[1000];intchain[20];intn;//迭代回溯法求解intbacktrack(intstep){if(a[step]==n){if(step<minStep){minStep=step;for(inti=1;i<=minStep;i++)chain[i]=a[i];returnstep;}}for(inti=step;i>=1;i--){if(2*a[i]>a[step])for(intj=i;j>=1;j--){intk=a[i]+a[j];a[step+1]=k;if(k>a[step]&&k<=n)backtrack(step+1);}}}intmain(){//輸入數(shù)據(jù)ifstreamin("input.txt");if(!in){return0;}in>>n;in.close();//求解問(wèn)題a[1]=1;backtrack(1);//輸出數(shù)據(jù)ofstreamout("output.txt");out<<minStep<<endl;for(inti=1;i<minStep;i++){out<<chain[i]<<"";}//最后一個(gè)元素out<<chain[minStep];out.close();system("PAUSE");returnEXIT_SUCCESS;}實(shí)驗(yàn)截圖：輸入：輸出：實(shí)驗(yàn)五：[實(shí)驗(yàn)題目]旅行售貨員問(wèn)題[問(wèn)題描述]某售貨員要到若干城市去推銷(xiāo)商品，已知各城市之間的路程（或旅費(fèi)）。他要選擇一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍，最后回到駐地的路線，使總的路程（或總旅費(fèi)）最小。[算法設(shè)計(jì)]對(duì)于給定的鄰接矩陣圖，計(jì)算花費(fèi)最少的周游路。[算法分析]數(shù)據(jù)輸入：由input.txt文件提供輸入，第一行n表示城市數(shù)目，之后為n行n列表示城市的鄰接矩陣，-1表示兩個(gè)城市直接沒(méi)有路。數(shù)據(jù)輸出：將最小花費(fèi)輸出到output.txt。本算法采用最小值堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。其優(yōu)先級(jí)是節(jié)點(diǎn)當(dāng)前費(fèi)用。堆的數(shù)據(jù)結(jié)構(gòu)不再贅述。對(duì)排列數(shù)的解空間進(jìn)行廣度優(yōu)先遍歷，每次將活結(jié)點(diǎn)入堆，從堆頂取出結(jié)點(diǎn)并展開(kāi)，記錄最小花費(fèi)，當(dāng)堆中元素為空時(shí)輸出結(jié)果到output.txt。#include<stdio.h>#include<stdlib.h>#include<math.h>#include<limits.h>typedefstructpoint{ intx,y;}point;doubleget_distance(constpoint*a,constpoint*b);intcmp_point(constvoid*a,constvoid*b){ point*p_a=(point*)a; point*p_b=(point*)b; returnp_a->x-p_b->x;}intpoint_size;point*points=NULL;double**distances;double*results=NULL;voidread_in(){ inti,j; scanf("%d",&point_size); points=(point*)malloc(sizeof(point)*point_size); for(i=0;i<point_size;i++) { scanf("%d%d",&(points[i].x),&(points[i].y)); } distances=(double**)malloc(sizeof(double*)*point_size); for(i=0;i<point_size;i++) { distances[i]=(double*)malloc(sizeof(double)*point_size); distances[i][i]=0; for(j=i+1;j<point_size;j++) { distances[i][j]=get_distance(points+i,points+j); } } results=(double*)malloc(sizeof(double)*point_size); results[0]=0; results[1]=distances[0][1]*2;}voiddestory(){ free(points); points=NULL; point_size=0; free(results);}doubleget_distance(constpoint*a,constpoint*b){ intx1=a->x; inty1=a->y; intx2=b->x; inty2=b->y; returnsqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}doubleget_min(){ inti,k,j; for(i=2;i<point_size;i++) { results[i]=INT_MAX; for(k=1;k<i;k++) { doublesum_distance=0.0; doublek_distance=distances[k-1][k]; doublek_i_distance=distances[k-1][i]; for(j=k;j<i;j++) { sum_distance+=distances[j][j+1]; } if(results[i]>results[k]+sum_distance+k_i_distance-k_distance) { results[i]=results[k]+sum_distance+k_i_distance-k_distance; } } } returnresults[point_size-1];}intmain(intargc,char*argv[]){ read_in(); printf("%.2lf\n",get_min()); destory(); return0;}/**706102354617582*/運(yùn)行結(jié)果如下：

時(shí)間復(fù)雜度：O(n3),空間復(fù)雜度是O(n2).旅行售貨員回溯法#include<stdio.h>#include<string.h>#include<stdlib.h>#include<float.h>#defineN1000doubleminCost=DBL_MAX;doublecost[N][N];intnodeNumber;doublecurCost;intrecord[N];intminRecord[N];voidreadInfo(){ scanf("%d",&nodeNumber); intcount; scanf("%d",&count); inti,j; for(i=0;i<nodeNumber;i++) { for(j=0;j<nodeNumber;j++) { cost[i][j]=0; } } while(count--) { intleft,right; scanf("%d%d",&left,&right); scanf("%lf",&(cost[left][right])); cost[right][left]=cost[left][right]; } for(i=0;i<nodeNumber;i++) { record[i]=i; }}voidswap(int*a,int*b){ inttemp=*a; *a=*b; *b=temp;}//初始值depth為1,而不為0.voidBacktrack(intdepth){ if(depth==nodeNumber) { if(cost[record[depth-1]][0]) { if(cost[record[depth-1]][0]+curCost<minCost) { minCost=cost[record[depth-1]][0]+curCost; inti; for(i=0;i<nodeNumber;i++) { minRecord[i]=record[i]; } } } return; } inti; for(i=depth;i<nodeNumber;i++) { if(cost[record[depth-1]][i]) { swap(record+i,record+depth); //添加該節(jié)點(diǎn). curCost+=cost[record[depth-1]][i]; intj; for(j=0;j<=i;j++) { printf("%d\t",record[j]); } printf("\n"); Backtrack(depth+1); curCost-=cost[record[depth-1]][i]; swap(record+i,record+depth); } }}voidwriteInfo(){ printf("minCost:%lf\n",minCost); inti; for(i=0;i<nodeNumber;i++) { printf("%d\t",minRecord[i]); } printf("0"); printf("\n");}intmain(intargc,char*argv[]){ readInfo(); Backtrack(1); writeInfo();}/**46011.6021.1031.2121.4131.5231.7*/截圖顯示：

旅行售貨員問(wèn)題：分支限界法顯示：

使用了最小優(yōu)先級(jí)隊(duì)列：minPriority:頭文件：miqueue.h

#ifndef_MINQUEUE_H#define_MINQUEUE_H#include"travel.h"externstructelementqueue[N];//隊(duì)列的大小.externintelementSize;voidadd_queue(structelemente);//查看最小.intpeel(structelement*first);//刪除最小,如果說(shuō)返回NULL,標(biāo)明peek為空.intpeek(structelement*first);#endifDiver.h:#ifndef_H_TRAVEL#define_H_TRAVEL#defineN1000structelement{ intvisited[N]; //當(dāng)前節(jié)點(diǎn)是否被訪問(wèn). doublecost; //當(dāng)前的花費(fèi). intvisitedNumber;//當(dāng)前訪問(wèn)的節(jié)點(diǎn)的數(shù)目，當(dāng)?shù)扔趎odeNumber的時(shí)候，說(shuō)明了訪問(wèn)結(jié)束，同時(shí)cost加上它到其實(shí)節(jié)點(diǎn)的花費(fèi)就可以得到總的花費(fèi). intlastNode; //最后被訪問(wèn)的節(jié)點(diǎn).};//最小花費(fèi).externdoubleminCost;//兩個(gè)節(jié)點(diǎn)的花費(fèi).externdoublecost[N][N];#endifMinqueue.c:#include"minqueue.h"structelementqueue[N];intelementSize=0;staticvoidkeepQueueInUp();staticvoidkeepQueueInDown();staticdoublecmpElement();voidadd_queue(structelemente){ queue[elementSize]=e; elementSize++; keepQueueInUp();}//查看最小.intpeel(structelement*first){ if(elementSize==0) { return0; } *first=queue[0]; return1;}//刪除最小,如果說(shuō)返回NULL,標(biāo)明peek為空.intpeek(structelement*first){ if(elementSize==0) { return0; } elementSize--; *first=queue[0]; queue[0]=queue[elementSize]; keepQueueInDown(0); return1;}voidkeepQueueInUp(){ //最后一個(gè)值可能不滿足堆的性質(zhì). inttempIndex=elementSize-1; while(tempIndex!=0) { //滿足堆性質(zhì). if(cmpElement(queue+(tempIndex-1)/2,queue+tempIndex)<=0.0) { break; } //進(jìn)行交換. structelementtemp=queue[tempIndex]; queue[tempIndex]=queue[(tempIndex-1)/2]; queue[(tempIndex-1)/2]=temp; //繼續(xù)向上. tempIndex=(tempIndex-1)/2; }}voidkeepQueueInDown(intparent){ intleft=parent*2+1; intright=parent*2+2; intmin=parent; if(left<elementSize&&cmpElement(queue+min,queue+left)>0.0) { min=left; } if(right<elementSize&&cmpElement(queue+min,queue+right)>0.0) { min=right; } if(min!=parent) { structelementtemp=queue[parent]; queue[parent]=queue[min]; queue[min]=temp; keepQueueInDown(min); }}doublecmpElement(structelement*a,structelement*b){ returna->cost-b->cost;}Driver.c:#include<stdio.h>#include<float.h>#include"travel.h"#include"minqueue.h"#include<string.h>#include<stdlib.h>doubleminCost=DBL_MAX;//節(jié)點(diǎn)的數(shù)目.intnodeNumber;//兩個(gè)節(jié)點(diǎn)的花費(fèi).doublecost[N][N];voidreadInfo(){ scanf("%d",&nodeNumber); intcount; scanf("%d",&count); inti,j; for(i=0;i<nodeNumber;i++) { for(j=0;j<nodeNumber;j++) { cost[i][j]=0; } } while(count--) { intleft,right; scanf("%d%d",&left,&right); scanf("%lf",&(cost[left][right])); cost[right][left]=cost[left][right]; }}staticvoidinitElement(structelement