Tävlingsprogrammering/Uppgifter/Räkna med bråk
Räkna med bråk (PO-kvalet 2008)
I egyptisk matematik hade de så kallade heltalsreciprokerna
särskild betydelse. Övriga bråk skrevs som summor av dessa tal, t.ex.
Skriv ett program som tar emot ett bråk (förkortat så långt som möjligt) och avgör om det kan skrivas som en sådan summa, under villkoren att bara de tio första heltalsreciprokerna (alltså t.o.m. 1/10) får användas, och att varje tal endast får användas en gång. Om det går ska programmet skriva ut de ingående termerna i summan, annars ska det skriva ut Omöjligt. Om det finns flera lösningar ska programmet skriva ut vilken som helst av dem.
Två körningsexempel:
Täljare ? 67 Nämnare ? 60 Termer: 1/2 1/4 1/5 1/6
Täljare ? 2 Nämnare ? 5 Omöjligt
Lösning
[redigera]Antalet möjliga delmängder av de tio termerna är bara 210=1024. Därför kan vi lätt testa alla möjligheter, beräkna summan och jämföra den med det inmatade bråket. För att enkelt generera alla delmängderna kan man använda sig av bit-visa operatorer. Fördelen med detta är att man kan använda en vanlig loop där ett heltal går från 0 till 1023 (eller uttryckt binärt från 0000000000 till 1111111111). Varje bit i talet anger om ett visst element ska vara med i delmängden eller inte. Exempelvis motsvarar talet 0010010110 delmängden {1/2, 1/3, 1/5, 1/8} om vi räknar från höger. Detsamma går förstås att göra med en rekursiv funktion eller (i nödfall) tio nästlade for-loopar.
För att addera två bråk ska man, enligt grundskolans bråkräkning, hitta minsta gemensamma nämnaren (lcm). Detta går i och för sig lätt eftersom lcm(k,n)=k*n/gcd(k,n), där gcd (största gemensamma delaren) kan hittas genom Euklides algoritm. Men det finns ingen anledning att krångla, talen blir inte större än att vi har råd att använda k*n som nämnare, alltså
vilket upprepas för vart och ett av de ingående bråken i summan. Naturligtvis är det inte säkert att det resulterande bråket är maximalt förkortat (detta gäller även om vi använder minsta gemensamma nämnaren), men vi är bara intresserade av att jämföra det med det inmatade bråket och den jämförelsen görs lätt genom att multiplicera korsvis (flyttalsräkning bör undvikas p.g.a. avrundningsfel).
Lösningsexempel i C
#include <stdio.h>
int main() {
int k,n,t,i,ta,na;
printf("Täljare ? ");
scanf("%d", &ta);
printf("Nämnare ? ");
scanf("%d", &na);
for(i=0;i<1024;i++) { //Loopa över delmängderna
t=0; n=1; //Starta med talet 0 (kan skrivas 0/1)
for(k=1;k<=10;k++) if((i>>(k-1))&1) { //Är den k:te biten från höger 1?
t=t*k+n; //Addera 1/k till den framväxande summan t/n
n*=k;
}
if(ta*n==na*t) { //Är t/n lika med ta/na ?
printf("Termer: ");
for(k=1;k<=10;k++) if((i>>(k-1))&1) printf("%d/%d ",1,k); //Skriv ut termerna
printf("\n");
return 0;
}
}
printf("Omöjligt\n"); //Hit kommer vi bara om if-satsen aldrig blir sann
return 0;
}
Ett lösningsexempel i Java som använder en rekursiv metod för att testa alla kombinationer och kollar om någon fungerar. Lösningen sätter alla bråk på gemensam nämnare (om det går) och sedan testar att addera ihop (tillåtna) täljare tills man har fått samma täljare som användaren matade in. Om man inte har fått samma täljare när alla kombinationer har prövats, så var uppgiften omöjlig och programmet skriver följaktligen ut det.
import java.util.*;
public class Fractions
{
//Nämnarna till våra bråk som vi får bilda summor av.
static int [] denominator = {1,2,3,4,5,6,7,8,9,10};
//Täljarna till våra bråk, när vi har förlängt alla till gemensam nämnare.
//Alla initieras till 0. Om en täljare senare fortfarande är 0, så betyder det
// att det bråket inte är kompatibelt med bråket som användaren har matat in.
static int [] numerator = new int [denominator.length];
//Täljaren som användaren ska ange.
static int taljare;
//Nämnaren som användaren ska ange.
static int namnare;
//Sparar talföljden av bråk som kunde bilda det önskade bråket.
//Om längden på strängen frotfarande är 0 vid programmets slut
// så betyder det att uppgiften var omöjlig.
static String successful = "";
//Vår rekursiva funktion som ska lösa problemet.
/*
frac: Täljaren till det bråk vi för tillfället har. Nämnaren behöver vi inte
hålla reda på eftrsom den är densamma för alla.
sequence: Talföljden av bråk som ledde fram till vårt nuvarande.
int i: Indexet för det bråk vi är på och ska testa att lägga till på talföljden.
*/
public static void rek(int frac, String sequence, int i)
{
//Om vår täljare är = den önskade täljaren så har vi lyckats.
if(frac==taljare)
{
//Sparar talföljden som ledde fram till svaret.
successful = sequence;
//Det är ju dumt att lägga till bråk på ett bråk som redan är rätt.
return;
}
else if(frac>taljare || i>=denominator.length)
{
//Om vårt bråk redan är större än det önskade, så behöver vi ju inte fortsätta
// att lägga till bråk på talföljden. Det vore ju dumt.
//Eller om vi redan har avverkat alla bråk, då ska man avbryta.
return;
}
//Om detta bråk är kompatibelt med vårt bråk.
if(numerator[i]!=0)
{
//Lägger till bråket på talföljden.
rek(frac+numerator[i], sequence+"1/"+denominator[i]+" ", i+1);
//Bara för att bråket är kompatibelt, så behöver ju inte det betyda att det ska ingå i den korrekta talfölden.
//Att testa att inte ta med bråket är minst lika viktigt.
rek(frac, sequence, i+1);
}
else
{
//Om bråket inte var kompatibelt, så ska det givetvis inte ingå i talfölden och vi går vidare till nästa bråk.
rek(frac, sequence, i+1);
}
//Här slutar metoden.
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Täljare: ");
taljare = scan.nextInt();
System.out.print("Nämnare: ");
namnare = scan.nextInt();
//Loopar igenom alla bråk och kollar om de funkar tillsammans med det inmatade bråket.
for(int i = 0; i<denominator.length; i++)
{
//Om den inmatade nämnaren är jämnt delbar med nuvarande bråks nämnare, så är bråket kompatibelt.
if(namnare%denominator[i]==0)
{
//Då tänker vi oss att vi förlänger bråket till det inmatade bråkets nämnare. Jag sa vi tänker.
//Eftersom alla kompatibla bråk kommer ha samma nämnare som det inmatade bråkets nämnare,
//när de är förlängda så är det ju onödigt att ändra på dem. Det vi behöver ändra på är bråkets täljare bara
//vilken blir divisionen mellan nämnarna.
numerator[i] = namnare/denominator[i];
}
//Om inte så förblir täljaren till bråket 0, vilket indikerar att bråket inte är kompatibelt.
}
//Nu ska vi hitta talföljden, det enda vi behöver göra är att addera ihop våra täljare som vi har tagit fram
// i loopen ovan tills vi får samma täljare som användaren har matat in. Lätt som en plätt.
//Vi börjar så klart med 0 (vi har inte adderat några täljare ännu), en tom sträng (inga tal ingår i talföljden än så länge)
// och vi ska börja att testa med det första bråket (täljaren) som har index 0.
rek(0, "", 0);
//Om strängen som har svaret inte har längden 0, så finns det ett svar.
if(successful.length()!=0)
{
System.out.println("Termer: " + successful);
}
else //Om den är 0 så var visst uppgiften omöjlig.
{
System.out.println("Omöjligt");
}
}
}
Lösning i Haskell.
-- Räkna med Bråk
module Main where
import IO
import Data.Ratio
main = do {
putStr "Taljare: ";
taljare <- getLine;
numer <- return $ read taljare;
putStr "Namnare: ";
namnare <- getLine;
denom <- return $ read namnare;
putStrLn (isPossible $ (%) numer denom)
}
reciproker = [(%) 1 1, (%) 1 2, (%) 1 3, (%) 1 4, (%) 1 5, (%) 1 6, (%) 1 7, (%) 1 8, (%) 1 9, (%) 1 10]
isPossible :: Rational -> String
isPossible n = loop n 0 "Termer:"
where
loop r p acc | r==0 = acc
| p==10 || r<0 = "Omojligt"
| otherwise = if (branch1 == "Omojligt")
then branch2
else branch1
where
branch1 = loop (r - (reciproker !! p)) (p+1) (acc ++ " 1/" ++ (show $ p+1))
branch2 = loop r (p+1) acc