编程工具：C-Free 5.0
【实验一】：使用递归方法输出杨辉三角
杨辉三角.cpp
//使用递归方法输出杨辉三角，每个数字占用4个空格位#include
#include
int calcit(int x, int y)
{
if (x==y||y==0)
return 1;
else
return calcit(x-1,y-1)+calcit(x-1,y);
}
int main()
{
int i, j,k,n;
printf("请输入行数(最好<=13)：");
scanf("%d",&n);
for (i = 0; i { for(k=(n-i)*2;k>0;k--) printf(" "); for (j=0;j<=i;j++) printf("%4d",calcit(i, j)); printf("\n"); } return 0; } 杨辉三角的规律以及定理 李博洋 摘要杨辉三角中的一些规律 关键词杨辉三角幂二项式 引言 杨辉是我国南宋末年的一位杰出的数学家。在他所着的《详解九章算法》一书 中，画了一张表示二项式展开后的系数构成的三角图形，称做“开方做法本源”，现 在简称为“杨辉三角”，它是世界的一大重要研究成果。我们则来对“杨辉三角”的 规律进行探讨和研究。 内容 1二项式定理与杨辉三角 与杨辉三角联系最紧密的是二项式乘方展开式的系数规律，即。 杨辉三角我们首先从一个二次多项式(a+b)2的展开式来探讨。 由上式得出：(a+b)2＝a2+2ab+b2此代数式的系数为：121 则(a+b)3的展开式是什么呢？答案为：a3+3a2b+3ab2+b3由此可发现，此代数式的系数 为：1331但似乎没有什么规律，所以让我们再来看看(a+b)4的展开式。 展开式为：a4+4a3b+6a2b2+4ab3+b4由此又可发现，代数式的系数为： 14641似乎发现了一些规律，就可以发现以下呈三角形的数列： 1(110) 11(111) 121(112) 1331(113) 14641(114) 15101051(115) 1615201561(116) 因此可得出二项式定理的公式为： (a+b)n=C(n,0)a^n*b^0+C(n,1)a^(n-1)*b^1+...+C(n,r)a^(n-r)*b^r...+C(n,n)a^0*b^n 因此，二项式定理与杨辉三角形是一对天然的数形趣遇，它把带进了。求二项式展开式系数的问题，实际上是一种组合数的计算问题。用系数来计算，称为“式算”；用杨辉三角形来计算，称作“图算”。 2杨辉三角的幂的关系 首先我们把杨辉三角的每一行分别相加，如下： 1(1) 11(1+1=2) 121(1+2+1=4) 1331(1+3+3+1=8) 14641(1+4+6+4+1=16) 15101051(1+5+10+10+5+1=32) 1615201561(1+6+15+20+15+6+1=64) …… 相加得到的数是1，2，4，8，16，32，64，…刚好是2的0，1，2，3，4，5，6，…次幂，即杨辉三角第n行中n个数之和等于2的n-1次幂 3杨辉三角中斜行和水平行之间的关系 (1) 1(2)n=1 11(3)n=2 121(4)n=3 1331(5)n=4 显示杨辉三角实验报告 姓名：许严班级：计122 学号：1213023050 1.问题描述 杨辉三角如图2.4.3所示，其特点是两个腰上数值是1，其他位置上的每一个整数都是它的上一行相邻两个整数之和。问题是：对于指定的最大行数rmax,要求从第一行到第rmax逐行显示杨辉三角形的所有元素。 2.基本要求 ⑴设计输出形式，尽量反映杨辉三角的特点。 ⑵设计计算杨辉三角形各行数值的方法。 ⑶输入：rmax从键盘输入。 ⑷输出：屏幕输出杨辉三角形. 3.实现提示 ⑴存储设计 计算杨辉三角形第i行时，如果在第i-1行两侧各添加一个0，则第i行的第j个元素等于第i-1行的第j-1个元素与第j个元素的和。计算如图2.4.4所示。第i行计算完，第i-1行的数据就没有用了，依据第i行数据可计算第i+1行的数据。 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 … 图2.4.3 杨辉三角形 从上述计算中不难看出，第i行的元素从左往右依次可被求得，求解过程中也是从左往右依次使用地i-1行的数据，显然，具有先入先出的特点。所以，可借助一个队列存放计算过程中所需的数据，如图2.4.5所示。 但随着航数的增加，队列会很长。所以，可以设置一循环队列，队长不少于rmax+2,边计算边出队。 （2）算法设计 计算各行元素的算法步骤如下。 Step1:队列初始化，0、1入队。队头ftont指向0处，队尾指向1后。 Step2:i从1到rmax,循环执行下列操作，求第i行数据。 2.1 0入队。 2.2 从队首起直到队尾，每出队两元素，求和后入队。 输出时注意0不输出。 网上看了许多杨辉三角队列实现的代码，结果运行时都或多或少有点小问题，为此我提供一份自己运行正确的。 程序无误，细心做一下 注意，这是做成三个文件运行的 第一个文件命名 stdafx.h #include int GetQueueFirstData(SqQueue Q) { return Q->base[Q->front]; } int isEmptyQueue(SqQueue Q) { if(Q->front=Q->rear) return 1; else return 0; } SqQueue InitQueue() { SqQueue Q; Q=(SqQueue)malloc(sizeof(struct queue)); if (Q==NULL) return NULL; Q->base=(int *)malloc(Max*sizeof(int)); if(Q->base==NULL) return NULL; Q->front=Q->rear=0; return Q; } int EnQueue(SqQueue Q,int e) { if((Q->rear+1)%Max==Q->front) return 0; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%Max; return 1; } int DeQueue(SqQueue Q) { int e; if(Q->front==Q->rear) return 0; e=Q->base[Q->front]; Q->front=(Q->front+1)%Max; return e; } 杨辉三角形规律 每行数字两边对称每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 第n行的数字个数为n个。 第n行数字和为2^(n－1)。（2的（n-1）次方） 每个数字等于上一行的左右两个数字之和。可用此性质写出整个帕斯卡三角形。 将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第2n个斐波那契数。将第2n行第2个数，跟第2n+1行第4个数、第2n+2行第6个数……这些数之和是第2n-1个斐波那契数。 第n行的第1个数为1，第二个数为1×(n-1)，第三个数为1×(n-1)×（n-2）/2，第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。 两个未知数和的n次方运算后的各项系数依次为杨辉三角的第(n+1)行 杨辉三角在弹球游戏中的应用 如图1的弹球游戏，小球向容器内跌落，碰到第一层挡物后向两侧跌落碰到第二层阻挡物，再向两侧跌落第三层阻挡物，如此一直下跌最终小球落入底层。根据具体地区获的相应的奖品（。 图1 我们来分析一下为什么小球落到不同区域奖品会有如此大的差别？A 区的奖品价值高于D 区，说明小球落入A 区的可能性要比落入D 区的可能性小，转化为数学问题就是小球落入A 区和D 区的概率。小球要落入D 区的情况有两种，有概率知识得： D 1 D 2 就是说，小球落入D 区的概率是等于它肩上两区域概率之和的 2 1，据此小球落入各区的概率为可以按以上方法类推，如下： 2121 1 8381 3213232323232 1 64646641564206415646641 A B C D E F G 图2 队列实验 学号：姓名： 一、实验目的： 1．掌握队列的顺序存储结构 2．掌握队列先进先出运算原则在解决实际问题中的应用 二、实验内容： 利用循环顺序队列打印杨辉三角形。杨辉三角形的特点是两个腰上的数字都为1，其它位置上的数字是其上一行中与之相邻的两个整数之和。所以在打印过程中，第i行上的元素要由第i-1行中的元素来生成。在循环队列中依次存放第i-1行上的元素，然后逐个出队并打印，同时生成第i行中间的（n-2）个元素并入队列。打印的杨辉三角形如下所示： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 三、队列顺序存储结构的基本操作： 杨辉三角形输出的行数可以在程序中由输入控制。 队列的基本操作代码参考如下： #include /*初始化操作*/ void InitQueue(SeqQueue *Q) { /* 将*Q初始化为一个空的循环队列*/ Q->front=Q->rear=0; } /*入队操作*/ int EnterQueue(SeqQueue *Q, int x) { /*将元素x入队*/ if((Q->rear+1)%MAXSIZE==Q->front) /*队列已经满了*/ return(FALSE); Q->rear=(Q->rear+1)%MAXSIZE; /* 重新设置队尾指针*/ Q->element[Q->rear]=x; return(TRUE); /*操作成功*/ } /*出队操作*/ int DeleteQueue(SeqQueue *Q, int *x) { /*删除队列的队头元素，用x返回其值*/ if(Q->front==Q->rear) /*队列为空*/ return(FALSE); Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/ *x=Q->element[Q->front]; return(TRUE); /*操作成功*/ } /*提取队列的队头元素，用x返回其值*/ int GetHead(SeqQueue *Q, int *x) { if(Q->front==Q->rear) /*队列为空*/ return(FALSE); *x=Q->element[Q->front]; return(TRUE); /*操作成功*/ } 四、打印杨辉三角的函数： void PrintTriangle (int N ) { int i,,n,x,temp; SeqQueue Q; 实验二递归向下分析法 一、实验目和要求 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验内容 （1）功能描述 1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法， 3、递归下降分析法实验设计思想及算法 为G 的每个非终结符号U 构造一个递归过程,不妨命名为U。 U 的产生式的右边指出这个过程的代码结构： 1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。 2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。 具体为： （1）对于每个非终结符号U->u1|u2|…|un处理的方法如下： U( ) { ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; … else error() } （2）对于每个右部u1->x1x2…xn的处理架构如下： 处理x1的程序； 处理x2的程序； … 处理xn的程序； （3）如果右部为空，则不处理。 （4）对于右部中的每个符号xi ①如果xi为终结符号： if(xi= = 当前的符号) { NextChar()； return; } else 出错处理 ②如果xi为非终结符号，直接调用相应的过程xi() 说明： NextChar为前进一个字符函数。 （2）程序结构描述 程序要求： 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS| / FS （6）S->ε （7）F->(E) （8）F->i 输入出的格式如下： (1)E 盘建立一个文本文档" 222.txt"存储一个以#结束的符号串(包括+—*/（）i#)，在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串” 函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。 程序所用主要参数和头文件说明： #include 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; Main： queue.h： typedef int ElemType; typedef struct Inode{ ElemType data; struct Inode *next; }Inode; typedef struct linkque{ Inode *front; Inode *rear; }linkque; int QueInit(linkque &); int QueIn(linkque &,ElemType); int QueOut(linkque &,ElemType &); app.cpp： #include printf("%d",e2); printf("\n"); } while(q2.front!=q2.rear){ QueOut(q2,e); QueIn(q1,e); } } } queue.cpp： #include 1.用递归法计算n! 【讲解】 递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。 递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。 递归概述 一个函数在它的函数体内调用它自身称为递归（recursion）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 使用递归要注意以下几点： （1）递归就是在过程或函数里调用自身； （2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 例如有函数r如下： int r(int a) { b=r(a?1); return b; } 这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。 构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。 例4-1 用递归法计算n!。 n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 （1）描述递归关系 递归关系是这样的一种关系。设{U 1,U 2 ,U 3 ,…,U n ,…}是一个序列，如果从某一项k开始， U n 和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当n≥1时，n!=n*(n?1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k?1)!有关。 （2）确定递归边界 在步骤1的递归关系中，对大于k的U n 的求解将最终归结为对U k 的求解。这里的U k 称 为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。 确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序： #include 杨辉三角与二项式系数的性质 教学反思 本节课有以下几点值得一提： 一、目标定位准确 本节课，在充分挖掘教学内容的内在联系，了解学生已有知识基础，充分分析学情后，确定的教学目标：理解、领悟二项式系数性质；渗透数形结合和分类讨论思想；灵活有效地运用赋值法.应该说具有具体而又准确，科学而有效的特点.随着课堂的实践得到了落实，并且将“知识目标”、“能力目标”、“情感目标”融为一体. 教学目标基本符合学生“认识规律”，以递进的形式呈现：观察分析、归纳猜想、抽象概括，提炼上升；特殊——一般——特殊到一般…，课堂实践表明，这些目标，在师生共同努力及合作下是完全可以达到的. 二、突出主体地位 1．放手发动学生 把课堂还给学生，一直是课改的大方向，也是新课标的原动力之一. 还给学生什么呢？教师作了很好的诠释： 一是给“问题”，当然问题有预设的，也有生成的，符合从学生“思维最近发展区”出发这一根本教学原则. 二是给“时间”，这体现了教师的先进教学理念，即便是教学难点“中间项系数最大”这一组合数计算讨论过程仍由学生尝试. 当然，n=6，7时，离散型函数的图象起了直观引领，奠基的重要作用. 不为完成任务所累，不为主宰课堂所困. 三是给“机会”，让学生展示自主探索，合作交流的成果，极大地保护和激发了学生学习的热情和积极性，参与程度和激情得到了空前的提高. 2．彰显理性数学 本节课，无论是对称性，增减性（最大值），及二项式系数和的逐步生成，学生都能从“特殊到一般”的认识规律，归纳猜想到结论. 但数形结合的函数思想，组合数两个性质的运用，两个计数原理的巧妙“会师”，奇数项二项式系数和等于偶数项二项式系数和，反馈升华例示中赋值法再现. 这正是“数学演绎”、“理性数学”的精华，让学生找到内化和建构的多种途径. for(i=1;i<=N;++i) { for(j=0;j<30-3*i;++j)//打印每行前面的空格 printf(" "); do { DeQueue(); GetHead(); if(e!=0) printf("%6d",e); EnQueue(); }while(e!=0); UpQueue(); puts("");//每行后回车换行 } 以n=4举例 结果为： 1 1 1 2 1 1 3 3 1 1 4 6 4 1 解析： queue_size=n+2;//队列的最大容量queue_size=6（数组空间大小） for(i=0;i 继续执行do……while语句因为e不为0 DeQueue(); 删除队首元素，并将queue[2]赋值s front=3 GetHead(); 取队首元素，e= queue[front]=queue[3]=1 if(e!=0) printf("%6d",e); e！=0 打印e 即1 EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[0]=2 rear=1 继续执行do……while语句因为e不为0 DeQueue(); 删除队首元素，并将queue[3]赋值s front=4 GetHead(); 取队首元素，e= queue[front]=queue[4]=0 if(e!=0) printf("%6d",e); e==0 不执行printf（）语句 EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[1]=1 rear=2 此时e==0跳出do……while语句 即打印第一行完毕输出： 1 1 UpQueue(); 在队尾添加元素0 即queue[rear]=queue[2]=0 rear=3 队列为： 2 1 0 1 0 1 puts("");//每行后回车换行rear front /* Name: 杨辉三角算法集锦 Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处Author: goal00001111 Date: 27-11-08 19:04 Description: 分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法 算法思路详见代码注释——注释很详细，呵呵 */ #include cout << endl; Fun_6(row); cout << endl; Fun_7(row); cout << endl; Fun_8(row); cout << endl; Fun_9(row); system("pause"); return 0; } //输出n个空格 void PrintBlank(int n) { for (int i=0; i 1.3.2二项式系数的性质(第一课时) 学校：新塘中学 班级：高二A8班 教师：段建辉 ●教学目标 （一）知识与技能 1.二项式系数的性质：对称性，增减性与最大值，各二项式系数的和. 2.掌握“赋值法”，并会简单应用 （二）情感与价值观 1.树立由一般到特殊及特殊到一般的意识. 2.了解中国古代数学成就及地位．．．．．．．．．．．．． ●教学重点：二项式系数的性质 ●教学难点：二项式系数的最大值的理解与二项展开式中系数最大项有的求解. ●教学方法:发现法 ●授课类型：新授 ●教学情境设计： 一、复习回顾 1．二项式定理及其特例： （1）01()()n n n r n r r n n n n n n a b C a C a b C a b C b n N -*+=+++++∈L L ， （2）1(1)1n r r n n n x C x C x x +=+++++L L . 2．二项展开式的通项公式：1r n r r r n T C a b -+= 二、引入 通项公式中的r n C ，我们称其为二项式系数.当n 依次取1，2，3…时， n b a )(+二项式系数，如下表所示： 表1 此表叫二项式系数表,早在南宋数学家杨辉所著的《详解九章算法》一书中出现了又叫杨辉三角.国外最早发现是在欧洲,叫帕斯卡三角，比中国晚了500年 下面我们可以利用“杨辉三角”来研究二项式系数的性质 三、探究 观察二项式系数表,根据提示的方法,寻找表中的规律. 【注意】 ?1）不要孤立的看、规律应该体现在联系之中 ?2）既要注意横向观察，也要注意纵向观察，横向观察是重点 ?3）可以结合函数图象或图表来研究，也可以和集合作联系 1、二项式系数表的规律 ①每行两端都是1 ②除1以外的每1个数都等于它肩上两个数的和（如何用数学知识解释？） 【提示】设这一数为r C 1-r n 和C r n ，由组合数知识可知： 1 1 01C C 02 C 12 C 2 2C 03 C 13 C 23 C 33 C 1 4C 0 4 C 3 4C 2 4C 4 4C 0 5C 1 5C 2 5C 35 C 4 5C 55 C 实验二栈与队列操作 实验目的： (1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (2)了解复杂问题的递归算法设计。 本次实验中，下列实验项目选做一。 1、顺序栈的基本操作 [问题描述] 设计算法，实现顺序栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立顺序栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）将栈顶元素出栈。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、链栈的基本操作 [问题描述] 设计算法，实现链栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立带头结点的链栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）完成出栈操作。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 （7）输出链栈的长度。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 3、循环队列的基本操作 [问题描述] 设计算法，实现循环顺序队列的建立、入队、出队等操作。 [基本要求] （1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。 （2）从键盘输入1个元素，执行入队操作，并显示结果。 （3）将队头元素出队，并显示结果。 （4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 4、只用尾指针表示的循环链表队列的综合操作 [问题描述] 假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。 [基本要求及提示] （1）首先定义链表结点类型。 （2）编写带头结点的循环链表的初始化函数，只用尾指针表示。 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。 5、用标志域表示队空队满状态的循环队列的综合操作 [问题描述] 要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。 [基本要求及提示] （1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。 （2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型： Typedef struct { QueueElementType element[MAXSIZE]; int front; int rear; int tag; }SeqQueue; 此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和 Q->front==Q->rear&&tag==1 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。 6、利用辅助数组进行栈的逆置 [问题描述] 利用辅助栈将栈中的元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。 7、利用辅助栈进行队列的逆置 [问题描述] 利用辅助栈进行队列元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。 8、Hanoi塔问题 精心整理 杨辉三角的规律以及定理 二项式定理与杨辉三角1与杨辉三角联系最紧密的是二项式乘方展开式的系数规律，即二项式定理。 2的展开式来探讨。杨辉三角我们首先从一个二次多项式(a+b)222此代数式的系数为：121 由上式得出：(a+b)+2ab+b＝由此可发现，此代数式的系+3+b+3ab(a+b 的展开式是什么呢？答案为(a+b的展开式。为133但似乎没有什么规律，所以让我们再来看b2+4a展开式为由此又可发现，代数式的系数为+4+b+6464似乎发现了一些规律，就可以发现以下呈三角形的数列：1 ) 1(1)11(112) 121(113) 1331(114) 14641(115) 15101051(116) 1615201561(11）1,4,6,4,1,（,1,2,1）（1,3,3,1）1,杨辉三角形的系数分别为：（1,1）,（：所以（）,1,7,21,35,35,21,7,1） （1,5,10,10,5,1）,（1,6,15,20,15,6,17642547765233 (a+b)=ab+7ab+21a+bb+35a+7abb+35a。b+21a n的次数依次上b-n，n-n 等于a的次数依次下降、n-1、2...n由上式可以看出，(a+b) (2) 方。系数是杨辉三角里的系数。、、升，01 杨辉三角的幂的关系2 精心整理． 精心整理 首先我们把杨辉三角的每一行分别相加，如下： 1(1) 11(1+1=2) 121(1+2+1=4) 1331(1+3+3+1=8) 14641(1+4+6+4+1=16) 15101051(1+5+10+10+5+1=32) 1615201561(1+6+15+20+15+6+1=64) … 相加得到的数136…刚好，6，…次幂，即杨辉三角行个数之和等n-次 杨辉三角中斜行和水平行之间的关 (1) 1(2)n=1 11(3)n=2 121(4)n=3 1331(5)n=4 14641(6)n=5 15101051n=6 1615201561 把斜行(1)中第7行之前的数字相加得1+1+1+1+1+1+1=6 1． 3．2“杨辉三角”与二项式系数的性质 教学目标： 知识与技能：掌握二项式系数的四个性质。 过程与方法：培养观察发现，抽象概括及分析解决问题的能力。 情感、态度与价值观：要启发学生认真分析书本图1－5－1提供的信息，从特殊到一般，归纳猜想，合情推理得到二项式系数的性质再给出严格的证明。 教学重点：如何灵活运用展开式、通项公式、二项式系数的性质解题教学难点：如何灵活运用展开式、通项公式、二项式系数的性质解题授课类型：新授课 教 具：多媒体、实物投影仪 第一课时 一、复习引入： 1．二项式定理及其特例： （1）01()()n n n r n r r n n n n n n a b C a C a b C a b C b n N -*+=+++++∈， （2）1 (1)1n r r n n n x C x C x x +=++ ++ +. 2．二项展开式的通项公式：1r n r r r n T C a b -+= 3．求常数项、有理项和系数最大的项时，要根据通项公式讨论对r 的限制；求有理项时要注意到指数及项数的整数性 二、讲解新课： 1二项式系数表（杨辉三角） ()n a b +展开式的二项式系数，当n 依次取1,2,3…时，二项式系数 表，表中每行两端都是1，除1以外的每一个数都等于它肩上两个数的和 2．二项式系数的性质： ()n a b +展开式的二项式系数是0n C ，1n C ，2n C ，…，n n C ．r n C 可以看成 以r 为自变量的函数()f r 定义域是{0,1,2, ,}n ，例当6n =时，其图象是7个孤立的点（如图） （1）对称性．与首末两端“等距离”的两个二项式系数相等 （∵m n m n n C C -=）． 直线2 n r = 是图象的对称轴． （2）增减性与最大值．∵1(1)(2)(1)1!k k n n n n n n k n k C C k k ----+-+= =? ， 杨辉三角显示实验报告 1.问题描述： 编写程序，根据输入的行数，屏幕显示杨辉三角。 2.基本要求： （1）行数不大于20行。 （2）基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现） （3）基于数组实现队列的物理数据结构 3.需求分析： 1、输入形式：输入一个整数n ，0<=n<=20 2、输出形式：打印出来前(n+1)行的杨辉三角数列 3、功能实现：输出前20层的杨辉三角序列 4、样例输入输出：（数据加强版） 输入：10 输出： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 5、效率分析：O(n) 4.概要设计： 利用到队列先进先出的性质（First In First Out），基本的算法实现是利用已经进队的元素在其出队之前杨辉三角的下一行数列，----即利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，我们来构造杨辉三角的第N+1行，从而实现打印杨辉三角的目的。 5.详细设计： 算法思想已经在概要设计中提到了，现在通过基于队列基本操作的函数以及程序的模块化思想来实现杨辉三角的打印输出问题。 算法函数描述： 队列类： 队列类的数据成员： int front，rear,//ront和rear分别是指向队头和队尾的指针 maxsize;//队列中的元素数 int* listArray //存放队列中的元素 队列的基本操作： V oid Queue(int ) function://构造一个空队列 软件学院 上机实验报告 课程名称：数据结构 实验项目：队列的应用 实验室：耘慧420 姓名：学号 专业班级：实验时间： 2016.11.17 一、实验目的及要求 (一) 目的 1．掌握栈队列特点及顺序存储结构(循环队列)下基本操作的实现。 2．掌握队列的应用，能根据问题特点选择队列结构。 （二）.要求 1．定义循环队列的存储结构 2．完成入队、出队、取队头等基本操作的实现。 3．利用队列的基本操作实现n行杨辉三角的输出。 4．主函数调用杨辉三角输出函数，实现n行杨辉三角输出。 二、性质 设计性 三、实验学时 2学时 四、实验环境 C与C++程序设计学习与实验系统 五、实验内容及步骤 (一).内容 1．定义循环队列的存储结构，完成入队、出队、取队头等基本操作的实现。 2. 利用循环队列实现杨辉三角的输出 (二).步骤 1.//---------循环队列—队列的顺序存储结构 ----- #define MAXSIZE 100 typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针，队列不空指向队列头元素 int rear; //尾指针，队列不空指向队列尾元素下一位置 } SqQueue; 2.杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …………………… 这是一个初等数学中讨论的问题。系数表中的第 k行有 k个数，除了第一个和最后一个数为1之外，其余的数则为上一行中位其左、右的两数之和。 如果要求计算并输出杨辉三角前n行的值，则队列的最大空间应为 n+2。假设队列中已存有第 k 行的计算结果，并为了计算方便，在两行之间添加一个"0"作为行界值，则在计算第 k+1 行之前，头指针正指向第 k 行的"0"，而尾元素为第 k+1 行的"0"。由此从左到右依次输出第 k 行的值，并将计算所得的第 k+1 行的值插入队列的基本操作为： void YangHui(int n) { printf("1\n"); EnQueue(&q,0); /*开始*/ EnQueue(&q,1); /*第1行*/ EnQueue(&q,1); for(j=2;j<=n;j++) { EnQueue(&q,0); do{杨辉三角的规律以及推导公式
显示杨辉三角实验报告
杨辉三角队列实现
杨辉三角形的生活运用和规律
队列实验
编译原理实验(递归向下语法分析法实验)附C语言源码-成功测试
数据结构第三章栈和队列3习题
队列实现杨辉三角
04.递归算法讲解
杨辉三角与二项式系数的性质教学反思07
杨辉三角解析(队列实现)
杨辉三角的各种算法实现
(完整版)教学案例.杨辉三角与二项式系数性质(标准)
实验二 栈与队列操作实验题目
杨辉三角的规律以及推导公式
杨辉三角与二项式系数的性质(教案)
杨辉三角队列实现
数据结构——队列的应用
相关主题
文本预览