《常用软件算法基础》课件-第0章 循环算法

第十章班长评选（循环算法）内容目标：循环算法的基本概念。循环算法的设计要点班长评选循环算法案例分析具体到抽象循环算法案例分析用单向链表实现循环算法案例分析重难点：循环算法设计思想以及应用1.功能描述2.循环算法的基本概念基本概念 事实上，在一般情况下只有处理大量数据才借助于计算机，所以算法设计中很重要的工作就是对数据的处理归结成较规范的可重复的“机械化的操作”交给计算机去完成。即将重复处理大量数据的步骤抽象成“循环”或“递归”的模式，设计出可以针对不同规模解决问题的方法。不同于机器生产产品的“机械化的操作”，计算机进行数据处理不可能是完全相同的重复。所以必须要设计出表现形式不变，但能实现动态处理数据的“机械化的操作”。也就是说，在重复操作中，“循环条件”、:“循环体”都必须是“不变式”，而数据处理对象却是变化的，算法是在渐进地完成处理数据的操作。算法设计中，一个重要的工作就是从已建立好的数学模型中，构造出“不变式”的“循环条件”、“循环体”。“不变式”主要是依靠变量或数组元素表示的，因为变量名或数组元素是“不变”的，而变量或数组元素中的数据是不断变化的，从而数据处理是动态的、渐进的。3.1.1业务实现---班长评选算法设计：将所有的学生信息放入到顺序表中，并进行编号标识，编号标识顺序为1，2，3，…，n，当报号到r时，作淘汰操作，将对应的学生编号标识改为-1，如此下去当剩下一个时，即为所要评选的班长，最后输出编号标志不为-1的学生信息即是班长。数据结构设计：用一维数组的顺序表来保存学生的信息和编号标识。3.1.2业务实现---班长评选定义学生信息顺序表结点类：用以记录学生的信息和学生在顺序表中的编号，具体实现如下：publicclassnode{//学生信息顺序表结点类

publicStudent_infoData; //学生信息对象

publicintflag; //学生编号用以记录是否淘汰的标准，若为-1表示已经淘汰

publicnode() { }}

3.1.3业务实现---班长评选定义学生信息顺序表结点类：用以记录学生的信息和学生在顺序表中的编号，具体实现如下：publicclassbanzhang{ public LinkL;//实现班长评选算法的链表对象

publicStudentMangerBa=newStudentManger();//创建数据控制层对象

publicnode[]tp;//实现班长评选算法的顺序表对象

publicbanzhang() { } publicintLink_Init(intn)//单向循环链表的初始化

publicStudent_infoLink_select(intn,intr){…}//用单向循环链表实现班长评选算法

publicintsx_Init(intn){…}//顺序表的初始化

publicStudent_infosx_select(intn,intr){…}//用顺序表实现班长评选算法

}

3.1.4业务实现---班长评选为学生信息顺序表的初始化：根据所传入的学生总人数，进行学生信息顺序表的初始化，实现的步骤如下：判断所传入的学生总人数是否超出数据库中总学生数，若是返回0。为学生信息顺序表分配足够的内存空间。逐个为学生信息顺序表每个成员进行初始化。初始化完毕返回1。 publicintsx_Init(intn) {//初始化顺序表，输入总的学生人数

if(n>Ba.Max)return0; tp=newnode[n]; for(inti=0;i<n;i++)//为顺序表每个学生信息进行初始化

{ tp[i]=newnode(); tp[i].Data=Ba.base_info[i]; tp[i].flag=i+1; } return1; }

3.1.5业务实现---班长评选用以实现对给定的学生总人数n和所要淘汰号r，进行班长评选的设计，在这里采用“自顶向下”的方法来设计：首先：将算法分为三部分，即：学生信息初始化、学生信息淘汰、班长信息显示。其次：学生信息初始化包括：学生信息顺序表初始化，局部变量初始化（包括：记录学生报数变量，记录学生淘汰人数变量，记录所访问的学生编号变量）。学生信息淘汰，确定循环算法结束条件，进行信息淘汰，步骤如下：学生依次报数，实现报数变量自加。判断报数号是否与淘汰号r相等，若相等，实现淘汰操作处理，否则继续报数。判断学生报数是否一圈走完，若是从头开始，否则继续。班长信息显示：在顺序表中，逐个判断，寻找未淘汰的的学生信息，进行返回。 最后，对各个步骤进行细化，进行算法实现，代码如下：3.1.5业务实现---班长评选publicStudent_infosx_select(intn,intr){//应用顺序表实现班长评选

if(sx_Init(n)==0)//初始化顺序表

returnnull; inti,Out,count; i=0; Out=0;//记录淘汰的学生人数

count=0;//记录学生报数的

while(Out<n-1) { if(tp[i].flag!=-1)//该学生为淘汰，报数加1 { count++; } if(count==r)//报数为r，淘汰学生数加1，报数从0开发

{tp[i].flag=-1; count=0;Out++; } i++; if(i==n)//当一轮走完后，回到第一个学生位置

i=0; } for(i=0;i<n;i++)//返回最后的评选结果

{if(tp[i].flag>-1) returntp[i].Data; } returnnull;}

3.1.6业务实现---班长评选用单向循环链表实现班长评选：算法设计：应用单向循环链表的思想，进行班长的评选，首先将所有学生添加到单向循环链表中，通过链表指针的移动，实现结点的删除（即进行淘汰操作），当循环链表中只有一个元素时，即得到问题的解。数据结构设计：应用不带头指针的单向循环链表保存学生信息，通过指针移动实现淘汰元素的删除。3.1.7业务实现---班长评选学生单向循环链表结点类

publicclassLink {//学生信息链表结点

publicStudent_infoData;//学生信息对象

publicLinknext; //指向下一个学生信息对象

publicLink() { } }

3.1.8业务实现---班长评选学生信息循环链表的初始化：根据所传入的学生总人数，实现单向循环链表的初始化，实现的步骤如下：根据所传入的学生总人数n与数据库中学生总数进行比较，若大返回0。初始化单向循环链表对象L和局部结点对象s。逐个取出数据库中学生信息，添加到链表中。在添加第一个学生信息时，添加到首结点的数据域中，并记录该结点对象s。添加其他学生信息结点时，依次添加到首结点前面。最后将第一次添加对象s的指针域指向首结点。。3.1.9业务实现---班长评选publicintLink_Init(intn){//单向循环链表初始化，输入要创建的n个结点

if(n>Ba.Max)return0; inti;L=newLink();L.next=L;//初始化不带头指针的循环链表

Links=newLink(); for(i=n-1;i>=0;i--) {Student_infotemp=Ba.base_info[i]; Linkp=newLink(); if(i==n-1)//初始化第一个结点的数据域

{ L.Data=temp; s=L;//s指向尾结点 } else//初始化其他结点的数据域和指针域

{ p.Data=temp; p.next=L; L=p; } } s.next=L;//尾结点指针域指向头结点

return1;}

3.1.10业务实现---班长评选用循环链表实现班长评选：用以实现对给定的学生总人数n和所要淘汰号r，进行班长评选的设计，在这里采用“自顶向下”的方法的循环链表设计如下：首先：将算法分为三部分，即：学生信息初始化、移动指针淘汰学生、班长信息返回。其次：学生信息初始化包括：循环链表初始化、局部对象初始化移动指针实现学生信息的淘汰：循环终止条件：循环链表只剩一个学生即：test.next!=test。循环体：链表指针的移动r次，实现链表中淘汰学生结点删除。最后：实现班长信息的返回。3.1.11业务实现---班长评选publicStudent_infoLink_select(intn,intr){//用循环链表实现班长评选

if(Link_Init(n)==0)//初始化循环链表

returnnull; Linklast,test;//局部结点对象

Student_infotemp; inti; test=L; last=L; while(test.next!=test) { for(i=1;i<r;i++)//在循环链表中，结点指针移动

{ last=test; test=test.next; } last.next=test.next;//在循环实现学生信息删除

test=last.next; } temp=test.Data; returntemp; }

4.1.1知识扩展：长整数问题设计方法介绍：自顶向下的设计方法是从全局走向局部、从策略走向详尽的设计方法。自顶向下是系统分解和细化的过程。首先，根据题意，总体规划设计算法的主要组成或步骤。其次，分别对各个步骤进行分解，理清各个子步骤的算法框架。最后，继续为各个子步骤算法进行细化，直至算法实现。4.1.1知识扩展：长整数问题

问题描述：.给定1个正整数n（n<35），求n!的精确值。问题分析：由于34！的位数已经是40位了，在个人计算机中，没有任何一种标准的数据类型能够准确记录这样大的数。我们可以考虑用一个大小为40的一维整数数组，分别记录其各位的值。在输出时，按高位到低位进行输出。在每次n*(n-1)!时，用n乘以数组的每个元素，然后对数组的每个元素进行是否进位的检查，若第k元素大于9，将其十位上的数字加到第k+1元素上去，其个位仍然保留。4.1.2知识扩展：长整数问题实现步骤：现采用“自顶向下”的设计方法解决该问题的具体步骤如下：首先：从总体上该问题可分为如下几个部分：数组定义和初始化；n！阶乘的实现；n！阶乘的显示。其次：将各个组成部分的算法进行细化，设计出各个子步骤的算法框架:数组定义和初始化；数组的定义和初始化算法所用的变量的确定和初始化n！阶乘的实现；实现n*（n-1）!的算法进行数组元素进位判断，实现进位操作。、n！阶乘的显示。从高位到低位输出数组进行高位是否为0的判断，若为0，不进行输出，否则其后的各位都应进行输出。最后，对各个子步骤进行算法细化，进行算法实现。4.1.3知识扩展：长整数问题4.1.4知识扩展：长整数问题代码实现：publicvoidjc(intn)//任意输入n，n<=34{int[]a=newint[40];//初始化一维数组

a[0]=1;inti,j,k; //定义算法中的循环变量

boolflag=false;//定义数组元素是否该打印标志，开始为不用打印

for(i=2;i<=n;i++)//实现n的阶乘

{for(j=0;j<40;j++)//为数组每一元素都乘以某一值j { a[j]=a[j]*i; } for(k=0;k<40;k++)//检查数组每一元素是否超过10 {if(a[k]>9)//进行进位操作

{a[k+1]=a[k+1]+a[k]/10;//将k元素的高位进位到k+1元素上

a[k]=a[k]%10; //保留第k元素的个位

}}}Console.Write("{0}!=",n); for(k=39;k>=0;k--)//进行阶乘打印

{if(flag==true||a[k]!=0)//高位不为0进行打印

{Console.Write("{0}",a[k]); flag=true; } }}

4.2.1知识扩展：具体到抽象案例分析从具体到抽象的设计步骤：从给定的问题的具体特点为依据进行算法设计，循环变量的定义不是固定不变的。其范围及引用等细节，由具体实例进行归纳，可以比较容易地得到抽象的表达式。具体的设计步骤如下：首先：仔细了解问题的含义，从具体的问题中，归纳或抽象出具有普遍意义的共同特征。其次：根据归纳得到的共同特征，设计算法，构造出“不变式”的“循环条件”和“循环体”。最后：将问题进一步进行逐步细化，最终得到解决问题的算法。4.2.2知识扩展：具体到抽象案例分析问题描述： 问题：编写算法：打印具有下面规律的图形

152863109744.2.3知识扩展：具体到抽象案例分析问题分析和设计：问题分析：无论从题意理解，还是从算法的通用性来考虑，算法设计不能只针对图中的4*4的二维数组进行。下面以任意阶的二维数组n*n讨论。为分析方便，数组的起始下标为1。 算法设计：对二维表的操作一般按列或行进行的，但此图形中数据的排列方法却不是按行、列进行的。二维表是否只能按行、列的顺序进行操作呢？回答是否定的，下面根据排列的特点，按“层”对数据进行处理。容易发现图形中自然数在矩阵中的排列规律，题目中1，2，3，4所在的位置称为第1层（主对角线），例图中5，6，7所在位置称为第2层，…。一般地，第一层有n个元素，第2层有n-1个元素…。4.2.4知识扩展：具体到抽象案例分析问题分析和设计：基于以上数据变化的规律，以层号作为外层循环，循环变量为i（范围为1~n）；以层内元素从上到下的序号作为内循环，循环变量为j（范围为1~n+1-i）。这样循环的执行过程正好与“摆放”自然自然数的顺序相同。用一个变量k模拟要“摆放”的数据，下面的问题就是怎样将数据存储到对应的数组元素。数组元素的存取，只能按行、列号操作的。所以下面用由具体到抽象设计循环的“归纳法”，找出数组元素的行号