Recherche…


Remarques

Introduction aux algorithmes

Les algorithmes sont omniprésents en informatique et en génie logiciel. La sélection d'algorithmes et de structures de données appropriés améliore l'efficacité du programme en termes de coûts et de temps.

Qu'est-ce qu'un algorithme? Informellement, un algorithme est une procédure pour accomplir une tâche spécifique. [Skiena: 2008: ADM: 1410219] Spécifiquement, un algorithme est une procédure de calcul bien définie , qui prend une valeur (ou un ensemble de valeurs) comme entrée et produit une valeur ou un ensemble de valeurs en sortie . Un algorithme est donc une suite d'étapes de calcul qui transforment l'entrée en sortie. Cormen et. Al. n'indique pas explicitement qu'un algorithme ne nécessite pas nécessairement une entrée. [Cormen: 2001: IA: 580470]

Formellement, un algorithme doit satisfaire à cinq caractéristiques: [Knuth: 1997: ACP: 260999]

  1. Durée . Un algorithme doit toujours se terminer après un nombre fini d'étapes.
  2. Définitivité Chaque étape d'un algorithme doit être définie avec précision; les actions à mener doivent être rigoureusement spécifiées. C'est cette qualité que [Cormen: 2001: IA: 580470] désigne avec le terme "bien défini".
  3. Entrée Un algorithme a zéro ou plusieurs entrées . Ce sont des quantités qui sont données à l'algorithme initialement avant qu'il ne commence ou dynamiquement pendant qu'il s'exécute.
  4. Sortie . Un algorithme a une ou plusieurs sorties . Ce sont des quantités qui ont une relation spécifiée avec les entrées. Nous nous attendons à ce qu'un algorithme produise le même résultat lorsqu'il reçoit la même entrée encore et encore.
  5. Efficacité Un algorithme devrait également être efficace . Ses opérations doivent être suffisamment simples pour pouvoir être effectuées exactement en principe et dans un temps limité par un crayon et du papier.

Une procédure qui manque de finitude mais satisfait à toutes les autres caractéristiques d'un algorithme peut être appelée méthode de calcul . [Knuth: 1997: ACP: 260999]

Un exemple de problème algorithmique

Un problème algorithmique est spécifié en décrivant l'ensemble complet des instances sur lesquelles il doit travailler et de sa sortie après avoir été exécuté sur l'une de ces instances. Cette distinction entre un problème et une instance de problème est fondamentale. Le problème algorithmique connu sous le nom de tri est défini comme suit: [Skiena: 2008: ADM: 1410219]

  • Problème: Tri
  • Entrée: Une séquence de n clés, a_1, a_2, ..., a_n .
  • Sortie: La réorganisation de la séquence d'entrée telle que a'_1 <= a'_2 <= ... <= a'_{n-1} <= a'_n

Une instance de tri peut être un tableau de chaînes, tel que { Haskell, Emacs } ou une séquence de nombres tels que { 154, 245, 1337 } .

Premiers pas avec l'algorithme Simple Fizz Buzz dans Swift

Pour ceux d'entre vous qui sont nouveaux dans la programmation de Swift et ceux qui viennent de différentes bases de programmation, telles que Python ou Java, cet article devrait être très utile. Dans cet article, nous discuterons d'une solution simple pour implémenter des algorithmes rapides.

Fizz Buzz

Vous avez peut-être vu Fizz Buzz écrit comme Fizz Buzz, FizzBuzz ou Fizz-Buzz; ils font tous référence à la même chose. Cette "chose" est le sujet principal de discussion aujourd'hui. Tout d'abord, qu'est-ce que FizzBuzz?

C'est une question courante qui se pose dans les entretiens d'embauche.

Imaginez une série d'un nombre de 1 à 10.

1 2 3 4 5 6 7 8 9 10

Fizz et Buzz font référence à un nombre multiple de 3 et 5 respectivement. En d'autres termes, si un nombre est divisible par 3, il est remplacé par fizz; si un nombre est divisible par 5, il est remplacé par un buzz. Si un nombre est simultanément un multiple de 3 et 5, le numéro est remplacé par "fizz buzz". En substance, il émule le célèbre jeu pour enfants "fizz buzz".

Pour travailler sur ce problème, ouvrez Xcode pour créer un nouveau terrain de jeu et initialiser un tableau comme ci-dessous:

// for example 
let number  = [1,2,3,4,5]
// here 3 is fizz and 5 is buzz

Pour trouver tous les effets et les buzz, il faut parcourir le tableau et vérifier quels nombres sont fizz et quels sont les buzz. Pour ce faire, créez une boucle for pour parcourir le tableau que nous avons initialisé:

for num in number {
  // Body and calculation goes here
}

Après cela, nous pouvons simplement utiliser la condition "if else" et l'opérateur de module dans swift ie -% pour localiser le fizz et le buzz

for num in number {
  if num % 3 == 0 {
    print("\(num) fizz")
  } else {
    print(num)
  }
}

Génial! Vous pouvez aller à la console de débogage dans la cour de jeu Xcode pour voir la sortie. Vous constaterez que les "fizzes" ont été triés dans votre tableau.

Pour la partie Buzz, nous utiliserons la même technique. Essayons avant de faire défiler l'article - vous pouvez vérifier vos résultats contre cet article une fois que vous avez terminé.

for num in number {
  if num % 3 == 0 {
    print("\(num) fizz")
  } else if num % 5 == 0 {
    print("\(num) buzz")
  } else {
    print(num)
  }
}

Vérifiez la sortie!

C'est plutôt simple - vous avez divisé le nombre par 3, fizz et divisé le nombre par 5, buzz. Maintenant, augmentez les nombres dans le tableau

let number = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

Nous avons augmenté la gamme des nombres de 1 à 10 à 1 à 15 afin de démontrer le concept d'un «buzz de fizz». Puisque 15 est un multiple de 3 et 5, le nombre doit être remplacé par "buzz". Essayez par vous-même et vérifiez la réponse!

Voici la solution:

for num in number {
  if num % 3 == 0 && num % 5 == 0 {
    print("\(num) fizz buzz")
  } else if num % 3 == 0 {
    print("\(num) fizz")
  } else if num % 5 == 0 {
    print("\(num) buzz")
  } else {
    print(num)
  }
}

Attendez ... ce n'est pas fini! Le but de l'algorithme est de personnaliser le runtime correctement. Imaginez si la plage augmente de 1-15 à 1-100. Le compilateur vérifiera chaque nombre pour déterminer s'il est divisible par 3 ou 5. Il relèverait alors les nombres pour vérifier si les nombres sont divisibles par 3 et 5. Le code devrait essentiellement parcourir chaque nombre du tableau. deux fois - il devrait d'abord exécuter les nombres par 3 et ensuite l'exécuter par 5. Pour accélérer le processus, nous pouvons simplement dire à notre code de diviser les nombres directement par 15.

Voici le code final:

for num in number {
  if num % 15 == 0 {
    print("\(num) fizz buzz")
  } else if num % 3 == 0 {
    print("\(num) fizz")
  } else if num % 5 == 0 {
    print("\(num) buzz")
  } else {
    print(num)
  }
}

Aussi simple que cela, vous pouvez utiliser n'importe quelle langue de votre choix et commencer

Profitez du codage



Modified text is an extract of the original Stack Overflow Documentation
Sous licence CC BY-SA 3.0
Non affilié à Stack Overflow