精华内容
下载资源
问答
  • 动态规划算法实现币值最大化问题:传入列表list。创建一个描述最大币值列表C。列表C开头位置添加0。C第一个位置添加硬币第一个。从index=2开始到index=最后硬币位置,循环。C列表每个index等于硬币列表list对应...

    动态规划算法实现币值最大化问题传入列表list。创建一个描述最大币值的列表C。在列表C开头位置添加0C第一个位置添加硬币第一个。从index=2开始到index=最后硬币的位置,循环。C列表每个index等于硬币列表list对应位置的值加上index-2位置(不连续的)的值和,与index-1(上一个位置)中的最大值。直到循环结束,C列表最后一个位置记录了,最大币值。

     

    递归实现币值最大化问题不用新窗帘最大币值列表C,在币值列表list里直接更新数据。递归返回Index位置上的值,等于硬币列表list对应位置的值加上index-2位置(不连续的)的值和,与index-1(上一个位置)中的最大值。另一个返回值为当前位置。

     

    动态规划算法实现找零问题传入硬币列表和需要找零的金额。如果硬币列表中有需找零金额,只需一个硬币即可,直接返回1。创建一个长度为需找零金额的大小。从1到此金额做循环。找到每个金额的最少硬币数。循环内循环查找,此金额减去每种硬币面值,那种情况所需硬币数最小。存入temp。最终返回。

     

    递归实现找零问题同动态算法一样,硬币面值中含有需找零金额时,返回1。其余情况返回最小所需硬币数。

     

    import time
    import matplotlib.pyplot as plt
    plt.rcParams['font.sans-serif']=['SimHei'] #正常显示中文标签
    import random
    
    
    list = [5,1,2,10,6,2] #币值最大化列表
    D = [1,2,5,10]#为了方便设置 从小到大排序的列表 并缺硬币最小值为1。
    
    #动态规划算法实现 币值最大化问题
    def coin(list):
        list.insert(0, 0)
        C=[]
        C.append(0)
        C.append(list[1])
        for _ in range(2,len(list)):
            C.append(max((list[_]+C[_-2]),C[_-1])) 
        return C
    
    #递归实现 币值最大化问题
    def coin2(list,i):
        if i == 0:
            return 0
        if i == 1:
            return list[1]
        return max((list[i]+coin2(list,i-2)),coin2(list,i-1))
    
    #递归实现 零钱找零
    def coins_change(coin_values, change):
        min_count = change
        if change in coin_values:
            return 1
        for value in [i for i in coin_values if i <= change]:
            count = 1 + coins_change(coin_values, change-value)
            if count < min_count:
                min_count = count
        return min_count
    
    #print('需要硬币个数:',coins_change(D,32))
    
    #动态规划实现 零钱找零
    def ChangeMaking(coin_values, change):
        if change in coin_values:
            return 1
        F = []
        F.append(0)
        for _ in range(1,change+1): #创建一个长度为change的列表
            F.append(0)
        for i in range(1,change+1):
            temp = 999
            j = 1
            while(j <= len(coin_values) and i >= coin_values[j-1]):
                temp = min(F[i - coin_values[j-1]], temp)
                j += 1
            F[i] = temp +1
        return F[i]
    
    #print('需要硬币个数:',ChangeMaking(D,32))
    
    #硬币最大化  动态输入硬币列表
    '''
    list = []
    lei = int(input(" 请输入硬币种类数:"))
    print("输入硬币种类:")
    for _ in range(0,lei):
        list.append(int(input()))
    print('硬币为:',list)
    print('动态算法不相邻硬币最大化:',coin(list).pop())
    # list.insert(0,0)           #若也要运行coin(),则注销这行; 若只运行coin2,则不注销
    print('递归算法不相邻硬币最大化:',coin2(list,6))
    '''
    
    #找零问题
    '''
    D = []
    lei = int(input(" 请输入硬币种类数:"))
    print("输入硬币种类(包含币值为1):")
    for _ in range(0,lei):
        D.append(int(input()))
    D.sort()
    print('硬币为:',D)
    money = int(input("输入需要找零金额:"))
    print('递归算法需要硬币个数:',coins_change(D,money))
    print('动态算法需要硬币个数:',ChangeMaking(D,money))
    '''
    
    #硬币最大化 折线图对比动态规划和递归
    '''
    start_coin = []
    end_coin = []
    start_coin2 = []
    end_coin2 = []
    x = []
    y_coin = []
    y_coin2 = []
    
    for _ in range(0,10):
        print(_+1)
        list = []
        lei = int(input(" 请输入硬币种类数:"))
        x.append(lei)
        for i in range(0, lei):
            list.append(random.randint(1,10))
        print('硬币为:', list)
    
        start_coin.append(time.time())
        print(coin(list).pop())
        end_coin.append(time.time())
    
        start_coin2.append(time.time())
        print(coin2(list,lei))
        end_coin2.append(time.time())
    
    for _ in range(0, len(start_coin)):
        print((end_coin[_]-start_coin[_])*100000)
        y_coin.append((end_coin[_]-start_coin[_])*100000)
    
    for _ in range(0, len(start_coin)):
        print((end_coin2[_]-start_coin2[_])*100000)
        y_coin2.append((end_coin2[_]-start_coin2[_])*100000)
    
    
    plt.plot(x, y_coin, label='coin', linewidth=1, color='r', marker='o', markerfacecolor='blue', markersize=8)
    plt.plot(x, y_coin2, label='coin2', linewidth=1, color='b', marker='o', markerfacecolor='blue', markersize=8)
    plt.xlabel('num')
    plt.ylabel('time')
    
    plt.title('visible')
    plt.legend()
    plt.show()
    '''
    
    #找零问题 折线图对比动态规划和递归
    start_Recursive = []
    end_Recursive = []
    start_dynamic = []
    end_dynamic = []
    x = []
    y_Recursive = []
    y_dynamic = []
    
    D = []
    D = [1, 2, 3, 5, 10]
    D.sort()
    
    for _ in range(0,10):
        print('\n','第',_+1,'次循环')
        print('硬币为:', D)
        money = int(input("输入需要找零金额:"))
        x.append(money)
    
        start_Recursive.append(time.time())
        print(coins_change(D,money))
        end_Recursive.append(time.time())
    
        start_dynamic.append(time.time())
        print(ChangeMaking(D,money))
        end_dynamic.append(time.time())
    
    for _ in range(0, len(start_Recursive)):
        print((end_Recursive[_]-start_Recursive[_])*100000)
        y_Recursive.append((end_Recursive[_]-start_Recursive[_])*100000)
    
    for _ in range(0, len(start_dynamic)):
        print((end_dynamic[_]-start_dynamic[_])*100000)
        y_dynamic.append((end_dynamic[_]-start_dynamic[_])*100000)
    
    
    plt.plot(x, y_Recursive, label='Recursive', linewidth=1, color='r', marker='o', markerfacecolor='blue', markersize=8)
    plt.plot(x, y_dynamic, label='dynamic', linewidth=1, color='b', marker='o', markerfacecolor='blue', markersize=8)
    plt.xlabel('num')
    plt.ylabel('time')
    
    plt.title('visible')
    plt.legend()
    plt.show()

     

     

    展开全文
  • 一般情况,算法中基本操作重复执行次数是问题规模n的某个函数f(n),所以算法时间...由于算法时间复杂度考虑只是对于问题规模n的增长率,所以难以精确计算基本操作执行次数情况,我们只求出它关于n的增...

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),所以算法的时间复杂度记做

    T(n)=O(f(n))

    表示问题规模n的增大,算法执行时间的增长率和f(n)的增长率同。

    大多数情况下基本操作的原操作应是最深层循环内的语句,它的执行次数和包含它的语句频度相同。

    由于算法的时间复杂度考虑的只是对于问题规模n的增长率,所以在难以精确计算基本操作执行次数的情况下,我们只求出它关于n的增长率(也就是阶)即可。

    一个程序在计算机上运行所费的时间通常取决于下面几个因素:

    1,算法的策略。

    2,问题的规模,例如10个数排序还是1000个数排序。

    3,书写程序的语言,对于同一个算法,实现语言越高级,执行效率越低。

    4,编译程序产生机器代码的质量。

    5,机器执行指令的速度。(也就是汇编速度)

    展开全文
  • 自顶向,逐步求精

    2017-11-28 17:06:58
     计算机科学中,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 二、基本思想及策略  ...

    一、基本概念

       在计算机科学中,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。


    二、基本思想及策略

       分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

       分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。


    三、基本步骤

        step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

        step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

        step3 合并:将各个子问题的解合并为原问题的解。

    四.洗衣机例子

    1.用户输入参数(水位和洗衣的模式)

    2.当关闭洗衣机门后进行灌水,直到指定的水位停止。

    3.根据用户所输入的洗衣模式来控制洗衣的时间,以及转动的速度

    4.当时间到后,打开排水开关,直到水排干后进入脱水模式

    5.脱水模式进行至指定的时间。

    伪代码:

    scanf(水位,洗衣模式)

    while(当前水位<指定水位)

    加水;

    while(运行时间<指定洗衣模式时间)

    洗衣机来回转动;

    while(水位=0)

    进入脱水模式;

    while(脱水时间=指定时间)

    exit;

    展开全文
  • 当对交换变量定义多项式优化问题时,生成SDP层次结构与相同这种情况,功能类似于MATLAB工具箱 ,而弦扩展名为 。 和多项式优化问题。 当多项式非交换算子上时,生成SDP是Navascués-Pironio-Acín...
  • dfs解决全排列问题

    2020-05-20 10:41:11
    依次进行,那我们发现,其实选择放置一个数字时,和解决之前的问题是一样的 还是要没有放置过的数字当中选一个放置,这样就是把问题分解成为了规模更小的相同的问题,那么我们就想到递归。 递归 首先要有一个...

    dfs解决全排列问题 题目链接.

    问题描述

    给定一个n(0<n≤10),打印n的全排列,要求按字典序输出。

    解题思路

    该问题相当于找出从某点到目的点的所有路径问题,于是想到用dfs深度优先算法,找到一条路径即可直接输出,直到找到所有的路径。思路大致是,先放置一个数,然后在没有放置过的数字当中选择一个放在下一个位置,依次进行,那我们发现,其实在选择放置下一个数字时,和解决之前的问题是一样的 还是要在没有放置过的数字当中选一个放置,这样就是把问题分解成为了规模更小的相同的问题,那么我们就想到递归。

    递归 首先要有一个终止条件,那么这个问题的终止条件就是你已经放置了n个数字。那么在放置过程中,我们需要记录你此时在放置第几个数字。而且需要标记每一个数字是否已经放置过了。

    具体代码如下

    #include<bits/stdc++.h>
    using namespace std;
    
    int n;
    int a[12];
    bool vis[12];
    void dfs(int x){
    	if(x == n+1){ //此处为n+1 而不是n,因为如果在第n次时就输出,那么第n个数是没有存进去的 
    		for(int i = 1; i<= n-1; i++) {
    			printf("%d ",a[i]);
    		}
    		printf("%d\n",a[n]);
    		return;
    	}
    	for(int i = 1; i<=n; i++){ //遍历n个数字中哪一个没有放置过
    		if(vis[i] == false) {
    			a[x] = i;
    			vis[i] = true;
    			dfs(x+1);
    			vis[i] = false;
    		}
    	}
    	return;
    }
    int main(){
    	scanf("%d",&n);
    	memset(vis,false,sizeof(vis));
    	dfs(1); //此时放置第1个数字
    } 
    
    展开全文
  • CSDN博主Forskamse对这个问题有很好描述。...相同问题规模下,指数型时间复杂度远远大于多项式时间复杂度。 当我们解决一个问题时,我们选择算法通常都需要是多项式时间复杂度,指数型时间复杂度算法是...
  • 程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的证书,它们互不相同的条件,测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量取尽...
  •  “这个嘛~首先你要这里加上一个这种颜色珠子,然后这里去掉这个珠子,然后……,最后你看看是不是漂亮很多咧~”土方一子说出了m个修改步骤。  盾神觉得这个用人工做太麻烦了,于是交给了你。 输入格式  ...
  • 问题描述 给定2个有序数组arr1和arr2,已知2个数组的长度都是N,求2个数组中所有数的上中位数up_mid_val。...递归的核心思想是保证子问题性质相同的情况不断缩小问题规模。那么现在先分析如何从原问题
  • 算法时间复杂度 如果某个算法复杂度可以表示为O(nk)O(nk),即问题规模n出现底数位置,这种复杂度称为多项式时间复杂度;...相同问题规模下,指数型时间复杂度远远大于多项式时间复杂度。 当我们...
  • 7、 对长度为N的线性表进行顺序查找,最坏情况所需要比较次数为()。 A、 N+1 B、N C、(N+1)/2 D、N/2 我答案:C 8、 视图设计一般有3种设计次序,下列不属于视图设计是()。 A、 自顶向 B、...
  • 算法时间复杂度

    2020-11-09 15:51:53
    定义:进行算法分析时,语句总执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n数量级。算法复杂度就是算法时间量度,记做:T(n)=O(f(n))。他表示随着问题规模n的...
  • 时间复杂度理解

    2019-01-17 16:30:05
    它表示随问题规模n的增大,算法执行时间增长率和f(n增长率相同,称作算法渐进时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数 这样用O()来体现算法时间复杂度记法,我们称之为大O记法。 ...
  • 一个算法语句总执行次数是关于问题规模N的某个函数,记为f(N),N称为问题规模。语句总执行次数记为T(N),当N不断变化时,T(N)也变化,算法执行次数增长速率和f(N)增长速率相同。 则有T(N) = O(f(N)),这...
  • 任何情况,时间复杂度为O(n​2)O(n^​2)O(n​2)算法比时间复杂度为O(n∗logn)O(n*logn)O(n∗logn)算法所花费时间都长。 对于某些算法,随着问题规模的扩大,所花时间不一定单调增加。 选择题 下面代码...
  • 快速排序虽然最坏情况时间复杂度O(n^2),但它是实际排序应用中最好选择,它平均性能时间复杂度O(nlgn),其隐含常熟因子非常小。其次,它能进行原址排序,虚存中也能很好工作。 快速排序描述 思想:分治...
  • 任何情况,时间复杂度为O(n​^2​​) 算法 比时间复杂度为O(n*logn)算法所花费时间都长。(F) [解析]数据规模小时候n^2要快 1-7 对于某些算法,随着问题规模的扩大,所花时间不一定单调增加。(T)
  • 任何情况,时间复杂度为O(n​2​​) 算法比时间复杂度为O(n*logn)算法所花费时间都长。(F) 1-7 对于某些算法,随着问题规模的扩大,所花时间不一定单调增加。(T) 选择题 2-1 下面代码段时间...
  •  所有评测用例满足:2 ≤ m, n ≤ 100,0 ≤ q ≤ 100,0 ≤ x (x表示输入数据中所有位置x坐标),0 ≤ y < n(y表示输入数据中所有位置y坐标)。 以下是我代码 ``` #include #include char output...
  • 时间复杂度介绍

    2018-04-25 09:42:29
    时间复杂度表示方法  设解决一个问题规模为n,基本操作被重复执行次数是n的...算法时间复杂度考虑只是对于问题规模n的增长率,则难以精确计算情况,只需考虑它关于n的增长率或阶即可。   时间复杂...
  • 分治法典型例子 --- 二分搜索

    千次阅读 2007-01-31 18:15:00
    分治法的基本思想是将一个规模n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归的解这些子问题,然后将各个子问题的解合并得到原问题的解。下面有两种描述算法的代码,其中一种是用递...
  • 进行算法分析时,语句总执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)数量级。算法时间复杂度,也就是算法时间度量,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行...
  • 算法时间复杂度分析

    2021-01-20 21:30:00
    它表示随着问题规模n的增大,算法执行时间增长率和f(n)增长率相同,称作算法渐进时间复杂度,简称为时间复杂度,其中f(n)是问题规模n的某个函数。 用大写O()来体现算法时间复杂度记法,我们称之为大O记法。...
  • 算法时间复杂度

    2020-01-12 16:59:03
    算法时间复杂度定义:进行算法分析时,语句总执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)数量级。算法时间复杂度,也就是算法时间量度,记作:T(n)=O(f(n))。它表示随问题...
  • 进行算法分析时,语句总执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)数量级。算法时间复杂度,也就是算法时间度量,记作T(n) = O(f(n))。它表示随问题规模n的增大,算法执行...
  • 现在小明要把相同深度节点权值加一起,他想知道哪个深度节点 权值之和最大?如果有多个深度权值和同为最大,请你输出其中最小深度。 注:根深度是 1。 输入: 第一行包含一个整数 N。 第二行包含 N 个...
  • 进行算法分析时,语句总执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)数量级。算法时间复杂度(算法时间量度)。记作:T(n) = O(f(n)) 它表示随着问题规模n的增大,算法执行...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 126
精华内容 50
关键字:

在相同的问题规模下n下