游乐场实习报告

时间:2022-10-14 01:26:04 作者:网友上传 字数:1507字

无忧范文网小编为你整理了多篇《游乐场实习报告》范文,希望对您的工作学习有帮助,你还可以在无忧范文网网可以找到更多《游乐场实习报告》。

数据结构实习报告

班级:13软件二班

姓名:殷健 学号:1345536225

子集和数问题

1:问题描述

子集和数问题1:子集和问题的为〈W,c〉。其中,W={w1,w2,...,wn}是一个正整数的集合,子集和数问题判定是否存在W的一个子集W1,使得∑W1=c∑W(0

2:问题分析

程序中设计了函数void computeSumofSub(int s,int k,int r),其意义是从第k项开始,如果s(已经决策的和数)和w[k](当前元素)之和为和数,就把结果输出来,否则如果s与,w[k],w[k+1]之和小于和数,则调用computeSumofsub(s+w[k],k+1,r-w[k]),意为选择此结点的左分支,再判断s和后面所有元素之和是否不小于M(所有的加起来都小,必定无解),并且s+w[k+1]M,也是无解),若条件符合即调用computeSumofSub(s,k+1,r-w[k]),即选择当前结点的右分支。

算法展示:

#include using namespace std;#include #include #define M 50 cla SumOfSub{ private: int w[M];

int m;int x[M];public: SumOfSub(int a[], int b, int n){

for(int i=0;i=m&&s+w[k+1]

};void main(){ int sum=0;int w[M];srand((unsigned)time(NULL));

for(int i=0;i

} cout

cout

} cout>m;sum=m*sum;cout

复杂性分析: 对于不同的输入结果,算法的执行次数有所不同,最好情况是n,最坏情况是n*2^n。尽管差异很大,但当n很大时,对某些输入而言,回溯法仍可在短时间内求解。其它说明: 按书中所讲的约束条件,程序中所有变量都是整型,输入的各元素要从小到大输入,而且不能有重复的元素。若是想要无序输入,可以程序中加入程序1.c的归并排序算法,对输入的数组排序即可。

拓展一

问题描述: 子集和数问题拓展一:子集和问题的为〈W,c,p〉。其中,W={w1,w2,...,wn}是一个正整数的集合,子集和数问题判定是否存在W的一个子集W1,使得∑W1=c∑W(0

问题分析:

增加一个数组p,使得p的每个元素与w对应元素关系为pi=Wi+10;最后结果W子集中元素个数越多,则p和最大,但也可以将每个符合条件子集对应P集合的元素和计算出做个比较,然后输出最大的再对应原W子集。

算法演示

#include using namespace std;#include #include #define M 50 cla SumOfSub{ private: int w[M];int p[M];int m;int x[M];

int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){

max=0;j=0;

for(int i=0;i

w[i]=a[i];

p[i]=a[i]+10;

}

m = b;

x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout

} else if(s+w[k]+w[k+1] =m&&s+w[k+1]

int S=0;int i;

cout

for(i=0;i

S=S+p[i];

cout

}

cout

cout

if(S>max){

max=S;

int J=0;

for(i=0;i

if(x[i]==1){

N[J]=w[i];

J++;

}

}

j=J;

} } void special(){

cout

for(int i=0;i

cout

}

cout

for(int i=0;i

w[i]=rand();

if(w[i]==0){

w[i]=rand();

}

sum=sum+w[i];} cout

cout>m;sum=m*sum;cout

r += w[i];} sumOfSub.computeSumOfSub(0, 0, r);

sumOfSub.special();} 运行结果

复杂性分析

对于不同的输入结果,算法的执行次数有所不同,最好情况是n,最坏情况是n*2^n。尽管差异很大,但当n很大时,对某些输入而言,回溯法仍可在短时间内求解。

拓展二

问题描述

子集和数问题拓展一:子集和问题的为〈W,c,P〉。其中,W={w1,w2,...,wn}是一个正整数的集合,子集和数问题判定是否存在W的一个子集W1,使得∑W1=c∑W(0

问题分析

增加一个数组随机数组P,每个符合条件子集对应P集合的元素和计算出做个比较,然后输出最大的再对应原W子集。

算法演示

#include using namespace std;#include #include #define M 50 cla SumOfSub{ private: int w[M];int p[M];int m;

int x[M];int N[M];int max;int j;public: SumOfSub(int a[], int b, int n){

max=0;

j=0;

cout

for(int i=0;i

w[i]=a[i];

p[i]=rand();

cout

}

cout

m = b;

x[0]=n;} void computeSumOfSub(int s, int k, int r){ x[k] = 1;if(s+w[k] == m){ printResult(k);cout

} else if(s+w[k]+w[k+1] =m&&s+w[k+1]

int S=0;int i;

cout

for(i=0;i

S=S+p[i];

cout

}

cout

cout

if(S>max){

max=S;

int J=0;

for(i=0;i

if(x[i]==1){

N[J]=w[i];

J++;

}

}

j=J;

} } void special(){

cout

for(int i=0;i

cout

}

cout

for(int i=0;i

w[i]=rand();

if(w[i]==0){

w[i]=rand();

}

sum=sum+w[i];} cout

cout>m;sum=m*sum;cout

r += w[i];} sumOfSub.computeSumOfSub(0, 0, r);

sumOfSub.special();}

运行结果

复杂性分析

对于不同的输入结果,算法的执行次数有所不同,最好情况是n,最坏情况是n*2^n。尽管差异很大,但当n很大时,对某些输入而言,回溯法仍可在短时间内求解。

《游乐场实习报告.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档