Programme JavaScript pour vérifier si toutes les rotations d'un nombre donné sont supérieures ou égales à un nombre donné

Dans cet article, nous allons passer par un programme JavaScript pour vérifier si toutes les rotations d'un nombre donné sont supérieures ou égales à un nombre donné. Nous allons écrire un algorithme et expliquer chaque étape que nous effectuons. La complexité temporelle des codes qui seront discutés sera optimiste, tandis que la complexité spatiale s'améliorera d'un code à l'autre.

Introduction au problème

Dans cette question, on nous donne un nombre et nous devons vérifier si chaque rotation est supérieure au nombre actuel ou simplement nous devons trouver la rotation du nombre actuel qui est inférieure au nombre actuel et s'il y a un nombre plus petit dans la rotation alors nous retournerons faux, sinon nous retournerons vrai.

Rotation d'un numéro donné

Exemple

La rotation d'un nombre donné peut être de deux types : dans le sens horaire ou antihoraire. En rotation dans le sens des aiguilles d'une montre, nous prenons le dernier chiffre du nombre et l'ajoutons avant le premier chiffre. Par exemple -

var number = 1234 
var last_digit = number%10;
number /= 10;
number = Math.floor(number)
var answer = last_digit.toString() + number.toString();
console.log("The first rotation of the given number is: " + answer)

Dans le code ci-dessus, on nous donne un nombre et nous devons trouver la première rotation du nombre donné. Tout d’abord, nous stockons le dernier chiffre du nombre actuel dans une autre variable, puis supprimons le dernier chiffre du nombre donné en le divisant par 10 et en prenant la limite.

Enfin, nous ajoutons le numéro actuel après le dernier numéro, ce qui nous donne notre premier tour.

Exemple

Pour obtenir le prochain tour ou le deuxième tour du numéro actuel, nous pouvons obtenir le prochain tour du premier tour ou même nous pouvons le faire par une autre méthode commune à tout tour, voyons cela à travers le code -

var number = 1234 
var i = 2
var n_string = number.toString()
var last_i_elements = n_string.substring(n_string.length-i);
var answer = last_i_elements+ n_string.substring(0,n_string.length-i);
console.log("The ith rotation of the given number is: " + answer)

Dans le code ci-dessus, on nous donne un nombre et nous devons trouver la ième rotation du nombre donné. Tout d’abord, nous stockons le dernier chiffre « i » du numéro actuel dans une autre variable.

Enfin, nous ajoutons le numéro actuel à la chaîne contenant le dernier numéro "i", ce qui nous donne notre premier tour.

La méthode décrite ci-dessus consiste à faire pivoter le numéro dans le sens des aiguilles d'une montre et pour une rotation dans le sens inverse des aiguilles d'une montre, nous devons sélectionner le numéro à l'avant et l'ajouter à la fin.

Lorsqu’il n’y a aucune spécification quant à la rotation que nous devons choisir, nous choisissons dans le sens des aiguilles d’une montre. Ainsi dans l’exemple nous verrons une rotation dans le sens des aiguilles d’une montre.

Méthode

Cette méthode est la méthode de la force brute, dans cette méthode, nous trouverons chaque tour d'un nombre donné et vérifierons chaque nombre supérieur. Si nous trouvons un nombre inférieur au nombre actuel, nous renverrons faux, sinon nous renverrons vrai.

Exemple

Jetons d’abord un coup d’œil au code, puis passons à l’explication du code -

function check(number,i){
   var n_string = number.toString()
   var last_i_elements = n_string.substring(n_string.length-i);
   var answer = last_i_elements+ n_string.substring(0,n_string.length-i);
   if(answer < n_string){
      return false;
   }
   return true;
}

var number = 12345
// checking for every rotation
var ans = true;
for(var i=1;i<number.toString().length;i++){
   ans = check(number,i);
   if(ans == false){
      break;
   }
}
if(ans == true){
   console.log("There is no rotation present which is less then given number")
}
else{
   console.log("There is a rotation of given number present which is less then given number")
}

Dans le programme ci-dessus, nous parcourons d'abord de 1 à la taille du nombre moins 1 dans une boucle for pour obtenir chaque rotation de 1 à la taille moins 1. A chaque itération, nous appelons une fonction prédéfinie.

Dans la fonction, nous obtiendrons la ième rotation qui est passée en argument à la fonction et comparée au nombre donné. Si la ième rotation est inférieure au nombre donné, alors nous renverrons false comme valeur de retour, sinon nous renverrons true.

Nous maintenons une variable appelée réponse qui stockera les valeurs vraies et fausses renvoyées par la fonction et imprimera la réponse sur demande.

Complexité temporelle et spatiale

Dans le code ci-dessus, nous avons appelé la fonction check() n fois au total, où n est la taille du nombre donné. À l’intérieur de la fonction, nous créons une sous-chaîne qui est une copie du nombre donné et itérons n fois, ce qui signifie que nous l’utilisons n*n fois. Par conséquent, la complexité temporelle de la fonction donnée est O(N*N).

Dans la fonction de vérification, chaque fois que nous créons une copie du numéro donné, cela signifie que nous utilisons N espaces supplémentaires. Par conséquent, la complexité spatiale de la fonction donnée est O(N).

Idée générale

Dans le code ci-dessus, si tous les nombres sont différents, alors nous pouvons obtenir la réponse en complexité temporelle O(N) et en complexité spatiale O(1), car si un nombre est inférieur au premier nombre, cela signifie qu'il y a un possibilité que le nombre soit inférieur dans un tour exact par rapport au nombre initial.

Conclusion

Dans ce tutoriel, nous utilisons un programme JavaScript pour vérifier si toutes les rotations d'un nombre donné sont supérieures ou égales à un nombre donné. La complexité temporelle du programme est O(N*N) et la complexité spatiale est O(N), où N est la taille du nombre donné. Nous avons mis en place un programme qui nous permet de trouver chaque tour d'un numéro donné et de le comparer avec le numéro d'origine.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!