栈(Stack)类,用于模拟一种具有后进先出(LIFO)特性的数据结构

#!/usr/bin/python3
#功能:模拟Stack(栈)- 后进先出(LIFO)

class Stack:
def __init__(self,start = []):
self.stack = []
for i in start:
self.push(i) #压栈
#判断当前栈是否为空(返回 True 或 False)
def isEmpty(self):
return not self.stack

#往栈的顶部压入一个数据项
def push(self,obj):
self.stack.append(obj)

#从栈顶弹出一个数据项(并在栈中删除)
def pop(self):
if not self.stack:
print('警告, Stack 已空!')
else:
self.stack.pop() #弹栈

#显示当前栈顶的一个数据项
def top(self):
if not self.stack:
print('警告, Stack 已空!')
else:
return self.stack[-1] #显示栈顶

#显示当前栈底的一个数据项
def bottom(self):
if not self.stack:
print('警告, Stack 已空!')
else:
return self.stack[0]

demo = Stack([1,2,3,4,5])
print(demo.top(),demo.bottom()) #显示栈顶/栈底

栈和队列数据结构

    • 先进后出
  • 队列
    • 先进先出

你还能复述出“迭代”的概念吗?

所谓迭代,是重复反馈过程的活动,其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”,而每一次迭代得到的结果会被用来作为下一次迭代的初始值。

为什么这么说呢?不要忘了,递归的实现可以是函数自个儿调用自个儿,每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈操作,所以在这上边是非常消耗时间和空间的。

另外,如果递归一旦忘记了返回,或者错误的设置了返回条件,那么执行这样的递归代码就会变成一个无底洞:只进不出!所以在写递归代码的时候,千万要记住口诀:递归递归,归去来兮!出来混,总有一天是要还的!
递归必须满足哪两个基本条件?
答:
一、函数调用自身
二、设置了正确的返回条件

  1. 请聊一聊递归的优缺点(无需官方陈词,想到什么写什么就可以)

答:

优点:

1)递归的基本思想是把规模大的问题转变成规模小的问题组合,从而简化问题的解决难度(例如汉诺塔游戏)。

2)有些问题使用递归使得代码简洁易懂(例如你可以很容易的写出前中后序的二叉树遍历的递归算法,但如果要写出相应的非递归算法就不是初学者可以做到的了。)

缺点:

1)由于递归的原理是函数调用自个儿,所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”(当然法拉利也奢侈,但还是很多人趋之若鹜)。

2)初学者很容易错误的设置了返回条件,导致递归代码无休止调用,最终栈溢出,程序崩溃。

1.计算闰年与平年

定义闰年的原理:能被4整除但不能被100整除,或者能被400整除都是闰年。

//############# 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 就是一个水仙花数;


############# 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)

欧几里德算法

#!/usr/bin/python
#辗转相除法(欧几里德算法|计算大数效率高)

#方式1:
def gcd(x,y):
while 1:
temp = x % y
if temp == 0:
return y
x, y = y, temp
temp = input("输入除数与被除数利用,分割如( 319,377 ):")
temp = temp.split(',')
x = int(temp[0])
y = int(temp[1])
print("%d 与 %d 的最大公约数:" %(x,y),gcd(x,y))

#方式2:递归求出最大公约数(比较耗费资源)
def gcd(x,y):
if y:
return gcd(y, x % y) #精辟呀
else:
return x

##############计算结果###############
# 输入除数与被除数利用,分割如( 112,145 ):112,106
# 112 与 106 的最大公约数: 2

编码

  1. 编写一个将十进制转换为二进制的函数,要求采用“除2取余”(脑补链接)的方式,结果与调用bin()一样返回字符串形式。
    def 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的倍数的时候将被剔除,直至剩下最后一人;

package com.weiyigeek.Collection;
import java.util.ArrayList;
public class Demo9_ArrayList {
4public static void main(String[] args) {
44// 1.约瑟夫环
44System.out.println("幸运人的编号 : " + getLuckly(8));
4}
4/**
* getLuckly : 实现约瑟夫环算法
* @param i : 人数
* @return Integer
*/
4private static Integer getLuckly(int i) {
44ArrayList<Integer> list = new ArrayList<Integer>(); //创建存储1到num的对象
44for(int num = 1; num <= i; num ++){ //注意位置号从1开始到i结束
444list.add(num); //将每一个人进行标位置号
44}
44
44int count = 1; // 计算器如果是3的倍数的人将被剔除
44for(int num = 0; list.size() != 1; num++)
44{
444if(num == list.size()){
4444num = 0; //如果当索引值等于列表总的个数的时候,重置为0进行下一轮比较剔除
444}
444
444if(count % 3 == 0) {
4444list.remove(num--); //非常注意这里因为ArrayList删除列表元素后,后面的元素会向前补齐(索引这里需要要索引移动回到删除的位置)
444}
444count++;
44}
44return list.get(0); //最后只剩下1人打印其的位置号
4}
}

//幸运人的编号 : 7