...hvordan kan man finne ut, uten å utføre den faktiske divisjonen, om brøken vil kunne utvides til et desimaltall med endelig antall desimaler eller ikke?
F.eks., hvis man får a = 1 og b = 3, som tilsvarer [tex]1 \over 3[/tex], da kan ikke brøken utvides til et desimaltall, fordi man vil få uendelig antall desimaler. Men hvis man derimot får a = 2 og b = 5, kan brøken utvides til et desimaltall med endelig antall desimaler, nemlig 0,4.
Er det mulig å finne ut dette uten å utføre selve divisjonen?
Gitt en brøk a/b...
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
-
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
Svaret på spørsmålet er ja. Anta at du har en brøk a/b der 0 < a < b, og at denne brøken er maksimalt forkortet, dvs. at største felles divisor (SFD) til a og b er 1. Dersom det desimaltallet som denne brøken tilsvarer, har et endelig antall desimaler n, så finnes det et naturlig tall m < 10[sup]n[/sup] slik at
[tex](1) \;\; \frac{a}{b} \;=\; \frac{m}{10^n} \, .[/tex]
Ved å multiplisere (1) med 10[sup]n[/sup], får vi at
[tex](2) \;\; \frac{a \cdot 10^n}{b} \;=\; m.[/tex]
I.o.m. at m er et naturlig tall og SFD(a,b) = 1, følger det av (2) at b er en faktor i 10[sup]n[/sup]. M.a.o. er 2 og 5 de eneste primtall som kan være delelig med b.
På grunnlag av dette resonnementet kan vi stille opp følgende regel:
En brøk a/b som er maksimalt forkortet, kan skrives som et endelig desimaltall hvis og bare hvis nevneren kan skrives på formen b = 2[sup]p [/sup] 5[sup]q[/sup], der p og q er ikke-negative heltall.
[tex](1) \;\; \frac{a}{b} \;=\; \frac{m}{10^n} \, .[/tex]
Ved å multiplisere (1) med 10[sup]n[/sup], får vi at
[tex](2) \;\; \frac{a \cdot 10^n}{b} \;=\; m.[/tex]
I.o.m. at m er et naturlig tall og SFD(a,b) = 1, følger det av (2) at b er en faktor i 10[sup]n[/sup]. M.a.o. er 2 og 5 de eneste primtall som kan være delelig med b.
På grunnlag av dette resonnementet kan vi stille opp følgende regel:
En brøk a/b som er maksimalt forkortet, kan skrives som et endelig desimaltall hvis og bare hvis nevneren kan skrives på formen b = 2[sup]p [/sup] 5[sup]q[/sup], der p og q er ikke-negative heltall.
Takk! Så genialt!
En grei algoritme for å få til dette i et dataprogram er vel noe sånt som:
Skal innrømme at jeg prøver å lage et dataprogram som bl.a. kan regne med brøker, og da er egentlig funksjonen til det her å bestemme om det er "lurt" å utvide brøken til et desimaltall eller beholde den som den er. Og det er jo absolutt ikke lurt å utvide en brøk til et desimaltall hvis det har uendelig mange desimaler...
Dette var bare et kjapt forsøk på en algoritme som fungerer. Den deler nevner på 2 til den ikke kan deles på 2 mer, så deler den nevner på 5 til den ikke kan deles på 5 mer. Så sjekker den om det er igjen flere faktorer.
Det sier vel seg selv at det tar lang tid å dele på 2 og 5 mange ganger etter hverandre for store tall, og worst-case-scenariet kan jo gå ut på at nevner er på formen 2^n, da programmet vil dele på 2 ganske, ganske lenge. Kan det finnes en raskere metode som involverer logaritmer, kanskje?
En grei algoritme for å få til dette i et dataprogram er vel noe sånt som:
Kode: Velg alt
bool Expandable(int a, int b)
{
if (!(a > 0 && a < b)) return false;
// quotient q
int q = b;
while(q % 2 == 0)
q = q / 2;
while(q % 5 == 0)
q = q / 5;
return q == 1;
}
Dette var bare et kjapt forsøk på en algoritme som fungerer. Den deler nevner på 2 til den ikke kan deles på 2 mer, så deler den nevner på 5 til den ikke kan deles på 5 mer. Så sjekker den om det er igjen flere faktorer.
Det sier vel seg selv at det tar lang tid å dele på 2 og 5 mange ganger etter hverandre for store tall, og worst-case-scenariet kan jo gå ut på at nevner er på formen 2^n, da programmet vil dele på 2 ganske, ganske lenge. Kan det finnes en raskere metode som involverer logaritmer, kanskje?