[TOC]
栈(Stack)类,用于模拟一种具有后进先出(LIFO)特性的数据结构
1 | #!/usr/bin/python3 |
栈和队列数据结构
- 栈
- 先进后出
- 队列
- 先进先出
你还能复述出“迭代”的概念吗?
所谓迭代,是重复反馈过程的活动,其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”,而每一次迭代得到的结果会被用来作为下一次迭代的初始值。
为什么这么说呢?不要忘了,递归的实现可以是函数自个儿调用自个儿,每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈操作,所以在这上边是非常消耗时间和空间的。
另外,如果递归一旦忘记了返回,或者错误的设置了返回条件,那么执行这样的递归代码就会变成一个无底洞:只进不出!所以在写递归代码的时候,千万要记住口诀:递归递归,归去来兮!出来混,总有一天是要还的!
递归必须满足哪两个基本条件?
答:
一、函数调用自身
二、设置了正确的返回条件
- 请聊一聊递归的优缺点(无需官方陈词,想到什么写什么就可以)
答:
优点:
1)递归的基本思想是把规模大的问题转变成规模小的问题组合,从而简化问题的解决难度(例如汉诺塔游戏)。
2)有些问题使用递归使得代码简洁易懂(例如你可以很容易的写出前中后序的二叉树遍历的递归算法,但如果要写出相应的非递归算法就不是初学者可以做到的了。)
缺点:
1)由于递归的原理是函数调用自个儿,所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”(当然法拉利也奢侈,但还是很多人趋之若鹜)。
2)初学者很容易错误的设置了返回条件,导致递归代码无休止调用,最终栈溢出,程序崩溃。
1.计算闰年与平年
定义闰年的原理:能被4整除但不能被100整除,或者能被400整除都是闰年。1
2
3
4
5
6
7
8
9
10
11
12
13
14//############# python ###############
#!/usr/bin/python
year = input("请输入一个年份:")
while not year.isdigit():
year = input("输入错误请重新输入年份:")
year = int(year)
if (year % 400 == 0):
print(year," 年是闰年!") # 注意不同类型 的不能进行 + 拼接
else:
if (year % 4 == 0) and (year % 100 != 0):
print(year," 年是闰年!")
else:
print(year," 年是平年!")
2.水仙花数
如果一个 3 位数等于其各位数字的立方和,则称这个数为水仙花数。例如:153 = 1^3 + 5^3 + 3^3,因此 153 就是一个水仙花数;1
2
3
4
5
6
7
8
9
10
11
############# python ###############
#!/usr/bin/python
for i in range(100, 1000):
sum = 0
temp = i
while temp:
sum = sum + (temp%10) ** 3
temp //= 10 # 注意这里要使用地板除哦~ (即 从最低取开始取值)
if sum == i:
print(i)
欧几里德算法
1 | #!/usr/bin/python |
编码
- 编写一个将十进制转换为二进制的函数,要求采用“除2取余”(脑补链接)的方式,结果与调用bin()一样返回字符串形式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def Dec2Bin(dec):
temp = []
result = ''
while dec: #如当desc 10
quo = dec % 2
dec = dec // 2
temp.append(quo) # [0,0,0,1]
while temp:
result += str(temp.pop()) #pop是弹栈 1000 (默认是弹出列表得最后一个元素)
return result
print(Dec2Bin(62))
4.约瑟夫环
描述: 将多个人排出一个圆圈并且为每一个人的所站进行编号,当那个人的编号是3的倍数的时候将被剔除,直至剩下最后一人;
1 | package com.weiyigeek.Collection; |