国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

python 算法

lentrue / 2776人閱讀

摘要:歸并排序的時(shí)間復(fù)雜度是下列哪個(gè)問題可以用貪心算法求解哈夫曼編碼問題遞歸算法和遞歸函數(shù)主分析法求時(shí)間復(fù)雜度當(dāng)這種情況意味著遞歸樹上各層結(jié)點(diǎn)的和從根結(jié)點(diǎn)開始依次遞增由于漸進(jìn)表示可以去掉低次項(xiàng)因此得。給出一個(gè)算法要求用最小的箱子數(shù)將物品全部裝入。

引言

定義:算法就是按照一定步驟解決問題的辦法

屬性:

正確:就是可以正確的求解問題

快速:就是時(shí)間復(fù)雜度要盡量小

有窮性:要在有限個(gè)步驟解決問題

輸入

輸出

漸進(jìn)分析法為什么可以做到與算法運(yùn)行硬件環(huán)境無關(guān)?

算法分析時(shí)往往假設(shè)輸入規(guī)模n足夠大,甚至趨近于無窮大。這樣的假設(shè),意味著我們關(guān)注的是算法運(yùn)算時(shí)間的增長(zhǎng)率,也就是,隨著輸入規(guī)模n的增長(zhǎng),T(n)的增長(zhǎng)率。當(dāng)n趨向于無窮大時(shí),決定T(n)增長(zhǎng)率的便是T(n)中的高次項(xiàng),從而可以忽略T(n)中的低次項(xiàng)以及高次項(xiàng)前的常數(shù)項(xiàng)。這些低次項(xiàng)或者高次項(xiàng)前的常數(shù)項(xiàng),往往是機(jī)器性能、程序設(shè)計(jì)語言的性能和編譯器性能等因素產(chǎn)生,而這些在算法時(shí)間復(fù)雜度分析中都是需要略去的次要因素。

為什么說多項(xiàng)式時(shí)間復(fù)雜度的算法要優(yōu)于指數(shù)時(shí)間復(fù)雜度的算法?

漸進(jìn)分析與python模型

二分搜索

def binary_search(A,k):
    first=0
    last= len(A)-1 
    found=False
    while first<=last and not found:
        midpoint=(first+last)//2
        if A[midpoint]==k: 
            found=True
        else:
            if k < A[midpoint]:
                last=midpoint-1 
            else:
                first=midpoint+1
    return found

確界Θ、上界Ο、下界Ω

問題求解和代碼優(yōu)化

1.動(dòng)態(tài)規(guī)劃算法的基本要素為最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)

2.能采用貪心算法求最優(yōu)解的問題,一般具有的重要性質(zhì)為最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)

3.使用分治法求解不需要滿足的條件是(A )。

A 子問題必須是一樣的 B 子問題不能夠重復(fù)

C 子問題的解可以合并 D 原問題和子問題使用相同的方法解

4.矩陣連乘問題的算法可由 動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。

5..算法是由若干條指令組成的有窮序列,且要滿足輸入、輸出、確定性和有限性四條性質(zhì)。

6.歸并排序的時(shí)間復(fù)雜度是c

(a)n (b)n^2 (c)nlgn (d)lgn

7.下列哪個(gè)問題可以用貪心算法求解( D )D.哈夫曼編碼問題

遞歸算法和遞歸函數(shù)

主分析法求時(shí)間復(fù)雜度

當(dāng)f(n) < nlogba,這種情況意味著,遞歸樹上各層結(jié)點(diǎn)的和從根結(jié)點(diǎn)開始依次遞增,由于漸進(jìn)表示可以去掉低次項(xiàng),因此得T(n)=Θ(nlogba)。

當(dāng)f(n) = nlogba,k是大于等于0的常數(shù)。這種情況意味著,遞歸樹上各層結(jié)點(diǎn)的和從根結(jié)點(diǎn)開始并沒有顯著變化,因此得 T(n)=Θ( nlogba*logn)

當(dāng)f(n) > nlogba,同時(shí)對(duì)于常數(shù)c<1滿足af(n/b)≤cf(n)。這種情況意味著,遞歸樹上各層結(jié)點(diǎn)的和從根結(jié)點(diǎn)開始依次遞減,因此得T(n)=Θ(f(n)。

給定正整數(shù)N,計(jì)算所有長(zhǎng)度為N但沒有連續(xù)1的二分字符。比如,N=2時(shí),輸

出為[00,01,10]:當(dāng)N=3時(shí),輸出為1000,001,010,100,101。

import math

N = int(input("輸入N:"))

def ss(a):
    a = bin(a)[2:]
    j = 6
    for i in a:
        if j == i == "1":
            return False
        j = i
    return True

def printN(a, N):
    a = bin(i)[2:]
    while len(a) < N:
        a = "0" + a
    print(a)


for i in range(int(math.pow(2,N))):
    if ss(i):
        printN(i,N)

統(tǒng)計(jì)逆序數(shù)問題

#_*_coding:UTF-8_*_

import random


#逆序計(jì)算的簡(jiǎn)單算法
def count_inversions_simple(A):
    inv_count = 0
    inv_list = []
    for i in range(len(A)):
        for j in range(i, len(A)):
            if A[i] > A[j]:
                inv_count += 1
                inv_list.append([A[i],A[j]])
    return inv_count, inv_list


#逆序計(jì)算的分治算法   邊排序邊找逆序數(shù)
#類似歸并排序,加入了逆序數(shù)計(jì)算 T(n) = 2T(n/2) + O(n) = O(nlogn)
def count_inversions_dc(A):
    if len(A) <= 1:        #邊界條件
        return 0, A
    middle = len(A) // 2
    leftA = A[:middle]
    rightA = A[middle:]
    countLA, leftA = count_inversions_dc(leftA)
    countRA, rightA = count_inversions_dc(rightA)
    countLRA, mergedA = merger_and_count(leftA,rightA)
    return countLA + countRA + countLRA, mergedA


#前提:輸入的A,B是有序的 
def merger_and_count(A,B):
    i, j, inv_count = 0, 0, 0
    alist = []
    while i < len(A) and j < len(B):
        if A[i] < B[j]:
            alist.append(A[i])
            i += 1
        else:            # A[i] > B[j] 則B[j]與A右邊所有元素構(gòu)成逆序
            inv_count += len(A) - i
            alist.append(B[j])
            j += 1
    while i < len(A):
        alist.append(A[i])
        i += 1
    while j < len(B):
        alist.append(B[j])
        j += 1
    return inv_count, alist



def main():
    list = [random.randint(1,10) for x in range(10)]
    sum, alist = count_inversions_dc(list)
    print(str(list))
    print("逆序數(shù):"+str(sum)+",排序后: "+str(alist))
    


if __name__ == "__main__":
    main()

第k小的數(shù)

方法一(課本):

#_*_coding:utf-8_*_

import random

def select_fct(array, k):
    if len(array) <= 10:
        array.sort()
        return array[k]
    pivot = get_pivot(array)
    array_lt, array_gt, array_eq = patition_array(array, pivot)
    if k < len(array_lt):
        return select_fct(array_lt, k)
    elif k < len(array_lt) + len(array_eq):
        return array_eq[0]
    else:
        normalized_k = k - (len(array_lt) + len(array_eq))
        return select_fct(array_gt, normalized_k)

def get_pivot(array):
    subset_size = 5
    subsets = []
    num_medians = len(array) // subset_size
    if (len(array) % subset_size) > 0:
        num_medians += 1
    for i in range(num_medians):
        beg = i * subset_size
        end = min(len(array), beg+subset_size)
        subset = array[beg:end]
        subsets.append(subset)
    medians = []
    for subset in subsets:
        median = select_fct(subset, len(subset)//2)
        medians.append(median)
    pivot = select_fct(medians, len(subset)//2)
    return pivot

def patition_array(array, pivot):
    array_lt = []
    array_gt = []
    array_eq = []
    for item in array:
        if item < pivot:
            array_lt.append(item)
        elif item > pivot:
            array_gt.append(item)
        else:
            array_eq.append(item)
    return array_lt, array_gt, array_eq


def main():
    num = 20
    array = [random.randint(1,100) for x in range(num)]
    random.shuffle(array)         #random.shuffle(x[, random]):用于將一個(gè)列表中的元素打亂
    random.shuffle(array)
    k = 7
    print(sorted(array))
    kval = select_fct(array, k)
    print("第八小:"+str(kval))
    sorted_array = sorted(array)
    assert sorted_array[k] == kval    #python assert斷言是聲明其布爾值必須為真的判定,如果發(fā)生異常就說明表達(dá)示為假。
    
if __name__ == "__main__":
    main()

方法二:

#_*_coding:utf-8_*_
#分治法解決第k小的數(shù)
import random

def partition(nums):
    pi = nums[0]
    low = [x for x in nums[1:] if x < pi]
    high = [x for x in nums[1:] if x >= pi]
    return low, pi, high

# 查找第 k 小的元素
def solve(nums, k):
    low, pi,high = partition(nums)    #分解
    n = len(low) 
    if n+1 == k:    #k+1表示第k小
        return pi
    elif n < k:
        return solve(high,k-n-1) #減去小于和等于的
    else:
        return solve(low,k)

if __name__ == "__main__":
    list = [random.randint(1,20) for x in range(20)]
    print(sorted(list))
    print(solve(list,3)) #第三小
    print(solve(list,10)) #第十小

硬幣找零,貪心算法

#零錢找零,pay是應(yīng)付金額
def coin(pay):
    m = [100, 25, 10, 5, 1]
    list = []

    sort_m = sorted(m, reverse=True)
    for i in sort_m:
        coin_count = int(pay/i)
        list += [i,] * coin_count
        pay -= coin_count*i
        if pay <= 0:
            break
    return list
    
    
 def main():
    #硬幣找零
    pay = 263
    print(coin(pay))
    
 if __name__ == "__main__":
    main()

digkstra算法求單源最短路徑

#_*_coding:utf-8_*_
#單源最短路徑問題

MAX_value = 999999

def dijkstra(graph, s):  #s是源點(diǎn),d(s) = 0
    if graph is None:    # 判斷圖是否為空,如果為空直接退出
        return None
    dist = [MAX_value,]*len(graph)
    dist[s] = 0
    S = []
    Q = [i for i in range(len(graph))]
    dist_init = [i for i in graph[s]]
    while Q:
        u_dist = min([d for v, d in enumerate(dist_init) if v in Q])
        u = dist_init.index(u_dist)
        S.append(u)
        Q.remove(u)
 
        for v, d in enumerate(graph[u]):
            if 0 < d < MAX_value:
                if dist[v] > dist[u]+d:
                    dist[v] = dist[u]+d
                    dist_init[v] = dist[v]
                    print(dist[v])
    return dist    #到每一個(gè)點(diǎn)的最短路徑距離
 
 
if __name__ == "__main__":
    graph_list = [  [0, 9, MAX_value, MAX_value, MAX_value, 14, 15, MAX_value],
                    [9, 0, 24, MAX_value, MAX_value, MAX_value,MAX_value,MAX_value],
                    [MAX_value, 24, 0, 6, 2, 18,MAX_value,19],
                    [MAX_value, MAX_value, 6, 0, 11,MAX_value,MAX_value, 6],
                    [MAX_value,MAX_value, 2, 11, 0, 30,20, 16],
                    [14,MAX_value,18,MAX_value,30,0,5,MAX_value],
                    [15,MAX_value,MAX_value,MAX_value,20,5,0,44],
                    [MAX_value,MAX_value,19,6,16,MAX_value,44,0]]
 
    distance = dijkstra(graph_list, 0)
    print(distance)  

給定n件物品的序列,以及容量為c的箱子。求將物品裝入到箱子,每一個(gè)箱子裝人的物品總重量不能超過箱子的容量。給出一個(gè)算法,要求用最小的箱子數(shù)將物品全部裝入。

比如有6個(gè)物品,其重量分別為[4,8,1,42,1],箱子容量c=10。那么最少需要2個(gè)箱子將物品全部裝入,其中一個(gè)箱子裝入[4,4,2],另一個(gè)箱子裝入[8,2]

#_*_coding:utf-8_*_

def box(list, n):
    list.sort(reverse = True)
    aa = [[] for x in range(len(list))] 

    for element in list:
        for j in range(len(list)):
            if sum(aa[j]) + element <= n:
                aa[j].append(element)
                break
              
    aa = [x for x in aa if len(x)!=0]
    return aa

list = [4,8,1,4,2,1]
print(box(list, 10))

動(dòng)態(tài)規(guī)劃問題

#_*_coding:utf-8_*_
#動(dòng)態(tài)規(guī)劃
import numpy as np 
import random

#斐波那契函數(shù)
memo = {}   #字典
def fib2(n):
    if n in memo:
        return memo[n]
    else:
        if n <= 2:
            f = 1
        else:
            f = fib2(n-1) + fib2(n-2)
        memo[n] = f
        return f

def fib_bottom_up(n):
    fib = {}             #存儲(chǔ)結(jié)果的字典
    for k in range(n+1):
        if k <= 2:
            f = 1
        else:
            f = fib[k-1] + fib[k-2]   #填表
        fib[k] = f

    return fib[n]


#撿硬幣
#自底向上實(shí)現(xiàn)遞歸策略
def bottom_up_coins(row_coins):
    table = [None] * (len(row_coins) + 1)    #申明表格
    table[0] = 0
    table[1] = row_coins[0]
    for i in range(2, len(row_coins)+1):
        table[i] = max(table[i-2] + row_coins[i-1], table[i-1])  #填表
    return table

#回溯
def trace_back_coins(row_coins, table):
    select = []
    i = len(row_coins)     #從最后一位索引
    while i >= 1:
        if table[i] > table[i-1]:
            select.append(row_coins[i-1])
            i -= 2
        else:
            i -= 1
    return select



#子序列和的最大值
def num_max(alist):    #自底向上遞歸
    table = [None] * (len(alist)+1)      
    table[0] = 0
    for i in range(1, len(alist)+1):
        table[i] = max(table[i-1] + alist[i-1], alist[i-1])  #計(jì)算重新開始的優(yōu)劣
    return table

def tract_back_subseq(alist, table):
    select = []
    ind_max = np.argmax(table)        #得到最大值索引
    while ind_max >= 1:
        if table[ind_max] == alist[ind_max-1] + table[ind_max-1]:
            select.append(alist[ind_max-1])
            ind_max -= 1
        else:
            select.append(alist[ind_max-1])
            break
    return select


if __name__ == "__main__":
    list = [random.randint(1,20) for x in range(10)]
    print(list)
    print(fib2(10))
    print(fib_bottom_up(10))

    table = bottom_up_coins(list)
    print(trace_back_coins(list, table))

    table = num_max(list)
    print(tract_back_subseq(list, table))
    

0,1 背包問題

#_*_coding:utf-8_*_
#0 1 背包問題
#分析: k(i, x) = max(k(i-1, x), k(i-1, x-s) + v) 物品i放入背包,不放入背包

def knapSack(W, wt, val, n):
    #W是容量, wt是物品容量,val是價(jià)值, n是物品數(shù)量
    k = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i == 0 or w == 0:     #不滿足條件,物品或者容量為空
                k[i][w] = 0
            elif wt[i-1] <= w:
                k[i][w] = max(val[i-1] + k[i-1][w-wt[i-1]], k[i-1][w])
            else:
                k[i][w] = k[i-1][w]
    return k

if __name__ == "__main__":
    k = knapSack(10, [1,2,3], [2,3,4], 3)
    print(k)


習(xí)題參考

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/45083.html

相關(guān)文章

  • 100 個(gè)基本 Python 面試問題第二部分(21-40)

    摘要:為我們提供了許多內(nèi)置函數(shù),例如并提供了創(chuàng)建用戶定義函數(shù)的能力。會(huì)將該變量視為函數(shù)級(jí)作用域中的局部變量。回到目錄中函數(shù)的用途是什么是中的內(nèi)置函數(shù)之一。請(qǐng)注意,這種類型的參數(shù)語法不允許將命名參數(shù)傳遞給函數(shù)。函數(shù)接受一個(gè)稱為的可選參數(shù)。 ...

    2450184176 評(píng)論0 收藏0
  • 算法日積月累】1-選擇排序

    摘要:選擇排序算法實(shí)現(xiàn)實(shí)現(xiàn)選擇排序,記錄最小元素的索引,最后才交換位置說明交換兩個(gè)數(shù)組中的元素,在中有更簡(jiǎn)單的寫法,這是的語法糖,其它語言中是沒有的。和語言中比較器的實(shí)現(xiàn)前面我們說到了,我們?yōu)榱送怀雠判蛩惴ǖ乃枷耄瑢⑺械睦觾H限在數(shù)組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

    neuSnail 評(píng)論0 收藏0
  • 處理python遞歸函數(shù)及遞歸算法頻次受限制難題

      本文關(guān)鍵闡述了處理python遞歸函數(shù)及遞歸算法頻次受限制難題,具有非常好的實(shí)用價(jià)值,希望能幫助到大家。如有誤或者未考慮到真正的地區(qū),望鼎力相助  遞歸函數(shù)及遞歸算法頻次受限制  一個(gè)函數(shù)在外部啟用自身,那么這樣的函數(shù)是遞歸函數(shù)。遞歸算法要反復(fù)應(yīng)用自身,每遞歸算法一回,越近最后的值。如果一個(gè)難題需要由很多類似小問題處理,可以選擇應(yīng)用遞歸函數(shù)。伴隨著遞歸算法的深層次,難題經(jīng)營(yíng)規(guī)模對(duì)比之前都應(yīng)該所...

    89542767 評(píng)論0 收藏0
  • python模塊之hashlib

    摘要:使用算法名稱構(gòu)造函數(shù)較使用更快所有平臺(tái)的模塊都支持的算法的名稱集合。的結(jié)果集總是結(jié)果集的子集對(duì)象的字節(jié)長(zhǎng)度對(duì)象的內(nèi)部塊大小對(duì)象的名稱傳遞類字節(jié)參數(shù)通常是更新對(duì)象。表示的哈希摘要算法的名稱,比如或。表示迭代次數(shù),基于算法以及機(jī)器計(jì)算能力設(shè)置。 hashlib模塊實(shí)現(xiàn)了多種安全哈希和信息摘要算法的通用接口,包括FIPS中定義的SHA1, SHA224, SHA256, SHA384, SH...

    luodongseu 評(píng)論0 收藏0
  • 利用python進(jìn)行識(shí)別相似圖片(一)

    摘要:圖像指紋與漢明距離在介紹下面其他判別相似度的方法前,先補(bǔ)充一些概念。漢明距離為,即代表兩張圖片完全一樣。下一次將講述利用和以訓(xùn)練好的模型來進(jìn)行人臉識(shí)別。本文參考文章和圖片來源的文章賴勇浩的文章下一篇地址利用進(jìn)行識(shí)別相似圖片二 文章簡(jiǎn)介 在網(wǎng)上看到python做圖像識(shí)別的相關(guān)文章后,真心感覺python的功能實(shí)在太強(qiáng)大,因此將這些文章總結(jié)一下,建立一下自己的知識(shí)體系。當(dāng)然了,圖像識(shí)別這個(gè)...

    HitenDev 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<