python 算法 小试牛刀

 

1.打印从1到100，碰到3倍数用fizz代替，碰到5倍数，用buzz代替，3和5的倍数，FizzBuzz代替

def func():
    for i in range(1,101):
        if i % 3 == 0 & i % 5 == 0
           print("FizzBuzz")
        elif i % 3 == 0:
            print("fizz")
        elif i % 5 == 0:
            print("buzz")
        else:
            print(i)

func()

 

2. 顺序（搜索）算法

顺序搜索是一个简单的搜索算法。搜索牌堆中的一张特定牌，有就停止；没有，搜索完也停止

def funz(number_list,n):
    found = False
    for i in number_list:
        if  i == n:
            found = True
            break
    return found

'''
#以数字为例
numbers = range(0,100)
ss = funz(numbers,3)
print(ss)
sss = funz(numbers,201)
print(sss)
'''
    

用found记录是否找到。找到就设置为true，退出循环，并返回found变量；没有找到，就继续搜索下一张牌，如果遍历完所有的牌，返回变量found。通过found的值判断是否找到该牌。

 

3. 回文词（palindrome）

逆序和正序写出的单词是相同的词,大小写视为同一个单词。如何判断是否为回文词：

def palindrome(word):
    word = word.lower()
    return word[::-1] == word

print(palindrome("Morde"))
print(palindrome("Mom"))

[::-1]是python中逆序返回可迭代对象的切片的语法。

 

4.变位词（anagram）

通过重组另一个单词的字母组成的单词。iceman 是cinema的一个变位词。如何判断是否为变位词：

def funa(word1,word2):
    w1 = word1.lower()
    w2 = word2.lower()
    return sorted(w1) == sorted(w2)


print(funa("iceman","cinema"))
print(funa("lead"，"wolf")

避免大小写影响算法结果，对单词使用lower方法。判断单词是否一样，只需要进行排序，排序后的结果相同，则返回True，否则返回False。（sorted方法会返回一个以字母顺序排序的结果。）

 

5.计算字母频数

判断单词中每个字母出现的次数：

def funv(string):
    dict = {}
    for c in string:
        if c in dict:
            dict[c] += 1
        else:
            dict[c] = 1
    print(dict)
  

'''
#为了更直观的了解代码，可以用下面的代码
def funv(string):
    dict = {}
    for c in string:
        if c in dict:
            dict[c] += 1
            print(dict)
        else:
            dict[c] = 1
    print("&&&&&&&")
    print(dict)

print(funv("sftinigddd"))
'''

遍历参数string的每个字母，如果字母存在字典dict中，将对应的值递增1；不在的话，添加到字典dict中，并将对应值置为1.for循环结束后，dict将包含字符串每个字母的键值对。每个键的值就是字符串中该字母所出现的次数。

 

6.递归

recursion是将问题不断切分成更小的问题。直到小问题可以轻松解决的一种方法。

       迭代式算法：使用循环不断重复一个步骤来解决问题。

       递归式算法：通过调用自身函数来实现。

任何可以迭代式解决的问题，都可以递归式地解决。

       递归算法，必须要有一个终止条件（base case），每次调用自己的时候，会离终止条件越来越近。最终满足终止条件，此时问题得到解决，函数停止调用自己。故三个条件：a.递归算法必须有终止条件；b.递归算法必须改变自己的状态，不断靠近终止条件；c.递归算法必须递归地不断调用自己。

def bottles(bob):
    """Prints 99 Bottle
       of Beer on the
       Wall lyrics.
       :param bob:Must
       be a positive
       integer.
    """
    if bob < 1:
        print("""No more
                 bottles
                 of beer
                 on the wall.
                 more
                 bottles of
                 beer.""")
        return 
    tmp = bob
    bob -= 1
    print("""{} bottles of
             beer on the
             wall. {} bottles
             of beer. Take one
             down, pass it
             around, {} bottles
             of beer on the
             wall.
             """.format(tmp,
                        tmp,
                        bob))
    bottles(bob)

(a)  递归的第一个原则通过如下终止条件满足:

if bob < 1:
        print("""No more
                 bottles
                 of beer
                 on the wall.
                 more
                 bottles of
                 beer.""")
        return 

(b)  bob -= 1 满足了递归的第二个原则,因为递减变量bob 的值将使其不断接近终止条件。变量bob 的值小于1 时，满足终止条件，函数每调用一次自身，就离终止条件更近一步。
(c)  递归的最后一个原则也满足了：

bottles(bob)