算法学习

算法学习之旅

3.9算法分析学习

欧几里得算法

求最大公约数

gcd(m,n)=gcd(n,m mod n)

gcd(60,24)=gcd(24,12)=gcd(12,0)=12

Pseudo code

euclid(m,n)
//使用欧几里得算法计算gcd(m,n)
//输入：两个不全为0的非负整数m,n
//输出：m,n的最大公约数
while n!= 0 do
    r <- m mod n
    m <- n
    n <- r
return m

Python

num1=int(input("Enter the first Number:"))
num2=int(input("Enter the second Number:"))
while num2 != 0:
    r=num1 % num2
    num1 = num2
    num2 = r
print(num1)

埃拉托色尼筛选法

找出不大于n的质数序列

p*p<=n //p表示仍未削去的最大数
p<=|n^(1/2)|

Pseudo code

Sieve(n)
//实现“埃拉托色尼筛选法”
//输入：一个正整数n>1
//输出：包含所有小于等于n的质数的数组L
for p<-2 to n do A[p]<-p
for p<-2 to |n^(1/2)| do
    if A[p]!=0
    j<-p*p
    while j<=n do
    A[j]<-0
    j<-j+p
    i<-0
    for p<-2 to n do
        if A[p]!=n
            L[i]<-A[p]
            i<-i+1
        return L

Python

def _int_iter():#生成器生成从3开始的无限奇数序列
    n = 1
    while True:
        n = n + 2
        yield n
 
def  _not_divisible(n):#定义筛选函数
    return lambda x:x % n > 0
 
def primes():
    yield 2          #先返回一个2
    it = _int_iter() # 初始序列
    while True:
        n = next(it) # 返回序列的第一个数
        yield n
        it = filter(_not_divisible(n), it) # 构造新序列
for n in primes():#构造循环条件，使之可以输出任何范围的素数序列
    if n < 1000:
        print(n)
    else:
        break

3.11算法分析学习

牛顿迭代法求开方

可以利用一个“将长方形变得更像正方形”的思路求得A的算数平方根的迭代公式
$$
x_{k+1}=\frac{1}{2}\left ( x_{k}+\frac{A}{x_k} \right )
$$

算是通俗易懂地得到了这个迭代公式。
首先是考虑$\sqrt{A}$是面积为A的正方形的边长，如果画一个临边不等的面积是A的长方形，设这个长方形的长为L，宽为A/L，那么怎样才能让这个长方形变得更像一个正方形呢？是要把长变得短一点，宽变得长一点，可以用长和宽的平均数(L+A/L)/2来作为新的长$L_{new}$，在面积不变的条件下，新的宽是$A/L_{new}$。这样不断操作下去，长方形的长和宽会越来越接近，就是一直趋近与$\sqrt{A}$了。

这样更新长方形长的方法
$$
L_{new}=\frac{1}{2}\left ( L+\frac{A}{L} \right )
$$

也就是求$\sqrt{A}$的迭代公式。

C语言实现

#include <stdio.h>
#include <math.h>

double Sqr(double a) {
	double x = a, y = 0.0;
	while (fabs(x - y) > 0.00001) {
		y = x;
		x = 0.5 * (x + a / x);
	}
	return x;
}
void main()
{
	double d = Sqr(16);
	printf("%.3f", d);
}

持续更新中。。。

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： y0lo
• 本文链接： http://example.com/2021/03/11/算法学习/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！