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

1、.安 徽 工 業(yè) 大 學(xué)專 業(yè)：班 級：姓 名：學(xué) 號： 實(shí)驗(yàn)一：回溯法完成0-1背包問題代碼如下：#include "stdafx.h"#include<iostream>#include<cstdio>#include<conio.h>#include<iomanip>using namespace std;template<class ty>class Knappublic:friend void Init();friend void Knapsack();friend void Backtrack(int

2、i);friend float Bound(int i);bool operator<(Knap<ty> a)constif(fl<a.fl) return true;else return false;private:ty w; /重量ty v; /價(jià)值float fl; /單位重量的價(jià)值v/wint kk; /記錄第幾個(gè)物品int flag; /記錄是否放入包中;template<class ty>void Sort(Knap<ty> *li,int n)int i,j,k; Knap<ty> minl;for(i=1;i<

3、n;i+)minl=li0; k=0;for(j=1;j<=n-i;j+)if(minl<lij)minl=lij; swap(lij,lik); k=j;namespace jie /命名空間int c=0,n=0;int *x=NULL;Knap<int> *bag=NULL;int cp=0,cw=0;int bestp=0;using namespace jie;void Init()int i=0;cout<<endl;cout<<"請輸入物品數(shù)量 n = "cin>>n; cout<<end

4、l;cout<<"請輸入背包容量 C = "cin>>c; cout<<endl;bag=new Knap<int> n;x=new intn;cout<<"請依次輸入"<<n<<"個(gè)物品的重量W:"<<endl;for(i=0;i<n;i+)cin>>bagi.w;cout<<endl;cout<<"請依次輸入"<<n<<"個(gè)物品的價(jià)值P:&q

5、uot;<<endl;for(i=0;i<n;i+)cin>>bagi.v;for(i=0;i<n;i+)bagi.flag=0; bagi.kk=i;bagi.fl=1.0*bagi.v/bagi.w;void Backtrack(int i)if(i>=n) /到達(dá)葉節(jié)點(diǎn)bestp=cp; /更新最優(yōu)價(jià)值return;if(cw+bagi.w<=c) /進(jìn)入左子樹bagi.flag=1; cw+=bagi.w;cp+=bagi.v; Backtrack(i+1);cw-=bagi.w; cp-=bagi.v;if(Bound(i+1)>

6、bestp)/進(jìn)入右子樹bagi.flag=0; Backtrack(i+1);/計(jì)算當(dāng)前節(jié)點(diǎn)處的上界float Bound(int i)int cleft = c-cw; /剩余容量float b = cp;while (i<n&&bagi.w<=cleft)/以物品單位重量價(jià)值遞減序裝入cleft-=bagi.w ;b+=bagi.v;i+;/裝滿背包if (i<n) b+=1.0*bagi.v/bagi.w * cleft;return b;void Knapsack() /計(jì)算最優(yōu)解和變量值int L(0); /用L累計(jì)價(jià)值，初始價(jià)值設(shè)置為0for(i

7、nt k=0;k<n;k+)xbagk.kk=bagk.flag; /x=0表示未放入背包，x=1表示放入背包L+=bagk.flag*bagk.v; /價(jià)值累加cout<<endl;cout<<"當(dāng)前最優(yōu)價(jià)值為:"<<L<<endl;cout<<"變量值 x = "for(int i=1;i<=n;i+)cout<<xi-1;delete bag; bag=NULL;delete x; x=NULL;cout<<endl; getch();int main(

8、)cout<<endl;cout<<"|*回溯法解0-1背包問題*|"<<endl;Init();Backtrack(0);Knapsack();return 0;運(yùn)行結(jié)果:實(shí)驗(yàn)二：分治法實(shí)現(xiàn)快速排序代碼如下：#include <stdio.h> #include <time.h> #include <stdlib.h> 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;

9、p = x; q = m; MergeSort(data,x,m,temp); MergeSort(data,m,y,temp); while(p<m|q<y) if (q>=y|(p<m&&datap<dataq) tempi+ = datap+; else tempi+ = dataq+; for(i=x;i<y;i+) datai = tempi; void HoareSort(int *data,int x,int y) int p=x,q=y-1,temp; while(p<q) while (q>p&&

10、dataq>=datap) q-; if (q>p) temp = datap,datap = dataq,dataq =temp; p+; while(q>p&&datap<=dataq) p+; if (p<q) temp = datap,datap = dataq,dataq =temp; q-; if (p=q) HoareSort(data,x,p); HoareSort(data,p+1,y); int main() int data100,i; int temp100; srand(time(NULL); for (i=0;i<

11、=100;i+) datai = rand()%100; for (i=0;i<=100;i+) printf("%d ",datai); printf("n"); HoareSort(data,0,10); for (i=0;i<=100;i+) printf("%d ",datai); printf("n"); 運(yùn)行結(jié)果：實(shí)驗(yàn)三：遞歸法實(shí)現(xiàn)楊輝三角的輸出代碼如下：#include"stdio.h"#include "stdlib.h"#include"

12、;conio.h"int Try(int n, int k)/遞歸函數(shù) if (k = 0 | k = n)/在左右兩側(cè)返回1return 1; /遞歸出口return Try(n-1,k-1) + Try(n-1,k);/返回遞歸公式void print_spack(int t,int mode=0)/顯示空格函數(shù)，這個(gè)是楊輝三角格式控制的關(guān)鍵if (mode!=0)/當(dāng)mode不等于0時(shí)，代表要輸出每行前面的空格，直接循環(huán)輸出t次空格，并退出函數(shù)for (int i = 0; i < t; i+)printf(" ");return ;/直接返回Aif(

13、t<10) printf(" ");/這兒我隨意設(shè)置的！else if (t>9&&t<100)printf(" ");/但是記住規(guī)則：每一行最開始部分的空格減少了k個(gè)，那么當(dāng)t為個(gè)位數(shù)時(shí)輸出k+2個(gè)空格else if(t>99&&t<1000)printf(" ");/其他t的情況依次遞減就行了else if(t>999&&t<10000)printf(" ");/如，我在此設(shè)計(jì)的每行開頭部分減少3個(gè)空格，那么t<9時(shí)

14、輸出5個(gè)空格，t>9&&t<100時(shí)輸出4個(gè)空格，其他遞減else if(t>9999&&t<100000)printf(" ");void scan(int row)/楊輝三角掃描輸出函數(shù)int t = 0 ;if (row>10)/當(dāng)行數(shù)大于10行時(shí)，應(yīng)該將窗口尺寸該大到150,以保證楊輝三角正常顯示，這是一條dos命令，使用system函數(shù)推送執(zhí)行的system("mode con cols=150 lines=150");for (int n=0; n<row; n+)print_spack(3*(row-n),1);/后面第二個(gè)參數(shù)傳了一個(gè)非零參數(shù)，是因?yàn)楦嬖V函數(shù)要直接輸出3*(row-n)個(gè)空格for (int m=0; m<=n; m+)/輸出中間元素printf("%d",t = Try(n,m);/遞歸調(diào)用獲得當(dāng)前第n行，第m個(gè)元素的值，輸出同時(shí)賦值給tprint_spack(t);/這兒沒有傳第二個(gè)參數(shù)是告訴函數(shù)，需要判斷t參數(shù)的位數(shù)來決定