Ich habe gerade diese interessante Frage von meinem Kollegen erhalten. Ich versuche es jetzt, aber in der Zwischenzeit dachte ich, ich könnte es hier teilen.
Wie viele gültige Passwörter sind mit dem auf dem Android-Startbildschirm angezeigten Passwortraster möglich? Mindestlänge des Passworts: 4 max: 9 (korrigieren Sie mich, wenn ich falsch liege)
Die vollständigen Kombinationen von 4 bis 9 unterscheidbaren Zahlen, abzüglich der Kombinationen, die ungültige "Sprünge" enthalten.
Die Regel für Android 3x3 Passwortraster:
ausnahmsweise ein Punkt
nicht über einen Punkt "springen" kann
Der Autor des ursprünglichen Beitrags verwendete Mathematica, um alle 985824 Kombinationen zu generieren.
Da es keinen "Sprung" gibt, sind mehrere Paare von aufeinander folgenden Punkten ungültig.
Löschen Sie alle ungültigen Kombinationen, um das Ergebnis zu erhalten.
Die Kombinationen für 4-zu-9-Punkte-Pfade sind jeweils 1624, 7152, 26016, 72912, 140704, 140704.
Die Referenz stammt aus guokr ein ähnlicher Standort Stack Exchange Skeptiker in Form von Blogs.
Ich weiß, dass diese Frage alt ist, aber ich habe sie in einem anderen Artikel beantwortet Frage (bevor ich diese Frage fand) mit einem Brute-Force-Ansatz in Python, so dass ich ihn hier für die Nachwelt hinzufüge:
pegs = {
1: {3:2, 7:4, 9:5},
2: {8:5},
3: {1:2, 7:5, 9:6},
4: {6:5},
5: {},
6: {4:5},
7: {1:4, 3:5, 9:8},
8: {2:5},
9: {1:5, 3:6, 7:8}
}
def next_steps(path):
return (n for n in range(1,10) if (not path or n not in path and
(n not in pegs[path[-1]]
or pegs[path[-1]][n] in path)))
def patterns(path, steps, verbose=False):
if steps == 0:
if verbose: print(path)
return 1
return sum(patterns(path+[n], steps-1) for n in next_steps(path))Sie können also alle # von Mustern für eine beliebige Anzahl von Schritten auflisten:
>>> [(steps, patterns([], steps)) for steps in range(1,10)]
[(1, 9),
(2, 56),
(3, 320),
(4, 1624),
(5, 7152),
(6, 26016),
(7, 72912),
(8, 140704),
(9, 140704)]
>>> sum(patterns([], steps) for steps in range(4,10))
389112Dies ist nicht die effizienteste Art der Lösung, denn man könnte Spiegelungen verwenden und nur 4*Ecke + 4*Mitte + 1*Mitte berechnen, z. B.:
>>> patterns([], 6) == 4*patterns([1], 5) + 4*patterns([2], 5) + patterns([5], 5)
True
Ich habe die Antwort mit einer rekursiven Suche erzwungen und eine größere Antwort gefunden, 487272. Der Algorithmus ist einfach: alles ausprobieren. Ich habe ihn hier unten zitiert. Ich habe keinen Fehler in meinem Code gefunden (aber ich bin nicht sehr geschickt mit C++). Sorry für den grammatikalischen Fehler ich bin nicht Englisch.
#include <iostream>
#include <stdlib.h>
using namespace std;
int combo; //counter
void research(int Ipoints /*number of points already took*/, bool Icheck[9]/*points matrix*/,int Ilast/*last took point*/,
int Icomboval/*combination representation, only for printing purpose*/, int deep/*number of iteration, only for printing purpose*/)
{
// int numcall = 0; //DEBUG
for( int i=0; i<9; i++) //Controlling every free point in search of a valid way to contimue
if( Icheck[i] == false )
{
//Just for security, coping every variable in a new variable. I don't know how c++ works but I will make it works
int points = Ipoints;
int last = Ilast;
int comboval = Icomboval;
bool check[9];
for( int j=0; j<9; j++)
check[j] = Icheck[j];
int e1,e2;
int middle = -1;
e1=i; e2=last; //Ccontrolling duble jumps
if( e1 == 0 && e2 == 2 ) middle = 1;
if( e1 == 3 && e2 == 5 ) middle = 4;
if( e1 == 6 && e2 == 8 ) middle = 7;
if( e1 == 0 && e2 == 6 ) middle = 3;
if( e1 == 1 && e2 == 7 ) middle = 4;
if( e1 == 2 && e2 == 8 ) middle = 5;
if( e1 == 0 && e2 == 8 ) middle = 4;
if( e1 == 6 && e2 == 2 ) middle = 4;
e2=i; e1=last; // in both way
if( e1 == 0 && e2 == 2 ) middle = 1;
if( e1 == 3 && e2 == 5 ) middle = 4;
if( e1 == 6 && e2 == 8 ) middle = 7;
if( e1 == 0 && e2 == 6 ) middle = 3;
if( e1 == 1 && e2 == 7 ) middle = 4;
if( e1 == 2 && e2 == 8 ) middle = 5;
if( e1 == 0 && e2 == 8 ) middle = 4;
if( e1 == 6 && e2 == 2 ) middle = 4;
if((middle != -1) && !(check[middle])) {
check[middle] = true;
points++; //adding middle points
comboval *= 10;
comboval += middle;
}
check[i] = true;
points++; // get the point
comboval*=10;
comboval += i+1;
if(points > 3)
{
combo++; // every iteration over tree points is a valid combo
// If you want to see they all, beware because printing they all is truly slow:
// cout << "Combination n. " << combo << " found: " << comboval << " , points " << points << " with " << deep << " iterations\n";
}
if(points > 9) //Just for sure, emergency shutdown,
{ exit(1); }
research(points,check,i,comboval,deep+1); /*Recursive, here is the true program!*/
// numcall++; //DEBUG
}
// cout << "Ended " << deep << " , with " << numcall << " subs called\n"; // Only for debug purposes,remove with all the //DEBUG thing
}
int main ()
{
combo = 0; //no initial knows combo
bool checkerboard[9];
for( int i=0; i<9; i++) checkerboard[i]=false; //blank initial pattern
research(0/*no point taken*/,checkerboard,-1/*just a useless value*/,0/*blank combo*/,1/*it's the firs iteration*/); //let's search!
cout << "\n" ;
cout << "And the answer is ... " << combo << "\n"; //out
char ans='\0';
while(ans=='\0')
{ //just waiting
cin >> ans;
}
return 0;
}
Ich habe gerade einen Python-Code ausgeführt, um mögliche Kombinationen zu erhalten Ich habe 985824 Möglichkeiten
from itertools import permutations
numbers = "123456789"
total_combos = list(permutations(numbers,4))+list(permutations(numbers,5))+list(permutations(numbers,6))+list(permutations(numbers,7))+list(permutations(numbers,8))+list(permutations(numbers,9))
print(len(total_combos))
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
