手機的九宮格圖案解鎖總共能繪出多少種圖案？
需要滿足的要求有：
至少經過四個點；
不能重複經過同一個點；
路徑上的中間點不能跳過（如從1到3一定會經過2）；
如果中間的點是之前已經用過的，那麼這個點就可以被跳過（如213，因為2已經被用過，1就可以越過2與3連接，132是不允許的）。
from itertools import chain, permutations
impossible = {"13": "2",
"46": "5",
"79": "8",
"17": "4",
"28": "5",
"39": "6",
"19": "5",
"37": "5",
"31": "2",
"64": "5",
"97": "8",
"71": "4",
"82": "5",
"93": "6",
"91": "5",
"73": "5"}
def counts():
iterlst = chain(*(permutations("123456789", i) for i in range(4, 10)))
count = 0
for i in iterlst:
stri = "".join(i)
for k, v in impossible.items():
if k in stri and v not in stri[:stri.find(k)]:
break
else:
count += 1
return count
print(counts())#389112
我用python寫了段代碼，先計算出所有大於四個數字的所有排列組合，然後從中剃除穿過中間那個數字的組合，剩下的既為符合要求的代碼。
例如13組合是不可能存在的，因為它會穿過2，19組合也不可能存在，因為它會穿過5，總共有16個這樣的組合。
但是假如中間這個數字已經用過了，是可以穿過的，比如213，2已經用過了，1是可以穿過2與3連接的。
如此篩選以後，就得到正確答案389112了。
以下引用自果殼網：智能手機的密碼總共有多少種
Android 的密碼是 3 × 3 點陣中的一條路徑，這條路徑可以交叉，可以「走日字」，幾乎是無所不能（只要不經過重複點），但卻有一個例外：路徑不允許跳過途中必須要經過的點。例如， 如果從左上角的點連接到右上角的點，中間的那個點會被自動地加進路徑里。但麻煩就麻煩在，這個規則本身也有一個值得注意的地方：如果中間的點是之前已經用過的，那麼這個點就可以被跳過去了。
我們不妨把點陣中的九個點分別用數字 1 到 9 編號。按照上述規則，4136、4192 都是不合法的，但 24136、654192 則都是可行的。死理性派這下苦惱了，似乎五花八門的組合數學模型在這裡都派不上用場。怎麼辦呢？別急，我們還有強大的計算機幫忙。下面，有請編輯最愛的數學軟體 Mathematica 登場。
首先，讓我們生成所有 985 824 種沒有限制的排列組合：
再記下不能直接連接的點對：
由此生成不合法的排列規則：
從全部排列組合中刪掉不合法的，便得到了所有可能的 Android 密碼了：
Android 密碼一共有多少種可能性呢？讓我們來看看：
這樣，我們就得到了一個準確的數字：在 Android 系統上一共有 389 112 種可能的密碼，只佔之前估計的密碼數上限的 1/3 左右。
@linkwun 的代碼寫的非常漂亮. 他的評論區有不少人在稱讚Python代碼是多麼地簡潔和優秀, 並且順代吐糟了一下C. 但是我想說的是其實現在C++委員會的目標是語言更加簡單化、智能化, 向更現代的語言靠近. 我先寫了一個利用深度優先查找實現的程序:
#include &
#include &
#include &
#include &
#include &
using namespace std;
unsigned int state_count = 0;
vector&
{ 5 },
{ 2, 5, 6 },
{ 5 },
{},
{ 5 },
{ 4, 5, 8 },
{ 5 },
{ 5, 6, 8 } };
vector&
{ 8 },
{ 1, 7, 9 },
{ 6 },
{},
{ 4 },
{ 1, 3, 9 },
{ 2 },
{ 1, 3, 7 } };
vector&
{ 1, 3, 4, 6, 7, 9 },
{ 4, 8 },
{ 1, 2, 3, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 7, 8, 9 },
{ 2, 6 },
{ 1, 3, 4, 6, 7, 9 },
{ 2, 4 } };
struct State {
vector&
vector&
State() : flags(9U, false) {}
State(const State _other) : flags(9U, false) { *this = _other; }
State(const State _other) :flags(9U) { *this = _other; }
State operator=(const State _other) {
preceding_path.clear();
copy(_other.preceding_path.begin(), _other.preceding_path.end(), back_inserter(preceding_path));
copy(_other.flags.begin(), _other.flags.end(), flags.begin());
return *this;
}
State operator=(const State _other) {
preceding_path.clear();
flags.clear();
preceding_path = move(_other.preceding_path);
flags = move(_other.flags);
return *this;
}
vector& 大部C/C++的回答者都是這個思路, 這也是很多人對這個問題的第一反應了. 但是linkwun提供了一個非常巧妙的作法, 大大地簡化了代碼, 原理是利用itertools工具包, 並且用字典巧妙地解決了問題. 其實在C++中利用各種標準庫的函數, 我們也可以簡潔地寫出緊湊和優雅的代碼. 參考linkwun的思路整理C++代碼如下: 這樣看來, C++是不是也很"短小"呢?哈哈 其實Python的chain函數,in關鍵字和分片是讓代碼縮短的主要原因, C++要在這上面花上不少功夫.
vector&
char back = preceding_path.back();
vector&
for (auto i = 0U; i &< ac.size(); ++i) {
if (!flags[ac[i] - 1]) {
res.push_back(ac[i]);
}
}
vector&
vector&
for (char i = 0; i &< (char)jpb.size(); ++i) {
if (flags[jpb[i] - 1]) {
if (!flags[jpd[i] - 1]) {
res.push_back(jpd[i]);
}
}
else {
res.push_back(jpb[i]);
}
}
return res;
}
void push_path(char _node) {
preceding_path.push_back(_node);
flags[_node - 1] = true;
}
};
list&
void dfs() {
while (!stack.empty()) {
auto front = move(stack.front());
stack.pop_front();
if (front.preceding_path.size() &> 3)++state_count;
vector&
if (res.size() == 0)continue;
else {
for (const auto ele : res) {
State new_state{ front };
new_state.push_path(ele);
stack.emplace_front(new_state);
}
}
}
}
int main() {
auto s = chrono::system_clock::now();
for (char i = 1; i&<10; ++i) {
State state;
state.push_path(i);
stack.emplace_back(state);
}
dfs();
cout &<&< state_count &<&< endl;
auto e = chrono::system_clock::now();
cout &<&< chrono::duration_cast&#include &
#include &
#include &
#include &
#include &
#include &
using namespace std;
vector&
"936","915", "735" };
string num{ "123456789" };
unsigned int valid_count = 0;
int main() {
auto s = chrono::system_clock::now();
vector&
map&
for (const auto ele : raw) {
string str{ ele };
imp[str.substr(0, 2)] = str[2];
}
for (auto i = 4; i &< 10; ++i) {
com.resize(9, false);
for (auto iter = com.end() - i; iter != com.end(); ++iter)*iter = true;
do {
string per;
for (auto j = 0; j &< 9; ++j) if (com[j])per.push_back(num[j]);
do {
bool valid = true;
for (auto iter = imp.begin(); iter != imp.end(); ++iter) {
auto pos = per.find(iter-&>first);
if (pos != string::npos per.substr(0, pos).find(iter-&>second) == string::npos) {
valid = false;
break;
}
}
if (valid)++valid_count;
} while (next_permutation(per.begin(), per.end()));
} while (next_permutation(com.begin(), com.end()));
}
cout &<&< valid_count &<&< endl;
auto e = chrono::system_clock::now();
cout &<&< chrono::duration_cast&
我來個R語言版本
我的計算過程如下：
(一)確定手勢密碼的規則
a)
按1至9編碼，則必須要4至9個數字。
b)
不能跳過中間的數字。不合法的情況：
c)
當中間的那個點是之前用過的，則這個點可以被跳過去。
(二)根據規則用R語言編程計算。
1)
首先，根據規則a）計算所有排列的上限。即：9×8×7×…×1+9×8×7×…×2+?+9×8×7×6=985624
2)
根據規則b),構造不合法的情況集合。
3)
結合規則b）和c），使用正則表達式函數，統計不合法的情況個數。
4)
排除不合法的情況個數，最終得到總共的合法手勢密碼個數為：389112.
我的R代碼如下（R代碼的效率有點低，運行耗時兩個小時左右）：
#載入需要的包
library(stringr)
library(dplyr)
library(gtools)
#######################
#生成所有的排列組合上限
#共9×8×7...×1 + 9*8*7*...*2 + ...+ 9*8*7*6 =
sum &<- 0
for(i in 1:6){
sum &<- sum+prod(i:9)
}
sum
#######################
## 生成所有的候選排列組合
x &<- c(1:9)
Permus &<- list()
Permus&<-lapply(9:4,function(i){
permutations(n = 9, r = i, v = x)
})
######################
# 把所有的排列情況矩陣轉換成字元串集，並轉換成一個字元串向量
matrix_to_string &<- function(inmat){
apply(inmat,1,paste,collapse = "")
}
strings&<-list()
strings&<-lapply(Permus, matrix_to_string)
strings&<-unlist(strings)
str(strings)
#####################
# 不合法的情況子集
Illegal&<-c("13","46","79","17","28","39",
"19","37","31","64","97","71",
"82","93","91","73")
CrossNum&<-as.character(c(2,5,8,4,5,6,5,5,2,5,8,4,5,6,5,5))
#####################
# 統計不合法的情況個數
for(i in 1:length(strings)){
for(j in 1:length(Illegal)){
IllegalCode&<-str_locate(string = strings[i],pattern = Illegal[j]) %&>%
unlist(.)
if(!is.na(IllegalCode[1]) (!str_detect((str_sub(string = strings[i],end = IllegalCode[1])),
CrossNum[j]))){
count &<- count + 1
break;
}
}
}
count
sum - count
用matlab寫了幾行算了下，答案是389112種。
s = struct("end_points", {"13"; "31"; "46"; "64"; "79"; "97"; "17"; ...
"71"; "28"; "82"; "39"; "93"; "37"; "73"; "19"; "91"}, ...
"mid_point", {"2"; "2"; "5"; "5"; "8"; "8"; "4"; "4"; "5"; ...
"5"; "6"; "6"; "5"; "5"; "5"; "5"});
num = 0;
for i = 4:9
c = nchoosek("123456789", i);
for j = 1:size(c, 1)
p = perms(c(j, :));
for k = 1:size(p, 1)
n = 0;
for l = 1:size(s, 1)
if ~isempty(strfind(p(k, :), s(l).end_points)) ...
isempty(strfind(p(k, (1:(strfind(p(k, :), ...
s(l).end_points) - 1))), s(l).mid_point))
break
end
n = n + 1;
end
if n == l
num = num + 1;
end
end
end
end
安卓手機圖案解鎖共389112種（僅供參考）
手機九宮格圖案解鎖也擁有一定的規則，具體來說是：
1.至少經過四個點
2.不能重複經過同一個點
3.路徑中間的點不能跳過（比如從1至3必須經過2）除非中間點被使用過。
如圖：
考慮到上述運行規則，可以用計算機寫一段代碼進行運算，而最後得出的答案為389112種，這個答案獲得了普遍的認可。當然，其實對於Android來說，連通6個點的安全性已經足夠強了，至於是否需要把手指用到抽筋，繪製極為複雜的圖案，完全就看個人喜好和能力了。
因為訪問過的 pattern的state和順序無關，記住求過的state會快很多。用一個int的低9位表示當前訪問過的數字狀態，再加上前一個訪問的數字構成當前的state編碼，編碼的範圍是[ 0, 9 * 2^9]。
numberOfPatterns函數中m為pattern最小長度，n為最大長度。 // check if the ith number is visited or not
bool isVisited(int i, int table) {
return table (1 &<&< i);
}
bool isValidMove(int cur, int pre, int table) {
if (isVisited(cur, table)) return false;
// no number has been used or no gap, then is a valid move
int rowSum = cur/3 + pre/3;
int colSum = cur%3 + pre%3;
if (table == 0 || rowSum % 2 || colSum % 2) return true;
// if there is a gap
int mid = rowSum/2*3 + colSum/2;
return isVisited(mid, table);
}
// recursion
int patternNum(int m, int n, int curLen, int visitedTable, int pre, vector&
if (curLen == n) return 1;
// search cached state
int stateCode = visitedTable + (pre &<&< 9);
if (cache[stateCode] &> 0) return cache[stateCode];
int count = (m &<= curLen) ? 1 : 0;
for (int i = 0; i &< 9; ++i) {
if (isValidMove(i, pre, visitedTable)) {
count += patternNum(m, n, curLen + 1, visitedTable | (1 &<&< i), i, cache);
}
}
cache[stateCode] = count;
return count;
}
int numberOfPatterns(int m, int n) {
vector&
return patternNum(m, n, 0, 0, 4, cache);
}
終於有機會見識了聰明的程序員們究竟是怎麼一群人。 你們真棒！
貼個c代碼，輕拍
#include &
int res[1000000][10];
int cnt=0,t=0;
int genarry(int*a,int n[9],int l,int s){
int i;
if(l==0){
for(i=0;i&
}
else
for(i=0;i&<9;i++){
if(n[i]==0)continue;
*a=i+1;
n[i]=0;
genarry(a+1,n,l-1,s);
n[i]=1;
}
return 0;
}
int select(){
int taboo[16][2]={
{1,3},{3,1},
{4,6},{6,4},
{7,9},{9,7},
{1,7},{7,1},
{2,8},{8,2},
{3,9},{9,3},
{1,9},{9,1},
{3,7},{7,3}
};
int i;
for(i=0;i&
for(j=0;res[i][j+1]!=0!flag;j++){
int k;
for(k=0;k&<16!flag;k++){
if(res[i][j]==taboo[k][0]res[i][j+1]==taboo[k][1]){
int l;
flag=1;
for(l=0;l&
}
if(flag){
t++;
res[i][9]=-1;
}
}
}
}
}
return cnt-t;
}
int main(){
int a[9],n[9],i,count;
for(i=0;i&<9;i++)n[i]=1;
for(i=4;i&<10;i++)
genarry(a,n,i,i);
count=select();
printf("%d
",count);
return 0;
}
nums = range(1, 10)
ngraph = {
(1, 3): 2, (1, 7): 4, (1, 9): 5,
(2, 8): 5,
(3, 1): 2, (3, 7): 5, (3, 9): 6,
(4, 6): 5,
(6, 4): 5,
(7, 1): 4, (7, 3): 5, (7, 9): 8,
(8, 2): 5,
(9, 1): 5, (9, 3): 6, (9, 7): 8
}
def permutation():
ret = {i: 0 for i in range(4, 10)}
def perm(which, what, n):
nums[which], nums[what] = nums[what], nums[which]
if which + 1&>= n:
ret[n] += 1
else:
for i in range(which+1, 9):
key = (nums[i], nums[which])
if key not in ngraph or ngraph[key] in nums[:which]:
# 如果i和which指向的點可以直連，
# 或者不可以直連但是連接這兩個點必定會經過的點已經被使用，
# 則這個手勢可以進行下去，否則不能
perm(which+1, i, n)
nums[which], nums[what] = nums[what], nums[which]
for n in range(4, 10):
for i in range(9):
perm(0, i, n)
return ret
a9n = permutation()
print(a9n)
print(sum(a9n.values()))
結果：{4: 1624, 5: 7152, 6: 26016, 7: 72912, 8: 140704, 9: 140704}
389112
貼一個JAVA代碼:
public static void main(String[] args) {
int res=counts();
System.out.println(res);
}
public static int counts(){
HashMap&
ArrayList&
for(int i=4;i&<=9;i++){
permute.addAll(permutation(9,i));
}
System.out.println(permute.size());
map.put("13", "2");
map.put("46", "5");
map.put("79", "8");
map.put("17", "4");
map.put("28", "5");
map.put("39", "6");
map.put("19", "5");
map.put("37", "5");
map.put("31", "2");
map.put("64", "5");
map.put("97", "8");
map.put("71", "4");
map.put("82", "5");
map.put("93", "6");
map.put("91", "5");
map.put("73", "5");
int count = permute.size();
for(String cur :permute){
for (Entry&
String key = entry.getKey();
String value = entry.getValue();
if(cur.contains(key) (cur.indexOf(value) == -1 || cur.indexOf(value) &> cur.indexOf(key)) ){
count--;
break;
}
}
}
return count;
}
public static ArrayList&
ArrayList&
for(int i =1;i&<=n;i++){
StringBuilder temp= new StringBuilder();
temp.append(i);
BFS(n,k,temp,1,i,res);
}
return res;
}
public static void BFS(int n, int k,StringBuilder cur,int depth, int x,ArrayList&
if(depth == k){
res.add(new String(cur));
return;
}
for(int i=1;i&<=n;i++){
if(cur.indexOf(String.valueOf(i)) &>=0) continue;
cur.append(i);
BFS(n,k,cur,depth+1,i,res);
cur.deleteCharAt(cur.length()-1);
}
}
我是來比誰的程序更簡單的...
#include&
#define ABS(a) (((a)&>=0)?(a):-(a))
#define HALF(a,b) ((a)%3 + (b)%3)/2 + 3*(((a)/3 + (b)/3)/2)
bool flags[9]={true,true,true,true,true,true,true,true,true};
bool check(int a,int b)
{
if(a%3 == b%3 ABS(a/3 - b/3) == 2 flags[HALF(a,b)])return false;
if(a/3 == b/3 ABS(a%3 - b%3) == 2 flags[HALF(a,b)])return false;
if(ABS(a%3 - b%3) == 2 ABS(a/3 - b/3) == 2 flags[HALF(a,b)])return false;
return true;
}
int count(int j,int pre,int counter)
{
for(int i=0;i&<9;i++){
if(flags[i] check(pre,i)){
flags[i] = false;
counter = count(j+1,i,counter);
flags[i] = true;
}
}
return (j&>2)?counter + 1:counter;
}
int main()
{
flags[0] = false;
int a = count(0,0,0)*4;
flags[1] = false;flags[0] = true;
int b = count(0,1,0)*4;
flags[4] = false;flags[1] = true;
int c = count(0,4,0);
printf("%d
",a+b+c);
return 0;
}
根據對稱性做了優化。
pascal語言不知有誰知道沒有...
var flag:array[0..9]of boolean; plus:array[0..9,0..9]of longint;
ans,i:longint;
procedure search(t,count,pre:longint);
var k:longint;
begin
if count=t then begin inc(ans);exit; end
else if count&>t then exit;
for k:=1 to 9 do
if flag[k] and not(flag[plus[pre,k]] or flag[plus[k,pre]]) then
begin
flag[k]:=false;
search(t,count+1,k);
flag[k]:=true;
end
else if flag[k] and (flag[plus[pre,k]] or flag[plus[k,pre]]) //middle does not used
then continue;
end;
begin //MAIN
fillchar(flag,sizeof(flag),true);
flag[0]:=false;
fillchar(plus,sizeof(plus),0);
plus[1,3]:=0;
plus[7,9]:=8;
plus[1,7]:=4;
plus[2,8]:=5;
plus[9,3]:=6;
plus[1,9]:=5;
plus[3,7]:=5;
plus[4,6]:=5;
ans:=0;
for i:=4 to 9 do
search(i,0,0);
writeln(ans);
end.
dfs代碼，用標記數組標記不合法的情況，在所有的排列裡面剔除不合法的情況，暴力枚舉。
#include&
#include&
using namespace std;
int mark[10][10], vis[20];
int num[20], ans = 0, lim;
void dfs(int cnt)
{
if(cnt &>= 5)
{
ans++;
}
for(int i = 1; i&<=9; i++)
{
if(!vis[i])
{
if(mark[i][num[cnt-1]] !vis[mark[i][num[cnt-1]]])
continue;
num[cnt] = i;
vis[i] = 1;
dfs(cnt+1);
vis[i] = 0;
}
}
}
int main()
{
num[0] = 0;
memset(mark, 0, sizeof(mark));
mark[1][3] = 2, mark[1][7] = 4, mark[1][9] = 5;
mark[2][8] = 5, mark[3][7] = 5, mark[3][9] = 6;
mark[4][6] = 5, mark[7][9] = 8;
for(int i = 1; i&<=9; i++)
for(int j = i+1; j&<=9; j++)
mark[j][i] = mark[i][j];
memset(vis, 0, sizeof(vis));
dfs(1);
cout&<& return 0;
}
是389112種
用 Ruby 來一波騷操作。
neighbours = [
nil, # placeholder
[[2, 4, 5], [6, 8]], #1
[[5], [1, 3, 4, 6, 7, 9]], #2
[[2, 5, 6], [4, 8]], #3
[[5], [1, 2, 7, 8, 3, 9]], #4
[[], [1, 2, 3, 4, 6, 7, 8, 9]], #5
[[5], [2, 3, 8, 9, 1, 7]], #6
[[4, 5, 8], [2, 6]], #7
[[5], [4, 6, 7, 9, 1, 3]], #8
[[5, 6, 8], [2, 4]] #9
]
ways = 0
define_method :traverse do |visited|
ways += 1 if visited.count &>= 4
neighbours[visited.last][0].map { |n|
if visited.include? n then 2 * n - visited.last else n end
}.concat(neighbours[visited.last][1]).reject { |n|
visited.include? n
}.each { |a|
traverse(visited + [a])
}
end
(1..9).each do |i|
traverse([i])
end
puts ways
順便吐槽一下知乎對 Firefox 的支持是真的爛。
https://www.rvfu98.com/
我一直想把自己的學到的知識運用起來，那樣的話才是自己的知識。我記得在上高中的時候，當時我們學習排列組合，我當時就有一個想法，就是把手機九宮格的解鎖的可能的情況算出來。不過當時還是中學的我，在努力了很長時間之後還是放棄了。複雜的等價情況以及一團亂麻的情況讓我感到無從下手。但是今天的時候我突然想到了這個問題，然後又想到了我剛剛入門的C++，不自覺的覺得有點靈感。然後就寫了一個小程序解決這個問題。
解決的思維比較簡單，感謝現代CPU的運行速度。我寫的這個程序很簡單，只要有基本C++知識就能看懂，因為我的C++知識就是基本的。
1.對九宮格裡面的圖案進行編號
2.窮舉所有可能的情況
3.去掉不符合的情況
- 有重複數字的情況
- 兩個相鄰的不能直接相鄰的情況（至於這個不理解的看下面的解釋）
對於上面情況的解釋：
比如說0和6是不能相鄰的，0和8頁也是不能相鄰的，這是因為中間的3和4是不能跳過的。
換一種理解方式就是兩點可以構成一條直線。在這裡我們可以把直線理解成由三個點構成，包括的情況有橫豎斜三種情況，當這三個點裡面的兩個端點相鄰時就說明出現了錯誤。
注意：綜合以上兩種情況，就出現了第三種情況。比如說，當0和6相鄰時是我們應該捨去的情況，但是當在0和6之前出現了3的話，那麼就可以保留這種情況了。
//
// main.cpp
// how_many
//
// Created by rvfu98 on 6/16/17.
// Copyright ? 2017 rvfu98.com All rights reserved.
//
#include &
#include &
#include &
using namespace std;
//函數聲明
bool repeat(int*, int);
bool beside(int* ,int);
bool isBefore (int*, int, int);
int main(){ ======== 2017年9月26日 看來還是要學習一下。。。。
clock_t start,finish;
double totaltime;
start=clock();
int a[10], temp, count = 1, i, j, k, tt;
for (tt=4; tt&<10; tt++){
//遍歷所有可能的結果
for (i=0; i&
前天剛搞完這個
c#來懟一發
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp1 {
class Program {
static int sum;
static int[] nsum = new int[10];
static bool[] used = new bool[10];
static int[,] mid = new int[10, 10];
static int[] res = new int[10];
static FileStream fs;
static StreamWriter sw;
/// &
/// &
int i, j;
for (i = 0; i &< 10; i++) {
for (j = 0; j &< 10; j++) mid[i, j] = 0;
}
mid[1, 3] = 2;
mid[1, 7] = 4;
mid[1, 9] = 5;
mid[2, 8] = 5;
mid[3, 1] = 2;
mid[3, 7] = 5;
mid[3, 9] = 6;
mid[4, 6] = 5;
mid[6, 4] = 5;
mid[7, 1] = 4;
mid[7, 3] = 5;
mid[7, 9] = 8;
mid[8, 2] = 5;
mid[9, 1] = 5;
mid[9, 3] = 6;
mid[9, 7] = 8;
used[0] = true;
//界面
Console.CursorLeft = 2;
Console.CursorTop = 2;
Console.Write("X X ...");
for (i = 4; i &< 10; i++) {
Console.CursorLeft = 16;
Console.CursorTop = i - 2;
Console.Write("{0} : ", i);
}
Console.CursorLeft = 16;
Console.CursorTop = i - 1;
Console.Write("sum : ");
}
static void PrRe(int num) {
int i;
sum++;
sw.Write(sum.ToString("0000000"));
sw.Write(" : ");
for (i = 1; i &< num; i++) {
sw.Write(res[i]);
sw.Write(" - ");
}
sw.WriteLine(res[i]);
sw.Flush();
nsum[num]++;
if (nsum[num] % 1000 == 0 || sum % 5000 == 0) {
Console.CursorLeft = 2;
Console.CursorTop = 2;
Console.Write("{0} {1} ...", res[1], res[2]);
for (i = 4; i &< 10; i++) {
Console.CursorLeft = 20;
Console.CursorTop = i - 2;
Console.Write(nsum[i]);
}
Console.CursorLeft = 22;
Console.CursorTop = i - 1;
Console.Write(sum);
}
}
/// &
/// &
當前點序號& /// &
當前深度&
static void DFS(int nownode, int deep) {
//deep check
if (deep &>= 4) {
res[deep] = nownode;
PrRe(deep);
}
if (deep == 9) return;
used[nownode] = true;
int i;
res[deep] = nownode;
for (i = 1; i &<= 9; i++) {
if (used[i]) continue;
if (used[mid[nownode, i]]) {
DFS(i, deep + 1);
}
}
used[nownode] = false;
return;
}
static void Main(string[] args) {
fs = new FileStream("re.txt", FileMode.OpenOrCreate);
sw = new StreamWriter(fs, Encoding.UTF8);
Init();
int i;
for (i = 1; i &< 10; i++) {
res[1] = i;
DFS(i, 1);
}
Console.CursorLeft = 2;
Console.CursorTop = 2;
Console.Write("{0} {1} ...", res[1], res[2]);
for (i = 4; i &< 10; i++) {
Console.CursorLeft = 20;
Console.CursorTop = i - 2;
Console.Write(nsum[i]);
}
Console.CursorLeft = 22;
Console.CursorTop = i - 1;
Console.Write(sum);
sw.Close();
fs.Close();
Console.ReadLine();
}
}
}
左邊是表示當前搜的前兩位
右邊表示當前的長度為多少的結果是幾
sum：當前的總和
我的程序會向工作目錄下的re.txt寫入結果，不需要的話自行注釋掉相應代碼
這是一道比較簡單的深度遍歷的題目，答案是389112。雖然已經有很多人貼了答案，我還是貼出我的java版，寫的比較簡單，一步一步的，沒有多高的演算法：
public class Main {
static int[][] a= new int[10][10];
public static void main(String[] args) {
a[1][3] = 2;
a[4][6] = 5;
a[7][9] = 8;
a[1][7] = 4;
a[2][8] = 5;
a[3][9] = 6;
a[1][9] = 5;
a[3][7] = 5;
a[3][1] = 2;
a[6][4] = 5;
a[9][7] = 8;
a[7][1] = 4;
a[8][2] = 5;
a[9][3] = 6;
a[9][1] = 5;
a[7][3] = 5;
System.out.println(f(4,"") + f(5,"") +f(6,"") +f(7,"") +f(8,"") +f(9,""));
}
private static int f(int tar, String result) {
int sum = 0;
if(tar == 0)
return 1;
for(int i=1;i&<=9;i++){
if(result.contains(i+""))
continue;
if(result.length()&>0){
int x = result.charAt(result.length()-1)-"0";
if(a[x][i]&>0 !result.contains(a[x][i]+""))
continue;
}
sum += f(tar-1, result + i);
}
return sum;
}
}
求大佬解答6*6的_(:з」∠)_
推薦閱讀：
※什麼是動態規劃？動態規劃的意義是什麼？
※PRML為何是機器學習的經典書籍中的經典？
※1000桶水，其中一桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？
※想學好計算機演算法，是否需要重新學數學呢?
※只用你的十隻手指，你能表達多少數字？