安卓手機的屏幕鎖有多少種形狀組合? | 知乎問答精選

 

A-A+

安卓手機的屏幕鎖有多少種形狀組合?

2018年02月01日 GOOGLE, 知乎問答精選 暫無評論 閱讀 3 ℃ 次

安卓手機的屏幕鎖是3*3的9點矩陣。相鄰的點可以用一條直線連接,但每個點不可以重複連接。如果必須連接4個點(含4個點)以上才是一個有效的形狀,一共有多少種形狀組合?

用組合數學的辦法可以解答嗎?

如果用軟件算法來解答,最佳算法是什麼?

【祝風翔的回答(30票)】:

啊哈~既然樓主不喜歡用窮舉的方法解決,我就用動態規劃的方法來做做吧。

這個題目最關鍵的一個限制條件是每個點只能經過一次,很容易就想到Hamilton路問題。所以我就把這題當作特殊條件下的Hamilton路來做。

我們用dp[i,j]用來表示當前已經路過的點集合為i,當前路線所在點為j時,路線的總數。其中i是一個狀態壓縮數,它的第i個二進制位表示第i個點有沒有在已經走過的路線裡(0表示沒有,1表示有,為了方便,我們將3*3的矩陣編號為0-8)。

我們每次遇到一個狀態dp[i,j]就枚舉不在i集合中的格子k,判斷從j能否走到k。如果能的話,就將dp[i,j]的值累加到dp[i+(1<<k)][k]中,由於從j走到了k,所以當前路線所在終點就變成了k。

狀態轉移的過程:dp[i][j] = sigma{dp[i^(1<<j)][k],從j走到k為合法}

這樣,總的時間複雜度為:O(2^9*9^2)

略微寫了寫代碼,有點亂,求輕拍。

01#include <iostream>

02#include <math.h>

03?

04#define take(a,b) (((a)>>(b))&1)

05int?dp[1<<10][10],m[1<<10];

06bool?check(int?s,int?t,int?Mask){//判斷從s可否走到t

07?????int?rs = s/3,cs = s%3;

08?????int?rt = t/3,ct = t%3;

09?????int?dx =?abs(rs - rt),dy =?abs(cs - ct);

10?????if(dx + dy == 1)?return?true;//s,t相鄰

11?????if(dx * dy == 1 || dx * dy == 2)?return?true;//st斜對角或者日字型

12?????if(dx * dy == 4)?return?take(Mask,4);

13?????if(dx == 0)??????return?take(Mask,3*rs+1);

14?????if(dy == 0)??????return?take(Mask,3+cs);

15}

16int?main(){

17????int?i,j,k,sum = 0;

18????for(i = 0;i < 9;i++) dp[1<<i][i] = 1;

19????for(i = 0;i < (1<<9);i++) m[i] = m[i/2] + i%2;//計算二進制中1的個數

20????for(i = 0;i < (1<<9);i++) {

21????????for(j = 0;j < 9;j++){

22????????????if(m[i] >= 4) sum += dp[i][j];//訪問點超過4個,則為可行路線,累加至答案

23????????????for(k = 0;k < 9;k++) {

24????????????????if(take(i,k) == 0) {

25????????????????????if(check(j,k,i))

26????????????????????????dp[i+(1<<k)][k] += dp[i][j];

27????????????????}

28????????????}

29????????}

30????}

31????printf("The total number of Andriod is : %dn",sum);

32}

帶高亮看著更養眼的代碼點這裡:shaidaima.com/source

運行的結果:

【孫立的回答(14票)】:

我不欣賞@劉中陽@TangWei熱心推薦的《智能手機的密碼總共有多少種》這種缺乏思考的窮舉法,而且這個問題也挺有趣,所有我自己動手編程序計算,結果發現這個問題並不像看起來那麼難,程序的核心邏輯甚至不到10行代碼(Python)。 先看一下我的計算結果。

相鄰的點細分有2類,以上圖1號點為例:藍色箭頭所指的是直觀的、大部分人用的近點,紅色箭頭所指的是不直觀的、很少人用的遠點。我分別計算了只用近點(下圖藍色方塊)和用全部點(下圖紅色方塊)、從1點到9點的各種長度下,一共能有多少種形狀組合,匯總在下圖中。

從圖中可以看出來,只用近點的組合(我稱為「懶惰」組合)遠遠少於用全部點的組合,如果再只用4個或5個點,這樣的密碼安全性並不高。為了密碼安全,我推薦您使用8點全部組合方式。

再看一下我的程序結構,我用Python語言根據經典「圖」算法(單向、無權重)來計算這個3*3的9點矩陣:9個點從1到9編號(源程序第5行);每個點預設相應的鄰居點(源程序第8~18行);函數scan(源程序第44~52行)從任意一點起遞歸搜索所有可能的組合;函數log(源程序第37~41行)用文本樹格式記錄找到的組合;主程序(源程序第55~57行)針對9個不同的起點調用scan函數9次,最後打印計算結果。

我已經把這個小程序的Python源碼和計算出來的全部組合上傳到GitHub,請去我的個人網站?mrsunli.com/2012查看、下載或修改。

最後還有個小遺憾:我的這個小程序算法複雜度有點高 O(n!),不知道組合數學有沒有更好的辦法來分析這個問題。

轉自:mrsunli.com/2012?

【劉中陽的回答(7票)】:

Android 有389 112 種密碼。

摘自matrix67大神著作:《智能手機的密碼總共有多少種》

傳送門:guokr.com/article

【TangWei的回答(4票)】:

果殼上的 matrix67 已經給出解答了:

Android 有389 112 種密碼

把點陣中的九個點分別用數字 1 到 9 編號。按照上述規則,4136、4192 都是不合法的,但 24136、654192 則都是可行的。死理性派這下苦惱了,似乎五花八門的組合數學模型在這裡都派不上用場。怎麼辦呢?別急,我們還有強大的計算機幫忙。下面,有請編輯最愛的數學軟件 Mathematica 登場。

首先,讓我們生成所有 985 824 種沒有限制的排列組合:

再記下不能直接連接的點對:?

由此生成不合法的排列規則:?

從全部排列組合中刪掉不合法的,便得到了所有可能的 Android 密碼了:?

Android 密碼一共有多少種可能性呢?讓我們來看看:?

這樣,我們就得到了一個準確的數字:在 Android 系統上一共有 389 112 種可能的密碼,只佔之前估計的密碼數上限的 1/3 左右。?

引用來源:果殼?guokr.com/article

【Edison Huang的回答(0票)】:

拋個磚吧:

4點:9*8*7*6

5點:9*8*7*6*5

6點:9*8*7*6*5*4

7點:9*8*7*6*5*4*3

8點:9*8*7*6*5*4*3*2

9點:9*8*7*6*5*4*3*2*1

標籤:-算法 -數學 -Android -組合數學(Combinatorics) -祝風翔


相關資源:





給我留言