algorithmAan de slag met algoritme


Opmerkingen

Inleiding tot algoritmen

Algoritmen zijn alomtegenwoordig in informatica en software engineering. Selectie van geschikte algoritmen en gegevensstructuren verbetert de efficiëntie van ons programma in kosten en tijd.

Wat is een algoritme? Informeel is een algoritme een procedure om een specifieke taak te volbrengen. [Skiena: 2008: ADM: 1410219] Specifiek is een algoritme een goed gedefinieerde rekenprocedure, waarbij een bepaalde waarde (of een reeks waarden) als invoer wordt gebruikt en een bepaalde waarde, of een reeks waarden, als uitvoer wordt geproduceerd. Een algoritme is dus een reeks computationele stappen die de invoer in de uitvoer transformeren. Cormen et. al. merkt niet expliciet op dat een algoritme niet noodzakelijk een invoer vereist. [Cormen: 2001: IA: 580470]

Formeel moet een algoritme voldoen aan vijf kenmerken: [Knuth: 1997: ACP: 260999]

  1. Eindigheid . Een algoritme moet altijd eindigen na een eindig aantal stappen.
  2. Definitiviteit . Elke stap van een algoritme moet nauwkeurig worden gedefinieerd; de uit te voeren acties moeten strikt worden gespecificeerd. Het is deze kwaliteit waarnaar [Cormen: 2001: IA: 580470] verwijst met de term "goed gedefinieerd".
  3. Input . Een algoritme heeft nul of meer ingangen . Dit zijn hoeveelheden die in eerste instantie aan het algoritme worden gegeven voordat het begint of dynamisch tijdens de uitvoering.
  4. Uitgang . Een algoritme heeft een of meer uitgangen . Dit zijn hoeveelheden die een gespecificeerde relatie hebben met de ingangen. We verwachten dat een algoritme dezelfde uitvoer produceert wanneer deze steeds opnieuw dezelfde invoer krijgt.
  5. Effectiviteit . Algemeen wordt verwacht dat een algoritme effectief is . De werking ervan moet voldoende basaal zijn om precies in principe en in een beperkte tijd te kunnen worden uitgevoerd door iemand die potlood en papier gebruikt.

Een procedure die eindigheid mist maar aan alle andere kenmerken van een algoritme voldoet, kan een berekeningsmethode worden genoemd. [Knuth: 1997: ACP: 260999]

Een voorbeeld van een algoritmisch probleem

Een algoritmisch probleem wordt gespecificeerd door de volledige set van instanties te beschrijven waaraan het moet werken en van zijn uitvoer na uitvoering op een van deze instanties. Dit onderscheid tussen een probleem en een voorbeeld van een probleem is fundamenteel. Het algoritmische probleem dat bekend staat als sorteren, is als volgt gedefinieerd: [Skiena: 2008: ADM: 1410219]

  • Probleem: sorteren
  • Input: een reeks van n toetsen, a_1, a_2, ..., a_n .
  • Uitvoer: Het opnieuw ordenen van de invoerreeks zodat a'_1 <= a'_2 <= ... <= a'_{n-1} <= a'_n

Een voorbeeld van sorteren kan een reeks strings zijn, zoals { Haskell, Emacs } of een reeks getallen zoals { 154, 245, 1337 } .

Aan de slag met Simple Fizz Buzz-algoritme in Swift

Voor degenen onder u die nieuw zijn in programmeren in Swift en degenen onder u die uit verschillende programmeerbases komen, zoals Python of Java, zou dit artikel zeer nuttig moeten zijn. In dit bericht zullen we een eenvoudige oplossing bespreken voor het implementeren van snelle algoritmen.

Fizz Buzz

Je hebt misschien Fizz Buzz geschreven als Fizz Buzz, FizzBuzz of Fizz-Buzz; ze verwijzen allemaal naar hetzelfde. Dat "ding" is vandaag het belangrijkste onderwerp van discussie. Ten eerste, wat is FizzBuzz?

Dit is een veel voorkomende vraag die naar voren komt in sollicitatiegesprekken.

Stel je een reeks van een getal van 1 tot 10 voor.

1 2 3 4 5 6 7 8 9 10
 

Fizz en Buzz verwijzen naar elk getal dat een veelvoud is van respectievelijk 3 en 5. Met andere woorden, als een nummer deelbaar is door 3, wordt het vervangen door fizz; als een getal deelbaar is door 5, wordt het vervangen door buzz. Als een nummer tegelijkertijd een veelvoud is van 3 EN 5, wordt het nummer vervangen door 'bruisen'. In essentie bootst het het beroemde spel voor kinderen "bruisen" na.

Om aan dit probleem te werken, opent u Xcode om een nieuwe speeltuin te maken en een reeks zoals hieronder te initialiseren:

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

Om alle bruisingen en buzz te vinden, moeten we door de reeks bladeren en controleren welke nummers bruisen en welke buzz zijn. Om dit te doen, maakt u een for-lus om door de array te lopen die we hebben geïnitialiseerd:

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

Hierna kunnen we eenvoudig de "if else" -voorwaarde en module-operator snel gebruiken, dwz -% om het bruisen en zoemen te lokaliseren

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

Super goed! U kunt naar de foutopsporingsconsole in Xcode-speeltuin gaan om de uitvoer te bekijken. U zult zien dat de "bruisen" in uw array zijn opgelost.

Voor het gedeelte Buzz gebruiken we dezelfde techniek. Laten we het proberen voordat u door het artikel bladert - u kunt uw resultaten vergelijken met dit artikel zodra u dit hebt gedaan.

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

Controleer de output!

Het is vrij eenvoudig - je hebt het getal gedeeld door 3, bruist en het getal gedeeld door 5, zoemen. Vergroot nu het aantal in de array

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

We hebben het bereik van getallen vergroot van 1-10 naar 1-15 om het concept van een "bruisende buzz" aan te tonen. Aangezien 15 een veelvoud is van zowel 3 als 5, moet het nummer worden vervangen door 'bruisen'. Probeer het zelf en controleer het antwoord!

Hier is de oplossing:

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

Wacht ... het is nog niet voorbij! Het hele doel van het algoritme is om de runtime correct aan te passen. Stel je voor dat het bereik toeneemt van 1-15 tot 1-100. De compiler zal elk nummer controleren om te bepalen of het deelbaar is door 3 of 5. Het zou dan de nummers opnieuw doorlopen om te controleren of de nummers deelbaar zijn door 3 en 5. De code zou in wezen elk nummer in de array moeten doorlopen twee keer - het zou eerst de nummers door 3 moeten laten lopen en vervolgens door 5. Om het proces te versnellen, kunnen we onze code vertellen dat we de nummers direct door 15 moeten delen.

Hier is de definitieve code:

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

Zo simpel als dat, u kunt elke gewenste taal gebruiken en aan de slag gaan

Geniet van codering