2020年計(jì)算機(jī)算法設(shè)計(jì)與分析課程設(shè)計(jì)常規(guī)題目的C及C代碼集

計(jì)算機(jī)算法設(shè)計(jì)與分析課程設(shè)計(jì)常規(guī)

題目的C及C代碼集

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

合并排序1:

#include<iostream>

usingnamespacestd;

constintN=100;

classlist

(

public:

intarray[N];

voidinput(inta);

voidmerge(intarrayc[],intarrayd[],int

l,intm,intr);

voidmergepass(intarrayx[],int

arrayy[],ints);

voidmergesort(intarrayl[]);

voiddiaplay(inta);

)；

voidlist::input(inta)

(

cout?MPleaseinputshortedarray:n?endl;

for(inti=0;i<a;i++)

cin?array[i];

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

voidlist::merge(intarrayc[],intarrayd[],intl,int

m,intr)

(

inti=l;

intj=m+l;

intk=l;

while((i<=m)&&(j<=r))

if(arrayc[i]<=arrayc[j])

arrayd[k++]=arrayc[i++];

elsearrayd[k++]=arrayc[j++];

if(i>m)

for(intq=j;q<=r;q++)

arrayd[k++]=arrayc[q];

else

for(intq=i;q<=m;q++)

arrayd[k++]=arrayc[q];

)

voidlist::mergepass(intarrayx[],intarrayy[],int

s)

inti=0;

while(i<=N-2*s)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

merge(arrayx,arrayy,i,i+s-l,i+2*s-l);

i=i+2*s;

)

if((i+s)<N)

merge(arrayx,arrayy,i,i+s-l,N-l);

else

for(intj=i;j<N;j++)

arrayy[j]=arrayx[j];

)

voidlist::mergesort(intarray1[])

(

intarray2[N];

ints=l;

while(s<N)

(

mergepass(arrayl,array2,s);

s+=s;

mergepass(array2,array1,s);

s+=s;

)

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

voidlist::diaplay(inta)

(

for(inti=N-a;i<N;i++)

cout?array[i];

)

voidmain()

(

listf;

inta;

coutvv”請(qǐng)輸入要合并排序的數(shù)組大小：(數(shù)

組最大上限100)”vveii祖；

cin?a;

f.input(a);

f.mergesort(f.array);

f.diaplay(a);

)

合并排序：2

#include<iostream>

usingnamespacestd;

voidMERGES(int*A,intp,intq,intr)〃下標(biāo)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

P<=q<r

intnl=q-p+l;//nl:p,q之間的數(shù)的個(gè)數(shù)

intn2=r-q;//n2：q以后到r的數(shù)的個(gè)數(shù)

int*L=newint[nl+1],〃動(dòng)態(tài)申請(qǐng)兩個(gè)子

數(shù)組

*R=newint[n2+l];

inti,j,k;

for(i=0;i<nl;i++)

(

L[i]=A[p+i-l];

)

for(j=0;j<n2;j++)

(

R[j]=A[q+j]；

)

L[nl]=10000;〃設(shè)置哨兵

R[n2]=10000;

i=0;

j=0；

for(k=p-l;k<r;k++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

if(L[i]<=R[j])

(

A[k]=L[i];

i=i+l;

)

else

(

A[k]=RU];

j=j+l；

)

)

)

voidMERGESORT(int*A,intp,intr)

(

if(P<r)

(

intq=(p+r)/2;

MERGESORT(A,p,q);

MERGESORT(A,q+l,r);

MERGES(A,p,q,r);

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

voidmain()

intx,z,p,r;

cout?”請(qǐng)輸入數(shù)組長(zhǎng)度"vVendl;

cin?x;

int*A=newint[x];

cout?"請(qǐng)輸入數(shù)組的元素"vvendl;

for(inty=0;y<x;y++)

(

cin?z;

A[y]=z;

)

coutvv”請(qǐng)輸入上下限p,rn?endl;

cin?p?r;

MERGESORT(A,p,r);

cout?"合并排序后為："vVendl;

for(intm=p;m<=r;m++)

(

cout?A[m];

)

delete[]A;

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

合并排序3：

#include<iomanip.h>

#include<iostream.h>〃這個(gè)函數(shù)將b[0]至

b[right」eft+l]拷貝到至a[right]

template<classT>

voidCopy(Ta[],Tb[],intleft,intright)

(

intsize=right-left+l;

for(inti=0;i<size;i++)

(

a[left++]=b[i];

)

)〃這個(gè)函數(shù)合并有序數(shù)組

到b,得到新的有序數(shù)組b

template<classT>

voidMerge(Ta[],Tb[],intleft,inti,intright)

(

intalcout=leftj/指向第一個(gè)數(shù)組開頭

alend=i〃指向第一個(gè)數(shù)組結(jié)尾

a2cout=i+l,〃指向第二個(gè)數(shù)組開頭

a2end=right,〃指向第二個(gè)數(shù)組結(jié)尾

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

bcout=0;〃指向b中的元素

for(intj=0;j<right-left+1；j++)//執(zhí)行

right-left+1次循環(huán)

(

if(alcout>alend)

(

b[bcout++]=a[a2cout++];

continue;

}〃如果第一個(gè)數(shù)組結(jié)束，拷貝第二個(gè)數(shù)組的

元素到b

if(a2cout>a2end)

(

b[bcout++]=a[alcout++];

continue;

}〃如果第二個(gè)數(shù)組結(jié)束，拷貝第一個(gè)數(shù)組的

元素到b

if(a[alcout]<a[a2cout])

(

b[bcout++]=a[alcout++];

continue;

}〃如果兩個(gè)數(shù)組都沒(méi)結(jié)束，比較元素大小，

把較小的放入b

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

else

b[bcout++]=a[a2cout++];

continue;

)

)

}〃對(duì)數(shù)組right]進(jìn)行合并排序

template<classT>

voidMergeSort(Ta[],intleft,intright)

(

T*b=newint[right-left+l];

if(left<right)

(

inti=(left+right)/2;〃取中點(diǎn)

MergeSort(a,left,i);〃左半邊進(jìn)行合并排序

MergeSort(a,i+l,right);〃右半邊進(jìn)行合并排

序

Merge(a,b,Ieft,i,right);〃左右合并到b中

Copy(a,b,left,right);//Ab拷貝回來(lái)

)

}//from

intmain()

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

intn;

cout?nhowmanynumberstosort:'';

cin?n;

int*a=newint[n];

cout?ninputn?n?nnumbers:n;

for(inti=0;i<n;i++)

(

cin?a[i];

)

MergeSort(a,0,n-1);

for(intj=O;j<n;j++)

(

cout?setw(5)?a[j];

)

return1;

)

合并排序4：

#include<iostream>

usingnamespacestd;

voidMerge(inta[],intb[],intl,intm,intr)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

inti=I,j=m+l,k=l;

while((i<=m)&&(j<=r))

if(a[i]<=a[j])b[k++]=a[i++];

elseb[k++]=a[j++];

if(i>m)

for(intq=j;q<=r;q++)

b[k++]=a[q];

else

for(intq=i;q<=m;q++)

b[k++]=a[q];

)

voidCopy(inta[],intb[],ints,intn)

(

for(inti=s;i<=n;i++)

a[i]=b[i];

)

voidMergeSort(inta[],intleft,intright)

(

inti;

if(left<right)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

i=(left+right)/2;

intb[100];

MergeSort(a,left,i)；

MergeSort(a,i+l,right);

Merge(a,b,left,i,right);

Copy(a,b,left,right);

)

)

intmain()

(

inta[100];

intn,i；

coutvv”輸入元素個(gè)數(shù)n:u;

cin?n;

coutvv”輸入一維數(shù)組a[n?n?n]:n;

for(i=0;i<n;i++)

cin?a[i];

MergeSort(a,0,n-l);

coutvv”輸出排序?yàn)?“；

for(i=0;i<n;i++)

cout?a[i]?,

cout?endl;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

return0;

)

矩陣相乘1：

#include<iostream>

#include<stdio.h>

usingnamespacestd;

intmain()

(

inti,j,k;

coutvv”輸入二維數(shù)組a的行數(shù)和二維數(shù)組c

的行數(shù)x:n;

intx;

cin?x;

coutvv”輸入二維數(shù)組a的列數(shù)和二維數(shù)組b

的行數(shù)y：n;

inty;

cin?y;

coutvv”輸入二維數(shù)組b的列數(shù)和二維數(shù)組c

的行數(shù)Z：”；

intz;

cin?z;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

int**a,**b,**c;

a=newint*[x];

for(i=0;i<x;i++)

(

a[i]=newint[y];

)

coutvv”輸入二維數(shù)組a:H?endl;

for(i=0;i<x;i++)

(

for(j=0;j<y;j++)

(

cin?a[i][j];

)

)

b=newint*[y];

for(i=0;i<y;i++)

(

b[i]=newint[z];

)

coutvv”輸入二維數(shù)組b:n?endl;

for(i=0;i<y;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(j=0;j<z;j++)

(

cin?b[i][j];

)

)

c=newint*[x];

for(i=0;i<x;i++)

(

c[i]=newint[z];

)

coutvv”輸入二維數(shù)組c:n?endl;

for(i=0;i<x;i++)

(

for(j=0;j<z;j++)

(

c[i]U]=0;

)

)

for(i=0;i<x;i++)

for(j=0;j<z;j++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(k=0;k<y;k++)

(

c[i][j]+=a[i][k]*b[k][j];

)

)

)

for(i=0;i<x;i++)

(

for(j=0;j<z;j++)

(

coutvvc[i][j]vv，'；

)

cout?endl;

)

for(i=0;i<x;i++)

(

delete[]a[i];

)

delete[]a;

for(i=0;i<x;i++)

delete[]c[i];

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

)

delete[]c;

for(i=0;i<y;i++)

(

delete[]b[i];

)

delete[]b;

return0;

)

矩陣相乘2：

#include<iostream>

usingnamespacestd;

#defineM2

#defineN3

#defineP4

intmain()

(

inta[M][N]={{l,2,3},{4,5,6});

intb[N][P]={{7,8,9」},{2,3,4,5},{6,7,8,9}};

intc[M][P];

inti,j,k;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(i=0;i<M;i++)

for(j=0;j<P;j++)

c[i][j]=O;

for(i=0;i<M;i++)

for(j=0;j<P;j++)

for(k=0;k<N;k++)

c[i][j]+=a[i][k]*b[k][j];

cout?n矩陣相乘結(jié)果是："vVendl;

for(i=0;i<M;i++){for(j=0;j<P;j++)

cout?c[i][j]?nn;

cout?endl;

}//system(npause");

return0;

)

矩陣相乘3：

#include<iostream>

#include<iomanip>

usingnamespacestd;

intmain()

constintm=3;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

constintn=3;

inta[m][n],i,j;〃初始化數(shù)組a,b

for(i=0;ivm;i++)〃對(duì)數(shù)組a賦值并顯示

(

for(j=O;j<n;j++)

(

cout?na[n?i?n]n?n[n?j?n]=n;

cin?a[i][j];

)

)

for(i=0;i<m;i++)

(

for(j=O;j<n;j++)

cout?setw(4)?a[i][j];

cout?endl;

)

constintk=3;

constinth=2;

intb[k][h],x,y;

for(x=0;x<k;x++)

for(y=0;y<h;y++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cout?nb[n?x?n]n?n[n?y?n]=n;

cin?b[x][y];

)

)

for(x=O;x<k;x++)

(

for(y=O;y<h;y++)

cout?setw(4)?b[x][y];

cout?endl;

)

intc[m][h];//乘賦值給數(shù)組c

for(intr=O;r<m;r++)

(

for(intt=O;t<h;t++)〃數(shù)組a與b相〃對(duì)

數(shù)組b賦值并顯示

(

c[r][t]=O;

for(ints=O;s<k;s++)

(

c[r][t]+=a[r][s]*b[s][t];

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

)

)

cout?nc[n?m?n]n?n[n?h?n]H?endI;

for(intz=O;z<m;z++)

(

for(intw=O;w<h;w++)

cout?setw(4)?c[z][w];

cout?endl;

)

return0;〃顯示數(shù)組c

)

矩陣相乘4：

#include<iostream>

usingnamespacestd;

voidchain(int*p,intn,intm[][7],mts[][7])//p維

數(shù)數(shù)組，m最優(yōu)乘次數(shù)組，s記錄劃分方案

(

intj;

for(inti=l;i<=n;i++)

m[i][i]=0;

for(intr=2;r<=n;r++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(i=l;i<=n-r+l;i++)

(

j=i+r-l；

m[i][j]=m[i+l][j]+p[i-l]*p[i]*p[j];

s[i][j]=i；

for(intk=i+l;k<j;k++)

(

int

t=m[i][k]+m[k+l][j]+p[i-l]*p[k]*p[j];

if(t<m[i][j])

(

m[i][j]=t;

s[i][j]=k;

)

)

for(i=l;iv=n;i++)〃我把它翻過(guò)來(lái)輸出。。。

for(j=ii;j>=i;j-)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cout?m[i][j]?M;

)

cout?endl;

)

)

voidTraceback(inti,intj,ints口[7])〃輸出相乘方

案

(

if(i==j)

return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+l,j,s);

cout?HMultiplyAn?i?n,n?s[i][j];

cout?"andB''?(s[i][j]+l)?n,H?j?endl;

return;

)

intmain()

(

intp[7],m[7][7],s[7][7],n;

while(n!=EOF)

for(inti=0;i<=n;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cin?p[i]?endl;

)

chain(p,n,m,s);

Traceback(l,6,s);

)

return0;

)

Haffman編碼1：

#include<iostream>

#include<string>

usingnamespacestd;

typedefstruct

(

intweight;

intflag;

intparent;

intlehild;

intrchild;

)

hnodetype;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

typedefstruct

(

intbit[10];

intstart;

charleaf;

)

hcodetype;

voidhuf(charcha[],intm[],mtn)

(

inti,j,ml,m2,xl,x2,c,p;

hnodetype*huffnode=newhnodetype[2*n-l];

hcodetype*huffcode=newhcodetype[n],cd;

for(i=0;i<2*n-l;i++)

(

huffnode[i].weight=0;

huffnode[i].parent=0;

huffnode[i].flag=0;

huffnode[i].lchild=-l;

huffnode[i].rchild=-l;

)

for(i=0;i<n;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

huffnode[i].weight=m[i];

huffcode[i].leaf=cha[i];

)

for(i=0;i<n-l;i++)

(

ml=m2=10000000;

xl=x2=0;

for(j=0;j<n+i;j++)

(

if

(huffnode[j].weight<=ml&&huffnode[j].flag==0

)

(

m2=ml;

x2=xl;

ml=huffnode[j].weight;

xl=j；

)

else

if(huffnode[j].weight<=m2&&huffnode[j].flag=

=0)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

m2=huffnode[j].weight;

x2=j;

)

)

huffnode[xl].parent=n+i;

huffnode[x2].parent=n+i;

huffnode[xl].flag=l;

huffnode[x2].flag=l;

huffnode[n+i].weight=huffnode[xl].weight+h

uffnode[x2].weight;

huffnode[n+i].lchild=xl;

huffnode[n+i].rchild=x2;

)

for(i=0;i<n;i++)

(

cd.start=n-l;

c=i;

p=huffnode[c].parent;

while(p!=O)

if(huffnode[p].lchild==c)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cd.bit[cd.start]=O;

else

cd.bit[cd.start]=l;

cd.start—;

c=p；

p=huffnode[c].parent;

)

cout?huffcode[i].leaf?

for(j=cd.start+l;j<n;j++)

(

huffcode[i].bit[j]=cd.bit[j];

cout?cd.bit[j];

)

cout?endl;

huffcode[i].start=cd.start;

)

delete[]huffcode;

delete[]huffnode;

)

voidmain()

stringstr;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

inti=0,j,n,m[100],h,k=0;

charcha[100];

coutvv”請(qǐng)輸入一個(gè)字符串n?endl;

cin?str;

n=str.length();

cout?n字符串總共有字符n?n?n個(gè)

n?endl;

for(i=0;i<n;i++)

(

j=0；

h=0;

while(str[i]!=str[j])

j++；

(

cha[k]=str[i];

cout?"字符"?cha[k]?"出現(xiàn)"；

)

elsecontinue;

for(j=i;j<n;j++)

if(str[i]==str[j])h++;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

)

cout?h?"次"vvendl;

m[k]=h;

k++;

)

coutvv”每個(gè)字符的哈夫曼編碼是：n?endl;

huf(cha,m,k);

cin.get();

cin.get();

)

Haffman編碼2：

#include<iostream>

usingnamespacestd;

〃********************************〃構(gòu)造哈

yvAis：尤//不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不/不

哈夫曼樹順序表的定義*/

typedefstruct

intweight;

intparent,lchild,rchild;

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

HTNode;

typedefHTNode*HuffmanTree;/*初始化一個(gè)

哈夫曼樹*/

voidInitHuffmanTree(HuffmaiiTree&HT,int

m)

(

inti;

HT=newHTNode[m];

for(i=0;i<m;i++)

HT[i].weight=O;

HT[i].parent=-l;

HT[i].lchild=-l;

HT[i].rchild=-l;

)

)

//al*a￡<?KJA<￡?<{>

1t

〃從n個(gè)結(jié)點(diǎn)中選取最小的兩個(gè)結(jié)點(diǎn)

//?]??￡??￡>?]?

1arj?q、rj、rJwrj?rj?rjwrjwrjwrj?rjwrJwrj?rj?rj?rf?rjwrj?乙、*Jwrjwrj—rj?rjwrj*rj?rj?rjfrj?rj>rjw

voidSelectMin(HuffmanTree&HT,intn,int

&minl,int&min2)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

typedefstruct

(

intNewWeight;〃存儲(chǔ)權(quán)

intp;〃存儲(chǔ)該結(jié)點(diǎn)所在的位置

)

TempNode,*TempTree;

TempTreeTT=newTempNode[n];

inti,j;

j=0；

for(i=0;i<n;i++)

(

if(HT[i].parent==-l&&HT[i].weight!=O)

(

TT[j].NewWeight=HT[i].weight;

TT[j].p=i;

j++；

)

}〃將HT中沒(méi)有雙親的結(jié)點(diǎn)存儲(chǔ)到TT中

intml,m2;

ml=m2=0;

for(i=0;i<j;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

if(TT[i].NewWeight<TT[ml].NewWeight)//

此處不讓取到相等，是因?yàn)榻Y(jié)點(diǎn)中有相同權(quán)值的

時(shí)候，ml取最前的那個(gè)。

ml=i;

)

for(i=0;i<j;i++)

(

if(ml==m2)

m2++;〃當(dāng)ml在第一個(gè)位置的時(shí)候，m2

向后移一位

if(TT[i].NewWeight<=TT[m2].NewWeight

&&i!=ml)〃此處取到相等，是讓在結(jié)點(diǎn)中有相

同的權(quán)值的時(shí)候，〃m2取最后的那個(gè)。

m2=i;

)

minl=TT[ml].p;min2=TT[m2].p;

}/*創(chuàng)立哈夫曼樹*/

voidCreateHaffmanTree(HuffmanTree&HT,int

n)

(

inti;

intm;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

intminl9min2;

if(n<=l)

cout?**ParameterError!n;

m=2*n-l;〃哈夫曼樹中結(jié)點(diǎn)的個(gè)數(shù)

InitHuffmanTree(HT,m);

for(i=0;i<n;i++)

(

cin?HT[i].weight;

)

for(i=n;i<m;i++)

(

SelectMin(HT,i,minl,min2);

HT[minl].parent=i;

HT[min2].parent=i;

HT[i].lchild=minl;

HT[i].rchild=min2;

HT[i].weight=HT[minl].weight+HT[min2].we

ight;

cout?minl?nn?min2?endl;

)

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

哈夫曼編碼

〃//芋￥￥7**，*1*￥￥￥*7，**1**￥￥￥<￡?*KJ***KY>￥￥<￡*￥**KJ>￥<￡?￥<￡?￥**KY>**!?￥<￡￥*K!￥?<?*>**KJ/*/*KJ*哈

夫曼編碼的定義*/

typedefstruct

(

charch;

charbits[10];

)

CodeNode;

typedefCodeNode*HuffmanCode;/*哈夫曼編

碼的構(gòu)造*/

voidCreateHuffmanCode(HuffmanTree

&HT,HuffmanCode&HC,intn)

(

inti;

intstart;

intc;

intp;

char*cd;

charq;

HC=newCodeNode[n];

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cd=newchar[n];

cd[n-l]=70,;

for(i=0;i<n;i++)

(

cin?q;

HC[i].ch=q;

start=n-l;

c=i;

while((p=HT[c].parent)>=0)

(

—start;

cd[start]=(HT[p].lchild==c)?,O*:T;c=p;

)

strcpy(HC[i].bits,&cd[start]);

)

deletecd;

}/*哈夫曼編碼的輸出*/

voidOutputHuffmanCode(HuffmanCode

&HC,intn)

(

inti;

for(i=0;i<n;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cout?HC[i].ch?nn?HC[i].bits?endl;

)

)

voidmain()

(

inti;

coutvv”輸入字符個(gè)數(shù)：”；

cin?i;

HuffmanTreeHT;

HuffmanCodeHC;

CreateHaffmanTree(HT,i);

CreateHuffmanCode(HT,HC,i)；

OutputHuffmanCode(HC,i)；

)

圖形著色1：

#include<cstdlib>

#includeviostream>〃回溯法

usingnamespacestd;//judgethecoloration

isValidornot.

boolisValid(boolb[5][5],intk,intx[])

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(inti=0;i<k;++i)

if(!b[k][i])

continue;

elseif(b[k][i]&&x[k]==x[i])

returnfalse;

returntrue;

}//by:潘喬木

intmain(intargc,char*argv[])

(

intn=5;

血111=3;〃第》個(gè)頂點(diǎn)的著色號(hào)碼(解向量)

intx[5];

boolb[5][5]={true,true,true,false,false,true,

true,true,true,true,true,

true,true,false,true,false,true,false,true,true,false

,true,true,true,true};

for(inti=0;i<5;i++)

x[i]=0;

intk=0;//whiles

while(k>=0)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

x[k]=x[k]+1;〃著色無(wú)效繼續(xù)再當(dāng)前層

搜索有效的顏色

while(x[k]<=m&&!isValid(b,k,x))

x[k]=x[k]+1;

if(x[k]<=m)

(

if(k==n-l)

break;//successelse

〃為下一個(gè)結(jié)點(diǎn)著色

k=k+1;

)

else

{〃返回至上一層

x[k]=0;

k=k-1;

)

}//print

cout?"Fivevertexes*colorationschemeis:''

?endl;

for(intj=0;j<5;j++)

cout?x[j]?nn;

cout?endl;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

system(nPAUSEn);

returnEXITSUCCESS;

)

0」背包回溯法1：

#include<iostream.h>

usingnamespacestd;

template<classTypew,classTypep>

classKnap

(

friendTypep

Knapsack(Typep*,Typew*,Typew,int);

private:

TypepBound(inti);

voidBacktrack(inti);

Typewc;

intn;

Typew*w;

Typep*p;

Typewcw;

Typepcp;

Typepbestp;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

);

template<classTypew,classTypep>

TypepKnap<Typew,Typep>::Bound(inti)

(

Typewcleft=c-cw;

Typepb=cp;

while(i<=n&&w[i]<=cleft)

(

cleft-=w[i];

b+=p[i]；

i++;

)

if(i<=n)b+=p[i]/w[i]*cleft;

returnb;

)

template<classTypew,classTypep>

voidKnap<Typew,Typep>::Backtrack(inti)

(

if(i>n)

(

bestp=cp;

return;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

)

if(cw+w[i]<=c)

(

cw+=w[i];

cp+=p[i];

Backtrack(i+1);

cw-=w[i];

cp-=p[i];

)

if(Bound(i+l)>bestp)

Backtrack(i+1);

)

classObject

(

friendintKnapsack(int*,mt

public:

intoperator<=(Objecta)const

|

return(d>=a.d);

)

private:

intID;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

floatd;

template<classTypew,classTypep>

(

TypepW=0;

TypepP=0;

Object*Q=newObject[n];

for(inti=l;i<=n;i++)

|

Q[i-l].ID=i;

Q[i-l].d=1.0*p[i]/w[i];

P+=p[i]；

W+=w[i];

)

if(W<=c)returnP;

sort(Q,n);

Knap<Typew,Typep>K;

K.p=newTypep[n+1];

K.w=newTypew[n+1];

for(inti=l;i<=n;i++)

K.p[i]=p[Q[i-l].ID];

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

K.w[i]=w[Q[i-l].ID];

)

K.cp=O;

K.cw=O;

K.c=c;

K.n=n;

K.bestp=O;

K.Backtrack(l);

delete[]Q;

delete[]K.w;

delete[]K.p;

returnK.bestp;

)；

intmainO

(

intp[]={0,4,3,5,6,3);

intw[]={0,3,5,6,2,7);

int*pl=p;

int*wl=w;

intc=10,n=5;

intbestx[6];

intx=Knapsack(p1,wl,c,n);

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cout?nbest=''?c?endl;

for(inti=0;i<6,i++)

(

cout?bestx[i];

)

cout?nResultn;

return0;

)

0-1背包動(dòng)態(tài)規(guī)劃法：

#include<iostream>

#include<fstream>

#include<memory.h>

usingnamespacestd;

intmax(inti,intj)

(

returni>j?i:j;

)

intmin(inti,intj)

(

returni<j?i:j;

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

template<classType>

voidKnapsack(Type*v,int*w,intc,intn,Type

**m)

(

//0-1背包算法

intjMax=min(w[ii]-l,c);

for(intj=O;j<=jMax;j++)

(

m[n][j]=0;

)

for(intt=w[n];t<=c;j++)

(

m[n][t]=v[n];

)

for(inti=n-l;i>l;i-)

(

jMax=min(w[i]-l,c);

for(intj=O;j<=jMax;j++)

for(intk=w[i];j<=c;j++)

m[i][k]=max(m[i+l][k],m[i+l][k-w[i]]+v[i]);

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

)

m[l][c]=m[2][c];

if(c>=w[l])

m[l][c]=max(m[l][c],m[2][c-w[l]]+v[l]);

)

template<classType>

voidTraceBack(Type**m,int*w,intc,intn,int*

x)

{

〃計(jì)算04背包路徑

for(inti=l;i<n;i++)

(

if(m[i][c]==m[i+l][c])

x[i]=0;

else

(

x[i]=l；

c-=w[i];

)

)

x[n]=(m[n][c])?l:0;

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

voidmain()

(

//物品量n,承載重量c,各物體重量：w,各

物體價(jià)值：v〃m用來(lái)存儲(chǔ)動(dòng)態(tài)規(guī)劃的子結(jié)構(gòu)值

intn,c,i；

int*w,*v,*x;

int**m;

ifstreaminput('*Input.txtH,ios::in);

ofstreamoutput(nOutput.txtn,ios::out);

if(!input||!output)

(

cerr?nFi!eopenorcreateerror!n?endl;

exit(O);

)

else

(

input?n?c;

w=newint[n+l];

v=newint[n+l];

x=newint[n+l];

m=newint*[n+l];

for(i=0;i<=n;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

m[i]=newint[c+l];

memset(m[i],0,(c+l)*sizeof(int));

}

for(i=l;i<=n;i++)

input?w[i];

for(i=l;i<=n;i++)

input?v[i];

input.closeQ;

for(i=0;i<n+l;i++)

for(intj=O;j<c+l;j++)

m[i][j]=0;

Knapsack(v,w,c,n,m);

for(i=0;i<=n;i++)

(

for(intk=0;k<=c;k++)

output?m[i][k]?nH;

output?endl;

)

output?endl;

TraceBack(m,w,c,n,x);

for(i=l;i<=n;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

output?x[i]?n

output,close。;〃回收內(nèi)存

for(i=0;i<=n;i++)

delete[]m[i];

delete[]w;

delete[]v;

delete[]x;

delete[]m;

)

)

0」背包回溯法2：

#include<iostream>

usingnamespacestd;

voidinput(int"number,int.weight,int*price)

(

inti,n;

coutvv”包的容量:H;

cin?weight[0];

coutvv”物品數(shù)：H;

cin?*number;

coutvv”各物品的重量：n;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(i=l;i<=*number;i++)

(

cin?weight[i];

)

coutvv”各物品的價(jià)值:n;

for(i=l;i<=*number;i++)

(

cin?price[i];

)

)

voidbacktrack(intt,intn,int.weight,int

*price,int*maxPrice,int*flag,int

*nowWeight,int*nowPrice,int*x)

(

inti;

if(t>n)

(

if(*nowWeight<=weight[0]&&*nowPrice>*m

axPrice)

//cout?nmaxPriceis

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

**?*maxPrice?11nowPriceis

n?*nowPrice?endl?endl;

*maxPrice=*nowPrice;

flag[0]=0;

for(i=l;i<=n;i++)

(

if(x[i])

|

//coutvv”深度是：”Wtvv"i是

n?i?endl?endl;

flag[++flag[O]]=i;

)

)

)

return;

)

else

(

for(i=0;i<=l;i++)

(

x[t]=i;

*nowWeight+=weight[t]*i;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

*nowPrice+=price[t]*i;

//cout?11nowPriceisn?*nowPrice?n

深度是:n?t?nx[n?t?n]是:n?i?endl;

backtrack(t+l,n,weight,price,maxPrice,flag,n

owWeight,nowPrice,x);

*nowWeight-=weight[t]*i;

*nowPrice-=price[t]*i;

)

)

)

voidoutput(int*maxPrice,int*flag)

(

inti;

cout?endl;

cout?''最大價(jià)值:H;

cout?*maxPrice?endl;

cout?”所選物品為:''；

for(i=l;i<=flag[0];i++)

(

cout?flag[i]?nn;

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cout?endl;

)

intmain()

(

inttempl=0,temp2=-l,temp3=0,temp4=0;〃這

一行很重要!!!!!!!！

int*number=&templ,weight[100],price[100];

int

*maxPrice=&temp2,flag[100],*nowWeight=&te

mp3,*nowPrice=&temp4,x[100];

input(number,weight,price);

backtrack(l,*number,weight,price,maxPrice,f

lag,nowWeight,nowPrice,x);

output(maxPrice,flag);

return0;

)

最小生成樹prim法1：

#include<string>

#include<iostream>

usingnamespacestd;

structMGraph

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

voidcreateGraph(intn,intm);

intPrim(intu);

intmat[100][100];//弧的信息

intvexnum;//頂點(diǎn)數(shù)

intMinVertex(intdist[],boolvisited[]);

)；

intMGraph::Prim(intu)

{〃從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)的從頂點(diǎn)最小生成

樹

intadjvex[100];

intdist[100];

boolvisited[100];

inti;//輔助數(shù)組初始化

for(i=0;i<vexnum;i++)

(

adjvex[i]=u;

dist[i]=mat[u][i];

)

fill(visited,visited+vexnum,false);

visited[u]=true;//初始，U={u}初始，=

for(intv=l;v<=vexnum-l;v++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

//選擇vexnum-1個(gè)頂點(diǎn)邊)個(gè)頂點(diǎn)(邊

intk=MinVertex(dist,visited);//加入生成

樹的下一個(gè)頂點(diǎn)(k)

visited[k]=true;〃新節(jié)點(diǎn)加入集合

U

//調(diào)整集合V-U中剩余頂點(diǎn)到集合U的

最短距離

for(i=0;i<vexnum;i++)

(

if(visited[i]==false&&mat[k][i]<dist[i])

(

adjvex[i]=k;

dist[i]=mat[k][i];

)

)

)

intcost=0;

dist[u]=0;

for(i=0;i<vexnum;i++)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cost+=dist[i];

)

returncost;

}//尋找V-U中未被訪問(wèn)，且dist最小的頂點(diǎn)

中未被訪問(wèn)，

intMGraph::MinVertex(intdist[],boolvisited[])

(

intk=-1;

intmin=INTMAX;

for(inti=0;i<vexnum;i++)

(

if(dist[i]<min&&visited[i]==false)

(

min=dist[i];

k=i;

)

)

returnk;

)

voidMGraph::createGraph(intn,intm)

vexnum=n;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

for(intv=0;v<vexnum;v++)

(

for(intw=0;w<vexnum;w++)

(

mat[v][w]=INT_MAX;

)

)

for(inti=0;i<m;i++)

(

inta,b,c;

cin?a?b?c;

mat[a][b]=c;

mat[b][a]=c;

)

)

intmain。//個(gè)頂點(diǎn)(邊〃選擇vexnum」個(gè)頂

點(diǎn)邊)

(

MGraphG;

intn,m;

cin?n?m;

G.createGraph(n,m);

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cout?G.Prim(0)?endl;

return0;

)

最小生成樹kruskal法1：

//#includenstdafx.hn

#include<iostream>

#defineMAX100

typedefintWeiType;

usingnamespacestd;//

structEdge

(

intno;〃邊的序號(hào)

intx;〃端點(diǎn)1序號(hào)

inty;//端點(diǎn)2序號(hào)

WeiTypeweight;〃權(quán)值

boolselected;〃是否被選擇

｝；〃邊集和

Edgeedge[MAX];〃已找到的最小生成樹其中一

部分的秩

intrank[MAX];〃已找到的最小生成樹其中一部

分的頭結(jié)點(diǎn)〃用來(lái)判斷一條邊的2個(gè)端點(diǎn)是否在

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

一個(gè)集合中，即加上這條邊是否會(huì)形成回路

intparent[MAX];〃找出每一集合的頭結(jié)點(diǎn)

intfind_set(intx)

(

if(x!=parent[x])

parent[x]=find_set(parent[x]);

returnparent[x];

}〃合并集合

voidunion_set(intx,inty,WeiTypew,WeiType

&sum)

(

if(x==y)

return;

if(rank[x]>rank[y])

parent[y]=x;

else

(

if(rank[x]==rank[y])

rank[y]++;

parent[x]=y;

)

sum+=w;

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

}〃依據(jù)邊的權(quán)值升序快速排序

voidfast_sort(Edge*edge,intbegin,intend)

(

if(begin<end)

(

inti=begin-lj=begin;

edge[0]=edge[end];

while(j<end)

(

if(edge[j].weight<edge[O].weight)

(

i++；

Edgetempi=edge[i];

edge[i]=edge[j];

edge[j]=tempi;

)

j++；

)

Edgetempi=edge[end];

edge[end]=edge[i+l];

edge[i+l]=temp2;

fast_sort(edge,begin,i)；

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

fast_sort(edge,i+2,end);

)

)

intmain(intargc,char*argv[])

(

intcases;

coutvv”請(qǐng)輸入案例的個(gè)數(shù)：”；

cin?cases;

while(cases—)

(

intn;〃最小生成樹的權(quán)值總和

WeiTypesum=0;

cout?”請(qǐng)輸入邊的個(gè)數(shù)：”；

cin?n;

inti;〃初始化

charchx,chy;

WeiTypeweight;

for(i=l;i<=n;i++)

(

edge[i].no=i;

coutvv”請(qǐng)輸入第”VViVV”條邊的二個(gè)端

點(diǎn)的名稱(小寫字符)：”；

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

cin?chx?chy;

edge[i].x=chx-'a，+l;

edge[i].y=chy-'a'+l;

coutvv”這條邊的權(quán)值為：”;

cin?weight;

edge[i].weight=weight;

edge[i].selected=false;

parent[edge[i].x]=edge[i].x;

parent[edge[i].y]=edge[i].y;

rank[edge[i].x]=0;

rank[edge[i].y]=0;

)〃快排

fast_sort(edge,l?n);

for(i=l;i<=n;i++)

(

intx,y;

x=find_set(edge[i].x);

y=find_set(edge[i].y);〃判斷即加上

這條邊是否會(huì)形成回路

if(x!=y)

〃選擇這條邊

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

edge[i].selected=true;

〃合并不會(huì)形成回路的二個(gè)集合

union_set(x,y9edge[i].weight,sum);

)

)

coutvv”最小生成樹的邊集為："vvendl;

for(i=l;i<=n;i++)

(

if(edge[i].selected)

(

coutvv”序號(hào)：n?edge[i].no?n''

vv"端點(diǎn)1："vv(char)(edge[i].x+'aLl)vv”,端點(diǎn)

2：n?(char)(edge[i].y+*a,-l)?endl;

)

)

cout?n最小生成樹的權(quán)值為：

H?sum?endl;

)

system(npausen);

return0;

)

文檔僅供參考，不當(dāng)之處，請(qǐng)聯(lián)系改正。

最小生成樹prim法2：

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#defineMAX_N