algorithmIniziare con l'algoritmo

Osservazioni

Introduzione agli algoritmi

Gli algoritmi sono onnipresenti in informatica e ingegneria del software. La selezione di algoritmi e strutture dati appropriati migliora l'efficienza del nostro programma in termini di costi e tempi.

Cos'è un algoritmo? Informalmente, un algoritmo è una procedura per eseguire un'attività specifica. [Skiena: 2008: ADM: 1410219] In particolare, un algoritmo è una procedura di calcolo ben definita , che prende un certo valore (o un insieme di valori) come input e produce un valore, o un insieme di valori, come output . Un algoritmo è quindi una sequenza di passaggi computazionali che trasformano l'input in output. Cormen et. al. non osserva esplicitamente che un algoritmo non richiede necessariamente un input. [Cormen: 2001: IA: 580.470]

Formalmente, un algoritmo deve soddisfare cinque caratteristiche: [Knuth: 1997: ACP: 260999]

  1. Finitudine Un algoritmo deve sempre terminare dopo un numero finito di passaggi.
  2. Definizione Ogni fase di un algoritmo deve essere definita con precisione; le azioni da eseguire devono essere rigorosamente specificate. È questa qualità che [Cormen: 2001: IA: 580470] si riferisce al termine "ben definito".
  3. Input . Un algoritmo ha zero o più input . Queste sono le quantità che vengono fornite all'algoritmo inizialmente prima che inizi o dinamicamente durante l'esecuzione.
  4. Uscita Un algoritmo ha uno o più output . Queste sono quantità che hanno una relazione specifica con gli input. Ci aspettiamo che un algoritmo produca lo stesso risultato quando viene dato lo stesso input più e più volte.
  5. Efficacia . Generalmente ci si aspetta che un algoritmo sia efficace . Le sue operazioni devono essere sufficientemente basiche da poter essere eseguite esattamente in linea di principio e in un tempo finito da qualcuno che usa carta e penna.

Una procedura che manca di finitezza ma che soddisfa tutte le altre caratteristiche di un algoritmo può essere chiamata un metodo computazionale . [Knuth: 1997: ACP: 260.999]

Un esempio di problema algoritmico

Un problema algoritmico viene specificato descrivendo l'insieme completo di istanze su cui deve lavorare e del suo output dopo l'esecuzione su una di queste istanze. Questa distinzione, tra un problema e un'istanza di un problema, è fondamentale. Il problema algoritmico noto come ordinamento è definito come segue: [Skiena: 2008: ADM: 1410219]

  • Problema: ordinamento
  • Input: una sequenza di n chiavi, a_1, a_2, ..., a_n .
  • Output: il riordino della sequenza di input tale che a'_1 <= a'_2 <= ... <= a'_{n-1} <= a'_n

Un'istanza di ordinamento potrebbe essere un array di stringhe, come { Haskell, Emacs } o una sequenza di numeri come { 154, 245, 1337 } .

Iniziare con il semplice algoritmo Fizz Buzz in Swift

Per quelli di voi che sono nuovi alla programmazione in Swift e quelli di voi che provengono da diverse basi di programmazione, come Python o Java, questo articolo dovrebbe essere abbastanza utile. In questo post, discuteremo una soluzione semplice per l'implementazione di algoritmi swift.

Fizz Buzz

Potresti aver visto Fizz Buzz scritto come Fizz Buzz, FizzBuzz o Fizz-Buzz; si riferiscono tutti alla stessa cosa. Quella "cosa" è l'argomento principale di discussione oggi. Innanzitutto, cos'è FizzBuzz?

Questa è una domanda comune che emerge nelle interviste di lavoro.

Immagina una serie di numeri da 1 a 10.

1 2 3 4 5 6 7 8 9 10
 

Fizz e Buzz si riferiscono a qualsiasi numero che sia multiplo di 3 e 5 rispettivamente. In altre parole, se un numero è divisibile per 3, viene sostituito con fizz; se un numero è divisibile per 5, è sostituito da buzz. Se un numero è contemporaneamente un multiplo di 3 E 5, il numero viene sostituito da "fizz buzz". In sostanza, emula il famoso gioco per bambini "fizz buzz".

Per risolvere questo problema, apri Xcode per creare un nuovo campo da gioco e inizializzare un array come di seguito:

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

Per trovare tutti i fizz e ronzio, dobbiamo scorrere l'array e controllare quali numeri sono fizz e quali sono ronzio. Per fare ciò, creare un ciclo for per scorrere l'array che abbiamo inizializzato:

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

Dopo questo, possiamo semplicemente usare la condizione "if else" e l'operatore del modulo in quick ie -% per localizzare il fizz e il buzz

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

Grande! Puoi andare alla console di debug nel parco giochi Xcode per vedere l'output. Scoprirai che i "fizz" sono stati ordinati nel tuo array.

Per la parte Buzz, useremo la stessa tecnica. Facciamo un tentativo prima di scorrere l'articolo: puoi controllare i tuoi risultati con questo articolo una volta che hai finito di farlo.

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

Controlla l'output!

È piuttosto semplice: hai diviso il numero per 3, fizz e hai diviso il numero per 5, ronzio. Ora, aumenta i numeri nella matrice

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

Abbiamo aumentato la gamma di numeri da 1-10 a 1-15 per dimostrare il concetto di "fizz buzz". Poiché 15 è un multiplo di entrambi 3 e 5, il numero deve essere sostituito da "fizz buzz". Prova tu stesso e controlla la risposta!

Ecco la soluzione:

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)
  }
}
 

Aspetta ... non è finita però! L'intero scopo dell'algoritmo è di personalizzare correttamente il runtime. Immagina se la gamma aumenta da 1 a 15 a 1-100. Il compilatore controllerà ogni numero per determinare se è divisibile per 3 o 5. Avrebbe quindi eseguito nuovamente i numeri per verificare se i numeri sono divisibili per 3 e 5. Il codice dovrebbe essenzialmente scorrere attraverso ogni numero nell'array due volte - dovrebbe prima eseguire i numeri per 3 e poi eseguirlo per 5. Per accelerare il processo, possiamo semplicemente dire al nostro codice di dividere i numeri per 15 direttamente.

Ecco il codice finale:

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)
  }
}
 

Semplice come quello, puoi usare qualsiasi lingua di tua scelta e iniziare

Goditi la programmazione