算法课程设计.docx

算法课程设计.docx

《算法课程设计.docx》由会员分享，可在线阅读，更多相关《算法课程设计.docx（15页珍藏版）》请在冰点文库上搜索。

算法课程设计

题目一数塔问题

问题描述：

有如右图所示的数塔，从顶部动身，在每一结点能够选择向左走或是向右走，一路走到底层，要求找出一条途径，使途径上的值最大

解决问题所用的方式：

动态计划

为了求得数塔1的解。

咱们将数塔1分解为如下的数塔1极点、数塔2和数塔3

数塔1的解=数塔1的极点+数塔2解与数塔3解的最大值，同理，咱们也将数塔2和数塔3分解为更小的数塔4、数塔5、数塔6和数塔7

……………

当数塔不可再分（仅有一层）时，确实是分治的最小单元。

现运用动态计划的思想，自底向上求解，并将中间果存储想来以便以后再用。

A（1……n,1……n）表示数塔各层数的数字

B（1……n,1,……n）用来存储中间结果

基于分治的方式，取得递推公式如下：

注：

i=1……n,j=1……i

自底向上求解该问题.

算法描述：

算法名称：

MAXVALUE

输入：

树塔的层数n和各层的数字A[n][n]

输出：

最大值和途径C[n]

算法实现细节（能够用流程图，伪代码）:

1.fori←1ton

2.B[n,i]←A[n,i]comment:

最下面一层为A[n,j]

3.endfor

4.fori←n-1to1

5.forj←1toi+1

6.B[i,j]←max{B[i+1,j],B[i+1,j+1]}+A[i,j]

7.comment:

B[i,j]等于下面它下面两个数的最大值加上A[i,j]

8.endfor

9.endfor

10.k←1

11.C[1]←1

12.fori←2ton

13.ifB[i,k+1]>B[i,k]thenk←k+1

14.comment:

寻觅途径，找它下面两个数中最大一个的下标并记录

15.endif

16.C[i]←k

17.endfor

18.returnB[1,1]comment：

返回最大途径的值

算法的时刻复杂度

算法实例：

数据的输入（能够有屏幕截图）

数据的输出（能够有屏幕截图）

题目二校园导航问题

问题描述：

设计你所在学校的平面图，至少包括10个以上的场所，每两个场所间能够有不同的路，且路长也可能不同，找出从任意场所抵达另一场所的最正确途径（最短途径）。

解决问题所用的方式：

贪婪算法

校园导航问题为最短途径问题。

设G=（V,E）是一个每条边有非负长度的无向图，有一点s称为源点，校园导航问题确实是要确信从s到V中的一个极点x的的最短距离。

初始时，将极点集合分为两个集合B={s},C={1……s-1,s+1……n}，每一步中，咱们选定源点到它的距离已经取得的一个极点c

C,并将它移入B中。

与C中的每一个极点c联系的是标记D[c]，它是只通过B中极点的最短途径，一旦极点c

C移到B中，与c相邻的每一个极点

C的标记就会被更新。

这表示找到了通过c到

的更短途径。

当x

C被移入B中时，x的标记确实是从源s到极点x的最短途径。

为了方便找出具体的的最短图径，咱们将标记矩阵概念为

二维矩阵D，第x列的最小值确实是源s到极点x的最小途径。

A（1……n,1……n）为无向图的邻接矩阵，咱们寻觅极点s到s的最短途径无心义，咱们将它到本身的距离概念为无穷大（只是为了方便）如以下图：

寻觅最短途径时，咱们选找极点x列的最小值的行标i，假设i不等于s，那么再找第i列的最小值所在的行标j，依次下去，直到行标为s时，这条途径确实是最短途径。

算法描述：

算法名称：

FINDMIN

输入：

地址的个数n之间的距离A[i,j]，和起始点a和终点b

输出：

最短途径值和其途径

算法实现细节（能够用流程图，伪代码）:

1.fori←1ton

2.C[i]←0comment:

初始化途径

3.endfor

4.fori←1ton

5.B[i]←1comment:

B[i]记录地址i是不是可用

6.endfor

7.forj←1ton

8.D[i,j]←

9.endfor

10.k←a

11.min←0

12.whilek≠b

13.fori←1ton

14.ifA[k,i]≠

15.thenD[k,j]←A[k,j]+min

16.comment:

若是A[k,j]不为无穷，那么D[k,j]等于A[k,j]加上最小值

17.endif

18.min←

19.forj←1ton

20.ifB[j]=0thencontinue

21.endif

22.fori←1ton

23.ifD[i,j]

寻觅a点到可用地址的最小值

24.thenmin←D[i,j]

25.l←j

26.endif

27.endfor

28.endfor

29.k←l

30.endwhile

31.min←

32.forj←0toncomment：

寻觅最小途径的值

33.min←min{min,D[j,b]}

34.endfor

35.k<-b

36.i<-1

37.whilek≠a

38.l←

39.C[i]←k

40.i←i+1

41.forj←0ton

42.ifl>D[j,k]

43.thend←j

44.l←D[j,k]comment：

寻觅最短的途径

45.endif

46.endfor

47.k←d

48.endwhile

49.C[i]←k

50.ifa=bthenreturn0

51.elsereturnmin

52.endif

算法的时刻复杂度:

算法实例：

数据的输入（能够有屏幕截图）

数据的输出（能够有屏幕截图）

题目三货物装车问题

问题描述：

在杂货店中有n种不同的货物。

现将货物装车，规定从每种货物中最多只能拿一件，车子的容量为c，物品i需占用wi的空间，价值为pi。

现要求设计算法和程序使车中装载的物品价值最大。

固然，所装货物不能超过车的容量，且同一种物品不得拿走多件

解决问题所用的方式：

动态计划

W（1……n）表示物品所占用的空间

P（（1……n）表示物品的价值

V[i,j]表示之前i个物品掏出来放入容积为j的货车上的最大价值。

i=0……n,j=0……c

当i或j等于0时，V[0,0]等于0

若是第i个物体的体积大于车的容积，那么V[i,j]=V[i-1,j]

若是第i个物体的体积不大于车的容积，那么V[i,j]=V[i-1,j]与V[i-1,j-W[i]]+P[i]的最大值

咱们取得公式：

运用动态动态计划的方式求解

算法描述：

算法名称：

BAGMAX

输入：

物品的个数，货车的最大容量，每件货物应的体积和价值

输出：

可拿的最大价值和该拿的货物

算法实现细节（能够用流程图，伪代码）:

1.fori←0ton

2.V[i,1]←0

3.endfor

4.fori←0toc

5.V[1,i]←0

6.endfor

7.fori←1ton

8.forj←1toc

9.ifw[i]>jthenV[i][j]←V[i-1][j]

10.elseV[i][j]←max{V[i-1][j],V[i-1,j-W[i-1]]+P[i-1]}

11.comment：

计算相应的值

12.endif

13.endfor

14.endfor

15.j←c

16.k←1

17.fori←nto0

18.ifV[i][j]=V[i-1]thenL[k]←i

19.k←k+1

20.j←j-W[i]comment：

找出应该拿的物品

21.endif

22.endfor

23.returnV[n,c]

算法的时刻复杂度

算法实例：

数据的输入（能够有屏幕截图）

数据的输出（能够有屏幕截图）

题目四party幸运人士

问题描述:

一次大型的party最后节目是选取一名幸运人士，该人将取得组织者预备的一个钻石戒指。

选择方法是让所有人一字排列，然后从左至右点数，凡是奇数号的全数删除。

对剩下的人，一样从左至右点数，逢奇数号就删除。

如此不断循环，直到只剩1人为止。

此即为幸运之

解决问题所用的方式：

归纳法

算法描述：

算法名称：

LUCKY

输入：

参加Party的人数

输出：

幸运号码

算法实现细节（能够用流程图，伪代码）:

1.fori←1ton

2.PM[i]←i

3.endfor

4.whilen>1

5.k←1

6.fori←1ton

7.ifi不能被2整除

8.thenPM[k]←PM[i]

9.k←k+1

10.endif

11.endfor

12.n←k-1

13.endwhile

14.returnPM[1]

算法的时刻复杂度

算法实例：

数据的输入输出（能够有屏幕截图）

题目五找零问题

问题描述:

假设你在餐馆用饭花了不到100元，结账时你给效劳员一张百元钞票，而效劳员希望用最少的纸币给你找钱。

请设计算法帮忙效劳员

解决问题所用的方式：

贪婪算法

算法描述：

算法名称：

CHANGE

输入：

消费的钱money

输出：

总的钱的张数和每种面额钱的张数

算法实现细节（能够用流程图，伪代码）:

1.tM←100-money

2.k←0

3.fori←1to9

4.M[i]←tM/MM[i]comment：

MM表示各类面额的钱

5.tM←tM-M[i]*MM[i]

6.k←k+M[i]

7.endfor

8.returnk

算法的时刻复杂度

算法实例：

数据的输入输出（能够有屏幕截图）

课程设计总结

算法是运算机理论和实践的核心，通过这次的课程设计，让我熟悉到算法的重要性。

学好算法对以后的学习有专门大的帮忙，专门是对程序开发等方面上有着举足轻重的作用。

这次的课程设计，共完成了5个题目，充分运用了归纳法、分治、贪婪等方式对题目进行分析，并用C语言将之实现。

通过这次比较完整的一个程序的设计，我摆脱了单纯的理论知识学习状态，和实际设计的结合锻炼了我的综合运用所学的墓础知识，解决实际问题的能力，同时也提高我查阅文献资料、对程序整体的把握等其他能力水平，而且通过对整体的掌控，对局部的取舍，和对细节的斟酌处置，都使我的能力取得了锻炼，体会取得了丰硕。

这是咱们都希望看到的也正是咱们进行课程设计的目的所在。

尽管设计内容繁多，进程繁琐但我的收成却加倍丰硕。

和教师和同窗的沟通交流更使我对程序整体的计划与设计有了新的熟悉也对自己提出了新的要求提高是有限的但提高也是全面的，正是这一次设计让我积存了许多实际体会，也必然会让我在以后的工作学习中表现出更高的应变能力和明白得力。

参考文献

[1]张建勋纪纲《C程序设计有效教程》中国铁道出版社2020年1月第1版

[2]吴伟昶方世昌《算法设计技术与分析》电子工业出版社

源码:

pp:

概念操纵台应用程序的入口点。

pp:

概念操纵台应用程序的入口点。

pp:

概念操纵台应用程序的入口点。

pp:

概念操纵台应用程序的入口点。

pp:

概念操纵台应用程序的入口点。

//

#include""

#include

usingnamespacestd;

intlucky（intn）

{

inti=0,k=1;

intPM[501];

for（i=1;i<=n;i++）

PM[i]=i;

while（n>1）

{

k=1;

for（i=1;i<=n;i++）

{

if（i%2==0）

{

PM[k]=PM[i];

k++;

}

}

n=k-1;

}

returnPM[1];

}

voidmain（）

{

intn;

while（n<=0||n>500）

{

cout<<"请输入参加party的人数（0—500）";

cin>>n;

}

n=lucky（n）;

cout<<"幸运人士为"<

}