第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全，請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題，去搜搜看，總會(huì)有你想問(wèn)的

使用python中的特定規(guī)則集生成電話號(hào)碼

使用python中的特定規(guī)則集生成電話號(hào)碼

慕碼人8056858 2021-09-11 19:19:14
我想編寫(xiě)一個(gè)函數(shù)，它使用以下規(guī)則集從標(biāo)準(zhǔn)電話鍵盤(pán)（圖 1）生成所有可能的數(shù)字：電話號(hào)碼以數(shù)字 2 開(kāi)頭電話號(hào)碼長(zhǎng)度為 10 位每個(gè)電話號(hào)碼中的連續(xù)數(shù)字是在國(guó)際象棋中的騎士移動(dòng)時(shí)選擇的在國(guó)際象棋中，騎士（有時(shí)稱為馬）垂直移動(dòng)兩步和水平移動(dòng)一步或水平移動(dòng)兩步和垂直移動(dòng)一步。電話號(hào)碼中只能使用數(shù)字 - 即不允許使用 (#) 和 (*) 鍵。該函數(shù)必須將電話號(hào)碼的長(zhǎng)度和初始位置作為輸入，并為輸出提供唯一電話號(hào)碼的數(shù)量。我是一個(gè)新手，面臨著構(gòu)建邏輯的困難。我嘗試按照以下方式進(jìn)行操作，這絕對(duì)不是正確的方法。def genNumbers(len, initpos):numb = list('2xxxxxxxxx')#index 1numb[1] = 7 or 9if numb[1] == 7:    numb[2] == 2 or 6elif numb[1] == 9:    numb[2] == 2 or 4#index 2if numb[2]== 2:    numb[3] == 7 or 9elif numb[2]== 4:    numb[3] == 3 or 9elif numb[2]== 6:    numb[3] == 1 or 7#index 3if numb[3]== 1:    numb[4] == 6 or 8  elif numb[3]== 3:    numb[4] == 4 or 8 elif numb[3]== 7:    numb[4] == 2 or 6 elif numb[3]== 9:    numb[4] == 2 or 4 #index 4if numb[4] == 8:    numb[5]== 1 or 3elif numb[4] == 2:    numb[5]== 7 or 9elif numb[4] == 4:    numb[5]== 3 or 9elif numb[4] == 6:    numb[5]== 1 or 7#index 5if numb[5] == 1:    numb[6]== 6 or 8elif numb[5] == 3:    numb[6]== 4 or 8elif numb[5] == 7:    numb[6]== 2 or 6 elif numb[5] == 9:    numb[6]== 2 or 4#index 6 if numb[6] == 2:    numb[7]== 7 or 9elif numb[6] == 4:    numb[7]== 3 or 9 elif numb[6] == 6:    numb[7]== 1 or 7elif numb[6] == 8:    numb[7]== 1 or 3#index 7 if numb[7] == 1:    numb[8]== 6 or 8elif numb[7] == 3:    numb[8]== 4 or 8elif numb[7] == 7:    numb[8]== 2 or 6   elif numb[7] == 9:    numb[8]== 2 or 4#index 8if numb[8] == 6:    numb[9]== 1 or 7elif numb[8] == 8:    numb[9]== 1 or 3elif numb[8] == 4:    numb[9]== 3 or 9elif numb[8] == 2:    numb[9]== 7 or 9return numb任何幫助將不勝感激！
查看完整描述

2 回答

?
三國(guó)紛爭(zhēng)

TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超7個(gè)贊

序幕

讓我們陳述另一種解決問(wèn)題的方法，該方法不涉及線性代數(shù)，但仍依賴于圖論。

表示

您的問(wèn)題的自然表示是如下所示的圖表：

http://img1.sycdn.imooc.com//613c90de0001056002280279.jpg

并且相當(dāng)于：

http://img1.sycdn.imooc.com//613c90e50001105003220254.jpg

我們可以用字典來(lái)表示這個(gè)圖：


G = {

    0: [4, 6],

    1: [6, 8],

    2: [7, 9],

    3: [4, 8],

    4: [0, 3, 9],

    5: [],  # This vertex could be ignored because there is no edge linked to it

    6: [0, 1, 7],

    7: [2, 6],

    8: [1, 3],

    9: [2, 4],

}

這種結(jié)構(gòu)將使您無(wú)需編寫(xiě)if語(yǔ)句。


鄰接矩陣

上面的表示包含與鄰接矩陣相同的信息。此外，我們可以從上面的結(jié)構(gòu)生成它（將布爾稀疏矩陣轉(zhuǎn)換為整數(shù)矩陣）：


def AdjacencyMatrix(d):

    A = np.zeros([len(d)]*2)

    for i in d:

        for j in d[i]:

            A[i,j] = 1

    return A


C = AdjacencyMatrix(G)

np.allclose(A, C) # True

另一個(gè)答案中A定義的鄰接矩陣在哪里。


遞歸

現(xiàn)在我們可以使用遞歸生成所有電話號(hào)碼：


def phoneNumbers(n=10, i=2, G=G, number='', store=None):

    if store is None:

        store = list()

    number += str(i)

    if n > 1:

        for j in G[i]:

            phoneNumbers(n=n-1, i=j, G=G, number=number, store=store)

    else:

        store.append(number)

    return store

然后我們建立電話號(hào)碼列表：


plist = phoneNumbers(n=10, i=2)

它返回：


['2727272727',

 '2727272729',

 '2727272760',

 '2727272761',

 '2727272767',

 ...

 '2949494927',

 '2949494929',

 '2949494940',

 '2949494943',

 '2949494949']

現(xiàn)在只是獲取列表的長(zhǎng)度：


len(plist) # 1424

檢查

我們可以檢查沒(méi)有重復(fù)：


len(set(plist)) # 1424

我們可以檢查比我們對(duì)另一個(gè)答案中最后一位數(shù)字所做的觀察在這個(gè)版本中仍然成立：


d = set([int(n[-1]) for n in plist]) # {0, 1, 3, 7, 9}

電話號(hào)碼不能以：


set(range(10)) - d # {2, 4, 5, 6, 8}

比較

這第二個(gè)答案：


不需要numpy（不需要線性代數(shù)），只使用 Python 標(biāo)準(zhǔn)庫(kù)；

是否使用圖形表示，因?yàn)樗悄鷨?wèn)題的自然表示；

在計(jì)算之前生成所有電話號(hào)碼，之前的答案沒(méi)有生成所有電話號(hào)碼，我們只有表格中的數(shù)字詳細(xì)信息x********y；

使用遞歸來(lái)解決問(wèn)題，并且似乎具有指數(shù)時(shí)間復(fù)雜度，如果我們不需要生成電話號(hào)碼，我們應(yīng)該使用 Matrix Power 版本。

基準(zhǔn)

遞歸函數(shù)的復(fù)雜性應(yīng)該在O(2^n)和之間，O(3^n)因?yàn)檫f歸樹(shù)的深度為n-1（并且所有分支具有相同的深度）并且每個(gè)內(nèi)部節(jié)點(diǎn)創(chuàng)建最少 2 條邊，最多 3 條邊。這里的方法不是分治算法，它是一個(gè)組合字符串生成器，這就是為什么我們期望復(fù)雜性是指數(shù)級(jí)的。


對(duì)兩個(gè)函數(shù)進(jìn)行基準(zhǔn)測(cè)試似乎證實(shí)了這一說(shuō)法：

http://img1.sycdn.imooc.com//613c90fa0001c6b107040468.jpg

遞歸函數(shù)在對(duì)數(shù)尺度上顯示線性行為，這證實(shí)了指數(shù)復(fù)雜性，并且如所述有界。更糟糕的是，除了計(jì)算之外，它還需要越來(lái)越多的內(nèi)存來(lái)存儲(chǔ)列表。我不能再進(jìn)一步了n=23，然后我的筆記本電腦在擁有MemoryError. 更好的復(fù)雜性估計(jì)是O((20/9)^n)基數(shù)等于頂點(diǎn)度數(shù)的平均值（不連接的頂點(diǎn)被忽略）。


Matrix Power 方法似乎對(duì)問(wèn)題的大小有一個(gè)恒定的時(shí)間n。numpy.linalg.matrix_power文檔中沒(méi)有實(shí)現(xiàn)細(xì)節(jié)，但這是一個(gè)已知的特征值問(wèn)題。因此我們可以解釋為什么之前的復(fù)雜性似乎是恒定的n。這是因?yàn)榫仃囆螤瞠?dú)立于n（它仍然是一個(gè)10x10矩陣）。大部分計(jì)算時(shí)間都用于解決特征值問(wèn)題，而不是將對(duì)角特征值矩陣提升到 n 次方，這是一個(gè)微不足道的操作（并且唯一依賴于n）。這就是為什么此解決方案以“恒定時(shí)間”執(zhí)行的原因。此外，它還需要準(zhǔn)恒定量的內(nèi)存來(lái)存儲(chǔ)矩陣及其分解，但這也與 無(wú)關(guān)n。


獎(jiǎng)金

在下面找到用于基準(zhǔn)函數(shù)的代碼：


import timeit


nr = 20

ns = 100

N = 15

nt = np.arange(N) + 1

t = np.full((N, 4), np.nan)

for (i, n) in enumerate(nt):

    t[i,0] = np.mean(timeit.Timer("phoneNumbersCount(n=%d)" % n, setup="from __main__ import phoneNumbersCount").repeat(nr, number=ns))

    t[i,1] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=2))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))

    t[i,2] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=0))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))

    t[i,3] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=6))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))

    print(n, t[i,:])


查看完整回答
反對(duì) 回復(fù) 2021-09-11
?
蕪湖不蕪

TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超7個(gè)贊

函數(shù)簽名

該函數(shù)必須將電話號(hào)碼的長(zhǎng)度和初始位置作為輸入，并為輸出提供唯一電話號(hào)碼的數(shù)量。


核心理念

你的問(wèn)題可以通過(guò)圖論和線性代數(shù)來(lái)解決（這些學(xué)科交匯的一個(gè)有趣的地方是離散數(shù)學(xué)）。


首先，我們創(chuàng)建一個(gè)表示手機(jī)鍵盤(pán)上合法移動(dòng)的鄰接矩陣：


import numpy as np


A = np.zeros((10, 10))

A[0,4]=1

A[0,6]=1

A[1,6]=1

A[1,8]=1

A[2,7]=1

A[2,9]=1

A[3,4]=1

A[3,8]=1

A[4,0]=1

A[4,3]=1

A[4,9]=1

A[6,0]=1

A[6,1]=1

A[6,7]=1

A[7,2]=1

A[7,6]=1

A[8,1]=1

A[8,3]=1

A[9,2]=1

A[9,4]=1

我們可以檢查矩陣是否對(duì)稱（不是必需的，但它是系統(tǒng)的一個(gè)屬性）：


np.allclose(A, A.T) # True

鄰接矩陣的輸入是這樣的：A[0,4]=1意味著從頂點(diǎn)移動(dòng)0到頂點(diǎn)4，A[0,5]=0意味著沒(méi)有移動(dòng)0到5。


[[0. 0. 0. 0. 1. 0. 1. 0. 0. 0.]

 [0. 0. 0. 0. 0. 0. 1. 0. 1. 0.]

 [0. 0. 0. 0. 0. 0. 0. 1. 0. 1.]

 [0. 0. 0. 0. 1. 0. 0. 0. 1. 0.]

 [1. 0. 0. 1. 0. 0. 0. 0. 0. 1.]

 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]

 [1. 1. 0. 0. 0. 0. 0. 1. 0. 0.]

 [0. 0. 1. 0. 0. 0. 1. 0. 0. 0.]

 [0. 1. 0. 1. 0. 0. 0. 0. 0. 0.]

 [0. 0. 1. 0. 1. 0. 0. 0. 0. 0.]]

然后我們計(jì)算A提出在電源9這給我們的數(shù)量階層的長(zhǎng)度9（這相當(dāng)于長(zhǎng)度的唯一的電話號(hào)碼數(shù)10）兩個(gè)給定頂點(diǎn)（從數(shù)字之間x以及與數(shù)字結(jié)尾y）：


W = np.linalg.matrix_power(A, 9)

路徑長(zhǎng)度是n-1因?yàn)轫旤c(diǎn)是數(shù)字，邊是鍵盤(pán)上的移動(dòng)，因此要撥打10-digits 電話號(hào)碼，您需要9移動(dòng)（長(zhǎng)度的步行9）。


它給了我們：


[[  0.   0. 336.   0. 544.   0. 544.   0. 336.   0.]

 [  0.   0. 264.   0. 432.   0. 448.   0. 280.   0.]

 [336. 264.   0. 264.   0.   0.   0. 280.   0. 280.]

 [  0.   0. 264.   0. 448.   0. 432.   0. 280.   0.]

 [544. 432.   0. 448.   0.   0.   0. 432.   0. 448.]

 [  0.   0.   0.   0.   0.   0.   0.   0.   0.   0.]

 [544. 448.   0. 432.   0.   0.   0. 448.   0. 432.]

 [  0.   0. 280.   0. 432.   0. 448.   0. 264.   0.]

 [336. 280.   0. 280.   0.   0.   0. 264.   0. 264.]

 [  0.   0. 280.   0. 448.   0. 432.   0. 264.   0.]]

矩陣W條目讀作：W[2,1] = 264表示存在264長(zhǎng)度以10開(kāi)頭2和結(jié)尾的電話號(hào)碼1。


現(xiàn)在我們總結(jié)從頂點(diǎn)開(kāi)始的步行2：


np.sum(W[2,:]) # 1424.0

有1424長(zhǎng)度的電話號(hào)碼10開(kāi)頭數(shù)字2為一組您所提供的規(guī)則。


功能

這個(gè)函數(shù)很容易寫(xiě)：


def phoneNumbersCount(n=10, i=2, A=A):

    return np.sum(np.linalg.matrix_power(A, n-1)[i,:])

大部分工作包括對(duì)描述規(guī)則集（鍵盤(pán)上允許的移動(dòng)）的矩陣進(jìn)行編碼。


檢查

根據(jù)我們可以從問(wèn)題描述中得出的觀察結(jié)果，例如@SpghttCd 所做的，我們可以檢查是否沒(méi)有10從2包含數(shù)字開(kāi)始的長(zhǎng)度數(shù)5：


W[2,5] # 0.0

我們可以檢查是否10可以從5以下位置開(kāi)始寫(xiě)入任何長(zhǎng)度：


phoneNumbersCount(10, 5) # 0.0

實(shí)際上5，對(duì)于給定的規(guī)則集，數(shù)字根本不可用。


我們還可以查看其他性質(zhì)并不明顯，例如：沒(méi)有號(hào)碼長(zhǎng)度的10開(kāi)始2和結(jié)束或者2，4，5，6或8：


W[2,:] # [336. 264.   0. 264.   0.   0.   0. 280.   0. 280.]

暗示

因?yàn)閳D沒(méi)有方向（每條邊都存在于兩個(gè)方向），所以鄰接矩陣是對(duì)稱的。因此，矩陣創(chuàng)建可以簡(jiǎn)化為：


B = np.zeros((10, 10))

B[0,4]=1

B[0,6]=1

B[1,6]=1

B[1,8]=1

B[2,7]=1

B[2,9]=1

B[3,4]=1

B[3,8]=1

B[4,9]=1

B[6,7]=1

B = np.maximum(B, B.T)


查看完整回答
反對(duì) 回復(fù) 2021-09-11
  • 2 回答
  • 0 關(guān)注
  • 291 瀏覽
慕課專(zhuān)欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

 公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)