Python-算法思维4.0.1迭代算法

第1关:谷角猜想

日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1。如此经过有限次运算后,总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。

编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程保存在列表中并打印出来。

#Student Start
n=int(input())
ls=[n]
while n>1:
    if n%2==0:
        n=n//2
    else:
        n=n*3+1
    ls.append(n)
print(ls)
#student End

第2关:阿米巴分裂

阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2n(n从键盘输入)个。试问,开始的时候往容器内放了多少个阿米巴?考虑特例,当容器容量较小时,开始1个阿米巴也不需要45分钟就可以充满,答案为1。请编程序算出开始时容器里面的阿米巴个数。

#Student Start
n=int(input())
x=2**n
for i in range(15):
    x=x//2
    if x==1:
        break
print(x)
#student End

第3关:平方根

求平方根的迭代公式:x1=1/2*(x0+a/x0)。 算法:

  1. 先自定一个初值x0,作为a的平方根值,在我们的程序中取a/2作为x0的初值;利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差很大。
  2. 把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1.
  3. 利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。
  4. 比较前后两次求得的平方根值x0和x1,如果它们的差值小于我们指定的值,即达到我们要求的精度,则认为x1就是a的平方根值,去执行步骤5;否则执行步骤2,即循环进行迭代。
  5. 输出方程的根x1。

根据输入的n值,计算并输出其平方根,要求精确到小数点后第六位(前后两次计算得到差值小于10的负六次方停止迭代)。

#Student Start
n=eval(input())
x0=n/2
x1=0.5*(x0+n/x0)
while abs (x1-x0)>1e-6:
    x0=x1
    x1=0.5*(x0+n/x0)
print('x=%.6f'%x1)
#student End 

第4关:牛顿迭代

牛顿迭代公式:假设r是方程f(x)=0的根,选取x0作为r的近似初值,过点(x0,f(x0))作切线L:y=f(x0)+f’(x0)(x-x0),则L与x轴的交点 x1=x0-f(x0)/f’(x0)称为r的一次近似值。过点(x1,f(x1))做切线与x轴的交点x2=x1-f(x1)/f’(x1) 称为r的二次近似值。重复该过程,得到第n+1交点 xn+1=xn-f(xn)/f’(xn) 称为r的n+1次近似值,这就是牛顿迭代公式。 已经证明,如果是连续的,并且待求的零点是孤立的,那么在零点周围存在一个区域,只要初始值位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。 迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。

使用牛顿迭代法求解给定方程x*3-10x*2-25x+250在输入x0附近的解,精度要求前后两次迭代的差值小于10的负六次方。

#Student Start
def f(x):
    return x**3-10*x**2-25*x+250
def fp(x):
    return 3*x**2-20*x-25
x0=eval(input())
x1=x0-f(x0)/fp(x0)
while abs(x1-x0)>=1e-6:
    x0=x1
    x1=x0-f(x0)/fp(x0)
print('x=%.6f'%x1)
#student End

求求三连。。。

上一篇:Selenium RC在Eclipse中的使用


下一篇:R语言中提取两个数据框中完全相同的行及保留唯一行