python算法（一）

一、求数x的因子

1 x=100
2 divisors=()#初始化空的元组
3 for i in range(1,x):
4     if x%i==0:
5         divisors=divisors+(i,)
6         print divisors

二、求数x各个数位之和

1 sumdigits=0
2 for c in str(1952):
3     sumdigits +=int(c)
4     print sumdigits
5 print sumdigits

三、鸡兔同笼以及变形

　　1.有鸡兔两种，共有x个头，y只脚，求解鸡兔各有几只？

 1 def slove(num_heads,num_legs):
 2     for chicken_num in range(0,num_heads+1):
 3         pig_num =num_heads-chicken_num
 4         top_legs=pig_num*4+chicken_num*2
 5         if top_legs==num_legs:
 6             return [chicken_num,pig_num]
 7     return [None,None]
 8 
 9 def barnYard():
10     heads=int(raw_input("Enter the number of heads: "))
11     legs=int (raw_input("Enter the number of legs: "))
12     chicken,pig=slove(heads,legs)
13     if chicken==None:
14         print "不可解"
15     else:
16         print "the number of chicken is:",chicken
17         print "the number of pig is:",pig
18 
19 barnYard()

2.有鸡兔，蜘蛛一共三种，共有x个头，y只脚，求解鸡兔，蜘蛛各有几只？

 1 def slove1(num_heads,num_legs):
 2     for spider_num in range(0,num_heads+1):
 3         for chicken_num in range(0,num_heads-spider_num):
 4             pig_num =num_heads-chicken_num-spider_num
 5             top_legs=pig_num*4+chicken_num*2+spider_num*8
 6             if top_legs==num_legs:
 7                 return [chicken_num,pig_num,spider_num]
 8     return [None,None,None]
 9 
10 def barnYard1():
11     heads=int(raw_input("Enter the number of heads: "))
12     legs=int (raw_input("Enter the number of legs: "))
13     chicken,pig,spider=slove1(heads,legs)
14     if chicken==None:
15         print "不可解"
16     else:
17         print "the number of chicken is:",chicken
18         print "the number of pig is:",pig
19         print "the number of spider is",spider
20 
21 barnYard1()

3.2中的问题或许不只有一个解答，依次输出符合要求的解答

 1 def slove2(num_heads,num_legs):
 2     solutionFound=False
 3     for spider_num in range(0,num_heads+1):
 4         for chicken_num in range(0,num_heads-spider_num):
 5             pig_num =num_heads-chicken_num-spider_num
 6             top_legs=pig_num*4+chicken_num*2+spider_num*8
 7             if top_legs==num_legs:
 8                 print "the number of chicken is:", chicken_num
 9                 print "the number of pig is:", pig_num
10                 print "the number of spider is", spider_num
11                 solutionFound=True
12     if not solutionFound:
13         print "不可解"
14 
15 
16 def barnYard2():
17     heads=int(raw_input("Enter the number of heads: "))
18     legs=int (raw_input("Enter the number of legs: "))
19     slove2(heads,legs)
20 
21 barnYard2()

四、递归判断字符串是否为回文

解法一：

1 def isPlalindrome(s):
2     if len(s)<=1:
3         return True
4     else :
5         return s[0]==s[-1] and isPlalindrome(s[1:-1])

解法二：

 1 def isPlalindrome1(s,indent):
 2     print indent, 'hisPalindromel called with', s
 3     if 1 >= len(s):
 4          print indent, 'About to return True from base case',s
 5          return True
 6     else:
 7         ans= s[0] == s[-1] and isPlalindrome1(s[1:-1], indent + indent)
 8         print indent, 'About to return ',ans
 9     return ans
10 
11 isPlalindrome1("abccba",1)

五、斐波那契数列

1 def fib(x):
2     sum=1;
3     if x==1 or x==0:
4         return 1;
5     else:
6         return fib(x-1)+fib(x-2)
7 
8 print fib(4)

六、求数x平方根

1.二分法求解

 1 def squrtRootBi(x,epsilon):
 2     assert x>=0,"x must be positive"+str(x)
 3     assert epsilon>0,"epsilon must be positive"+str(epsilon)
 4     low=0
 5     #high=x
 6     high=max(x,1.0)
 7     guess=(low+high)/2.0
 8     ctr=1
 9     while abs(guess**2-x)>epsilon and ctr<=100:
10         #print "low",low,"high",high,"guess",guess
11         if guess**2<x:
12             low=guess
13         else:
14             high=guess
15         guess=(low+high)/2.0
16         ctr+=1
17     assert ctr<=100,"not perfect square number!"
18     print "times of Iteration:",ctr," guess",guess
19     return guess
20 
21 def testBi():
22     squrtRootBi(4,0.0001)
23     squrtRootBi(2, 0.0001)
24     squrtRootBi(0.25, 0.0001)
25 
26 testBi()

2.牛顿迭代法求解

 1 def squrtRootNR(x,epsilon):
 2     assert x >= 0, "x must be positive" + str(x)
 3     assert epsilon > 0, "epsilon must be positive" + str(epsilon)
 4     x=float(x)
 5     guess=x/2.0
 6     #guess=0.001
 7     diff=guess**2-x
 8     ctr=1
 9     while abs(diff)>epsilon and ctr<=100:
10        # print "error",diff,"guess",guess
11         guess=guess-diff/(2.0*guess)
12         diff=guess**2-x
13         ctr+=1
14     assert ctr <= 100, "not perfect square number!"
15     print "times of Iteration:", ctr, " guess", guess
16     return guess
17 
18 def testBi1():
19     squrtRootNR(4,0.0001)
20     squrtRootNR(2, 0.0001)
21     squrtRootNR(0.25, 0.0001)
22 
23 testBi1()

本性的苏醒，往往在遭遇真实之后。