1 算法的概念

学习目标:

知道什么是算法

1.1 引入

首先我们先来看一道题:

如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?

第一次尝试

这里我们的思路:把所有的a,b,c的可能性都列举出来,然后一一进行验证最终得出结果.这种方法我们称之为 穷举法 (这也是我们的一种算法)

import time

start_time = time.time()

# 注意是三重循环
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a**2 + b**2 == c**2 and a+b+c == 1000:
                print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

运行结果：

a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 214.583347
complete!

注意运行的时间:214.583347秒

1.2 算法的提出

算法的概念

算法是计算机处理信息的本质，因为 计算机程序本质上是一个算法 来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法是独立存在的一种解决问题的方法和思想.

刚才我们提到了 穷举法, 穷举法就是一种算法, 一种思想.

对于算法而言，实现的语言并不重要，重要的是思想。也就是说算法本身是独立于程序和各种编程语言的,而我们的程序只不过是对算法的一种表达和实现.

算法可以有不同的语言描述实现版本（如C描述、C++描述、Python描述等），我们现在是在用Python语言进行描述实现。

算法的五大特性

输入: 算法具有0个或多个输入
输出: 算法至少有1个或多个输出
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

1.3 第二次尝试

既然算法是一种思想, 那么对于一个问题我们每个人都有不同的想法, 对于一个程序我们自然也能使用不同的算法去完成它.

import time

start_time = time.time()

# 注意是两重循环
for a in range(0, 1001):
    for b in range(0, 1001-a):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

运行结果：

a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 0.182897
complete!

注意运行的时间:0.182897秒

两次尝试我们使用了两种不同的算法,也就是两种有所不同的思想去解决它, 最终的问题解决时间相差也是非常的大的. 可见选择一个合适的算法去解决问题可以大大的提高我们的效率.

小结:

算法: 算法是独立存在的一种解决问题的方法和思想