欢迎大家来到IT世界,在知识的湖畔探索吧!

本文转载自吾爱激活成功教程[1]

题目 1：水仙花数

水仙花数（Narcissistic number）也被称为超完全数字不变数（pluperfect digital invariant, PPDI）、自恋数、自幂数、阿姆斯壮数或阿姆斯特朗数（Armstrong number）

水仙花数是指一个 3 位数，它的每个位上的数字的 3 次幂之和等于它本身。例如：1^3 + 5^3+ 3^3 = 153。

for i in range(100, 1000):
    i1 = i // 100       # 取百位数字 123//100=1
    i2 = i // 10 % 10   # 取十位数字 123//10=12  12%10=2
    i3 = i % 10         # 取个位数字 123%10=3

    if i1 ** 3 + i2 ** 3 + i3 ** 3 == i:
        print(f"{i}是水仙花数")
        # 153 是水仙花数
        # 370 是水仙花数
        # 371 是水仙花数
        # 407 是水仙花数

欢迎大家来到IT世界,在知识的湖畔探索吧!

题目 2：四叶玫瑰数

四叶玫瑰数是 4 位数的自幂数。自幂数是指一个 n 位数，它的每个位上的数字的 n 次幂之和等于它本身。

（例如：当 n 为 3 时，有 1^3 + 5^3 + 3^3 = 153，153 即是 n 为 3 时的一个自幂数，3 位数的自幂数被称为水仙花数）。

欢迎大家来到IT世界,在知识的湖畔探索吧!for i in range(1000,10000):
    i1 = i // 1000      # 取千位数字 1234//1000=1
    i2 = i // 100 % 10  # 取百位数字 1234//100=12  12%10=2
    i3 = i // 10 % 10   # 取十位数字 1234//10=123  123%10=3
    i4 = i % 10         # 取个位数字 1234%10=4
    # print(i,i1,i2,i3,i4)

    if i1 ** 4 + i2 ** 4 + i3 ** 4 + i4 ** 4 == i:
        print(f'{i}是四叶玫瑰数')
        # 1634 是四叶玫瑰数
        # 8208 是四叶玫瑰数
        # 9474 是四叶玫瑰数

题目 3：逆序输出字符串

• 写法 1：切片方式

str = input("请输入字符串")
print(str[::-1])

• 写法 2：循环转换

欢迎大家来到IT世界,在知识的湖畔探索吧!str = input("请输入字符串")
list = []
for x in range(len(str) -1,-1,-1):
    list.append(str[x])
print(''.join(list))

题目 4：猜数字小游戏

需求分析：

随机生成一个 100 以内的整数，共有 10 次机会开始游戏，输入猜测的数字。

• 如果猜小了，则提示：猜小了
• 如果猜大了，则提示：猜大了
• 猜对了，则提示：猜对了，并且结束游戏
• 10 次机会用完还没猜对，提示：游戏结束，没有猜到。

import random as rd

number = rd.randint(0,100)
for i in range(10):
    choice = int(input("请输入你要猜测的数字："))
    if choice > number:
        print("你猜大了")
    elif choice < number:
        print("你猜小了")
    else:
        print("你猜对了，真棒！")
        print(f'你一共用了{i + 1}次机会')
        break
    print(f'还剩{9 - i}次机会')
else:
    print('游戏结束，你没有猜到')

题目 5：百鸡百钱

需求分析：

公鸡每只 5 元，母鸡每只 3 元，小鸡 3 只一元，现要求用 100 元钱买 100 只鸡(三种类型的鸡都要买)，问公鸡、母鸡、小鸡各买几只?

数学方程：

• 设公鸡买了 x 只，母鸡买了 y 只，小鸡买了 z 只
• x+y+z= 100
• 5x+3y+z/3 = 100

算法思路

• 以公鸡为突破点，公鸡 5 元一只，100 元最多只能买 20 只，
• 由于三种鸡都要买，所以公鸡数一定是小于 20 的。
• 母鸡每只 3 元，100 全拿来买母鸡，最多也不能超过 33 只
• 设公鸡数为 x，母鸡数为 y，小鸡 z 只
• 只要满足 5x+3y+z/3=100 和 x+y+z==100 就可以输出此种组合的结果.

count = 0
for x in range(1,20):
    for y in range(1,33):
        z = 100 - x -y
        if z > 0 and 5 * x + 3 * y + z / 3 == 100:
            count += 1
            print("="*60)
            print(f'第{count}种买法，公鸡买了{x}只，母鸡买了{y}只，小鸡买了{z}只')
            # == == == == == == == == == == == == == == == == == == == == == == == == == == == == == ==
            # 第1种买法，公鸡买了4只，母鸡买了18只，小鸡买了78只
            # == == == == == == == == == == == == == == == == == == == == == == == == == == == == == ==
            # 第2种买法，公鸡买了8只，母鸡买了11只，小鸡买了81只
            # == == == == == == == == == == == == == == == == == == == == == == == == == == == == == ==
            # 第3种买法，公鸡买了12只，母鸡买了4只，小鸡买了84只

题目 6：闰年问题升级版

输入年月日，输出该日期是否是闰年，并且输出该日期是此年份的第几天

闰年判断条件：

• 能被 4 整除，并且不能被 100 整除
• 能被 400 整除
• 两个条件满足任意一个就为闰年

算法思路：

• 接收用户输入的年月日，创建保存 12 个月份天数的列表
• 根据年份判断是否是闰年，如果是把二月份设为 29 天，否则把二月份设为 28 天
• 根据月份和日期统计是当年的第几天

year = int(input("请输入年份"))
month = int(input("请输入月份"))
day = int(input("请输入日期"))

date_list = [31,29,31,30,31,30,31,31,30,31,30,31]
count_day = day
if year % 4 == 0 and year % 100 !=0 or year % 400 == 0:
    print(f'{year}年是闰年')
    date_list[1]=29
else:
    print(f'{year}年是平年')
    date_list[1]=28

for i in range(month-1):
    count_day += date_list[i]

print(f'{year}年{month}月{day}日是当年的第{count_day}天')

题目 7：猴子吃桃问题

需求分析：

• 猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。
• 第二天早上又将剩下的桃子吃掉一半，又多吃了一个。
• 以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，见只剩下一个桃子了。
• 求原来它一共摘了多少个桃子。

这题可以用递归思想倒着推。

• 第 10 天还没吃，就剩 1 个，说明第 9 天吃完一半再吃 1 个还剩 1 个。
• 假设第 9 天还没吃之前有桃子 p 个
• 可得：p/2 – 1 = 1，得出第九天的桃子数 p=4。
• 以此类推，即可算出第一天摘了多少桃子.

算法思路：

• 第 10 天还没吃之前的桃子数量初始化 p=1
• 从 9 至 1 循环 9 次，根据上述公式反推为 p=(p+1)*2 可得第 1 天还没吃之前的桃子数量

p = 1
print(f'第10天还剩下{p}个桃子')
for i in range(9,0,-1):
    p = (p + 1) * 2
    print(f'第{i}天还剩下{p}个桃子')
print(f'第一天一共摘了{p}个桃子')

# 第10天还剩下1个桃子
# 第9天还剩下4个桃子
# 第8天还剩下10个桃子
# 第7天还剩下22个桃子
# 第6天还剩下46个桃子
# 第5天还剩下94个桃子
# 第4天还剩下190个桃子
# 第3天还剩下382个桃子
# 第2天还剩下766个桃子
# 第1天还剩下1534个桃子
# 第一天一共摘了1534个桃子

题目 8：冒泡排序

冒泡排序算法由来： 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列)，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”

从前到后(即从下标较小的元素开始) 依次比较相邻元素的值，若发现比后一个值大则交换位置，使值较大的元素逐渐从前移向后部。

假设有一个列表 [29 ,12 ,19 ,37 ,14] 想按升序排列

第一轮：初始列表为 [29 ,12 ,19 ,37 ,14]

• 比较 29 > 12 交换位置：[12,29,19,37,14]
• 比较 29 > 19 交换位置：[12,19,29,37,14]
• 比较 29 > 37 不大于，不交换：列表同上不变
• 比较 37 > 14 交换位置：[12,19,29,14,37]

第二轮：列表继承上一轮为 [12,19,29,14,37]

• 比较 12 > 19 不大于，不交换：列表同上不变
• 比较 19 > 29 不大于，不交换：列表同上不变
• 比较 29 > 14 交换位置：[12,19,14,29,37]

第三轮：列表继承上一轮为 [12,19,14,29,37]

• 比较 12 > 19 不大于，不交换：列表同上不变
• 比较 19 > 14 交换位置：[12,14,19,29,37]

第四轮：列表继承上一轮为 [12,14,19,29,37]

• 比较 12 > 14 不大于，不交换：列表同上不变
• 列表排序完成：[12,14,19,29,37]

import numpy as np

pop_list = np.random.randint(100,size=6)

# pop_list = [82,15,15,41,37,31]
# pop_list = [29,12,19,37,14]

count = len(pop_list)
print('没排序之前的列表',pop_list)

for i in range(count-1):
    for j in range(count-i-1):
        if pop_list[j] > pop_list[j + 1]: # 如果要降序就是改成 < 号
            pop_list[j],pop_list[j+1] = pop_list[j+1],pop_list[j]
print('排好序的列表为',pop_list)
# 排好序的列表为 [15, 15, 31, 37, 41, 82]
# 排好序的列表为 [12, 14, 19, 29, 37]

题目 9：二分查找法

二分法是一种效率比较高的搜索方法

回忆之前做过的猜数字的小游戏，预先给定一个小于 100 的正整数 x，让你猜，猜测过程中给予大小判断的提示，问你怎样快速地猜出来？ 我们之前做的游戏给定的是 10 次机会，如果我们学会二分查找法以后，不管数字是多少，最多只需要 7 次就能猜到数字

• 二分查找法

首先先猜 50，如果猜对了，结束；如果猜大了，往小的方向猜，再猜 25；如果猜小了，往大的方向猜，再猜 75；…每猜测 1 次就去掉一半的数，这样我们就可以逐步逼近预先给定的数字.这种思想就是二分法。

二分法适用情况

• 必须是有序的序列。
• 对数据量大小有要求。
• 数据量太小不适合二分查找，与直接遍历相比效率提升不明显。
• 数据量太大也不适合用二分查找，因为数组需要连续的存储空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间

算法思路：

假设有一个有序列表：[5,7,11,22,27,33,39,52,58]

请问数字 11 是否在此列表中，如果在它的索引值为多少？

• 首先我们取有序列表的中间位置 27 和 11 进行比较 我们发现 11 是小于 27 的
• 所以我们排除 27 右边的数字，保留列表为：[5,7,11,22]
• 接着我们取 [5,7,11,22] 位置中间的 7 和 11 比较 发现 11 是大于 7 的 所以我们排除 7 左边的数字，保留列表为：[11,22]
• 最后我们取 11 和 22 的中间位置
• 刚好到了 11 这时候就可以返回 11 的索引值了，如果没有找到就提示不存在

第1种 纯算法的方式

arr_list = [5,7,11,22,27,33,39,52,58]
number = 11
count = 0
left = 0
right = len(arr_list)-1
while left<=right:
    middle = (left+right)//2
    count += 1
    if number > arr_list[middle]:
        left = middle +1
    elif number < arr_list[middle]:
        right = middle - 1
    else:
        print(f'数字{number}已找到，索引值为{middle}')
        break
else:
    print(f'数字{number}没有找到')
print(f'一共用了{count}次查找')

# 数字11已找到，索引值为2， 一共用了3次查找

第2种 递归函数的方式

arr_list = [5,7,11,22,27,33,39,52,58]

def binary_search(number,left,right):
    if left <= right:
        middle = (left + right) // 2
        if number < arr_list[middle]:
            right = middle - 1
        elif number > arr_list[middle]:
            left = middle + 1
        else:
            return middle
        return binary_search(number,left,right)
    else:
        return -1

print(binary_search(11,0,len(arr_list)-1))

题目 10：选择排序

基本思想：从未排序的序列中找到一个最小的元素，放到第一位，再从剩余未排序的序列中找到最小的元素，放到第二位，依此类推，直到所有元素都排序完毕

• 若列表为 [6, 8, 3, 5, 9, 10, 7, 2, 4, 1],先找到 1 最小 调换到第 1 个位置
• 得到列表[1, 8, 3, 5, 9, 10, 7, 2, 4, 6]，接着是 2 最小 调换到第 2 个位置
• 得到列表[1, 2, 3, 5, 9, 10, 7, 8, 4, 6]，接着是 3 最小 位置不变
• 得到列表[1, 2, 3, 5, 9, 10, 7, 8, 4, 6]，接着是 4 最小 调换到第 4 个位置
• 得到列表[1, 2, 3, 4, 9, 10, 7, 8, 5, 6]，接着是 5 最小 调换到第 5 个位置
• 得到列表[1, 2, 3, 4, 5, 10, 7, 8, 9, 6]，接着是 6 最小 调换到第 6 个位置
• 得到列表[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，接着是 7 最小 位置不变
• 得到列表[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，接着是 8 最小 位置不变
• 得到列表[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，接着是 9 最小 位置不变
• 得到列表[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，接着是 10 最小 位置不变，排序完成

import random as rd

sec_list = [rd.randint(1,100) for i in range(8)]
# sec_list = [91,30,93,98,26,98,20,90]
length = len(sec_list)
print(f'未排序的列表为：{sec_list}')

for i in range(length -1):
    min_index = i
    for j in range(i + 1,length):
        if sec_list[min_index] > sec_list[j]:
            min_index = j
    sec_list[min_index],sec_list[i] = sec_list[i],sec_list[min_index]
    print(f'第{i+1}轮排好序是：{sec_list}')
print(f'最终排好序的列表为：{sec_list}')

# 未排序的列表为：[91, 30, 93, 98, 26, 98, 20, 90]
# 第1轮排好序是：[20, 30, 93, 98, 26, 98, 91, 90]
# 第2轮排好序是：[20, 26, 93, 98, 30, 98, 91, 90]
# 第3轮排好序是：[20, 26, 30, 98, 93, 98, 91, 90]
# 第4轮排好序是：[20, 26, 30, 90, 93, 98, 91, 98]
# 第5轮排好序是：[20, 26, 30, 90, 91, 98, 93, 98]
# 第6轮排好序是：[20, 26, 30, 90, 91, 93, 98, 98]
# 第7轮排好序是：[20, 26, 30, 90, 91, 93, 98, 98]
# 最终排好序的列表为：[20, 26, 30, 90, 91, 93, 98, 98]

题目 11：剪刀石头布

• 游戏开始，初始状态下用户和电脑都有 100 分，赢一局+10 分，输一局-10 分。
• 当用户为 0 分时，游戏结束，提示游戏结束，比赛输了
• 当用户为 200 分时，游戏结束，提示游戏结束，赢得比赛、每轮比赛都输出当前的分数
• 1 代表剪刀 2 代表石头 3 代表布

import random as rd

print('=' * 60)
print(' ' * 20, '剪刀石头布游戏')
print('1代表剪刀 2代表石头 3代表布')

game_info = {1: "剪刀", 2: "石头", 3: "布"}
score = 100

while True:
    robots_choice = rd.randint(1, 3)
    user_choice = input("请出拳")
    if user_choice not in '123':
        print('出拳错误，请重新出拳')
        continue
    user_choice = int(user_choice)
    print('*' * 60)
    print(f'电脑出{game_info[robots_choice]}')
    print(f'你出{game_info[user_choice]}')
    print('*' * 60)
    if user_choice == 1 and robots_choice == 3 or user_choice == 2 \
            and robots_choice == 1 or user_choice == 3 and robots_choice == 2:
        score += 10
        print(f'你赢得本轮游戏，当前分数为{score}')
    elif user_choice == robots_choice:
        print(f'本轮游戏平局，当前分数为{score}')
    else:
        score -= 10
        print(f'你输了本轮游戏，当前分数{score}')
    if score >= 200:
        print('游戏结束，你赢得比赛')
        break
    elif score <= 0:
        print('游戏结束，你输了')
        break

题目 12：快乐数

在给定的数字下，该数字所有数位(digits)的平方和，得到的新数再次求所有数位的平方和，如此重复进行，最终结果必定为 1

比如数字：19

• 第 1 轮： (11)+(99) =1 + 81 = 82
• 第 2 轮： (88)+(22) =64 + 4 = 68
• 第 3 轮： (66)+ (88) =36 + 64 = 100
• 第 4 轮： (11) + (00) + (0*0) = 1

def sum_square(n):
    sum = 0
    for i in str(n):
        sum += int(i) ** 2
    return sum

list1 = []
n = int(input('请输入数字：'))
while sum_square(n) not in list1:
    n = sum_square(n)
    list1.append(n)

if n == 1:
    print('是快乐数')
else:
    print('不是快乐数')

题目 13：猜年龄（一）

小明带两个妹妹参加元宵灯会。别人问她们多大了，她们调皮地说：“我们俩的年龄之积是年龄之和的 6 倍“。 小明又补充说：“她们可不是双胞胎，年龄差肯定也不超过 8 岁啊。“ 请你写出：小明的较小的妹妹的年龄。

for i in range(1,100):
    for j in range(1,i):
        if i*j == 6*(i+j) and i-j<8:
            print(i,j)

# 15 10

题目 14：猜年龄(二)

美国数学家维纳(N.Wiener)智力早熟，11 岁就上了大学。 他曾在 1935~1936 年应邀来中国清华大学讲学。

一次，他参加某个重要会议，年轻的脸孔引人注目。

于是有人询问他的年龄，他回答说：

“我年龄的立方是个 4 位数。我年龄的 4 次方是个 6 位数。这 10 个数字正好包含了从 0 到 9 这 10 个数字，每个都恰好出现 1 次。“

请你推算一下，他当时到底有多年轻?

for i in range(10,30):
    i3 = str(i ** 3)
    i4 = str(i ** 4)
    if len(i3) == 4 and len(i4) == 6:
        if len(set(i3+i4)) == 10:
            print(i)
            print(i3 + i4)

# 18
# 5832104976 舍去

题目 15：split 算法实现

split 是 python 字符串内置的一个非常有用的方法

• 它可以将一个字符串通过分隔符切成我们想要的列表
• 比如现在我们有个字符串 life-is-short-you-need-python 每一个单词之间使用分隔符“-”进行分割
• 当我们去调用字符串 split 的方法之后传入我们的分隔符“-”，那我们就会得到一个列表列表里面每个元素其实就是通过分隔符切出来的子字符串
• 那这个算法该怎么样去实现呢？python 内置的 split 方法是通过 C 语言实现的，我们今天去写一个函数，去实现和 split 相同的功能
• 我们先来讲下算法该怎么样去实现，这个算法需要我们对字符串进行迭代，我们先去定义一个初始化的指针，因为我们切片的时候需要从哪一个开始的位置进行切
• 所以我们先要初始化一个指针我们可以定义一个指针变量，默认值为 0，紧接着我们开始对字符串进行迭代
• 当碰到第一个分隔符的时候，我们是不是会获取到当前分隔符的索引，那这个时候，我们就把初始的指针开始到分隔符结束对字符串进行切片
• 因为我们字符串是遵守左闭右开的，你的结束索引写的是分隔符的索引，所以只会切到 life，我们并把它添加到列表里面
• 紧接着添加完之后呢，我们需要把初始化的指针修改一下位置，修改到哪个地方呢？修改到我们第一次碰到的分隔符的下一个位置也就是 i，紧接着继续进行迭代
• 迭代之后发现第二个分隔符，是不是还有一个分隔符的索引，这个时候我们继续向字符串进行切片，切片的开始位置是你的 i 这个位置的指针，结束的位置是第二个 – 的指针，那遵循左闭右开，所以我们 is 这个单词，也可以添加进列表
• 就这样一直到最后呢，当我们去迭代到最后一个字符 n 的时候，发现后面是没有横杆分隔符了，这个时候我们需要进行处理一下，需要进行去判断一下，如果我们迭代到的字符是最后一个字符，那么我们进行切片的时候，就应该从哪个地方切呢？
• 从 p 开始 ，如果切到 n，我们只能取到 pytho，少切一个 n，所以到 n + 1 的位置，好，知道这个流程我们就用代码去实现这个算法

def split_s(string, sep="", num=0):
    split_words = []
    last_index = 0
    count = 0
    for index, char in enumerate(string):
        if count == num and num > 0:
            split_words.append(string[last_index:len(string)])
            break
        if char == sep:
            split_words.append(string[last_index:index])
            last_index = index + 1
            count += 1
        elif index + 1 == len(string):
            split_words.append(string[last_index:index + 1])
    return split_words

print(split_s("life-is-short-you-need-python",'-'))
# ['life', 'is', 'short', 'you', 'need', 'python']

print(split_s("life-is-short-you-need-python",'-',2))
# ['life', 'is', 'short-you-need-python']

题目 16：大衍数列

中国古代文献中，曾记载过“大衍数列”，主要用于解释中国传统文化中的太极衍生原理 它的前几项是：0、2、4、8、12、18、24、32、40、50… 其规律是：偶数项，是序号平方再除 2，奇数项，是序号平方减 1 再除 2。 打印大衍数列的前 100 项

for x in range(1,101):
    if x % 2 == 0: # 偶数
        a = int((x ** 2) / 2)
    else: # 奇数
        a = int((x ** 2 - 1) / 2)
    print(a)
# 0
# 2
# 4
# 8
# 12
# 18
# 24
# 32
# 40
# 50

题目 17：单词分析

小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词

现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这个字母出现的次数 其实就是让你输入一段字符串后，得到当前字符串出现最多的字母和它的次数

输入：HelloWorld
输出：
l # 小写字母 l
3 # 小写字母 l,出现了3次，出现次数最多

• 我们可以对当前的字符串进行循环迭代，然后把字符串当前每个字符当作 key 值，把它存到字典里面，如果当前 key 在字典里面，我们就让它加一
• 如果不在那我们就让它的次数初始化为 1，最终我们再从字典找到次数最多的 key 值和 value 值

def analyse_words(words):
    word_dict = {}
    for i in words:
        if i in word_dict:
            word_dict[i] += 1
        else:
            word_dict[i] = 1
    max_key = max(word_dict,key=word_dict.get)
    print(max_key)
    print(word_dict[max_key])
    # l
    # 3
analyse_words('helloworld')

题目 18：利用栈打印菱形

输入边长 n，打印对应边长的菱形

分析：

• 打印几行
• 每一行打印几个空格，几个星星
• 前几行打印之前加入到栈，利用栈的后进先出原则打印后几行的内容

def diamond(n):
    stack = []
    for i in range(1, 2 * n):
        if i <= n:
            p_str = ' ' * (n - i) + '*' * (2 * i - 1)
            if i != n:
                stack.append(p_str)
            print(p_str)
        else:
            print(stack.pop())

diamond(5)

# 为了区分我把空格换成了点
# ....*
# ...***
# ..*****
# .*******
# *********
# .*******
# ..*****
# ...***
# ....*

题目 19：深入理解递归函数

• 什么是递归函数？ 递归函数就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。
• 需要注意：递归函数必须有结束条件。

设计递归函数三要素：

• 明确你这个函数想要干什么
• 寻找递归结束条件
• 找出函数的等价关系式

def p(n):
    if n == 0:
        return
    print('递归前->',n)
    p(n-1)
    print('递归后->',n)
p(5)

# 递归前-> 5
# 递归前-> 4
# 递归前-> 3
# 递归前-> 2
# 递归前-> 1
# 递归后-> 1
# 递归后-> 2
# 递归后-> 3
# 递归后-> 4
# 递归后-> 5

题目 20：斐波那契递归函数

斐波那契数列(Fibonacci sequence)，又称黄金分割数列，因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列： 1、1、2、3、5、8、13、21、34、…

这个数列，前两项都是数字 1，从第三项开始，每一项数字是前两项数字之和

数学表达式：f(n) = f(n-1)+f(n-2)

def fib(n):
    if n<=2:
        return 1
    return fib(n-1)+fib(n-2)

print(fib(10)) # 55
print(fib(2)) # 1

递归与栈的关系 递归函数原理：每一次调用都会把当前调用压入到栈里，最后按照后进先出的原则，不停返回返回 由递归程序的执行过程，我们得知递归程序的调用是一层层向下的，而返回过程则恰好相反，一层层向上。

换个说法：最先一次的函数调用在最后返回，而最后一次的函数调用则是最先返回。这就跟栈的“后进先出”次序是一样的。因此，在实现递归调用的时候，通常就会使用栈来保存每一次调用的现场数据：

当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈，压入栈的现场数据称为栈帧。 当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回。

题目 21：三个数取最大数

己知数字 a，b，c 分别为 10，6，18 找出 a，b，c 中最大的数字(不借助函数以及列表等方式) 我们知道函数 max 可以直接获取到最大值，或者可以把数字添加到列表里，通过排序也能获取到最大数字，我们单纯使用 if 分支来实现

a, b, c = 10, 6, 18
if a > b:
    max_num = a
else:
    max_num = b
if max_num < c:
    max_num = c

print(max_num) # 18

题目 22：因子之和“完数”

• 什么是因子？ 因子就是所有可以整除这个数的数字，包括 1 但不包括这个数自身。比如 8 的因子有 1，2，4
• 什么是完数？ 一个数如果恰好等于它的因子之和，这个数就称为“完数”，打印输出 1000 以内的完数，例如 6=1+2+3，6 就是“完数

def factor_sum(n):
    s_sum = 0
    for i in range(1, n):
        if n % i == 0:
            s_sum += i
    return s_sum

for j in range(1, 1000):
    if j == factor_sum(j):
        print(j)
        # 6
        # 28
        # 496

题目 23：递归阶乘求和

一个正整数的阶乘(factorial)是所有小于及等于该数的正整数之积，并且 0 的阶乘为 1

如 5!=12345 计算 1!+2!+3!+4!+5!+…+10! 数学表达式：f(n) = n*f(n-1)：

def factor(n):
    if n < 2:
        return 1
    return n * factor(n - 1)

s_sum = 0
for i in range(1, 11):
    s_sum += factor(i)
print(s_sum)  # 4037913

题目 24：有效的括号

给定一个只包括'(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合
• 左括号必须以正确的顺序闭合
• 空字符串可被认为是有效字符串
• 示例 1：

输入：”()”

输出：True

• 示例 2：

输入：”()[]{}”

输出：True

• 示例 3：

输入：”(]”

输出：False

• 示例 4：

输入：”([)]”

输出：False

• 解法一：字符串替换法 在字符串中找成对的()、[]、{}，找到后替换成空 使用 while 循环，不停判断是否存在成对的小括号中括号大括号，如果存在就使用 replace 替换成空 直到无法再替换的时候，再判断下当前的字符串是否为空，如果为空说明字符串是有效的，如果不为空说明字符串是无效的

def valid_str(string):
    if len(string) % 2 == 1:
        return False
    while '()' in string or '[]' in string or '{}' in string:
        string = string.replace('()', '')
        string = string.replace('[]', '')
        string = string.replace('{}', '')
    return string == ''

print(valid_str('()'))  # True
print(valid_str('()[]{}'))  # True
print(valid_str('()[]{[()]}'))  # True
print(valid_str('()[]{[(}]}'))  # False

• 解法二：利用栈的后进先出原则 先去定义一个空栈，对当前栈进行循环遍历，遇到左括号我们就把当前的左括号添加到栈里面，遇到右括号，我们就和栈顶元素进行比对 看它们是不是成对的括号，如果是，就把当前的元素出栈，直到字符串遍历结束之后，我们再来看下字符串是不是空的，如果是空的说明字符串是有效的，如果不为空说明字符串是无效的

def valid_str(string):
    if len(string) % 2 == 1:
        return False
    stack = []
    char_dict = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    for char in string:
        if char in char_dict:
            # 右括号
            if not stack or char_dict[char] != stack.pop():
                return False
        else:
            # 左括号
            stack.append(char)
    return not stack

print(valid_str('(){}[({[]})]'))  # True
print(valid_str('(){}[({[)})]'))  # False
print(valid_str(''))  # True

题目 25：回文数的两种解法

回文数是指正序(从左向右)和倒序(从右向左)都是一样的整数。例如，1221 是回文，而 1222 不是。

• 解法一：通过逆转字符串进行比对

def is_palindrome(x):
    if x < 0 or x > 0 and x % 10 == 0:
        return False
    str_x = str(x)
    return str_x == str_x[::-1]

print(is_palindrome(121))  # True
print(is_palindrome(120))  # False

• 解法二：反转一半数字和前半部分的数字进行比较

流程

• 对于整数 x，将后半部分反转，保存到变量 reverted
• 每次循环 x%10 拿到末尾数字
• 然后 x/10 去除末尾的数字
• 循环结束条件 x<=reverted
• 数字长度（奇数） 12321
• 数字长度（偶数） 1221

def is_palindrome(x):
    if x < 0 or x > 0 and x % 10 == 0:
        return False
    reverted = 0
    while x > reverted:
        # 我们看下 1221
        # 第一次循环我们需要把末尾数字1取出来 第二次取末尾数字2 我们需要把21变成12
        reverted = reverted * 10 + x % 10
        # 把x的末尾数字删除掉
        x //= 10
    return x == reverted or x == reverted // 10

print(is_palindrome(1221))  # True
print(is_palindrome(1223))  # False
print(is_palindrome(123321))  # True

参考资料

[1]

自吾爱激活成功教程: https://www.52pojie.cn/thread-1689186-1-1.html