Trouver des numéros de taxi

Trouvez les n premiers numéros de taxi. Étant donné une valeur n . Je voudrais trouver les n premiers numéros de taxi. Un taxi est un nombre qui peut être exprimé par la sum de deux cubes parfaits de plusieurs façons.

(Notez qu’il existe deux ensembles liés mais différents appelés «numéros de taxi»: les sums de 2 cubes de plus d’une façon , et les plus petits nombres qui sont la sum de 2 cubes intégraux positifs de n façons . Cette question concerne le premier ensemble, puisque le dernier ensemble ne comprend que les six premiers membres)

Par exemple:

 1^3 + 12^3 = 1729 = 9^3 + 10^3 

Je voudrais un aperçu général de l’algorithme ou l’extrait C de la façon d’aborder le problème.

 The first five of these are: IJKL Number --------------------------------- 1 12 9 10 1729 2 16 9 15 4104 2 24 18 20 13832 10 27 19 24 20683 4 32 18 30 32832 

Vous trouverez ci-dessous le code java encore meilleur pour l’impression de nombres N ramanujan, car sa complexité temporelle est encore moindre. Parce qu’il n’en a qu’une pour la boucle.

 import java.util.*; public class SolutionRamanujan { public static void main(Ssortingng args[] ) throws Exception { SolutionRamanujan s=new SolutionRamanujan(); Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int i=0,k=1; while(i2){ //checking if two such pairs exists ie (a*a*a)+(b*b*b)=(c*c*c)+(d*d*d)=number return true; } } return false; } } 

J’ai compris que la réponse pourrait être obtenue de cette façon:

 #include int main() { int n, i, count=0, j, k, int_count; printf("Enter the number of values needed: "); scanf("%d", &n); i = 1; while(count < n) { int_count = 0; for (j=1; j<=pow(i, 1.0/3); j++) { for(k=j+1; k<=pow(i,1.0/3); k++) { if(j*j*j+k*k*k == i) int_count++; } } if(int_count == 2) { count++; printf("\nGot %d Hardy-Ramanujan numbers %d", count, i); } i++; } } 

Puisque a^3+b^3 = n , a devrait être inférieur à n^(1/3) .

Algorithme rapide et naïf (si je comprends bien le problème):

Calculons les cubes de tous les natifs entiers de 1 à N; calcule ensuite toutes les sums de deux cubes. Ces sums peuvent être stockées dans une masortingce sortingangular. évitez de remplir toute la masortingce carrée. Enfin, recherchez les éléments non uniques dans votre masortingce sortingangular, il s’agit des nombres HR mêmes (si vous me permettez d’appeler les nombres que nous voulons calculer comme ceci). De plus, en sortingant le tableau tout en conservant les index d’origine, vous pouvez facilement déduire les décompositions d’un tel nombre.

Ma solution a un petit défaut: je ne sais pas comment corriger N en fonction de votre entrée n, c’est combien de cubes dois-je calculer pour avoir au moins n nombres HR? Problème intéressant laissé.

EDIT : pour ceux qui ne savent pas ce que R est, voici un lien .

Mon C étant un peu rouillé … Je vais écrire une solution en R, ça ne devrait pas être difficile de s’adapter. La solution est très rapide en R, elle devrait donc l’être encore plus en C.

 # Create an hash table of cubes from 1 to 100 numbers <- 1:100 cubes <- numbers ^ 3 # The possible pairs of numbers pairs <- combn(numbers, 2) # Now sum the cubes of the combinations # This takes every couple and sums the values of the cubes # with the appropriate index sums <- apply(pairs, 2, function(x){sum(cubes[x])}) 

Alors:

numbers seront: 1, 2, 3, 4, ..., 98, 99, 100
cubes seront: 1, 8, 27, 64, ..., 941192, 970299, 1000000
pairs contiendront:

  [,1] [,2] [,3] [,4] [,5] ... [,4949] [,4950] [1,] 1 1 1 1 1 ... 98 99 [2,] 2 3 4 5 6 ... 100 100 

sums seront: 9 28 65 126 217 344 ... 1911491 1941192 1970299

Une vérification rapide que nous sums sur la bonne voie ...

 > which(sums == 1729) [1] 11 765 <--- the ids of the couples summing to 1729 > pairs[,11] [1] 1 12 > pairs[,765] [1] 9 10 

Maintenant, trouvons quels sont les couples avec les mêmes sums.

table(sums) nous donne un résumé soigné comme

 > 9 28 35 65 72 91 ... 1674 1729 1736 1 1 1 1 1 1 ....  ... 1 2 1 

Trouvons donc quels éléments de la table(sums) sont == 2

 doubles <- which(table(sums) == 2) taxi.numbers <- as.integer(names(doubles)) [1] 1729 4104 13832 20683 32832 39312 40033 46683 64232 65728 [11] 110656 110808 134379 149389 165464 171288 195841 216027 216125 262656 [21] 314496 320264 327763 373464 402597 439101 443889 513000 513856 515375 [31] 525824 558441 593047 684019 704977 805688 842751 885248 886464 920673 [41] 955016 984067 994688 1009736 1016496 

Et enfin (à lire deux par deux), les paires entières correspondantes

 > pairs[,doubles] [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [1,] 1 9 2 9 2 18 10 19 4 18 2 15 9 16 3 [2,] 12 10 16 15 24 20 27 24 32 30 34 33 34 33 36 [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29] [1,] 27 17 26 12 31 4 36 6 27 12 38 8 29 20 [2,] 30 39 36 40 33 48 40 48 45 51 43 53 50 54 [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38] [,39] [,40] [,41] [,42] [,43] [1,] 38 17 24 9 22 3 22 5 45 8 36 4 30 18 [2,] 48 55 54 58 57 60 59 60 50 64 60 68 66 68 [,44] [,45] [,46] [,47] [,48] [,49] [,50] [,51] [,52] [,53] [,54] [,55] [,56] [,57] [1,] 32 30 51 6 54 42 56 5 48 17 38 10 45 34 [2,] 66 67 58 72 60 69 61 76 69 76 73 80 75 78 [,58] [,59] [,60] [,61] [,62] [,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71] [1,] 52 15 54 24 62 30 57 7 63 51 64 2 41 11 [2,] 72 80 71 80 66 81 72 84 70 82 75 89 86 93 [,72] [,73] [,74] [,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85] [1,] 30 23 63 8 72 12 54 20 33 24 63 35 59 29 [2,] 92 94 84 96 80 96 90 97 96 98 89 98 92 99 [,86] [,87] [,88] [,89] [,90] [1,] 60 50 59 47 66 [2,] 92 96 93 97 90 

Alors:

1,12 et 9,10 donnent 1729
2,16 et 9,15 donnent 4104
2,24 et 18,20 donnent 13832
etc!

Meilleur algorithme que Nikhitha Reddy ci-dessus. Nous n’avons pas à vérifier (i, j) et (j, i) les deux.

Voici le code Java.

 import java.util.*; public class efficientRamanujan{ public static void main(Ssortingng[] args) { efficientRamanujan s=new efficientRamanujan(); Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int i=0,k=1; while(in){ y = y-1; }else{ count++; x = x+1; y = y-1; } if(count>=2){ return true; } } return false; } } 

Référence: blog

Cette solution (en python) génère le n premier numéro de taxi dans une approche ascendante. La complexité temporelle est m ^ 2, m étant le nombre le plus élevé utilisé pour générer les n nombres.

 def generate_taxi_cab_numbers(n): generated_number = 0 v = {} c = {} i = 0 while generated_number < n: c[i] = i*i*i for j in xrange(i): s = c[j] + c[i] if s in v: generated_number = generated_number + 1 yield (s, (j, i), v[s]) v[s] = (j,i) i = i + 1 def m(n): for x in generate_taxi_cab_numbers(n): print x 

Il existe deux manières d’écrire la solution en Python: programmation dynamic et force brute.

 def ramanujanDynamicProgramming(n): numbers = [] Ds = dict() # Init List for d in xrange(0, n ** 3): Ds[d] = False # Fill list for d in xrange(0, n): Ds[d**3] = d for a in xrange(0, n): for b in xrange(0, n): for c in xrange(0, n): if a != b and a != c and b != c: d = a ** 3 + b ** 3 - c ** 3 if a != d and b != d and c != d and d >= 0 and d < n ** 3: if Ds[d] != False: numbers.append((a, b, c, Ds[d])) return numbers print "Dynamic Programming" print ramanujanDynamicProgramming(n) 

L’approche DP ne prend que O (n ^ 3).

 def ramanujanBruteForce(n): numbers = [] for a in xrange(0, n): for b in xrange(0, n): for c in xrange(0, n): for d in xrange(0, n): if a != b and a != c and a != d and b != c and b != d and c != d: if a ** 3 + b ** 3 == c ** 3 + d ** 3: numbers.append((a, b, c, d)) return numbers print "Brute Force" print ramanujanBruteForce(n) 

L'approche BF est BF est O (n ^ 4).