打印杨辉三角形.ppt

《打印杨辉三角形.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、打印杨辉三角形。此问题是一个初等数学问题。系数表中的第i行有i+1个数，除了第1个和最后一个数为1外，其余的数则为上一行中位于其左、右的两数之和。（a+b）n的系数算法分析如果要计算并输出二项系数表（即杨辉三角形）的前n行的值，则所设循环队列的最大空间应为n+2。假设队列中已存有第i行的值，为计算方便，在两行之间均加一个“0”作为行间的分隔符，则在计算第i+1行之前，头指针正指向第i行的“0”，而尾元素为第i+1行的“0”。由此，从左至右输出第i行的值，并将计算所得的第i+1行的值插入队列。如第四行为：014641第五行为：015101051分析第i行元素与第i+1行元素的关

2、系如图所示：在i=2时,队列的头指针指向0，尾指针指向1的下一位，我们看如何由第二行得到第三行的。①第三行的0入队②队头元素0出队并送入s中③取队头元素1并送入t中④s+t的值1入队。这时队列的队头指针指向1，队尾指针指向第三行的第一个3的位置。重复②③④三步就得到第三行；类推，我们由第三行又得到第四行；……frontrear从第2行数据计算并存放第3行数据0在运算的任一时刻,要产生下一个入队的元素,均是队头方向的两元素相加后入队.杨辉三角形元素入队顺序000000假设n=4，i=3，则输出第3行元素并求解第4行元素值的循环执行过程中队列的变化状态如图所示：完整算法请看教材v

3、oidYangHui(intn)/*打印杨辉三角形的前n行*/{SeqQueue*q;inti,j,s,t;for(i=1;i<=n;i++)printf("");printf("1");/*在中心位置输出杨辉三角最顶端的1*/q=InitQueue();/*设置容量为n+2的空队列*/EnQueue(q,0);/*添加行分隔符，即0入队*/EnQueue(q,1);EnQueue(q,1);/*第一行的值入队*/１、出队并保存出队元素２、取出front所指元素并保存３、计算前两步得到的元素值之和并入队重复这三步。（当由第i行求得第i+1行时，０先入队……）上图的操作过程

4、是：for(j=1;j

5、+t入队*/}while(t!=0);}DeQueue(q);/*删除行分隔符*/printf("%3d",DeQueue(q));/*输出第n行的第一个元素*/while(!QueueEmpty(q))/*输出第n行的其余元素*/{t=DeQueue(q);printf(“%5d",t);}}队列不空，则出队输出杨辉三角形的最后一行（）第n行递归与回溯n皇后问题在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这n个皇后的互不攻击的布局。1#主对角线3#主对角线5#主对角线0#次对角线2#次对角线4#次对角

6、线6#次对角线1#次对角线3#次对角线5#次对角线0#主对角线2#主对角线4#主对角线6#主对角线01230123k=i+jk=n+i-j-1解题思路安放第i行皇后时，需要在列的方向从0到n-1试探(j=0,…,n-1)在第j列安放一个皇后：如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第j列安放的皇后不动，递归安放第i+1行皇后。设置4个数组col[n]：col[i]标识第i列是否安放了皇后md[2n-1]:md[k]标识第k条主对角线是否安放了皇后sd[2n-1]:sd[k]标识第k条次对角线是否安放了皇后q[n]:

7、q[i]记录第i行皇后在第几列voidQueen(inti){for(intj=0;j