加载中…近几天学习的算法：冒泡排序、选择排序、二分法（查找以及解方程）以及汉诺塔
(2022-04-18 07:03:55) | 分类： 研究-学习 |
对于最简单的排序算法，虽然大概知晓其基本原理，但畏难心理使得自己一直没能清晰明白搞懂具体的算法，以及冒泡和选择排序的区别。这两天我硬着头皮去逐句理解程序代码，并且用实际数据模拟推演了一遍，基本搞清楚了其算法流程。
n=len(a)
for i in
range(n-1,0,-1):
for j in range(i+1,n):
mid=(flag1+flag2)//2
step+=1
if a>mid:
flag1=mid+1
elif a
flag2=mid-1
else:
break
a.append(random.randint(1,100))
am=(a1+a2)//2
step=step+1
print("第",step,"次查找的数",a[am])
if a[am]>x:
a2=am-1
elif a[am]
a1=am+1
else:
break
return
x**3-x**2+x-1 #def 要有返回值
return
xm=(b+a)/2
if
f(a)*f(xm)<0:
b=xm
if
f(b)*f(xm)<0:
a=xm
if f(xm)==0:
break
if n==1:
print(s,'-->',t)
else:
hanota(n-1,s,t,m)
print(s,'-->',t)
hanota(n-1,m,s,t)
冒泡法：首先外层循环i是比较次数，从高到底，一开始两两比较的次数多，越往后越少。内循环j就是从外循环i值之后的一个数开始，一直到结束n
def maopao(a):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
alist=[1,4,3,5,7,6,8,2,9,0]
maopao(alist)
print(alist)
排序法：每次假设未排序的数列中第一个数为最小值，然后将后面的数值依次和最小值比较，如果有数值比最小值小，就交换，将后面的这个小的数值和最小值交换。
def paixu(a):
n=len(a)
for i in range(n-1):
amin=i
for j in range(i+1,n):
if a[j]
amin=j ### 此处不能弄反
if i!=amin:
a[amin],a[i]=a[i],a[amin]
alist=[1,4,3,5,7,6,8,2,9,0]
paixu(alist)
print(alist)
二分法：
【猜数字次数，教材内容】
a=int(input("请输入一个数："))
step=0
flag1=1
flag2=1000
while flag1<=flag2:
print("你找的数是",a,"找的次数：",step)
【猜列表中数字次数，此时用索引值进行判断，而非数值本身】
import random
a=[]
for i in range(20):
a.sort()#列表.sort()-- 改变原列表；sorted(列表)--不改变原列表
#a=sorted(a)
print(a)
x=int(input("你要查找的数："))
a1=0
a2=19
step=0
while a[a1]<=a[a2]:
print( x,'查找的次数：',step)
【二分法求解一元三次方程】
#尝试用二分法求 x3 - x2 + x - 1 = 0 在[-5,5]区间的解。
#各个系数同时取值可以：a,b,c,d = map(float,input().split())
def f(x):
a=-5
b=5
c=1e-6
while abs(a-b)>=c:
#满足条件才能运行，是a-b>c时才执行循环
print('x的值为',xm)
汉诺塔递归程序：
教材中使用汉诺塔案例来介绍递归的知识，因为有和斐波那契数列的对比，个人感觉学生通过学习斐波那契数列的知识来理解递归更容易入门。前两天和王老师聊天时，我也提及到好像只有进入到迭代、递归等知识的学习才有了那么一点计算思维的感觉。王老师的看法是，汉诺塔是学习递归算法的经典案例，因为采用其他算法进行汉诺塔都很难实现。教材编著者也是出于让学生体验计算思维的考虑，才把汉诺塔的例子引入。而教学现实是学生很难接受这样的知识。因为课堂教学时间有限，所以学生难以在应用中迁移，硬性理解又没有这样的氛围和动力，所以觉得这个内容枯燥无味，索性直接放弃学习了。而如果在课堂中一味的依据教材、依据考试内容指引，那课堂就会是死气沉沉甚至是压抑的了。而如何调动学生学习的积极性，带着学习热情去学会、会应用，这就是老师可以发挥的空间了。（虽然很难，也算是“带着镣铐跳舞”吧。）
def hanota(n,s,m,t):
n=int(input("n="))
hanota(n,'a','b','c')
汉诺塔递归法的学习，个人认为在教学过程中要注意两个点：
第一是要按照算法设计的思路，“接纳”这个算法思维【把n个盘子分成两部分，一部分是n-1，把它当作一个整体来思考，另外一个是最底下的一个盘子】；
第二是可以通过绘图的形式，模拟一下n个盘子（n-1和1）转移的过程。过程直观形象了，自然也更容易理解接受。
最后还要注意的是变量s、m、t皆为字符类型，所以在调用时要明确.
hnt(n,'A','B','C')
喜欢
0
赠金笔