SimpleAlgorithm

1.Exhaustive Enumeration-the while loop

Whenever you write a loop, you should think about an appropriate decrementing function. This is a function that has the following properties:

1. It maps a set of program variables into an integer.
2. When the loop is entered, its value is nonnegative.
3. When its value is ≤ 0, the loop terminates.
4. Its value is decreased every time through the loop.

What is the decrementing function for the while loop in Figure 3.1? It is abs(x) - ans**3

Some proper&es of itera&on loops:

• need to set an itera&on variable outside the loop
• need to test that variable to determine when done
• need to change that variable within the loop, in addi&on to other work

Loop characteristics

• Need a loop variable
  • Initialized outside loop
  • Changes within loop
  • Test for termina0on depends on variable

Now, add the statement:

print('Value of the decrementing function abs(x) - ans**3 is',
abs(x) - ans**3)
# then try for fun finding the cube root of 1957816251. The program will finish almost instantaneously. Now, try 7406961012236344616.

Experienced programmers often insert print statements, such as the one here, to test whether the decrementing function is indeed being decremented.

The algorithmic technique used in this program is a variant of guess and check called exhaustive enumeration. We enumerate all possibilities until we get to the right answer or exhaust the space of possibilities. At first blush, this may seem like an incredibly stupid way to solve a problem. Surprisingly, however, exhaustive enumeration algorithms are often the most practical way to solve a problem. They are typically easy to implement and easy to understand. And, in many cases, they run fast enough for all practical purposes.

考虑所有的条件，< = > != Compare，Iterate时候，不要将所要的结果排除在外！

print('Find the cube root of a perfect cube.')
x = int(input('Enter an integer: '))
ans = 0
while ans**3 <= abs(x): #因为有‘=’这个符号，所以无论选择什么数值，都会输出
    ans = ans + 1       # 'is not a perfect cube.') 因为在‘=’的情况下，
                        # 又循环递增了一次。
if ans**3 != abs(x):
    print(str(x), 'is not a perfect cube.')
else:
    ans = -ans
    print('Cube root of', str(x), 'is', str(ans))

报错：
无论输入什么数字，总是 '* is not a perfect cube.'

Formatted的应用，StackOverflow里的暖心解答

The Hard Way to Learn Python的第八节讲到formatted

print('Find the cube root of a perfect cube.')
x = int(input('Enter an integer: '))
ans = 0
while ans**3 < abs(x):  # This is a very intersting question.
    ans = ans + 1
if ans**3 != abs(x):
    print(x, 'is not a perfect cube.')
else:
    ans = -ans
    print('Cube root of %s is %s') % (str(x), str(ans))  # 直觉解答：%只能穿过一堵墙，%穿过’‘这堵墙，不能继续穿过第二堵墙。

报错：
 Traceback (most recent call last):
  File "3.SimpleAlgorithmeric.py", line 10, in <module>
    print('Cube root of %s is %s') % (str(x), str(ans))
TypeError: unsupported operand type(s) for %: 'NoneType' and 'tuple'

理论解答：You are calling the % outside of the print() function. This tries to see if the actual function print can be printed as %r, and because print doesn't return anything, it tries to get %rfor the value None (hence the NoneType error). Change it to

2 For Loops

The while loops we have used so far are highly stylized. Each iterates over a sequence of integers.

Python provides a language mechanism, the for loop, that can be used to simplify programs containing this kind of iteration.

print('Nested for loop')
x = 4
for j in range(x):
    print('the outer loop j', j)
    print('the outer loop x', x)
    for i in range(x):
        print('the inner loop x1: ', x)
        print('the inner loop i: ', i)
        x = 2
print('the inner loop x2', x)

the outer loop j 0 #
the outer loop x 4 # 最外层的X只循环一次，内层的X不断赋值改变。
the inner loop x1:  4
the inner loop i:  0--
the inner loop x1:  2
the inner loop i:  1--
the inner loop x1:  2
the inner loop i:  2--
the inner loop x1:  2
the inner loop i:  3--
the outer loop j 1------------
the outer loop x 2
the inner loop x1:  2
the inner loop i:  0
the inner loop x1:  2
the inner loop i:  1
the outer loop j 2-----------
the outer loop x 2
the inner loop x1:  2
the inner loop i:  0
the inner loop x1:  2
the inner loop i:  1
the outer loop j 3------------
the outer loop x 2
the inner loop x1:  2
the inner loop i:  0
the inner loop x1:  2
the inner loop i:  1
the inner loop x2 2

It raises the question of whether changing the value of x inside the loop affects the number of iterations. It does not. The arguments to the range function in the line with for are evaluated just before the first iteration of the loop, and not reevaluated for subsequent iterations.

加和数数：**

print('Number Counting')
total = 0
for c in range(101): #注意是100+1
    total = total + c
print(total)
输出：
Number Counting
5050

Print（）函数分析：

print('求立方根，方程式ans**3 = x')
x = int(input('Enter an integer: '))
for ans in range(abs(x)+1):
    if ans**3 >= abs(x):
        break
if ans**3 > abs(x):
    print('%s is not a perfect cube.' %x)
else:
    if x < 0:
        ans = -ans
    print('Cube root of %s is %s' %(x, ans))
print('2Cube root of %s is %s' %(x, ans))
## 与 for, if, else, 平行的print输出的是整体的结果。

练习题

for letter in greeting:
    # count += 1
    if count % 2 == 0:
        print(letter)
    print(letter)
print('done')
只有多做练习题，才能体验到编程的乐趣，#因为可以不断地测试。

3 Approximate Solutions and Bisection Search

print('Approximate Solution and Bisection Search')
x = float(input('Enter an integer: '))
epsilon = 0.01
step = epsilon**2
numberGuesses = 0
ans = 0
while abs(ans**2 - x) >= 2 and ans <= x:
    ans += step
    numberGuesses += 1
print('numberGuesses = ', numberGuesses)
if abs(ans**2 - x) >= 2:
    print(ans)
else:
    print('%s is close to square root of %s' %(ans, x))

print('Using bisection search to approximate square root.')
x = float(input('Please enter a number: '))
epsilon = 0.01**5
numberGuesses = 0
low = 0
high = max(1, x)
ans = (high+low)/2
while abs(ans**2 - x) >= epsilon:
    print("low = %r, high = %r, ans = %r" %(low, high, ans))
    numberGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2 #这是核心的公式。
    print('numberGuesses = %s' %numberGuesses)
print('Final-numberGuesses = %s' %numberGuesses)
print('%r is close to square root of %r' %(ans, x))

4 A Few Words About Using Floats

print('A Few Words About Using Floats')
x = 0
for i in range(10):
    x = x + 0.1
if x == 1.0:
    print(x, '=1.0')
else:
    print(x, 'is not 1.o')
    print x == 10 * 0.

5 Newton-Raphson

Newton proved a theorem that implies that if a value, call it guess, is an approximation to a root of a polynomial, then guess – p(guess)/p’(guess), where p’ is the first derivative of p, is a better approximation.

print('Newton-Raphson for square root.')
k = float(input('Enter a number: '))
guess = k/2
epsilon = 0.01
numerGuess = 0
while abs(guess**2 - k) >= epsilon:
    guess = guess - (((guess**2) - k)/(2*guess))
    numerGuess += 1

print('numerGuess=', numerGuess)
print('Square root of %r is about %r.' %(k, guess))