实验三文档格式.docx
《实验三文档格式.docx》由会员分享，可在线阅读，更多相关《实验三文档格式.docx（13页珍藏版）》请在冰点文库上搜索。
（见右图）
组合数计算方法：
C（n,m）=n!
/[m!
（n-m）!
]
8、（a+b）^n的展开式中的各项系数依次对应杨辉三角的第（n+1）行中的每一项。
[1]
9、将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第4n+1个斐波那契数；
将第2n行第2个数（n>
1），跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。
10、将各行数字相排列，可得11的N-1次方：
1=11^0;
11=11^1;
121=11^2……;
数据结构设计：
1.利用一个栈st进行判定，将“（”、“【”或“{”进栈，当遇到“）”、“】”或“}”时，检查当前栈顶元素是否是相对应的“（”、“【”或“{”，若是则退栈，否则返回表示不配对。
当整个算术表达式检查完毕时栈为空，表示括号正确配对；
否则不配对。
运行与测试：
2迷宫问题
2.显示杨辉三角形
总结与心得：
明白栈和队列的定义与功能，分析问题所需要何种结构，最终解决问题。
源程序：
1.表达式括号匹配对判断问题
#include<
iostream>
usingnamespacestd;
#defineMaxSize100//MaxSize为算术表达式中最大字符个数
voidcorrect（charexp[],int&
tag）//tag为引用型参量
{
charst[MaxSize];
inttop=-1,i=0;
tag=1;
while（exp[i]!
='
\0\'
&
&
tag）
）{
if（exp[i]=='
（'
||exp[i]=='
['
{'
）
{
top++;
//遇到‘（’，‘【’或‘{’，则将其进栈
st[top]=exp[i];
}
）'
）//遇到‘）’，若栈顶是‘（’，则继续处理，否则以不配对返回
if（st[top]=='
top--;
else
tag=0;
]'
）//遇到‘】’，若栈顶是‘【’，则继续处理，否则以不配对返回
if（st[top]='
}'
）//遇到‘}’，若栈顶是‘{’，则继续处理，否则以不配对返回
i++;
}
if（top!
=-1）//若栈不空，则不配对
tag=0;
}
intmain（void）
charexp[]="
{5+[3-（4*7）]}"
;
intt;
correct（exp,t）;
if（t）
cout<
<
exp<
"
true"
else
false"
return0;
2.迷宫问题
栈代码：
/************************************************************************/
/*自定义栈*/
/*通过自定义的简单栈以满足迷宫求解*/
/*功能：
push（）将元素加入栈中*/
/*pop（）退栈；
topValue（）获得栈顶元素*/
/*clear（）清除栈length（）获得栈中元素个数*/
#include<
stack>
template<
typenameElem>
classPathStack:
publicstack<
Elem>
private:
intsize;
inttop;
Elem*listArray;
public:
PathStack（intsz=DefaultListSize）{
size=sz;
top=0;
listArray=newElem[sz];
~PathStack（）{delete[]listArray;
voidclear（）{top=0;
/****向栈中加入元素****/
boolpush（constElem&
item）;
/***********退栈**********/
Elempop（）;
/********获得栈顶元素*******/
ElemtopValue（）const;
intlength（）const{returntop;
};
boolPathStack<
:
push（constElem&
item）{
if（top==size）returnfalse;
listArray[top++]=item;
returntrue;
ElemPathStack<
pop（）{
Elemit;
if（top==0）returnit;
it=listArray[--top];
returnit;
topValue（）const{
it=listArray[top-1];
CPP代码：
//迷宫求解的方法类
//功能：
通过findPath（）方法实现对路径的查找
//通过printPath（）方法将路径打印出来
#include"
PathStack.h"
classMazeSolveMethod
staticintmaze[10][10];
//存放迷宫数据
PathStack<
int>
pathStack;
//定义栈
MazeSolveMethod（）:
pathStack（100）{
~MazeSolveMethod（）{}
voidfindPath（intstartX,intstartY）;
voidprintPath（）const;
intMazeSolveMethod:
maze[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,0,0,0,1},
{1,0,0,0,1,0,1,0,0,1},
{1,0,1,0,0,0,1,1,0,1},
{1,0,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,1,1,1,1,0,0,0,1,1},
{1,1,1,1,1,1,1,0,0,1},
voidMazeSolveMethod:
findPath（intstartX,intstartY）{
intx=startX;
inty=startY;
pathStack.push（x）;
pathStack.push（y）;
maze[x][y]=2;
cout<
进入方法！
endl;
while（true）{
if（maze[x-1][y]==0）{
pathStack.push（--x）;
pathStack.push（y）;
maze[x][y]=2;
}elseif（maze[x][y-1]==0）{
pathStack.push（x）;
pathStack.push（--y）;
}elseif（maze[x][y+1]==0）{
pathStack.push（++y）;
}elseif（maze[x+1][y]==0）{
pathStack.push（++x）;
if（maze[x-1][y]!
=0&
maze[x][y+1]!
maze[x+1][y]!
maze[x][y-1]!
=0）{
if（x>
=8&
y>
=8）{
break;
}else{
maze[x][y]=3;
y=pathStack.pop（）;
x=pathStack.pop（）;
}
y=pathStack.topValue（）;
inttemp=pathStack.pop（）;
x=pathStack.topValue（）;
pathStack.push（temp）;
printPath（）const{
printPath"
for（inti=0;
i<
10;
i++）{
for（intj=0;
j<
j++）{
if（maze[i][j]==2）
cout<
'
*'
"
elseif（maze[i][j]==3）
0<
1<
主函数代码：
/*迷宫求解----栈方法实现*/
通过对栈实现迷宫算法求解
//Author：
Andrew
//Date：
2012-10-20
MazeSolveMethod.h"
usingstd:
cout;
intmain（）{
MazeSolveMethodsolve;
solve.findPath（1,1）;
solve.printPath（）;
system（"
pause"
）;
3.显示杨辉三角形
deque>
ints=0,t=0,rst,j;
deque<
que;
voidmain（）
que.push_back
（1）;
for（inti=1;
i<
i++）
{
que.push_back（0）;
for（j=0;
j<
i+1;
j++）
rst=que.front（）;
que.pop_front（）;
t=rst;
if（rst>
0）
cout<
rst<
que.push_back（s+t）;
s=t;
升级会员 