算法基本工具

1528631097412第十二页，共七十页，编辑于2023年，星期三2递归设计思路-例4程序结构化设计的三种基本结构，顺序、选择、循环是不是必须的？例4根据参数n，计算1+2+……+n。voidsum_loop(intn){ inti,sum=0; for(i=1;i<=n;i++){ sum=sum+i; } printf("\nsum=%d",sum);}nisum回答：在很多高级语言中，不是。可以抛弃谁呢？递归能取代循环的作用。13第十三页，共七十页，编辑于2023年，星期三2递归设计思路-例4例4根据参数n，计算1+2+……+n。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf("\nsum=%d",sum);returnsum;}sum(n)sum(n-1)n+sum(n-2)n-1+…….sum(n-3)n-2+1递归算法是一个模块(函数、过程)除了可调用其它模块(函数、过程)外，还可以直接或间接地调用自身的算法。直接/间接递归调用。代入n=4，走一遍。递归树！sum(1)2+14第十四页，共七十页，编辑于2023年，星期三2递归设计思路-例4例4根据参数n，计算1+2+……+n。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf("\nsum=%d",sum);returnsum;}

…栈顶(top)栈底(bottom)出栈进栈栈底元素

栈顶元素

n…sumn-1…sum……..;2…sum1…sum表面上是一个变量，实际上是一个栈15第十五页，共七十页，编辑于2023年，星期三2递归设计思路-例4例4根据参数n，计算1+2+……+n。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf("\nsum=%d",sum);returnsum;}T(n)=T(n-1)+O(1)sum(1)sum(n)sum(n-1)n+sum(n-2)n-1+…….sum(n-3)n-2+2+1

=T(n-2)+O(1)+O(1)

=……….

=n*O(1)=O(n)16第十六页，共七十页，编辑于2023年，星期三“收敛”3递归设计要点递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf("\nsum=%d",sum);returnsum;}sum(n)sum(n-1)n+sum(n-2)n-1+…….sum(n-3)n-2+sum(1)2+117第十七页，共七十页，编辑于2023年，星期三例1.1欧几里德算法gcd(m,n)=gcd(n,mmodn)输入正整数m和n

输出m和n的最大公因子如果n=0,计算停止返回m,m即为结果；否则继续2。记r为m除以n的余数，即r=mmodn。把n赋值给m，把r赋值给n，继续1。伪代码如下(循环)：

Euclid(m,n){whilen<>0{r=mmodn;m=n;n=r;}}递归代码：GCD(m,n)//约定m>n//{ifn=0return(m)elsereturn(GCD(n,mmodn))}18第十八页，共七十页，编辑于2023年，星期三GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2递推递推递推递推回归回归回归回归结果为GCD(22,8)=2例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;

19第十九页，共七十页，编辑于2023年，星期三3递归设计要点-hanoi塔Hanoi塔hanoi河内[越南首都]古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个盘子，且在移动过程中在3个基座上的盘子都始终保持大盘在下，小盘在上。在移动过程中可以利用C基座做辅助。请编程打印出移动过程。约定盘子自上而下的编号为1，2，3，……，n。20第二十页，共七十页，编辑于2023年，星期三3递归设计要点-hanoi塔首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：初始状态为A(1,2)B()C()第一步后A(2)B()C(1)第二步后A()B(2)C(1)第三步后A()B(1,2)C()用递归思路考虑21第二十一页，共七十页，编辑于2023年，星期三3递归设计要点-hanoi塔把n个盘子抽象地看作“两个盘子”，上面“一个”由1——n-1号组成，下面“一个”就是n号盘子。移动过程如下：第一步：先把上面“一个”盘子以a基座为起点借助b基座移到c基座。第二步：把下面“一个”盘子从a基座移到b基座。第三步：再把c基座上的n-1盘子借助a基座移到b基座。22第二十二页，共七十页，编辑于2023年，星期三3递归设计要点-hanoi塔把n阶的汉诺塔问题的模块记作hanoi(n,a,b,c)a代表每一次移动的起始基座；b代表每一次移动的终点基座；c代表每一次移动的辅助基座；则hanoi(n,a,c,b)，表示把n个盘子从a搬到c，可以借助b；hanoi(5,c,a,b)，表示把5个盘子从c搬到a，可以借助b。则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：第一步，hanoi(n-1,a,c,b)；第二步，把下面“一个”盘子从a基座移到b基座；第三步，hanoi(n-1,c,b,a)。至此找出了大规模问题与小规模问题的关系。23第二十三页，共七十页，编辑于2023年，星期三3递归设计要点-hanoi塔hanoi(n,a,b,c)a：起始基座b：终点基座c：辅助基座hanoi(n,a,b,c)hanoi(n-1,a,c,b)hanoi(n-1,c,b,a)移hanoi(n-2,a,b,c)hanoi(n-2,b,c,a)移………………hanoi(2,..,..,..)hanoi(2,..,..,..)移hanoi(1,..,..,..)移hanoi(1,..,..,..)hanoi(0,..,..,..)/hanoi(0,..,..,..)O(2n)24第二十四页，共七十页，编辑于2023年，星期三3递归设计要点-hanoi塔hanoi(intn,chara,charb,charc) /*a,b,c初值为”A”,”B”,”C”*/ if(n>0){/*0阶的汉诺塔问题当作停止条件*/ hanoi(n-1,a,c,b);

输出“Movedish”,n.”frompile”,a,”to”b); hanoi(n-1,c,b,a); }25第二十五页，共七十页，编辑于2023年，星期三4非递归(循环)/递归比较-非递归hanoi塔递归思路不适合人类使用：人脑的逆推深度是有限的，而计算机要比人脑深很多，论记忆的准确性，计算机要比人脑强很多。你用递归的程序，用n=10，试试看？通过分析可以找到非递归的思路，而这种思路是未学过递归思想的人常用的。26第二十六页，共七十页，编辑于2023年，星期三4非递归(循环)/递归比较-转化设计算法重复处理大量数据的思路：以不变应万变；两种思路：非递归(循环)、递归。1、有些问题可以方便的用循环/递归两种思路处理；如例4累加求和；在后面的课程中，会常遇到递归算法，以及同一问题的递归、非递归算法。2、有些问题用递归比较方便；转换成非递归过程可通过模拟递归过程的执行过程来实现；其基本思想是在程序中设置一个栈；如例5hanoi塔。同一个问题干嘛要学两种方法？27第二十七页，共七十页，编辑于2023年，星期三从算法设计的角度递归函数调用引起的栈操作4非递归(循环)/递归比较递归非递归程序可读性易难代码量大小小大时间长短占用空间大小适用范围广窄设计难度易难并不是每一门语言都支持/很好的支持递归；有助于理解递归的本质；有助于理解栈,树等数据结构；两者各有利弊：28第二十八页，共七十页，编辑于2023年，星期三1数据结构的选择很重要例6大整数存储及运算2算法和数据结构不分离例7线性表的实现3数组与指针例7线性表的实现一聚，一散一静，一动静中有动高级语言的支持3.2算法与基本数据结构29第二十九页，共七十页，编辑于2023年，星期三1数据结构的选择很重要计算机解决问题是对“数据”加工处理。例6编程求当N<=100时，N！的准确值。问题分析：例如：9！=362880100！=

93326215443944152681699263 856266700490715968264381621468592963 895217599993229915608914463976156578 286253697920827223758251185210916864 000000000000000000000000处理对象的情况严重影响处理过程、效果。数值问题/非数值问题。30第三十页，共七十页，编辑于2023年，星期三1DS选择-例6-问题分析计算机存储数据是按类型分配空间的。在PC上：整型：2个字节16位，则整型数据的范围为-32768—32767；长整型：4个字节32位，则长整型数据的范围为-2147483648—2147483647；实型：4个字节32位，但非精确存储数据，只有六位精度，数据的范围±(3.4e-38~3.4e+38)；双精度型：8个字节64位的存储空间，数据的范围±(1.7e-308~1.7e+308)，其精确位数是17位。这些类型无法存储100！这样的“大整数”。需要使用更复杂、更有针对性的数据结构。31第三十一页，共七十页，编辑于2023年，星期三1DS选择-例6-算法设计每一位数，都是一个10以内数字。多个，相同属性的，…数组是有头有尾的：a[1]~a[n]。高位、低位谁头谁尾？低位固定，而高位不定。最低位为a[1]，且在高端要为问题最大存储数据留够空位。基于存储的考虑inta[n]32第三十二页，共七十页，编辑于2023年，星期三1DS选择-例6-算法设计100！=1*2*3*……*99*100。按此方法计算，最困难的操作是：大整数*乘数，其中乘数<=100。基于功能的考虑原来一个元素存一位，现在是否要改变？改变是否有用？问题出在哪里？当低位元素计算后的值超过9时，需向高位元素进位。如何进位？33第三十三页，共七十页，编辑于2023年，星期三1DS选择-例6-算法设计inta[n]中的数组元素可以存放更大的数。如，每个存3位。基于性能的考虑进位4次。进位几次？进位需要特殊的处理；减少进位的处理，可以提高效率。每个元素处理的位数越多，进位次数越少。在前面提到的四种数据类型的基础上，粗略估计一下，本问题中，每个元素最多可以存储几位数据？34第三十四页，共七十页，编辑于2023年，星期三1DS选择-例6-算法实现main(){

longab[256],b,d;

intm,n,i,j,r;input(n);m=log(n)*n/6+2;ab[1]=1;

for(i=2;i<=m;i++)ab[i]=0;d=0;

for(i=2;i<=n;i++)

for(j=1;j<=m;j++){b=ab[j]*i+d;ab[j]=bmod1000000;d=b/1000000;}if(d<>0)a[j]=d;}

for(i=m;i>=1;i--)

if(ab[i]==0)continue;

else{r=i;break;}print(n,“!=”);print(ab[r]);

for(i=r-1;i>=1;i--){

if(ab[i]>99999){print(ab[i]);continue;}

if(ab[i]>9999){print(“0”,ab[i]);continue;}

if(ab[i]>999){print(“00”,ab[i]);continue;}

if(ab[i]>99){print(“000”,ab[i]);continue;}

if(ab[i]>9){print(“0000”,ab[i]);continue;}print(“00000”,ab[i]);}//for}B存储计算的中间结果，d存储超过6位数后的进位，ab数组存储每次累乘的结果，每个元素存储6位数字35第三十五页，共七十页，编辑于2023年，星期三算法说明m=log(n)*n/6+2;是对n!位数的粗略估计，这样做算法简单，但是效率低。改进方法：记录当前积所占数组元素的个数，初值为1，每次有进位时m增加1。将第二个for循环中if语句改为

if(d<>0){a[j]=d;m=m+1;}输出时，首先计算结果的准确位数r，然后输出最高位数据，输出其他单元数据要注意，如若结果为

123000001，ab[1]中是1，不是00000136第三十六页，共七十页，编辑于2023年，星期三1数据结构的选择很重要-总结基于存储的考虑基于功能的考虑基于性能的考虑37第三十七页，共七十页，编辑于2023年，星期三2数组与指针一聚，一散一动，一静静中有动高级语言的支持数组和指针在程序设计、数据结构中占重要角色。在基础类型上的扩展；构成复杂数据类型的基础和重要方式。数据的逻辑结构常分为四大类：集合结构线性结构树形结构图结构（网结构）数组和指针均可实现38第三十八页，共七十页，编辑于2023年，星期三3数组与指针——一聚，一散连续存储可随机存取(通过数组名、下标便可以访问)；La1a2an^…a1a2ai

an

…

…

链式存储在内存中方便利用碎片存储。例7线性表的实现无需多余存储单元，空间效率高。39第三十九页，共七十页，编辑于2023年，星期三3数组与指针——一动，一静La1a2an^…a1a2ai

an

…

…

例7线性表的实现连续存储数组的空间在分配后相对固定；链式存储可以方便的进行插入、删除操作。但也有变通方法，静中有动。40第四十页，共七十页，编辑于2023年，星期三3数组与指针——静中有动动态声明数组：动态数组动态声明C不支持C++通过指针支持Java支持C语言不支持：

intn; scanf("%d",&n); inta[n];C++语言利用指针支持：

int

len;

cin>>len;

int

*p=new

int[len];Java语言支持：

inta[]；输入len值；

a=newint[len]；41第四十一页，共七十页，编辑于2023年，星期三3数组与指针——静中有动初始化后改变长度动态数组初始化后可变长CRealloc帮助实现；C++不支持，有类支持；Java数组不支持，有ArrayList、Vector类支持。

Listlst=newArrayList();

lst.add(newInteger(37));

一个整型值37用于构造一个Integer封装类对象，然后那个对象被加入到列表。42第四十二页，共七十页，编辑于2023年，星期三3数组与指针——高级语言的支持在本课程的算法实现中，使用类C语言，在可能的情况下均使用数组，数组使用静态数组。这符合“简单明了”的表达原则。指针C支持C++支持Java不支持，通过“引用”部分的实现指针功能String

s

=

new

String(“howmuch?");43第四十三页，共七十页，编辑于2023年，星期三3.从算法到实现-算法基本技巧举例a.算术运算的妙用例8开灯问题b.巧用“标志量”例9判定输入n个数据互不相等例10冒泡排序c.信息数字化例11警察抓小偷d.学会找规律例12数组移位44第四十四页，共七十页，编辑于2023年，星期三a.算术运算的妙用-例8开灯问题算术运算：加减乘除。例8开灯问题有从1到n依次编号的n个同学和n盏灯。

1号同学将所有的灯都关掉；

2号同学将编号为2的倍数的灯都打开；

3号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；

以后的同学都将自己编号的倍数的灯，作相反处理。

问：经n个同学操作后，哪些灯是打开的？45第四十五页，共七十页，编辑于2023年，星期三问题分析：1）用数组表示某种状态，这里定义有n个元素的a数组，它的每个下标变量a[i]视为一灯，i表示其编号。a[i]=1表示灯处于打开状态，a[i]=0表示灯处于关闭状态。此用法也称为“乒乓开关”。简化逻辑表达式、减少条件判断2）实现将第i灯作相反处理的操作：条件语句if表示：

ifa[i]==1a[i]=0；

ifa[i]==0a[i]=1；

通过算术运算更简练、逼真：

a[i]=1-a[i]。a.算术运算的妙用-例8问题分析/建模46第四十六页，共七十页，编辑于2023年，星期三a.算术运算的妙用-例8-算法设计inta[1000]; 输入n的数值； 关闭所有灯，即a[1]~a[n]置为0； 第2个学生->第n个学生(学生i)进行操作：

操作对象：数组a，灯编号含因数i，即a[i*k]；

操作：

a[i*k]=1-a[i*k]； 输出灯的开关状态。47第四十七页，共七十页，编辑于2023年，星期三建立一个充分大的数组inta[1000];

输入n的数值； 关闭所有灯，即a[1]~a[n]置为0； 第2->第n个学生(每个学生i)进行操作： 操作对象：数组a， 灯编号含因数i，即a[i*k]

操作：a[i*k]=1-a[i*k]； 输出灯的开关状态。voidmain(){

intn,a[1000],i,k;scanf("%d",&n);

for(i=1;i<=n;i++)a[i]=0;

for(i=2;i<=n;i++){k=1;

while(i*k<=n){a[i*k]=1-a[i*k];k=k+1;}}

for(i=1;i<=n;i++)printf("%d",a[i]);}翻译a.算术运算的妙用-例8-算法设计/实现48第四十八页，共七十页，编辑于2023年，星期三b巧用“标志量”-例9-问题分析例9判定输入n个数据互不相等。问题分析/算法设计：完全比较一遍需要n-1+n-2+n-3+……+1=n*(n-1)/2次比较。双重循环；通过引入标志量记录数据是否有重复的情况，相当于整合每趟循环中的比较结果。49第四十九页，共七十页，编辑于2023年，星期三建立一个充分大的数组； 标志量flag=1； 输入n个数，保存在数组的前n个元素； 从第1个—>第n-1个(每个元素i)操作 与第i+1—>第n元素(每个元素j)比较，若相等则标志量置0，循环中断； 若flag=1，则无重复；反之，有重复。b巧用“标志量”-例9算法设计50第五十页，共七十页，编辑于2023年，星期三b巧用“标志量”-例9–

实现voidmain(){

inta[100],i,j,flag,n;scanf("%d",&n);

for(i=1;i<=n;i=i+1)scanf("%d",&a[i]);flag=1;

for(i=1;i<=n-1;i=i+1)

for(j=i+1;j<=n;j=j+1)

if(a[i]==a[j]){flag=0;break;}

if(flag==1)printf("Norepeat\n");

else

printf("Repeat\n");}51第五十一页，共七十页，编辑于2023年，星期三例10冒泡排序

排序过程1、比较第一个记录与第二个记录，若关键字为逆序则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第

n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。2、对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。3、重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。初始关键字4938659776132749

第一趟排序4938499776979713979727979749

97

38496576132749

97384965132749

76第二趟排序3849132749

65第三趟排序3813274949

第四趟排序13273849第五趟排序132738第六趟排序

for(j=1;j<n

;j++)if(r[j+1]<r[j])r[j]r[j+1];

for(j=1;j<n-1;j++)if(r[j+1]<r[j])r[j]r[j+1];for(i=n;i>1;i--)i

;{

}while(i>1){

}//whilei=n;i=k;VoidBubbleSort(SqList&L){}

冒泡排序算法

初始关键字4938659776132749

k=j;//交换的位置k=1;52第五十二页，共七十页，编辑于2023年，星期三冒泡算法改进如果原有数据有序，冒泡算法仍要做n-1趟比较。事实上一趟比较下来，如果发现没有交换，就说明数据已经有序，无须后续操作了数据原本有序概率不高，但经过少于n-1次比较后，有序概率就非常高了改进：设置标志位，检测数据是否有序

flag=0表示没有进行交换，一旦有交换则置flag=1.当一趟比较交换完成后，若flag仍为0，则无须进行下一趟操作。算法略53第五十三页，共七十页，编辑于2023年，星期三c信息数字化-例11警察抓小偷一些表面上看是非数值的问题，但经过进行数字化后，就可方便进行算法设计。例1.5警察抓小偷 警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中

a说：“我不是小偷。”

b说：“c是小偷。”

c说：“小偷肯定是d。”

d说：“c在冤枉人。”

现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？54第五十四页，共七十页，编辑于2023年，星期三c信息数字化-例11-问题分析问题分析：可通过循环，每次假设一名嫌疑犯为小偷，代入问题系统，检验是否只有一句假话。这种让所有可能解都进行检验，以求得真解的方法称为“枚举尝试法”，也是“蛮力法”、“暴力法”。为方便设计程序，将a,b,c,d将四个人进行编号，号码分别为1，2，3，4。55第五十五页，共七十页，编辑于2023年，星期三c信息数字化-例11-算法设计算法设计：用变量x存放小偷的编号，则x的取值范围从1取到4，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：a说的话：x<>1b说的话：x=3c说的话：x=4d说的话：x<>4或not(x=4)注意:在x的枚举过程中，当这四个逻辑式的值相加等于3时，即表示“四个人中三人说的是真话，一人说的是假话”。if((x!=1)+(x==3)+(x==4)+(x!=4)==3)56第五十六页，共七十页，编辑于2023年，星期三c信息数字化-例11-实现#include"stdafx.h"voidmain(){

intx;

for(x=1;x<=4;x=x+1)

if((x!=1)+(x==3)+(x==4)+(x!=4)==3) printf("%cisathief",char(64+x));}57第五十七页，共七十页，编辑于2023年，星期三3.4优化算法的数学模型

数学建模方法主要是归纳法。归纳法是从简单到复杂，由个别到一般的一种研究方法，也就是“找规律”。

学会找规律-例12数组移位例12数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后移k位，后面的元素则循环向前移k位，例：0、1、2、3、4循环移3位后为：2、3、4、0、1。考虑到n会很大，不允许用2*n以上个空间来完成此题。58第五十八页，共七十页，编辑于2023年，星期三d学会找规律-例12-问题分析(思路1)问题分析1：若题目中没有关于存储空间的限制，我们可以方便地开辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。开始部分的元素从前向后移，容易确定；但数组中后k个元素是从后向前移，如何确定？59第五十九页，共七十页，编辑于2023年，星期三d学会找规律-例12-问题分析(思路1)voidalg1(){

inta[100],b[100],i,n,k;scanf("%d,%d",&n,&k);

for(i=0;i<n;i=i+1)scanf("%d",&a[i]);

for(i=0;i<n;i=i+1)b[(k+i)%n]=a[i];

for(i=0;i<n;i=i+1)printf("%d,",b[i]);printf("\n");}60第六十页，共七十页，编辑于2023年，星期三d学会找规律-例12-问题分析(思路2)问题分析2：将最后一个存储空间的数据,存储在临时存储空间中；其余数据逐个向后移动一位。这样操作共k次就能完成问题的要求。61第六十一页，共七十页，编辑于2023年，星期三d学会找规律-例12-算法设计/实现(思路2)有可能k>n，这样移动会出现重复操作,可以在输入数据后，执行k=kmodn;以保证不出现重复移动的问题。这个算法的移动（赋值）次数为k*n。当n较大时不是一个好的算法。voidalg2(){

inta[100],i,j,n,k,temp;scanf("%d,%d",&n,&k);

for(i=0;i<n;i=i+1)scanf("%d",&a[i]);

for(i=0;i<k;i=i+1){temp=a[n-1];

for(j=n-1;j>0;j=j-1)a[j]=a[j-1];a[0]=temp;}

for(i=0;i<n;i=i+1)printf("%d,",a[i]);printf("\n");}62第六十二页，共七十页，编辑于2023年，星期三d学会找规律-例12-问题分析(思路3)问题分析3：利用一个临时存储空间，把每一个数据一次移动到位。1）一组循环移动的情况：通过计算我们可以确定某个元素移动后的具体位置，如n=5,k=3时：0、1、2、3、4循环移3位后为2、3、4、0、1。 可通过计算得出0移到3的位置，3移到1的位置，1移到4的位置，4移到2的位置，2移到0的位置；一组移动（