Trouvez tous les numéros de vampire à 4 chiffres

Ou vous pouvez utiliser une propriété de numéros de vampire décrite sur cette page (liée à Wikipedia):

Un résultat théorique important trouvé par Pete Hartley:

  If x·y is a vampire number then x·y == x+y (mod 9) 

Preuve: Soit mod l’opérateur modulo binary et d (x) la sum des chiffres décimaux de x. Il est bien connu que d (x) mod 9 = x mod 9, pour tout x. Supposons que x · y est un vampire. Ensuite, il contient les mêmes chiffres que x et y, et en particulier d (x · y) = d (x) + d (y). Ceci conduit à: (x · y) mod 9 = d (x · y) mod 9 = (d (x) + d (y)) mod 9 = (d (x) mod 9 + d (y) mod 9) mod 9 = (x mod 9 + y mod 9) mod 9 = (x + y) mod 9

Les solutions à la congruence sont (x mod 9, y mod 9) dans {(0,0), (2,2), (3,6), (5,8), (6,3), (8, 5)}

Donc, votre code pourrait ressembler à ceci:

 for(int i=18; i<100; i=i+9){ // 18 is the first multiple of 9 greater than 10 for(int j=i; j<100; j=j+9){ // Start at i because as @sh1 said it's useless to check both x*y and y*x checkVampire(i,j); } } for(int i=11; i<100; i=i+9){ // 11 is the first number greater than 10 which is = 2 mod 9 for(int j=i; j<100; j=j+9){ checkVampire(i,j); } } for(int i=12; i<100; i=i+9){ for(int j=i+3; j<100; j=j+9){ checkVampire(i,j); } } for(int i=14; i<100; i=i+9){ for(int j=i+3; j<100; j=j+9){ checkVampire(i,j); } } // We don't do the last 2 loops, again for symmetry reasons 

Comme il y a 40 éléments dans chacun des ensembles comme {(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100} {(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100} , vous ne faites que 4*40 = 160 itérations, quand une force brute vous donne 10 4 itérations. Vous pouvez faire encore moins d'opérations si vous prenez en compte la contrainte >= 1000 , par exemple vous pouvez éviter de vérifier si j < 1000/i .

Maintenant, vous pouvez facilement évoluer pour trouver des vampires avec plus de 4 chiffres =)

Parcourez tous les crocs possibles (100 x 100 = 10000 possibilités) et trouvez si leur produit a les mêmes chiffres que les crocs.

Encore une autre version de la force brute (C), avec un sorting à bulles libre pour démarrer …

 #include  static inline void bubsort(int *p) { while (1) { int s = 0; for (int i = 0; i < 3; ++i) if (p[i] > p[i + 1]) { s = 1; int t = p[i]; p[i] = p[i + 1]; p[i + 1] = t; } if (!s) break; } } int main() { for (int i = 10; i < 100; ++i) for (int j = i; j < 100; ++j) { int p = i * j; if (p < 1000) continue; int xd[4]; xd[0] = i % 10; xd[1] = i / 10; xd[2] = j % 10; xd[3] = j / 10; bubsort(xd); int x = xd[0] + xd[1] * 10 + xd[2] * 100 + xd[3] * 1000; int yd[4]; yd[0] = p % 10; yd[1] = (p / 10) % 10; yd[2] = (p / 100) % 10; yd[3] = (p / 1000); bubsort(yd); int y = yd[0] + yd[1] * 10 + yd[2] * 100 + yd[3] * 1000; if (x == y) printf("%2d * %2d = %4d\n", i, j, p); } return 0; } 

Fonctionne presque instantanément. Les noms de variables ne sont pas trop descriptifs, mais devraient être assez évidents ...

L'idée de base est de commencer avec deux crocs potentiels, de les décomposer en chiffres et de sortinger les chiffres pour faciliter la comparaison. Ensuite, nous faisons la même chose avec le produit: divisez-le en chiffres et sortingez. Ensuite, nous reconstituons deux entiers à partir des chiffres sortingés, et s'ils sont égaux, nous avons une correspondance.

Améliorations possibles: 1) lancer j à 1000 / i au lieu de i pour éviter de devoir faire if (p < 1000) ... , 2) peut-être utiliser un sorting par insertion au lieu du sorting par bulles (mais qui va remarquer ces 2 swaps supplémentaires?) , 3) utiliser une véritable implémentation swap() , 4) comparer directement les tableaux plutôt que d'en créer un entier synthétique. Je ne suis pas sûr que l'un de ces éléments fasse une différence mesurable, à moins que vous ne l'exécutiez sur un Commodore 64 ou quelque chose du genre ...

Edit: Juste par curiosité, j'ai pris cette version et je l'ai généralisée un peu plus pour travailler sur les boîtiers à 4, 6 et 8 chiffres - sans optimisation majeure, elle peut trouver tous les numéros de vampire à 8 chiffres en moins de 10 secondes. .

C’est un hack moche (force brute, vérification manuelle des permutations, opérations de tampons non sécurisées, production de dupes, etc.) mais cela fait l’affaire. Votre nouvel exercice consiste à l’améliorer: P

Wikipédia prétend qu’il y a 7 numéros de vampire qui ont 4 chiffres. Le code complet les a tous trouvés , même des doublons.

Edit: Voici une fonction de comparaison légèrement meilleure.

Edit 2: Voici une version C ++ dont les résultats sont uniques (par conséquent, elle évite les doublons) en utilisant un std::map (et stocke la dernière occurrence du nombre de vampires avec ses facteurs). Cela répond également au critère selon lequel au moins un des facteurs ne devrait pas se terminer par 0 , c’est-à-dire qu’un nombre n’est pas un nombre de vampires si les deux multiplicands sont alors divisibles. Ce test recherche des numéros de vampire à 6 chiffres et il en trouve en effet exactement 148, conformément aux critères de Wikipedia.

Le code d’origine:

 #include  void getdigits(char buf[], int n) { while (n) { *buf++ = n % 10; n /= 10; } } int is_vampire(const char n[4], const char i[2], const char j[2]) { /* maybe a bit faster if unrolled manually */ if (i[0] == n[0] && i[1] == n[1] && j[0] == n[2] && j[1] == n[3]) return 1; if (i[0] == n[1] && i[1] == n[0] && j[0] == n[2] && j[1] == n[3]) return 1; if (i[0] == n[0] && i[1] == n[1] && j[0] == n[3] && j[1] == n[2]) return 1; if (i[0] == n[1] && i[1] == n[0] && j[0] == n[3] && j[1] == n[2]) return 1; // et cetera, the following 20 repetitions are redacted for clarity // (this really should be a loop, shouldn't it?) return 0; } int main() { for (int i = 10; i < 100; i++) { for (int j = 10; j < 100; j++) { int n = i * j; if (n < 1000) continue; char ndigits[4]; getdigits(ndigits, n); char idigits[2]; char jdigits[2]; getdigits(idigits, i); getdigits(jdigits, j); if (is_vampire(ndigits, idigits, jdigits)) printf("%d * %d = %d\n", i, j, n); } } return 0; } 

Je n’aurais pas abandonné si facilement la force brute. Vous avez un ensemble de chiffres distinct, 1000 à 9999, que vous devez parcourir. Je diviserais l’ensemble en un certain nombre de sous-ensembles, puis relèverais les threads pour gérer chaque sous-ensemble.

Vous pourriez diviser encore le travail à venir avec les différentes combinaisons de chaque nombre; IRC mon calcul discret, vous avez 4 * 3 * 2 ou 24 combinaisons pour chaque nombre à essayer.

Une approche producteur / consommateur peut être utile.

L’itération me semble bien, car il vous suffit de le faire une fois pour trouver toutes les valeurs et vous pouvez simplement les mettre en cache par la suite. Version Python (3) qui prend environ 1,5 seconde:

 # just some setup from itertools import product, permutations dtoi = lambda *digits: int(''.join(str(digit) for digit in digits)) gen = ((dtoi(*digits), digits) for digits in product(range(10), repeat=4) if digits[0] != 0) l = [] for val, digits in gen: for check1, check2 in ((dtoi(*order[:2]), dtoi(*order[2:])) for order in permutations(digits) if order[0] > 0 and order[2] > 0): if check1 * check2 == val: l.append(val) break print(l) 

Ce qui vous donnera [1260, 1395, 1435, 1530, 1827, 2187, 6880]

EDIT: force brute qui élimine les valeurs X et Y identiques …

 import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Vampire { public static void main(Ssortingng[] args) { for (int x = 10; x < 100; x++) { String sx = String.valueOf(x); for (int y = x; y < 100; y++) { int v = x * y; String sy = String.valueOf(y); String sv = String.valueOf(v); if (sortVampire(sx + sy).equals(sortVampire(sv))) { System.out.printf("%d * %d = %d%n", x, y, v); } } } } private static List sortVampire(Ssortingng v) { List vc = new ArrayList(); for (int j = 0; j < v.length(); j++) { vc.add(v.charAt(j)); } Collections.sort(vc); return vc; } } 

Version Brute Force en C # avec LINQ:

 class VampireNumbers { static IEnumerable numberToDigits(int number) { while(number > 0) { yield return number % 10; number /= 10; } } static bool isVampire(int first, int second, int result) { var resultDigits = numberToDigits(result).OrderBy(x => x); var vampireDigits = numberToDigits(first) .Concat(numberToDigits(second)) .OrderBy(x => x); return resultDigits.SequenceEqual(vampireDigits); } static void Main(ssortingng[] args) { var vampires = from fang1 in Enumerable.Range(10, 89) from fang2 in Enumerable.Range(10, 89) where fang1 < fang2 && isVampire(fang1, fang2, fang1 * fang2) select new { fang1, fang2 }; foreach(var vampire in vampires) { Console.WriteLine(vampire.fang1 * vampire.fang2 + " = " + vampire.fang1 + " * " + vampire.fang2); } } } 

Semblable à quelqu’un mentionné ci-dessus, ma méthode consiste à trouver d’abord toutes les permutations d’un nombre, puis à les diviser en deux pour former deux nombres à deux chiffres et à tester si leur produit est égal au nombre d’origine.

Une autre discussion intéressante ci-dessus est combien de permutations un nombre peut avoir. Voici mon opinion: (1) un nombre dont les quatre numériques sont identiques a 1 permutation; (2) un nombre qui n’a que deux chiffres différents a 6 permutations (cela n’a pas d’importance s’il contient des zéros, car nous ne nous soucions pas de la permutation s’il s’agit toujours d’un nombre à 4 chiffres); (3) un nombre qui a trois chiffres différents a 12 permutations; (4) un nombre avec les quatre chiffres différents a 24 permutations.

 public class VampireNumber { // method to find all permutations of a 4-digit number public static void permuta(Ssortingng x, Ssortingng s, int v) {for(int i = 0; i < s.length(); i++) {permuta( x + s.charAt(i), s.substring(0,i) + s.substring(i+1), v); if (s.length() == 1) {x = x + s; int leftpart = Integer.parseInt(x.substring(0,2)); int rightpart = Integer.parseInt(x.substring(2)); if (leftpart*rightpart == v) {System.out.println("Vampir = " + v); } } } } public static void main(String[] args){ for (int i = 1000; i < 10000; i++) { permuta("", Integer.toString(i), i); //convert the integer to a string } } } 

L’approche que je voudrais essayer serait de parcourir chaque nombre dans [1000, 9999], et de tester si une permutation de ses chiffres (fractionnés au milieu) se multiplie pour le faire.

Cela nécessitera (9999 – 1000) * 24 = 215 976 tests, qui devraient s’exécuter rapidement sur une machine moderne.

Je voudrais certainement stocker les chiffres séparément, de sorte que vous pouvez éviter de faire quelque chose comme un tas de divisions pour extraire les chiffres d’un seul entier.

Si vous écrivez votre code de telle sorte que vous ne faites que des ajouts et des multiplications d’entiers (et peut-être même des divisions occasionnelles), cela devrait être assez rapide. Vous pouvez encore augmenter la vitesse en sautant des paires à deux chiffres qui, de toute évidence, ne fonctionneront pas – par exemple, celles avec des zéros en tête (notez que le plus grand produit peut être un nombre à un chiffre et un nombre à deux chiffres *) 99 ou 891).

Notez également que cette approche est extrêmement parallèle ( http://en.wikipedia.org/wiki/Embarrassingly_parallel ), donc si vous avez vraiment besoin de l’accélérer, vous devriez essayer de tester les nombres dans des threads séparés.

  doesnt match ABCD unset($product_digits[$array_serach($digits[$inc], $product_digits)]); $inc++; // If reached 4 -> vampire number if ($inc == 4) { $vampire[] = $product; break; } } } } // Print results print_r($vampire); ?> 

A pris moins d’une seconde sur PHP. ne pouvait même pas dire qu’il devait exécuter 8100 calculs … les ordinateurs sont rapides!

Résultats:

Vous donne tous les 4 chiffres et certains sont répétés. Vous pouvez poursuivre le traitement des données et supprimer les doublons.

Il me semble que pour effectuer le moins de tests possibles sans avoir recours à des idées particulièrement abstraites, vous voudrez probablement parcourir les crocs et éliminer tous les candidats manifestement inutiles.

Par exemple, puisque x*y == y*x environ la moitié de votre espace de recherche peut être éliminé en n’évaluant que les cas où y > x . Si le plus grand fang à deux chiffres est 99, le plus petit qui peut faire un nombre à quatre chiffres est 11, donc ne commencez pas par moins de 11.

MODIFIER:

OK, jetant tout ce que je pensais dans le mix (même si cela semble idiot contre la solution leader).

 for (x = 11; x < 100; x++) { /* start y either at x, or if x is too small then 1000 / x */ for (y = (x * x < 1000 ? 1000 / x : x); y < 100; y++) { int p = x * y; /* if sum of digits in product is != sum of digits in x+y, then skip */ if ((p - (x + y)) % 9 != 0) continue; if (is_vampire(p, x, y)) printf("%d\n", p); } } 

et le test, puisque je n'ai encore vu personne utiliser un histogramme:

 int is_vampire(int p, int x, int y) { int h[10] = { 0 }; int i; for (i = 0; i < 4; i++) { h[p % 10]++; p /= 10; } for (i = 0; i < 2; i++) { h[x % 10]--; h[y % 10]--; x /= 10; y /= 10; } for (i = 0; i < 10; i++) if (h[i] != 0) return 0; return 1; } 

1260 1395 1435 1530 1827 2187 6880 est vampire

Je suis nouveau dans la programmation … Mais il n’y a que 12 combinaisons pour trouver tous les numéros de vampire à 4 chiffres. Ma mauvaise réponse est:

 public class VampNo { public static void main(Ssortingng[] args) { for(int i = 1000; i < 10000; i++) { int a = i/1000; int b = i/100%10; int c = i/10%10; int d = i%10; if((a * 10 + b) * (c * 10 + d) == i || (b * 10 + a) * (d * 10 + c) == i || (a * 10 + d) * (b * 10 + c) == i || (d * 10 + a) * (c * 10 + b) == i || (a * 10 + c) * (b * 10 + d) == i || (c * 10 + a) * (d * 10 + b) == i || (a * 10 + b) * (d * 10 + c) == i || (b * 10 + a) * (c * 10 + d) == i || (b * 10 + c) * (d * 10 + a) == i || (c * 10 + b) * (a * 10 + d) == i || (a * 10 + c) * (d * 10 + b) == i || (c * 10 + a) * (b * 10 + d) == i) System.out.println(i + " is vampire"); } } } 

La tâche principale maintenant est de simplifier l'expression booléenne dans le bloc If ()

J’ai un peu modifié l’algorithme d’Owlstead pour le rendre plus compréhensible pour les débutants / apprenants Java.

 import java.util.Arrays; public class Vampire { public static void main(Ssortingng[] args) { for (int x = 10; x < 100; x++) { String sx = Integer.toString(x); for (int y = x; y < 100; y++) { int v = x * y; String sy = Integer.toString(y); String sv = Integer.toString(v); if( Arrays.equals(sortVampire(sx + sy), sortVampire(sv))) System.out.printf("%d * %d = %d%n", x, y, v); } } } private static char[] sortVampire (String v){ char[] sortedArray = v.toCharArray(); Arrays.sort(sortedArray); return sortedArray; } 

}

Ce code python est très rapide (O (n2))

 result = [] for i in range(10,100): for j in range(10, 100): list1 = [] list2 = [] k = i * j if k < 1000 or k > 10000: continue else: for item in str(i): list1.append(item) for item in str(j): list1.append(item) for item in str(k): list2.append(item) flag = 1 for each in list1: if each not in list2: flag = 0 else: list2.remove(each) for each in list2: if each not in list1: flag = 0 if flag == 1: if k not in result: result.append(k) for each in result: print(each) 

Et voici mon code. Pour générer des nombres de zombies, nous devons utiliser une classe aléatoire 🙂

 import java.io.PrintStream; import java.util.Set; import java.util.HashSet; import java.util.Iterator; class VampireNumbers { static PrintStream p = System.out; private static Set findVampireNumber() { Set vampireSet = new HashSet(); for (int y = 1000; y <= 9999; y++) { char[] numbersSeparately = ("" + y).toCharArray(); int numberOfDigits = numbersSeparately.length; for (int i = 0; i < numberOfDigits; i++) { for (int j = 0; j < numberOfDigits; j++) { if (i != j) { int value1 = Integer.valueOf("" + numbersSeparately[i] + numbersSeparately[j]); int ki = -1; for (int k = 0; k < numberOfDigits; k++) { if (k != i && k != j) { ki = k; } } int kj = -1; for (int t = 0; t < numberOfDigits; t++) { if (t != i && t != j && t != ki) { kj = t; } } int value21 = Integer.valueOf("" + numbersSeparately[ki] + numbersSeparately[kj]); int value22 = Integer.valueOf("" + numbersSeparately[kj] + numbersSeparately[ki]); if (value1 * value21 == y && !(numbersSeparately[j] == 0 && numbersSeparately[kj] == 0) || value1 * value22 == y && !(numbersSeparately[j] == 0 && numbersSeparately[ki] == 0)) { vampireSet.add(y); } } } } } return vampireSet; } public static void main(String[] args) { Set vampireSet = findVampireNumber(); Iterator i = vampireSet.iterator(); int number = 1; while (i.hasNext()) { p.println(number + ": " + i.next()); number++; } } }