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

算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告教師：學(xué)號(hào)：姓名：實(shí)驗(yàn)一：串匹配問(wèn)題實(shí)驗(yàn)?zāi)康模?1)深刻理解并掌握蠻力法的設(shè)計(jì)思想;(2)提高應(yīng)用蠻力法設(shè)計(jì)算法的技能;(3)理解這樣一個(gè)觀點(diǎn):用蠻力法設(shè)計(jì)的算法,一般來(lái)說(shuō),經(jīng)過(guò)適度的努力后,都可以對(duì)算法的第一個(gè)版本進(jìn)行一定程度的改良,改進(jìn)其時(shí)間性能。實(shí)驗(yàn)要求：(1)實(shí)現(xiàn)BF算法;(2)實(shí)現(xiàn)BF算法的改進(jìn)算法:KMP算法和BM算法; (3)對(duì)上述3個(gè)算法進(jìn)行時(shí)間復(fù)雜性分析,并設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)果。#include"stdio.h"#include"conio.h"#include<iostream>//BF算法intBF(chars[],chart[]){inti;inta;intb;intm,n;m=strlen(s);//主串長(zhǎng)度n=strlen(t);//子串長(zhǎng)度printf("\n*****BF*****算法\n");for(i=0;i<m;i++){b=0;a=i;while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!\n\n");return0;}}printf("找不到%s\n\n",t);return0;}//前綴函數(shù)值,用于KMP算法intGETNEXT(chart[],intb){intNEXT[10];NEXT[0]=-1;intj,k;j=0;k=-1;while(j<strlen(t)){if((k==-1)||(t[j]==t[k])){j++;k++;NEXT[j]=k;}elsek=NEXT[k];}b=NEXT[b];returnb;}//KMP算法intKMP(chars[],chart[]){inta=0;intb=0;intm,n;m=strlen(s);//主串長(zhǎng)度n=strlen(t);//子串長(zhǎng)度printf("\n*****KMP算法*****\n");while(a<=m-n){while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!\n\n");return0;}b=GETNEXT(t,b);a=a-b;if(b==-1)b++;}printf("找不到%s\n\n",t);return0;}//滑動(dòng)距離函數(shù),用于BM算法intDIST(chart[],charc){inti=0,x=1;intn;n=strlen(t);while(x&&i!=n-1){if(t[i]==c)x=0;elsei++;}if(i!=n-1)n=n-1-i;returnn;}//BM算法結(jié)果分析與體會(huì)：

glibc里的strstr函數(shù)用的是brute-force(naive)算法，它與其它算法的區(qū)別是strstr不對(duì)pattern(needle)進(jìn)行預(yù)處理，所以用起來(lái)很方便。理論復(fù)雜度O(mn),

實(shí)際上，平均復(fù)雜度為O(n),

大部分情況下高度優(yōu)化的算法性能要優(yōu)于基于自動(dòng)機(jī)的匹配算法，BF有一個(gè)重要性質(zhì)是事先不用知道串的長(zhǎng)度，而基于跳躍的算法是需要用字符串長(zhǎng)度來(lái)判斷結(jié)束位置的。實(shí)驗(yàn)二：最近對(duì)問(wèn)題實(shí)驗(yàn)?zāi)康模?1)進(jìn)一步掌握遞歸算法的設(shè)計(jì)思想以及遞歸程序的調(diào)試技術(shù);(2)理解這樣一個(gè)觀點(diǎn):分治與遞歸經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中。實(shí)驗(yàn)要求：(1)分別用蠻力法和分治法求解最近對(duì)問(wèn)題; (2)分析算法的時(shí)間性能,設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)論。ClosestPair1.java

//蠻力算法

import

java.util.*;

public

class

ClosestPair1

{

public

static

void

main(String[]

args)

{

/**

*輸入需要比較的點(diǎn)的對(duì)數(shù)存在變量n中

*/

Scanner

in=new

Scanner(System.in);

System.out.println("How

many

pairs

of

points

to

compare?(有多少對(duì)點(diǎn)需要比較?)");

int

n=in.nextInt();

int[]

x=new

int[n];

int[]

y=new

int[n];

/**

*輸入這些點(diǎn)的橫坐標(biāo)和縱坐標(biāo)分別存儲(chǔ)在x[n]和y[n]

*/

System.out.println("Please

enter

these

points,X-coordinate(請(qǐng)輸入這些點(diǎn),橫坐標(biāo)):");

for(int

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

{

x[i]=in.nextInt();

}

System.out.println("Please

enter

these

points,Y-coordinate(請(qǐng)輸入這些點(diǎn),縱坐標(biāo)):");

for(int

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

{

y[i]=in.nextInt();

}

double

minDist=Double.POSITIVE_INFINITY;

double

d;

int

indexI=0;

int

indexJ=0;

/**

*求解最近對(duì)距離存在minDist中

*/

double

startTime=System.currentTimeMillis();//startTime

for(int

i=0;i<n-1;i++)

{

for(int

j=i+1;j<n;j++)

{

d=Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

if(d<minDist)

{

minDist=d;

indexI=i;

indexJ=j;

}

}

}

double

endTime=System.currentTimeMillis();//endTime

/**

*打印輸出最后求出的結(jié)果，最近的是哪兩個(gè)點(diǎn)，以及最近距離和程序用的時(shí)間

*/

System.out.println("The

closest

pair

is:("+x[indexI]+","+y[indexI]+")

and

("+x[indexJ]+","+y[indexJ]+")");

System.out.println("The

closest

distance

is

"+minDist);

System.out.println("Basic

Statements

take(基本語(yǔ)句用時(shí))

"+(endTime-startTime)+"

milliseconds!");

}

}

ClosestPair2.java

//分治算法

import

java.util.*;

public

class

ClosestPair2

{

public

static

void

main(String[]

args)

{

/**

*輸入需要比較的點(diǎn)的對(duì)數(shù)存在變量n中

*/

Scanner

in=new

Scanner(System.in);

System.out.println("How

many

pairs

of

points

to

compare?(有多少對(duì)點(diǎn)需要比較?)");

int

n=in.nextInt();

/**

*輸入這些點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，存儲(chǔ)在點(diǎn)數(shù)組S[n]中

*/

System.out.println("Please

enter

these

points,X-coordinate

and

Y-coordinate.(請(qǐng)輸入這些點(diǎn)，x坐標(biāo)和y坐標(biāo))：");

Point[]

S=new

Point[n];

double

startTime=System.currentTimeMillis();//starttime

for(int

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

{

int

x=in.nextInt();

int

y=in.nextInt();

S[i]=new

Point(x,y);

System.out.println("("+S[i].getX()+","+S[i].getY()+")");

}

/**

*求出這點(diǎn)的x坐標(biāo)的中位數(shù)mid

*/

int

minX=(int)Double.POSITIVE_INFINITY;

int

maxX=(int)Double.NEGATIVE_INFINITY;

for(int

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

{

if(S[i].getX()<minX)

minX=S[i].getX();

if(S[i].getX()>maxX)

maxX=S[i].getX();

}

int

mid=(minX+maxX)/2;

/**

*以mid為界把S中的點(diǎn)分為兩組分別存放在范型數(shù)組列表point1和point2中

*/

ArrayList<Point>

point1=new

ArrayList<Point>();

ArrayList<Point>

point2=new

ArrayList<Point>();

for(int

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

{

if(S[i].getX()<=mid)

point1.add(S[i]);

else

point2.add(S[i]);

}

/**

*將范型數(shù)組列表轉(zhuǎn)換為數(shù)組類(lèi)型S1和S2

*/

Point[]

S1=new

Point[point1.size()];

Point[]

S2=new

Point[point2.size()];

point1.toArray(S1);

point2.toArray(S2);

/**

*將S1和S2中的點(diǎn)按x

坐標(biāo)升序排列

*/

sortX(S1);

sortX(S2);

/**

*打印輸出排序后S1和S2的點(diǎn)

*/

System.out.print("The

points

in

S1

are:");

for(int

i=0;i<S1.length;i++)

System.out.print("("+S1[i].getX()+","+S1[i].getY()+")

");

System.out.println();

System.out.print("The

points

in

S2

are:");

for(int

i=0;i<S2.length;i++)

System.out.print("("+S2[i].getX()+","+S2[i].getY()+")

");

System.out.println();

/**

*求S1中點(diǎn)的最近對(duì)及其距離并打印輸出結(jié)果

*/

double

minDist1=Double.POSITIVE_INFINITY;

int

indexI1=0;

int

indexJ1=0;

for(int

i=0;i<S1.length-1;i++)

{

for(int

j=i+1;j<S1.length;j++)

{

double

d=Math.sqrt(Math.pow((S1[i].getX()-S1[j].getX()),2)+Math.pow((S1[i].getY()-S1[j].getY()),2));

if(d<minDist1)

{

minDist1=d;

indexI1=i;

indexJ1=j;

}

}

}

System.out.println("The

closest

pair

in

S1

is:

"+"("+S1[indexI1].getX()+","+S1[indexI1].getY()+")"+

"and("+S1[indexJ1].getX()+","+S1[indexJ1].getY()+")"+",and

the

distance

is

"+minDist1);

/**

*求S2中點(diǎn)的最近對(duì)及其距離并打印輸出結(jié)果

*/

double

minDist2=Double.POSITIVE_INFINITY;

int

indexI2=0;

int

indexJ2=0;

for(int

i=0;i<S2.length-1;i++)

{

for(int

j=i+1;j<S2.length;j++)

{

double

d=Math.sqrt(Math.pow((S2[i].getX()-S2[j].getX()),2)+Math.pow((S2[i].getY()-S2[j].getY()),2));

if(d<minDist2)

{

minDist2=d;

indexI2=i;

indexJ2=j;

}

}

}

System.out.println("The

closest

pair

in

S2

is:

"+"("+S2[indexI2].getX()+","+S2[indexI2].getY()+")"+

"and("+S2[indexJ2].getX()+","+S2[indexJ2].getY()+")"+",and

the

distance

is

"+minDist2);

double

d1=Math.min(minDist1,minDist2);

/**

*求出S1和S2中點(diǎn)的橫坐標(biāo)離小于d1的所有點(diǎn)分別存在P1[]和P2[]中

*/

ArrayList<Point>

pp1=new

ArrayList<Point>();

ArrayList<Point>

pp2=new

ArrayList<Point>();

for(int

i=0;i<S1.length;i++)

{

if((mid-S1[i].getX())<d1)

pp1.add(S1[i]);

}

for(int

i=0;i<S2.length;i++)

{

if((S2[i].getX()-mid)<d1)

pp2.add(S2[i]);

}

Point[]

P1=new

Point[pp1.size()];

Point[]

P2=new

Point[pp2.size()];

pp1.toArray(P1);

pp2.toArray(P2);

/**將P1和P2中的點(diǎn)按Y坐標(biāo)升序排列

*/

sortY(P1);

sortY(P2);

/

*求解P1和P2兩者之間可能的最近對(duì)距離

*/

double

d2=Double.POSITIVE_INFINITY;

for(int

i=0;i<P1.length;i++)

{

for(int

j=0;j<P2.length;j++)

{

if(Math.abs(P1[i].getY()-P2[j].getY())<d1)

{

double

temp=Math.sqrt(Math.pow((P1[i].getX()-P2[j].getX()),2)+Math.pow((P1[i].getX()-P2[j].getX()),2));

if(temp<d2)

d2=temp;

}

}

}

double

endTime=System.currentTimeMillis();//endtime

/**

*打印輸出最后求出的結(jié)果，最近的是哪兩個(gè)點(diǎn)，以及最近距離和程序用的時(shí)間

*/

System.out.print("The

points

in

P1

are:");

for(int

i=0;i<P1.length;i++)

System.out.print("("+P1[i].getX()+","+P1[i].getY()+")

");

System.out.println();

System.out.print("The

points

in

P2

are:");

for(int

i=0;i<P2.length;i++)

System.out.print("("+P2[i].getX()+","+P2[i].getY()+")

");

System.out.println();

System.out.println("d2="+d2);

double

minDist=Math.min(d1,d2);

System.out.println("The

closest

distance

is

"+minDist);

System.out.println("Basic

Statements

take(基本語(yǔ)句用時(shí))

"+(endTime-startTime)+"

milliseconds!");

}

/**

*設(shè)計(jì)按點(diǎn)Point的x坐標(biāo)升序排列的函數(shù)sortX

*/

public

static

void

sortX(Point[]

p)

{

for(int

i=0;i<p.length-1;i++)

{

for(int

j=0;j<p.length-1-i;j++)

{

if(p[j].getX()>p[j+1].getX())

{

int

t=p[j].getX();

p[j].setX(p[j+1].getX());

p[j+1].setX(t);

int

n=p[j].getY();

p[j].setY(p[j+1].getY());

p[j+1].setY(n);

}

}

}

}

/**

*設(shè)計(jì)按點(diǎn)Point的y坐標(biāo)升序排列的函數(shù)sortY

*/

public

static

void

sortY(Point[]

p)

{

for(int

i=0;i<p.length-1;i++)

{

for(int

j=0;j<p.length-1-i;j++)

{

if(p[j].getY()>p[j+1].getY())

{

int

t=p[j].getY();

p[j].setY(p[j+1].getY());

p[j+1].setY(t);

int

n=p[j].getX();

p[j].setX(p[j+1].getX());

p[j+1].setX(n);

}

}

}

}

}

/**

*建立自己的類(lèi)Point

*/

class

Point

implements

Cloneable

{

public

Point()

{

x=0;

y=0;

}

public

Point(int

x,int

y)

{

this.x=x;

this.y=y;

}

public

void

setX(int

x)

{

this.x=x;

}

public

void

setY(int

y)

{

this.y=y;

}

public

int

getX()

{

return

x;

}

public

int

getY()

{

return

y;

}

private

int

x;

private

int

y;

}實(shí)驗(yàn)結(jié)果與結(jié)論：算法復(fù)雜度分析：為提高算法效率，在算法中采用預(yù)排序技術(shù)，即在使用分治法之前，預(yù)先將S中的n個(gè)點(diǎn)依其y坐標(biāo)排序好。經(jīng)過(guò)預(yù)排序處理后的算法所需的計(jì)算時(shí)間T(n)滿足遞歸方程：當(dāng)n小于4時(shí)，T(n)=O(1)；當(dāng)n大于等于4時(shí)，T(n)=2T(n/2)+O(n)。由此易知，T(n)=O(nlogn)。預(yù)排序所需的計(jì)算時(shí)間顯然為O(nlogn)。因此，整個(gè)算法所需的計(jì)算時(shí)間為O(nlogn)。在漸近的意義下，此算法已是最優(yōu)算法。實(shí)驗(yàn)三：8枚硬幣問(wèn)題實(shí)驗(yàn)?zāi)康模海?）深刻理解并掌握減治法的設(shè)計(jì)思想并能熟練運(yùn)用； （2）提高應(yīng)用減治法設(shè)計(jì)算法的技能；理解這樣一個(gè)觀點(diǎn)：建立正確的模型對(duì)于問(wèn)題的求解是非常重要的。實(shí)驗(yàn)要求：（1）、設(shè)計(jì)減治算法實(shí)現(xiàn)8枚硬幣問(wèn)題； （2）、設(shè)計(jì)實(shí)驗(yàn)程序，考察用減治技術(shù)設(shè)計(jì)的算法是否高效；（3）、擴(kuò)展算法，使之能處理n枚硬幣中有1枚假幣的問(wèn)題。#include<stdio.h>#include<stdlib.h>intFindmax(floata[],intn,intm)//用天平比較1~3次即可{floattemp=a[n];intadr=n;for(inti=n;i<m;i++){if(temp<a[i]）{temp=a[i];adr=i;break;}}returnadr;}intFindmin(floata[],intn,intm)//用天平比較1~3次即可{floattemp=a[n];intadr=n;for(inti=n;i<m;i++){if(temp>a[i]){temp=a[i];break;}}returnadr;}intDevide(floata[]){floatleft0=0.0;floatright0=0.0;floatleft1=0.0;floatright1=0.0;intadr=0;inti,j;//先比較前四個(gè)和后四個(gè)硬幣for(i=0;i<8;i++){if(i<4)left0+=a[i];elseright0+=a[i];}//此處用天枰比較一次即可if(left0<right0)//若Weight（1234）<Weight（5678）{for(i=0;i<4;i++){if(i<2)left1+=a[i];elseright1+=a[i];}if(left1!=right1)//若Weight（12）！=Weight（34）,則說(shuō)明假幣在前四個(gè)當(dāng)中，而且假幣Weight(假)<Weight(真){adr=Findmin(a,0,4);//找到其中最輕的便是假的}else//若Weight（12）==Weight（34）,則說(shuō)明假幣在后四個(gè)當(dāng)中，而且假幣Weight(假)>Weight(真){adr=Findmax(a,4,8);//找到其中最重的便是假的}}else//若Weight（1234）>Weight（5678）{for(i=0;i<4;i++){if(i<2)left1+=a[i];elseright1+=a[i];}if(left1!=right1)//若Weight（12）！=Weight（34）,則說(shuō)明假幣在前四個(gè)當(dāng)中，而且假幣Weight(假)>Weight(真){adr=Findmax(a,0,4);//找到其中最重的便是假的}else//若Weight（12）==Weight（34）,則說(shuō)明假幣在后四個(gè)當(dāng)中，而且假幣Weight(假)<Weight(真){adr=Findmin(a,4,8);//找到其中最輕的便是假的}}returnadr;}intmain(){inti=1;floata[8]={0};printf("請(qǐng)輸入8枚硬幣的重量：");for(i=0;i<8;i++){scanf("%f",&a[i])}printf("假幣的位置為：%d\n",Devide(a)+1);system("pause");return0;}結(jié)果分析與體會(huì)：通過(guò)硬幣問(wèn)題，讓我更加理解了減治法的使用，讓我對(duì)減治法有了更深的理解，對(duì)于以后的編程思想有了更深的研究。

論大學(xué)生寫(xiě)作能力寫(xiě)作能力是對(duì)自己所積累的信息進(jìn)行選擇、提取、加工、改造并將之形成為書(shū)面文字的能力。積累是寫(xiě)作的基礎(chǔ)，積累越厚實(shí)，寫(xiě)作就越有基礎(chǔ)，文章就能根深葉茂開(kāi)奇葩。沒(méi)有積累，胸?zé)o點(diǎn)墨，怎么也不會(huì)寫(xiě)出作文來(lái)的。寫(xiě)作能力是每個(gè)大學(xué)生必須具備的能力。從目前高校整體情況上看，大學(xué)生的寫(xiě)作能力較為欠缺。一、大學(xué)生應(yīng)用文寫(xiě)作能力的定義那么，大學(xué)生的寫(xiě)作能力究竟是指什么呢？葉圣陶先生曾經(jīng)說(shuō)過(guò)，“大學(xué)畢業(yè)生不一定能寫(xiě)小說(shuō)詩(shī)歌，但是一定要寫(xiě)工作和生活中實(shí)用的文章，而且非寫(xiě)得既通順又扎實(shí)不可?！睂?duì)于大學(xué)生的寫(xiě)作能力應(yīng)包含什么，可能有多種理解，但從葉圣陶先生的談話中，我認(rèn)為：大學(xué)生寫(xiě)作能力應(yīng)包括應(yīng)用寫(xiě)作能力和文學(xué)寫(xiě)作能力，而前者是必須的，后者是“不一定”要具備，能具備則更好。眾所周知，對(duì)于大學(xué)生來(lái)說(shuō)，是要寫(xiě)畢業(yè)論文的，我認(rèn)為寫(xiě)作論文的能力可以包含在應(yīng)用寫(xiě)作能力之中。大學(xué)生寫(xiě)作能力的體現(xiàn)，也往往是在撰寫(xiě)畢業(yè)論文中集中體現(xiàn)出來(lái)的。本科畢業(yè)論文無(wú)論是對(duì)于學(xué)生個(gè)人還是對(duì)于院系和學(xué)校來(lái)說(shuō)，都是十分重要的。如何提高本科畢業(yè)論文的質(zhì)量和水平，就成為教育行政部門(mén)和高校都很重視的一個(gè)重要課題。如何提高大學(xué)生的寫(xiě)作能力的問(wèn)題必須得到社會(huì)的廣泛關(guān)注，并且提出對(duì)策去實(shí)施解決。二、造成大學(xué)生應(yīng)用文寫(xiě)作困境的原因：（一）大學(xué)寫(xiě)作課開(kāi)設(shè)結(jié)構(gòu)不合理。就目前中國(guó)多數(shù)高校的學(xué)科設(shè)置來(lái)看，除了中文專(zhuān)業(yè)會(huì)系統(tǒng)開(kāi)設(shè)寫(xiě)作的系列課程外，其他專(zhuān)業(yè)的學(xué)生都只開(kāi)設(shè)了普及性的《大學(xué)語(yǔ)文》課。學(xué)生寫(xiě)作能力的提高是一項(xiàng)艱巨復(fù)雜的任務(wù)，而我們的課程設(shè)置僅把這一任務(wù)交給了大學(xué)語(yǔ)文教師，可大學(xué)語(yǔ)文教師既要在有限課時(shí)時(shí)間內(nèi)普及相關(guān)經(jīng)典名著知識(shí)，又要適度提高學(xué)生的鑒賞能力，且要教會(huì)學(xué)生寫(xiě)作規(guī)律并提高寫(xiě)作能力，任務(wù)之重實(shí)難完成。（二）對(duì)實(shí)用寫(xiě)作的普遍性不重視?！按髮W(xué)語(yǔ)文”教育已經(jīng)被嚴(yán)重地“邊緣化”。目前對(duì)中國(guó)語(yǔ)文的態(tài)度淡漠，而是呈現(xiàn)出全民學(xué)英語(yǔ)的大好勢(shì)頭。中小學(xué)如此，大學(xué)更是如此。對(duì)我們的母語(yǔ)中國(guó)語(yǔ)文，在大學(xué)反而被漠視，沒(méi)有相關(guān)的課程的設(shè)置，沒(méi)有系統(tǒng)的學(xué)習(xí)實(shí)踐訓(xùn)練。這其實(shí)是國(guó)人的一種偏見(jiàn)。應(yīng)用寫(xiě)作有它自身的規(guī)律和方法。一個(gè)人學(xué)問(wèn)很大，會(huì)寫(xiě)小說(shuō)、詩(shī)歌、戲劇等，但如果不曉得應(yīng)用文寫(xiě)作的特點(diǎn)和方法，他就寫(xiě)不好應(yīng)用文。（三）部分大學(xué)生學(xué)習(xí)態(tài)度不端正。很多非中文專(zhuān)業(yè)的大學(xué)生對(duì)寫(xiě)作的學(xué)習(xí)和訓(xùn)練都只是集中在《大學(xué)語(yǔ)文》這一門(mén)課上，大部分學(xué)生只愿意被動(dòng)地接受大學(xué)語(yǔ)文老師所講授的文學(xué)經(jīng)典故事，而對(duì)于需要學(xué)生動(dòng)手動(dòng)腦去寫(xiě)的作文，卻是盡可能應(yīng)付差事，這樣勢(shì)必不能