Loopar

Innan vi börjar programmera måste vi fundera ut en metod för att räkna punkterna. Genom att undersöka hur långt bort från origo en punkt ligger kan man avgöra om den ligger på cirkelskivan eller inte. Om avståndet till origo är större än cirkelns radie måste punkten ligga utanför cirkeln. Alltså när sqrt(x^2 + y^2) > r, där x och y är x- respektive y-koordinaten för punkten och r är cirkelns radie. Eftersom det finns oändligt många punkter i koordinatsystemet kan vi dock inte gå igenom och undersöka alla utan vi måste begränsa oss på något sätt. Det kan vi göra genom att sätta en kvadrat runt cirkeln och markera alla punkter innanför den.

För att bestämma en lämplig gräns för kvadraten kan vi avrunda cirkelns radie uppåt till närmaste heltal, r_\text{avr}. Då får vi halva sidan på en kvadrat som garanterat innesluter alla punkter som finns på cirkelskivan. Vi kan alltså söka igenom följande heltalskoordinater x och y. \begin{gathered} - r_\text{avr} \leq x \leq r_\text{avr} \quad \text{och} \quad - r_\text{avr} \leq y \leq r_\text{avr} \end{gathered} Nu när vi har en metod för att hitta punkterna kan vi börja programmera. Vårt invärde är radien r, så vi skapar en variabel r som vi sätter till det första värdet vi skulle testa, 5.

r = 5

Sedan måste vi se till att radien avrundas till ett heltal, annars kommer programmet undersöka punkter utan heltalskoordinater i de fall då radien inte är ett heltal. Vi använder funktionen ceil() från modulen math för att avrunda uppåt, vilket kräver att modulen importeras i början av programmet.

import math r = 5

r_heltal = math.ceil(r)

Innan vi börjar gå igenom alla punkter måste vi skapa en räknare som håller reda på hur många av dem som faktiskt ligger på cirkelskivan. Vi kallar den antal_punkter och startar den på 0.

import math r = 5

r_heltal = math.ceil(r) antal_punkter = 0

Nu när vi ska gå igenom punkterna gör vi det med två loopar: en för x-koordinaten och en för y-koordinaten. Vi använder for-satser som stegar igenom från -r_heltal till r_heltal med hjälp av funktionen range().

import math r = 5

r_heltal = math.ceil(r) antal_punkter = 0 for x in range(-r_heltal, r_heltal + 1): for y in range(-r_heltal, r_heltal + 1):

Notera att andra argumentet i range() är r_heltal + 1 eftersom range() inte har med den övre gränsen i uppräkningen, bara upp till den. Varje iteration av den inre loopen kommer då att ha ett x- och ett y-värde som motsvarar en av punkterna i kvadraten. Vi beräknar avståndet från denna punkt till origo.

import math r = 5

r_heltal = math.ceil(r) antal_punkter = 0 for x in range(-r_heltal, r_heltal + 1): for y in range(-r_heltal, r_heltal + 1): avstand = math.sqrt(x**2 + y**2)

Om detta avstånd är mindre än eller lika med cirkelns radie måste punkten ligga på cirkelskivan. Vi undersöker detta med en if-sats och ökar antal_punkter med 1 om det är sant.

import math r = 5

r_heltal = math.ceil(r) antal_punkter = 0 for x in range(-r_heltal, r_heltal + 1): for y in range(-r_heltal, r_heltal + 1): avstand = math.sqrt(x**2 + y**2) if avstand <= r: antal_punkter = antal_punkter + 1

När looparna har kört färdigt har vi undersökt alla punkter och den totala summan punkter på cirkelskivan finns lagrad i antal_punkter. Allt vi behöver göra är att skriva ut resultatet.

import math r = 5

r_heltal = math.ceil(r) antal_punkter = 0 for x in range(-r_heltal, r_heltal + 1): for y in range(-r_heltal, r_heltal + 1): avstand = math.sqrt(x**2 + y**2) if avstand <= r: antal_punkter = antal_punkter + 1 print(antal_punkter)

> 81

När radien på cirkeln är 5 finns det alltså 81 heltalspunkter på cirkelskivan. Vi byter ut värdet i r mot 28,47 och testar det andra fallet. Då får vi resultatet 2561. På samma sätt testar vi r = 100, vilket ger 31417 heltalspunkter.

Den kod som vi har skrivit fungerar och ger rätt antal punkter, men den är inte så effektiv. Exempelvis behöver man inte undersöka alla punkter i kvadraten. Det räcker egentligen med att undersöka en kvadrant eftersom de andra tre är speglingar av den första. Man måste dock vara försiktig så att man inte dubbelräknar de punkter som ligger på axlarna.

Det går dessutom bra att avrunda radien nedåt. Då hamnar visserligen delar av cirkeln utanför kvadraten, men aldrig några heltalspunkter.

Ett program som tar dessa saker i beaktning kan se ut på följande sätt.

import math r = 100

r_heltal = math.floor(r) punkter_i_kvadrant = 0 for x in range(0, r_heltal + 1): ##I x-led tar man med axeln. for y in range(1, r_heltal + 1): ##I y-led börjar man på 1 och tar inte med axeln. Detta för att undvika dubbelräkning av axlarna. avstand = math.sqrt(x**2 + y**2) if avstand <= r: punkter_i_kvadrant = punkter_i_kvadrant + 1 antal_punkter = 4*punkter_i_kvadrant + 1 ##Man missar origo i looparna. Den ingår alltid i cirkelskivan, så den måste läggas till. print(antal_punkter)

> 31417

Detta program är mer än fyra gånger så snabbt som originalprogrammet, så det finns en del att tjäna på att optimera sina program.

Vi börjar vårt program med att skapa variabler för de två invärdena: talet som vi vill dra roten ur och antalet gånger vi ska beräkna en ny uppskattning.

tal = 17 antal_upprepningar = 10

Vi behöver sedan en första uppskattning av kvadratroten. Enligt uppgiften ska vi använda det tal vi vill dra roten ur, vilket kan kännas som en ganska dålig uppskattning. Det visar sig dock att om man inte har så mycket annat att gå på fungerar det ursprungliga värdet ganska bra.

tal = 17 antal_upprepningar = 10

uppskattning = tal

Vi skapar sedan en for-loop som har lika många iterationer som det värde vi satte in i variabeln antal_upprepningar.

tal = 17 antal_upprepningar = 10

uppskattning = tal for n in range(antal_upprepningar): ##Variabeln n används aldrig i loopen. Den finns bara där för att man måste skriva något mellan for och in.

Inne i loopen beräknar vi nästa uppskattning med hjälp av formeln x_(n+1) = x_n + a/x_n2, där x_n är den nuvarande uppskattningen och a är det värde vi vill beräkna roten ur. Vi lägger resultatet i en ny variabel ny_uppskattning

tal = 17 antal_upprepningar = 10

uppskattning = tal for n in range(antal_upprepningar): ny_uppskattning = (uppskattning + tal/uppskattning) / 2

Vi byter sedan ut vår tidigare uppskattning med den nya. Vi hade egentligen kunnat göra detta på samma rad som förra uträkningen, men för tydlighetens skull delar vi upp det.

tal = 17 antal_upprepningar = 10

uppskattning = tal for n in range(antal_upprepningar): ny_uppskattning = (uppskattning + tal/uppskattning) / 2

   uppskattning = ny_uppskattning

Nu kommer programmet att loopa igenom dessa instruktioner och för varje iteration får vi en ny, bättre uppskattning av kvadratroten. När den är färdig är det bara för oss att skriva ut resultatet. Vi lägger också till en beräkning av kvadraten av vår rot för att se hur nära den ligger talet som vi började med.

tal = 17 antal_upprepningar = 10

uppskattning = tal for n in range(antal_upprepningar): ny_uppskattning = (uppskattning + tal/uppskattning) / 2 uppskattning = ny_uppskattning

print("Roten ur {}: {}".format(tal, uppskattning)) print("{} i kvadrat: {}".format(uppskattning, uppskattning**2))

> Roten ur 17: 4.123105625617661 4.123105625617661 i kvadrat: 17.0

Vårt resultat ligger tydligen så nära att datorn inte kan se skillnad på det och det exakta värdet!

Oftast är man ute efter en viss noggrannhet när man gör en uppskattning, inte att uppskattningen ska förfinas ett specifikt antal gånger. Vi vet dock inte vad den riktiga roten är så det är lite svårt att jämföra med den, men vi kan ju alltid kvadrera vår uppskattning och jämföra med det ursprungliga talet. Vi vill att skillnaden mellan dessa tal ska vara mindre än 10^(-15), alltså att |a - x_n^2| < 10^(-15). Här har vi satt ett absolutbelopp runt skillnaden a - x_n^2. Det är för att vi inte bryr oss om uppskattningen är för stor eller för liten, bara att den ligger tillräckligt nära det riktiga värdet. Vi kan nu skriva om vårt program med detta nya villkor, och vi börjar som tidigare med invärdet.

tal = 17

Vi använder återigen det ursprungliga talet som vår första uppskattning.

tal = 17

uppskattning = tal

Vi skapar sedan en ny variabel, fel, där vi sparar hur långt bort från det faktiska värdet vår uppskattning ligger. Vi använder den inbyggda funktionen abs() för att beräkna absolutbeloppet.

tal = 17

uppskattning = tal fel = abs(tal - uppskattning**2)

Så länge det här felet är större än 10^(-15) vill vi fortsätta att räkna ut nya uppskattningar. Då känns det lämpligt med en while-sats som fortsätter att loopa medan fel är mindre än 10^(-15).

tal = 17

uppskattning = tal fel = abs(tal - uppskattning**2) while fel > 10**-15:

Inne i loopen beräknar vi precis som tidigare en ny uppskattning med hjälp av den vi redan har. Sedan skriver vi över den gamla uppskattningen med den nya.

tal = 17

uppskattning = tal fel = abs(tal - uppskattning**2) while fel > 10**-15: ny_uppskattning = (uppskattning + tal/uppskattning) / 2 uppskattning = ny_uppskattning

Men med den nya uppskattningen får vi ju också ett nytt fel. Vi räknar ut det och skriver över variabeln fel med det nya värdet.

tal = 17

uppskattning = tal fel = abs(tal - uppskattning**2) while fel > 10**-15: ny_uppskattning = (uppskattning + tal/uppskattning) / 2 uppskattning = ny_uppskattning

   fel = abs(tal - uppskattning**2)

Nu när loopen går in i nästa iteration kommer det nya felet att jämföras med 10^(-15). Så länge felet är för stort fortsätter loopen att räkna ut nya uppskattningar och fel. När programmet till slut tar sig ur loopen vet vi att felet är tillräckligt litet och att vår uppskattning är bra nog. Då behöver vi bara skriva ut resultatet.

tal = 17

uppskattning = tal fel = abs(tal - uppskattning**2) while fel > 10**-15: ny_uppskattning = (uppskattning + tal/uppskattning) / 2 uppskattning = ny_uppskattning fel = abs(tal - uppskattning**2)

print("Roten ur {}: {}".format(tal, uppskattning)) print("{} i kvadrat: {}".format(uppskattning, uppskattning**2))

Roten ur 17: 4.123105625617661 4.123105625617661 i kvadrat: 17.0

Även denna gång ligger vår uppskattning nära nog det riktiga värdet att datorn inte gör någon skillnad på dem.

Här har vi flera villkor som ska gälla för talen a, b och c:

• De ska vara positiva heltal.
• De ska summeras till 600.
• De ska uppfylla Pythagoras sats.

En rimlig ansats är att använda loopar för att skapa kombinationer av heltal med summan 600, och sedan för varje kombination undersöka om Pythagoras sats gäller. I så fall skrivs kombinationen ut.

Kombinationer med summan 600

Vi tar en sidlängd i taget. Vilka värden kan sidan a ha? Det finns olika sätt att se på det, men vi räknar i grova drag nu. Alla tal är positiva heltal så a är minst 1. Vi vet också att talen ska bli 600 tillsammans, så a måste definitivt vara mindre än 600. Vi gör en loop som räknar upp möjliga värden på a.

for a in range(1, 600):

Sidan b är också minst 1 och mindre än 600, så vi gör samma loop för b. Vi sätter den då i loopen som räknar upp a-värden, så får vi alla kombinationer av a och b. Notera att den här uppräkningen är lite för generös: a och b kan inte båda vara t.ex. 400 om summan ska bli 600, men vi lämnar sådana förfiningar åt sidan.

for a in range(1, 600): for b in range(1, 600):

När a och b har värden kan c räknas fram, eftersom de tre ska bli 600 tillsammans: a+b+c = 600 ⇔ c = 600 - a - b. Vi drar alltså bort de två första sidorna från 600, och då måste c vara återstoden.

for a in range(1, 600): for b in range(1, 600): c = 600 - a - b

Looparna skapar nu uppsättningar av a, b och c vars summor är 600. Som koden är skriven är det däremot inte garanterat att alla är positiva heltal. Eftersom looparna tillåter att a och b är t.ex. 400 samtidigt kommer c ges ett negativt tal ibland. Vi löser inte det nu utan väntar och ser om det blir ett problem istället.

Test av Pythagoras sats

Om kombinationen uppfyller att a^2 + b^2 = c^2 ska den skrivas ut. Detta undersöks med en if-sats. Kom ihåg att använda operatorn ** för "upphöjt till" och att likheten undersöks med dubbla likhetstecken.

for a in range(1, 600): for b in range(1, 600): c = 600 - a - b if a**2 + b**2 == c**2: print(a, b, c)

> 100 240 260 120 225 255 150 200 250 200 150 250 225 120 255 240 100 260

Vi får sex utskriftsrader, men de sista tre är bara en upprepning av de första tre med lite ombytta platser. Det finns därför tre unika Pythagoreiska tripplar med summan 600.

Nu är programmet klart förutom att vi inte räknat iterationerna. Vi skapar variabeln iterationer innan loopandet börjar, och då är antalet iterationer 0. I den innersta loopen ska detta värde öka, t.ex. precis när c fått ett värde. Det är nämligen då vi räknat upp en ny talkombination. I slutet av programmet skriver vi ut antalet iterationer.

iterationer = 0 for a in range(1,600): for b in range(1,600): c = 600 - a - b iterationer = iterationer + 1 if a**2 + b**2 == c**2: print(a,b,c) print('Antal iterationer:', iterationer)

> 100 240 260 120 225 255 150 200 250 200 150 250 225 120 255 240 100 260 Antal iterationer: 358801

Som programmet är skrivet nu krävs alltså nästan 359 000 iterationer. Det gör inget om du skrivit ditt program annorlunda och fått ett annat antal. Det viktiga nu är att de tre unika tripplarna hittats, och att programmet kan räkna iterationerna.

I a) testades fler kombinationer av a och b än vad som behövs. Det ledde till upprepningar i utskrifterna och att programmet tog längre tid än nödvändigt. Nu vill vi strama åt looparna, så att programmet inte räknar upp överflödiga kombinationer.

Figuren ovan visar endast de kombinationer som följer storleksordningen. Det är alltså dessa som looparna ska räkna igenom, och sedan undersöker vi för varje kombination om Pythagoras sats är uppfylld. Det svåra är nu att lista ut hur uppräkningen ska göras för att inga andra kombinationer än dessa ska räknas upp.

Möjliga värden på a

a ska vara det minsta talet. Precis som tidigare kan det vara minst 1, men den övre gränsen kan nu flyttas ned. Som figuren visar kan a inte vara större än 199, eftersom det måste finnas plats för b och c också. Om t.ex. a=200 måste b vara minst 201 och c minst 202. Summan blir då för stor!

for a in range(1, 200): ## Övre gränsen ingår inte, så detta ger a värdena 1-199.

Möjliga värden på b

b måste alltid vara större än a, så det lägsta värdet att ge b beror på vilket värde som för tillfället ligger i a. Vi låter därför loopen som sätter värden på b börja på a+1. Den övre gränsen på b bestäms av villkoret b < c. Eftersom det är ett villkor som styr den övre gränsen är det nog lättast med en while-sats.

for a in range(1, 200): b = a + 1 while b < c: b = b + 1

Variabeln c är dock inte skapad än. Den måste skapas innan while-satsen så att loopen kan påbörjas. Men när b ändras måste även c ändras, så att summan fortfarande är 600.

for a in range(1, 200): b = a + 1 c = 600 - a - b while b < c: b = b + 1 c = 600 - a - b

Nu är loopstrukturen på plats, och då kan vi sätta tillbaka kontrollen för Pythagoras sats.

for a in range(1, 200): b = a + 1 c = 600 - a - b while b < c: if a**2 + b**2 == c**2: print(a, b, c) b = b + 1 c = 600 - a - b

> 100 240 260 120 225 255 150 200 250

Slutligen vill vi räkna iterationerna. Vi skapar variabeln innan alla loopar som i a), och sedan ökar vi variabelns värde med 1 inuti den innersta loopen.

iterationer = 0 for a in range(1, 200): b = a + 1 c = 600 - a - b while b < c: iterationer = iterationer + 1 if a**2 + b**2 == c**2: print(a, b, c) b = b + 1 c = 600 - a - b print('Antal iterationer:', iterationer)

> 100 240 260 120 225 255 150 200 250 Antal iterationer: 29701

Antalet iterationer är nu bara ca en tolftedel av vad vi fick tidigare! Programmet hittar nu de tre Pythagoreiska tripplarna betydligt snabbare, och dessutom utan upprepningar.