Lesson 8 初识算法 - 简单粗暴的穷举法¶
递归二¶
作业（三）¶
编写函数 reverse(a_list), 他将输入的字符串参数进行反转。在前面的练习中，大家已经学会使用循环的方法，此处要求使用递归的方法。
提示： 如果可以使用
list(string)方式先将字符串转换为list形式。如下所示：a_string = "hello" a_list = list(a_string) print(a_list) a_list[0] = '1' print(a_list) print("".join(a_list))可以看到运行结果为
a_string = "hello world" a_list = list(a_string) print(a_list) a_list[0] = '1' print(a_list) print("".join(a_list))
解法一¶
使用最简单的循环的方法去完成
def reverse(s):
i = 0
reversed = ""
while i < len(s):
reversed = s[i] + reversed
i += 1
return reversed
解法二¶
列表与字符串的切片(Slice)¶
字符串与列表可以使用切片的方法取得子串或者子列表。他的语法为[a:b], 表示取得a到b（不包括）之间的子串或者子字符串。当a == 0或者b == len-1时，这两个参数可以省略。请看下面的示例：
words = "abcefghijklmn"
# 这种写法等于没写，稍有些区别，但是这里先不讲。
print("words[:]=", words[:])
# 取words的1至3处的子字符串。
print("words[1:3]=", words[1:3])
# 取words的0至5处的字符串
print("words[:5]=", words[:5])
# 取words的下标1至末尾的字符串
print("words[1:]=", words[1:])
words[:]= abcefghijklmn
words[1:3]= bc
words[:5]= abcef
words[1:]= bcefghijklmn
¶
递归的方法，首先我们可以很快得到递归式：reverse(s) = reverse(s[1:]) + s[0]，在这里我们使用了切片的方式。
def reverse(s):
if len(s) == 0:
return ""
else:
return reverse(s[1:]) + s[0]
解法三¶
这种方法是Jackson完成的，大家来赏析一下。
new = ""
def reverse(s):
# 这里表明我们使用的new变量是函数外的new变量
global new
list_ = list(s)
if len(s) == 0:
print(new)
else:
new = list_[0] + new
del (list_[0])
reverse(list_)
解法四¶
采用了一种非常重要的方法：双指针法
指针，我们可以理解做是一个变量，他储存了列表（list）或者字符串内元素的地址。
这种方法的思路是:
1. 将1个指针i, 和1个指针j分别置于字符串的两端，即i = 0, j = len(s) - 1;
2. 将i指针所指的元素与j指针所指的元素进行调换;
3. 将i指针往右移动1格，同时将j指针往左移动1格。
4. 重复2，3步骤，直至i >= j时停止。
这种方法应用于此问题会显得有些低效，不过却是一种很好的思维训练。
def reverseHelper(s, i, j):
if i >= j:
return
else:
temp = s[i]
s[i] = s[j]
s[j] = temp
reverseHelper(s, i + 1, j - 1)
def reverse(s):
s_list = list(s)
reverseHelper(s_list, 0, len(s) - 1)
return "".join(s_list)
穷举法/暴力法 (Brutal Force)¶
穷举法是一种非常简单粗暴的方法，他主要的思想是：穷尽所有的可能的项，一一检查是否符合要求。 下面举两个例子来说明穷举法：
例1¶
现有硬币1元、5角、1角、5分四种硬币，且其中1元不超过30枚，5角不超过30枚，1角不超过20枚，5分不超过30枚。 现在想用这些硬币组合成 35元，求解有几种组合的方法？
- 首先确定所有可能的解的选项。从题中我们可以得知，所有可能的解包括有：
- 1元硬币 0 - 30枚
- 5角硬币 0 - 30枚
- 1角硬币 0 - 20枚
-
5分硬币 0 - 30枚
-
需要满足的条件：所有硬币数与币值数总和为35元，即可满足题目要求，为题目的解，需要输出。
有了这些分析，就可以写出如下的代码
i = 0
while i ____:
j = 0
while j ____:
k = 0
while k ____:
l = 0
while l ___:
if __________________:
print(i, j, k, l)
______
______
______
______
例2¶
给定一按顺序排列且无重复的数组，如[-7, -5, -3, -1, 1, 2, 5, 6, 7, 9], 请找出其中两数，且两数的和为0.
穷举法思路：将列表中所有的两个数两两相加，查看是否和为k，如果是就输出结果。
那么，你能找到什么方法来穷举呢？
def find_sum(array, k):
i = 0
while ___________:
j = __________
while j < len(array):
if __________________________:
print(array[i], array[j])
j += 1
i += 1
思考题
-
上题中如果列表中有重复的数字呢？
-
你能尝试用暴力法解决鸡兔同笼问题吗？
今有雉（鸡）兔同笼，上有三十五头，下有九十四足。问雉兔各几何？