python基础学习-02

发布时间:2024年01月21日

基本的程序设计模式

任何的程序设计都包含IPO,它们分别代表如下:

  • I:Input 输入,程序的输入

  • P:Process 处理,程序的主要逻辑过程

  • O:Output 输出,程序的输出

因此如果想要通过计算机实现某个功能,那么基本的程序设计模式包含三个部分,如下:

  • 确定IPO:明确需要实现功能的输入和输出,以及主要的实现逻辑过程;

  • 编写程序:将计算求解的逻辑过程通过编程语言进行设计展示;

  • 调试程序:对编写的程序按照逻辑过程进行调试,确保程序按照正确逻辑正确运行。

自顶向下-分而治之

如果要实现功能的逻辑比较复杂的时候,就需要对其进行模块化设计,将复杂问题进行分解,转化为多个简单问题,其中简单问题又可以继续分解为更加简单的问题,直到功能逻辑可以通过模块程序设计实现,这也是程序设计的自顶向下特点。总结如下:

  • 将一个总问题表达为若干个小问题组成的形式
  • 使用同样方法进一步分解小问题
  • 直至,小问题可以用计算机简单明了的解决

举例2:的斐波那契数列

自顶向下的方式其实就是使用递归来求解子问题,最终解只需要调用递归式,子问题逐步往下层递归的求解。

程序设计:

cache = {}

def fib(number):
    if number in cache:
        return cache[number]
    if number == 0 or number == 1:
        return 1
    else:
        cache[number] = fib(number - 1) + fib(number - 2)
    return cache[number]

if __name__ == '__main__':
    print(fib(35))

运行结果:

自底向上-模块化集成

自底向上(执行)就是一种逐步组建复杂系统的有效测试方法。首先将需要解决的问题分为各个三元进行测试,接着按照自顶向下相反的路径进行操作,然后对各个单元进行逐步组装,直至系统各

部分以组装的思路都经过测试和验证。

理解自底向上的执行思维:模块化集成

自底向上分析思想:

  • 任何时候栈中符号串和剩余符号串组成一个句型,当句柄出现在栈顶符号串中时,就用该句柄进行归约,这样一直归约到输入串只剩结束符、栈中符号只剩下开始符号,此时认为输入符号串是文法的句子,否则报错。

自底向上是?种求解动态规划问题的方法,它不使用递归式,而是直接使用循环来计算所有可能的结果,往上层逐渐累加子问题的解。在求解子问题的最优解的同时,也相当于是在求解整个问题的最优解。其中最难的部分是找到求解最终问题的递归关系式,或者说状态转移方程。

14930352
>>> 

理解自顶向下的设计思维:分而治之

?先要做的就是要找到“子问题”是什么。通过分析发现:每次背包新装进?个物品就可以把剩余的承重能力作为?个新的背包来求解,?直递推到承重为0的背包问题。

?m[i,w]?表示偷到商品的总价值,其中?i?表示?共多少个商品,w?表示总重量,所以求解 m[i,w]就是子问题,那么看到某?个商品i的时候,如何决定是不是要装进背包,需要考虑以下:

  • 该物品的重量大于背包的总重量,不考虑,换下?个商品;
  • 该商品的重量小于背包的总重量,那么尝试把它装进去,如果装不下就把其他东西换出来,看看装进去后的总价值是不是更高了,否则还是按照之前的装法;
  • 极端情况,所有的物品都装不下或者背包的承重能力为0,那么总价值都是0;

由以上的分析,可以得出m[i,w]的状态转移方程为:

程序设计
# 循环的?式,自底向上求解
cache = {}
items = range(1,9)
weights = [10,1,5,9,10,7,3,12,5]
values = [10,20,30,15,40,6,9,12,18]
# 最?承重能?
W = 4

def knapsack():
    for w in range(W+1):
        cache[get_key(0,w)] = 0
    for i in items:
        cache[get_key(i,0)] = 0
        for w in range(W+1):
            if w >= weights[i]:
                if cache[get_key(i-1,w-weights[i])] + values[i] > cache[get_key(i-1,w)]:
                    cache[get_key(i,w)] = values[i] + cache[get_key(i-1,w-weights[i])]
                else:
                    cache[get_key(i,w)] = cache[get_key(i-1,w)]
            else:
                cache[get_key(i,w)] = cache[get_key(i-1,w)]
    return cache[get_key(8,W)]

def get_key(i,w):
    return str(i)+','+str(w)

if __name__ == '__main__':
    # 背包把所有东西都能装进去做假设开始
    print(knapsack())
29
>>> 
文章来源:https://blog.csdn.net/jiang_changsheng/article/details/135715259
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。