计算思维导论（第2版）课件：算法基础.pptx

算法基础;对算法的认识;问题求解;4.1算法和算法描述;算法：解决问题的方法和步骤

数据结构：数据的存储组织方式;#includestdio.h

intmain()

{

return0;

};;有穷性;常量和变量;;;交换两个数;两碗饭，如何交换？;任务：交换两个整数

算法描述：

step1：读入两个非负整数a，b的值

step2：将a的值赋值给t

step3：将b的值赋值给a

step4：将t的值赋值给b

step5：输出a，b的值;图形符号;任务：交换两个整数

算法：

step1：读入两个非负整数a，b的值

step2：将a的值赋值给t

step3：将b的值赋值给a

step4：将t的值赋值给b

step5：输出a，b的值;顺序结构：传统流程图;选择结构：传统流程图;循环结构：传统流程图;运算符号说明;任务：交换两个整数

算法：

step1：读入两个非负整数a，b的值

step2：将a的值赋值给t

step3：将b的值赋值给a

step4：将t的值赋值给b

step5：输出a，b的值;;数组就是一组有序数据的集合;;1、下面伪代码输出的结果是：

a[5]={1,2,3,4,5}

outputa[1]

outputa[2]

outputa[3+1]

outputa[5];;a[5]=0,s=0,num=0

fori=1to5//累加求和求均值

inputa[i]

s=s+a[i]

endfor

avg=s/5;;a[10]=0,s=0

fori=1to10//输入且累加求和

inputa[i]

s=s+a[i]

endfor;数组作用

一次输入，多次使用;;函数就是模块化设计;类型

系统预定义（三角函数，……）

用户自定义;1、下面伪代码输出的结果是：

主调函数：

a=2

b=cube(a)

outputb

被调函数：

functioncube(x)

returnx^3

endfunction;;;主调函数：

inputm

flag=odd_even(m)

ifflag=0then

outputeven

else

outputodd

endif;;主调函数：

inputr

s=____________

outputs

被调函数：

functionarea(r)

return

endfunction;函数

函数名

函数参数

函数返回值;;算法的特征

有穷性、确定性

可行性、输入和输出;4.2经典算法;;;细数一下你身边的枚举法;找出100以内的素数;;任务1：百钱买百鸡

鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？;设要买x只公鸡，y只母鸡，z只小鸡，列方程：;x=;;任务2：猜字问题

雨水淋???了算术书的一道题，8个数字只能看清3个，第一个数字虽然看不清，但可看出不是1。求其余数字是什么？[□*(□3+□)]2=8□□9;任务2：猜字问题

雨水淋湿了算术书的一道题，8个数字只能看清3个，第一个数字虽然看不清，但可看出不是1。求其余数字是什么？[□*(□3+□)]2=8□□9;;;;如何求等差数列、等比数列的通项、以及数列和？

1）1,3,5,7,9,11,…,？

2)1,3,9,27,81,…,？;切0刀——1块

切1刀——2块

切2刀——4块

切3刀——7块

切4刀——11块

?;你还能找到通项吗？;;从问题的规模（项数）出发，找到大规模问题与小规模问题之间的关系（或前后项之间的关联），然后根据他们之间的联系逐步求解。这种在规定的初始条件下，找出后项对前项的依赖关系的操作，称为递推。;递推法设计;任务：兔子繁殖问题

这是一个古典数学问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第3个月后每个月又生一对兔子。假设所有的兔子不死，问第20月兔子总数为多少？;任务：兔子繁殖问题

算法分析;任务：兔子繁殖问题

算法分析

这就是著名的斐波那契数列。

1,1,2,3,5,8,13,…;a[20]=0,

a[1]=1,a[2]=1

inputn

fori=3ton

a[i]=a[i-1]+a[i-2]

endfor

outputa[n];任务：猴子