Programmeren in Ruby/Rekenproblemen

Programmeren in Ruby

Hierbij enkele typische de rekenproblemen, ieder onder een kopje. Eerst volgt de beschrijving van het probleem en daarna de programmeercode voor de oplossing.

Priemgetallen

Priemgetallen of priemen zijn die getallen groter dan 1 die uitsluitend door 1 of zichzelf gedeeld kunnen worden. De eenvoudigste zijn 2, 3 ,5, 7, 11, 13, enz., maar er is geen grootste priemgetal. Het vereist enig denkwerk en een programmaatje om op de computer dit soort getallen te voorschijn te toveren. Priemen kunnen op verschillende manieren verkregen en/of gecontroleerd worden. Met gecontroleerd wordt bedoeld, dat van een getal wordt vastgesteld dat het priem is. En met verkrijgen wordt het opleveren van een rij priemgetallen bedoeld.

Hieronder volgt een methode die controleert of een integer, een heel getal, ook een priemgetal is. Het kijkt gewoonweg of het niet deelbaar is door alle voorgaande getallen. Deze zeef laat dan alleen de priemen door.

 def priemgetal? (getal)
     priem = true
     huidiggetal = (getal.to_i) - 1
     while priem == true and huidiggetal > 1
          priem = false if getal % huidiggetal == 0
          huidiggetal -= 1
     end    
     return priem
 end

Ook andere rekenkundige manieren kunnen rijen priemgetallen opleveren. Dit kan als volgt worden geprogrammeerd:

 totgetal = 50
 priemgetallen = []
 totgetal.times do |getal|
     priemgetallen << getal if priemgetal?(getal) == true
 end

Dit gaat echter nogal sloom, want er komen lange rijen te voorschijn, terwijl er op een gegeven moment heel veel ruimte tussen de priemgetallen zit, want ze komen steeds verder uit elkaar te staan. Gelukkig zijn er ook andere rekenmethoden, zoals bijv. de bekende [1] zeef van Eratosthenes.

Grootste gemene deler (ggd)

De grootste gemene deler, afgekort met ggd van een aantal gegeven getallen is het grootste getal dat op al deze getallen deelbaar is.

Bijvoorbeeld de grootste gemene deler van 6 en 12 is het getal 6, want 6 en 12 zijn door ten hoogste 6 deelbaar. De grootste gemene deler van 15 en 20 is om dezelfde reden het getal 5. De grootste gemene deler van 6, 9 en 12 is dan 3. De grootste gemene deler wordt vaak afgekort tot ggd. Bijvoorbeeld ggd(6, 9, 12) = 3.

Een paar getallen waarvan de ggd gelijk is aan 1 wordt algemeen 'relatief' priem genoemd.

Het product van de ggd en het kleinste gemene veelvoud - kgv - van twee getallen is gelijk aan het product van die twee getallen.

Bepalen van de grootste gemene deler

Bovenstaande voorbeelden zijn eenvoudig, maar bij grotere getallen is het niet direct duidelijk wat de ggd is. Deze kan dan bijv. worden bepaald door beide getallen te ontbinden in factoren, wat wil zeggen dat van beide getallen wordt bepaald door welke priemgetallen ze deelbaar zijn. Daarbij wordt achtereenvolgens van elk priemgetal geprobeerd of dit een deler is. Als een getal 2 of meerdere malen door hetzelfde priemgetal deelbaar is wordt dit 2 of meerdere malen genoteerd. Vervolgens worden alle gemeenschappelijk priemfactoren met elkaar vermenigvuldigd. Het resultaat is de ggd.

Een voorbeeld maakt verduidelijkt dit:

Het getal 24 is deelbaar door de priemgetallen 2, 2, 2, 3 (want 24 is gelijk aan 2 × 2 × 2 × 3)

Het getal 102 is deelbaar door de priemgetallen 2, 3 en 17.

De grootste gemene deler van 24 en 102 is dus 2 × 3 = 6.

Deze methode zouden we kunnen gebruiken om de ggd te bepalen, waarbij we ze eerst moeten ontbinden in factoren. Hiervoor zouden we lijsten met priemgetallen bij de hand moeten hebben en vervolgens heel moeilijk gaan doen om het ontbinden te bewerkstelligen. Om dit te doen is er niet alleen veel tijd nodig, de computer zelf doet ook lang ook over grote getallen.

Er is echter een andere methode om dit aan te pakken, nl. het algoritme van Euclides. Voor grote getallen is dit algoritme te verkiezen boven de methode die ontbindt in factoren, omdat het ontbinden in factoren van grote getallen (zelfs voor computers) heel moeilijk kan zijn. De redenatie achter euclide verloopt als volgt:

Het algoritme van Euclides

Noem het grootste van de beide getallen A, het andere B.
Trek B net zo vaak van A af totdat er 0 over blijft of een getal kleiner dan B.
Wanneer er 0 over blijft zijn we klaar, en is B de ggd.
Zo niet, herhaal dan het algoritme met B en wat er van A over is.

Voorbeeld

Als een voorbeeld bepalen we met het algoritme van Euclides de ggd van 900 en 1140:

A is 1140, B is 900. We kunnen 900 eenmaal van 1140 aftrekken, we krijgen dan 240.
We herhalen het algoritme met A=900 en B=240. 240 kan driemaal van 900 worden afgetrokken, dan blijft 180 over.
We herhalen het algoritme met A=240 en B=180. 180 kan eenmaal van 240 worden afgetrokken. Dit levert 60.
We herhalen het algoritme met A=180 en B=60. 60 kan 3 maal van 180 afgetrokken worden, en 0 blijft dan over.
Daarmee zijn we aan het einde gekomen, en hebben bepaald dat 60 de grootste gemene deler van 900 en 1140 is, oftewel ggd(900,1140)=60.

Dit is wel vrij makkelijk met de computer te doen, hetgeen als volgt is te programmeren:

 def euclides_algoritme(getal1,getal2)
 	 if getal1 == getal2
 	      puts "getallen zijn gelijk, algoritme hoeft niet worden uitgevoerd."
 	      break
 	elsif getal1 < getal2
 		a = getal2
 		b = getal1
 	elsif getal1 > getal2
 		a = getal1
 		b = getal2
 	end
 	c = a.to_i
 	while c > 0
 	        a = c.to_i
 		c = a - b
 	end
 	return [c,a,b]
 end

Dit kunnen we gebruiken door dit te doen:

 loop do
 	puts "getal 1 is:"
 	getal1 = gets.chomp.to_i
 	puts "getal 2 is:"
 	getal2 = gets.chomp.to_i
 	puts "de gemeenschappelijke deler daarvan is"
 	starttijd = Time.new
 	c = -12
 	loops = 0
 	while c != 0
 		arr = euclides_algoritme(getal1,getal2)
 		c= arr[0]
 		getal1= arr[1]
 		getal2= arr[2]
 		loops += 1
 		print "."
 	end
 	puts "\n" + getal2.to_s + " -- berekent in " + (Time.new-starttijd).to_s + " seconden  en het algoritme moest " + loops.to_s + " keer uitgevoerd worden.\n\n\n"
 end

Dit programmaatje laat de tijd zien die de computer nodig had en tevens het aantal keren dat het algoritme herhaald moest worden. Op onze computer werd het in ongeveer 20 minuten afgehandeld.