Python数据结构与算法


1-01-算法引入

文章目录

为什么要学习数据结构与算法？

因为算法即兵法，是基本功，要不断地主动学习与积累

面试题

如果 a+b+c=1000，且 a^2 + b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?不允许依赖任何数学公式

解答

不依靠数学公式，我们靠枚举法

枚举法

思路

a=0
b=0
c=0

a=0
b=0
c=1

a=0
b=0
c=2

a=0
b=0
c=0~1000

a=0
b=1
c=0~1000
这样手工也可以解答出

如果题目改成

如果 a+b+c=2000，且 a^2 + b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?不允许依赖任何数学公式

这样的枚举法也是基于实现的

以上就是一个枚举法的思路
程序怎么来写呢

代码实现

# 如果 a+b+c=1000，且 a^2 + b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?不允许依赖任何数学公式
# a
# b
# c
for a in range(0,1001):
    for b in range(0,1001):
        for c in range(0,1001):
            # 要想两个不变 另一个一直变就用嵌套
            if a+b+c == 1000 and a**2+b**2==c**2:
                print("a,b,c:%d,%d,%d"%(a,b,c))

结果


注意！！！程序还没有结束，跑的很慢！！！继续等待！！！


还在继续运行！！！！


完成了总共四个结果

记录时间的代码实现

# 如果 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 + b + c == 1000 and a ** 2 + b ** 2 == c ** 2:
                print("a,b,c:%d,%d,%d" % (a, b, c))
end_time = time.time()
print("花费的时间times：%d" % (end_time - start_time))
print("finished")

说明

我们把思路用代码实现了出来。
那个思路就是算法
思路：怎么样让计算机吧我们的问题给解决出来

算法的定义

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

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

对于算法而言，实现的语言并不重要，重要的是思想。

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

推荐图书

算法的五大特性

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