C/Eksempel: brøkrekning

Nå skal vi se på et eksempel som på mange måter tar for seg det vi har lært så langt: Variabler, funksjoner og datastrukturer. Vi skal bruke dette til å lage et program for å rekne med brøker. Jeg antar de fleste vet hva en brøk er, men kort sagt er det en representasjon av et tall ved hjelp av divisjon. Det vil si at 0.25 kan skrives som 1/4 ("1 av 4", "1 over 4", "1 delt på 4" osv.) De to delene av en brøk kalles teller (over brøkstreken) og nevner (under brøkstreken.) I matematikken er det en rekke regler for å utføre aritmetiske operasjoner på brøker:

Addisjon og subtraksjon:

${\frac {a}{b}}\pm {\frac {c}{d}}={\frac {a\cdot d\pm c\cdot b}{b\cdot d}}$

Multiplikasjon:

${\frac {a}{b}}\cdot {\frac {c}{d}}={\frac {a\cdot c}{b\cdot d}}$

Divisjon:

${\frac {a}{b}}\div {\frac {c}{d}}={\frac {a\cdot d}{b\cdot c}}$

Representasjon av brøker

Vi skal altså lage et program som kan håndtere brøker og utføre operasjoner som å addere, subtrahere, multiplisere og dividere dem. Noe av det første vi må avgjøre da, er hvordan vi skal representere en brøk. Vi kan ha to variabler, en for teller og en for nevner, en tabell med to elementer (for teller og nevner), eller vi kan, som vi her skal, bruke en datastruktur med to felt:

typedef struct {
	int teller;
	int nevner;
} brok;

Nå som vi vet hvordan vi skal representere en brøk i C, kan vi tenke ut forskjellige funksjoner vi vil at programmet skal ha og skrive opp omtrent hvordan deklarasjonene blir:

brok Add(brok a, brok b);
brok Sub(brok a, brok b);
brok Mul(brok a, brok b);
brok Div(brok a, brok b);

Vi vil altså kunne f.eks. addere brøker ved å gi Add to brøker som argument og få resultatet i form av en ny brøk tilbake. Vi kan like så gjerne definere Add. Dette blir en smal sak, og går for det meste ut på å omforme den matematiske regelen over til C-kode:

brok Add(brok a, brok b)
{
	brok resultat;

	resultat.teller = a.teller * b.nevner + b.teller * a.nevner;
	resultat.nevner = a.nevner * b.nevner;
	return resultat;
}

Funksjonen får altså to brøker, a og b, av datatypen vi definerte tidligere, og oppretter en ny brøk for å holde svaret, som den senere skal returnere. De andre funksjonene blir som følger:

brok Sub(brok a, brok b)
{
	brok resultat;

	resultat.teller = a.teller * b.nevner - b.teller * a.nevner;
	resultat.nevner = a.nevner * b.nevner;
	return resultat;
}

brok Mul(brok a, brok b)
{
	brok resultat;

	resultat.teller = a.teller * b.teller;
	resultat.nevner = a.nevner * b.nevner;
	return resultat;
}

brok Div(brok a, brok b)
{
	brok resultat;

	resultat.teller = a.teller * b.nevner;
	resultat.nevner = a.nevner * b.teller;
	return resultat;
}

Vi kan teste funksjonene vi nå har laget:

int main(void)
{
	brok b1 = {3,6};
	brok b2 = {3,4};
	brok svar;

	svar = Add(b1, b2);
	printf("%d/%d\n", svar.teller, svar.nevner);
	return 0;
}

Her får vi følgende utskrift på skjermen:

30/24

Vi kan også teste Mul. Da får vi følgende utskrift:

9/24

Forenkling

Funksjonene våre ser ut til å fungere, men det er ett lite problem: Svarene er ikke skrevet på den enkleste måten. De enkleste svarene hadde vært:

5/4

for Add og:

3/8

for Mul.

Hvordan kan vi få til dette? Vi må korte brøkene ved å finne det største tallet som både teller og nevner kan deles på, som kalles største felles faktor eller greatest common divisor. I utskriftene over er det tallet 6 som er det høyeste tallet som både 30 og 24 kan deles på, og 3 som er det høyeste som 9 og 24 kan deles på. For å finne det høyeste tallet som hvilke som helst vilkårlige tall kan deles på, kan vi benytte Euklids algoritme, som er slik:

int Fellesfaktor(int a, int b)
{
	int c;

	while (a != 0) {
		c = a;
		a = b % a;
		b = c;
	}
	return b;
}

(Husk at %-operatøren tar resten etter en divisjon, dvs. 7 % 2 = 3 fordi 7 / 2 gir 4 og 3 i rest.)

Her vil b deles på a og tatt resten av, helt til resten er lik 0: Da er b det høyeste delelige tallet som tallene a og b som funksjonen fikk da den ble kalt, er delelige på. a vil hele tiden få resten av forrige divisjon, og b vil få det a var før det. Dette gjentar seg til resten av b / a = 0.

Vi kan tenke oss at løkka går slik når Fellesfaktor får argumentene 30 og 24:

a	b	Kommentar
30	24	Vi lar a være resten av 24 / 30 (b % a) som er 24, og b være det a var før, dvs. 30.
24	30	Vi lar a være resten av 30 / 24 som er 6, og b være det a var før, dvs. 24.
6	24	Vi lar a være resten av 30 / 24 som er 0, og b være det a var før, dvs. 6
0	6	Når a er lik 0 var resten av divisjonen 0, da inneholder b det tallet som gjorde divisjonen suksessfull, altså det tallet som argumentene a og b kan deles på. Løkka avbrytes fordi while-testen blir usann.

Med funksjonen for å finne høyeste fellesfaktor kan vi forenkle brøkene vi får som resultat av de forskjellige aritmetiske operasjonene vi utfører. Vi kan skrive en generell funksjon som tar en brøk og returnerer en forenklet versjon av den:

brok Forenkle(brok a)
{
	int fellesfaktor = Fellesfaktor(a.teller, a.nevner);

	a.teller = a.teller / fellesfaktor;
	a.nevner = a.nevner / fellesfaktor;
	return a;
}

Men hvor skal vi kalle denne fra? Skal vi måtte gjøre dette selv etter hver aritmetiske operasjon? Det letteste blir nok å kalle den der vi returnerer svaret av hver operasjon, altså i return-uttrykkene. Vi gjør altså denne enkle endringen:

return Forenkle(resultat);

i stedet for

return resultat;

Dette fungerer fordi Forenkle blir kalt før funksjonen returnerer. Returverdien blir altså resultatet av Forenkle.

Nå har vi skrevet et komplett system for å rekne med brøker. Om vi vil kan vi lage oss et grensesnitt rundt dette, der vi f.eks. spør om brøkstykker som skal løses, men det er noe som vil kreve et helt eksempelkapittel i seg selv. Vi kan dog se på et brøkstykke og løse dette ved hjelp av funksjonene våre:

${\frac {3+{\frac {2}{5}}}{2-{\frac {5}{2}}}}$

Denne kan vi løse med følgende main-funksjon:

int main(void)
{
	brok b1 = {3,1};
	brok b2 = {2,5};
	brok b3 = {2,1};
	brok b4 = {5,2};
	brok svar;

	svar = Div(Add(b1, b2), Sub(b3, b4));
	printf("%d/%d\n", svar.teller, svar.nevner);
	return 0;
}

Her definerer vi altså de fire "underbrøkene" hver for seg, og rekner dem ut ved å dividere resultatet av b1 + b2 med resultatet av b3 - b4. Dette går an å gjøre såpass enkelt fordi Div forventer to brøker, noe retuverdiene av Add og Sub er. Dermed trenger vi ikke lagre resultatene av disse operasjoner i mellomvariabler, vi kan gi dem til Div med en gang. Vi får -34/5 som svar, noe som stemmer helt, og som er så forenklet som mulig.

Hele eksempelkoden

Hele brøkprogrammet vårt ser slik ut:

#include <stdio.h>

/* Datastrukturen for brøker */
typedef struct {
	int teller;
	int nevner;
} brok;

/* Funksjonsdeklarasjoner */
brok Add(brok a, brok b);
brok Sub(brok a, brok b);
brok Mul(brok a, brok b);
brok Div(brok a, brok b);
int Fellesfaktor(int a, int b);
brok Forenkle(brok a);

/* Løs brøken (3 + 2/5) / (2 - 5/2) */
int main(void)
{
	brok b1 = {3,1};
	brok b2 = {2,5};
	brok b3 = {2,1};
	brok b4 = {5,2};
	brok svar1;
	brok svar2;

	svar1 = Div(Add(b1, b2), Sub(b3, b4));	

	printf("%d/%d\n", svar1.teller, svar1.nevner);
	return 0;
}

/* Addér brøken a med brøken b og returner en brøk med svaret */
brok Add(brok a, brok b)
{
       brok resultat;

       resultat.teller = a.teller * b.nevner + b.teller * a.nevner;
       resultat.nevner = a.nevner * b.nevner;
       return Forenkle(resultat);
}

/* Subtraher brøken b fra brøken a */ 
brok Sub(brok a, brok b)
{
       brok resultat;

       resultat.teller = a.teller * b.nevner - b.teller * a.nevner;
       resultat.nevner = a.nevner * b.nevner;
       return Forenkle(resultat);
}

/* Multipliser brøken a med brøken b */
brok Mul(brok a, brok b)
{
       brok resultat;

       resultat.teller = a.teller * b.teller;
       resultat.nevner = a.nevner * b.nevner;
       return Forenkle(resultat);
}

/* Divider brøken a på brøken b */
brok Div(brok a, brok b)
{
       brok resultat;

       resultat.teller = a.teller * b.nevner;
       resultat.nevner = a.nevner * b.teller;
       return Forenkle(resultat);
}

/* Finn høyeste fellesfaktor av a og b */
int Fellesfaktor(int a, int b)
{
       int c;

       while (a != 0) {
               c = a;
               a = b % a;
               b = c;
       }
       return b;
}

/* Forenkle brøken a */
brok Forenkle(brok a)
{
       int fellesfaktor = Fellesfaktor(a.teller, a.nevner);

       a.teller = a.teller / fellesfaktor;
       a.nevner = a.nevner / fellesfaktor;
       return a;
}