系統學習程式設計筆記（十一）

計算機科學和 Python 程式設計導論

第三講-簡單算法 Lecture 3 - Simple Algorithms

ProblemSet1: 使用for循環列印以下内容
print "Hello!"
print 10
print 8
print 6
print 4
print 2      

# There are always many ways to solve a programming problem. Here is one:
print "Hello!"
for num in range(0, 10, 2):
    print 10 - num

# Here is another:
print "Hello!"
for num in range(10, 0, -2):
    print num
           

ProblemSet2:編寫一個從1加到end的for循環。答案中比較巧妙的是将total初始化為end，這樣可以少做一次加運算。

# Here is another:
total = end
for next in range(end):
    total += next
print total
           

将浮點數表示成二進制

# lecture 3.4, slide 4

x = float(raw_input('Enter a decimal number between 0 and 1: '))

p = 0
while ((2**p)*x)%1 != 0:
    print('Remainder = ' + str((2**p)*x - int((2**p)*x)))
    p += 1

num = int(x*(2**p))

result = ''
if num == 0:
    result = '0'
while num > 0:
    result = str(num%2) + result
    num = num/2

for i in range(p - len(result)):
    result = '0' + result

result = result[0:-p] + '.' + result[-p:]
print('The binary representation of the decimal ' + str(x) + ' is ' + str(result))
           

使用便利貼展示了二分查找的強大~~~~

ProblemSet：In this problem, you'll create a program that guesses a secret number!

low = 0; high=100
print('Please think of a number between %d and %d !'% (low,high))
# 第一處修改，增加變量
guessed = False
#while True:    
while not guessed:    #第二處修改，使用變量去控制循環
    guess = (low+high)/2
    print('Is your secret number %d ?'% guess)
    ans = input("Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the\
 guess is too low. Enter 'c' to indicate I guessed correctly. ")
    if ans=='h':
        high=guess
    elif ans=='l':
        low = guess
    elif ans=='c':
        print('Game over. Your secret number was: %d'% guess)
        #break;
        guessed = True  #第三處修改，盡量避免用break來中斷循環
    else:
        print('Sorry, I did not understand your input.')
        #continue        #第四處修改，這是多餘的語句。
           

 Newton-Raphson方法求解：疊代算法，之前的例子都是采用窮舉法，而這裡利用數學特性來進行猜測，效率非常高。

# Lecture 3.7, slide 3

# Newton-Raphson for square root

epsilon = 0.01
y = 24.0
guess = y/2.0

while abs(guess*guess - y) >= epsilon:
    guess = guess - (((guess**2) - y)/(2*guess))
    print(guess)
print('Square root of ' + str(y) + ' is about ' + str(guess))