Cette semaine, c'est M@xime qui vous propose un #KataOfTheWeek : Les nombres narcissiques
Briefing du Kata : Un nombre narcissique (ou nombre d'Armstrong de première espèce, ou — en anglais — PPDI, pour PluPerfect Digit Invariant) est un entier naturel n non nul qui est égal à la somme des puissances p-ièmes de ses chiffres en base dix, où p désigne le nombre de chiffres de n.
Par exemple tous les entiers de 1 à 9 sont narcissiques. Les dix termes suivants de la suite des 88 nombres narcissiques sont 153, 370, 371, 407, 1 634, 8 208, 9 474, 54 748, 92 727 et 93 084.
153 = 1³ + 5³ + 3³ (n = 153, p = 3)
93084 = 9⁵ + 3⁵ + 0⁵ + 8⁵ + 4⁵ (n = 93084, p = 5)
Le plus grand nombre narcissique connu est 115 132 219 018 763 992 565 095 597 973 971 522 401
Objectif : développer une fonction qui affiche les nombres narcissiques compris entre 0 et 9 999 999 999 999 999 999.
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur :
Dans ces solutions, nous n'allons pas raisonner par bornes de calcul mais par nombre de chiffres dans la borne maximale. Par exemple, si l'on souhaite retrouve les nombres narcissiques entre 0 et 999, il faudra passer 3 en paramètres à notre fonction.
La première solution qui vient en tête est une solution "brute force" qui suit la logique suivante :
- Pour chaque entier entre 1 et K :
- Diviser cet entier en ses chiffres qui le composent (153 -> [1, 5, 3])
- Calculer la puissance de chaque digit
- Sommer ces puissances
- Si la somme est égale au nombre de départ, ajouter ce chiffre au tableau des narcissique
- Retourner la liste
Le code se trouve dans la classe NarcissicBruteForce.
Je vous déconseille fortement d'essayer cette solution avec N > 20. Déjà avec 10 vous risquez d'attendre un petit moment
Une autre solution un peu plus belle consiste à voir les nombres comme un groupement de chiffres. On peut affirmer que pour un groupe de nombre donné, la somme de ces puissances et toujours la même qu'elle que soit l'ordre de ces digits.
Par exemple :
Si on prend le groupe de nombre [1, 5, 3], alors 1³ + 5³ + 3³ = 153 mais également 3³ + 5³ + 1³ = 153.
On peut donc affirmer que pour tous set de chiffres de taille 1 à N il existe une et une seule somme des puissances de ce groupe qui peut (ou pas) être égale au chiffre lui-même.
Par exemple : Pour le set [1, 5, 3], la somme des puissance fait 153 et toutes les combinaisons possible de ces chiffres sont 153, 135, 531, 513, 315, 351. Dans toute ces possiblités on retrouve 153.
Donc 153 est narcissique.
On parle de multi-set ici car dans un set, les digits peuvent être multiple ([2, 2, 5, 3])
L'algorithme peut se décomposer comme suit :
- Pour chaque longueur entre 1 et N
- Générer tous les multi-set possibles de N digits
- Pour chaque multi-set
- calculer la somme des chiffres à la puissance N
- Vérifier s'il est possible de représenter le nombre résultant de la somme à partir de TOUS les digits du multi-set
- Si on trouve une correspondance, ajouter le nombre à la liste de résultat
- Retourner la liste
Vous trouverez cette solution dans la classe NarcissicMultiSet.
Comparaison de complexité : Pour la méthode brute force si on tente sur une machine surpuissante (et avec beaucoup de patience) de trouver les nombres narcissique entre 1 et 9 999 999 999 (N=10).
Cette méthode traite donc 9 999 999 999 cas.
Pour la méthode via multi-set le nombre de combinaisons calculés pour chaque length N est égale au nombre de combinaison de N+9 parmis N soit (N+9)!/(9!N!).
Cette méthode traite donc 92377 cas.
Le temps de calcul dépend forcément de la machine sur lequel est lancé le programme. Dans mon cas sur un ordinateur portable Takima Standard j'ai obtenu les résultats suivants :
int (N<10)long (N<20)BigInteger (N<40)Méthode brute force~ 3 minutesj'ai arrêté après 2hN/AMéthode multi-set~ 5 secondes~ 30 secondes~35 minutes
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// Solution 1
public class ArmstrongNumbersBruteforceOpt {
private static long[][] pows;
private static void genPows(int N) {
if (N > 20) {
throw new IllegalArgumentException();
}
pows = new long[10][N + 1];
for (int i = 0; i < pows.length; i++) {
long p = 1;
for (int j = 0; j < pows[i].length; j++) {
pows[i][j] = p;
p *= i;
}
}
}
private static List<Long> results;
private static int N;
private static void search(int depth, long num, long pow) {
if (depth == N) {
if (pow == num) {
results.add(num);
}
return;
}
num *= 10;
for (int i = 0; i < 10; i++) {
if (depth == 0 && i == 0) {
continue;
}
search(depth + 1, num + i, pow + pows[i][N]);
}
}
public static List<Long> generate(int maxN) {
if (maxN >= 20) {
throw new IllegalArgumentException();
}
results = new ArrayList<>();
genPows(maxN);
for (N = 1; N <= maxN; N++) {
search(0, 0, 0);
}
Collections.sort(results);
return results;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
List<Long> list = generate(9);
long finish = System.currentTimeMillis();
System.out.println("Time consumed: " + (finish - start) + " ms");
System.out.println(list.size());
System.out.println(list);
}
}
// Solution 2
public class NarcissicMultiSet {
private static int N;
private static int[] digitsMultiSet;
private static int[] testMultiSet;
private static List<Long> results;
private static long maxPow;
private static long minPow;
private static long[][] pows;
private static void genPows(int N) {
if (N > 20) {
throw new IllegalArgumentException();
}
pows = new long[10][N + 1];
for (int i = 0; i < pows.length; i++) {
long p = 1;
for (int j = 0; j < pows[i].length; j++) {
pows[i][j] = p;
p *= i;
}
}
}
private static boolean check(long pow) {
if (pow >= maxPow) {
return false;
}
if (pow < minPow) {
return false;
}
for (int i = 0; i < 10; i++) {
testMultiSet[i] = 0;
}
while (pow > 0) {
int i = (int) (pow % 10);
testMultiSet[i]++;
if (testMultiSet[i] > digitsMultiSet[i]) {
return false;
}
pow = pow / 10;
}
for (int i = 0; i < 10; i++) {
if (testMultiSet[i] != digitsMultiSet[i]) {
return false;
}
}
return true;
}
private static void search(int digit, int unused, long pow) {
if (pow >= maxPow) {
return;
}
if (digit == -1) {
if (check(pow)) {
results.add(pow);
}
return;
}
if (digit == 0) {
digitsMultiSet[digit] = unused;
search(digit - 1, 0, pow + unused * pows[digit][N]);
} else {
if (pow + unused * pows[digit][N] < minPow) {
return;
}
long p = pow;
for (int i = 0; i <= unused; i++) {
digitsMultiSet[digit] = i;
search(digit - 1, unused - i, p);
if (i != unused) {
p += pows[digit][N];
}
}
}
}
public static List<Long> generate(int maxN) {
if (maxN >= 20) {
throw new IllegalArgumentException();
}
genPows(maxN);
results = new ArrayList<>();
digitsMultiSet = new int[10];
testMultiSet = new int[10];
for (N = 1; N <= maxN; N++) {
minPow = (long) Math.pow(10, N - 1);
maxPow = (long) Math.pow(10, N);
search(9, N, 0);
}
Collections.sort(results);
return results;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
List<Long> list = generate(9);
long finish = System.currentTimeMillis();
System.out.println("Time consumed: " + (finish - start) + " ms");
System.out.println(list.size());
System.out.println(list);
}
}
Votre équipe TakiVeille
