Python数据结构与算法算法引入

数据结构与算法（Python）

如果将最终写好运行的程序比作战场，我们码农便是指挥作战的将军，而我们所写的代码便是士兵和武器

那么数据结构和算法是什么？答曰：兵法！

大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，就会性能低下；

---

---

引入问题：

先来看一道题:

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

不借助公式，最笨的方法就是一个个试，这就叫做 枚举法

---

枚举法：

思路：
a=0~1000 循环
b=0~1000 循环
c=0~1000 循环
三重循环找合适的组合。

---

---

---

第一次尝试（枚举法）

import time start_time=time.time() n=0 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:
                n+=1
                print(n,a,b,c) end_time=time.time() print('耗时{0}'.format(end_time-start_time)) 

1 0 500 500
2 200 375 425
3 375 200 425
计算花费了很长时间，过了五六分钟计算出上面三个结果。

最后的输出结果有如下几组：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500

---

---

老师的程序：

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!") 

---

---

算法的提出

算法的概念

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

---

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

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

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

---

---

---

算法的五大特性

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

本文地址：https://blog.csdn.net/asd1103810477/article/details/108248297