Tävlingsprogrammering/Uppgifter/Datumräkning
Datumräkning
Eftersom 2009 inte är ett skottår har det förstås 365 dagar. För att kontrollera detta ville
datumräkningsmyndigheten ändå skriva upp alla datum: 1/1, 2/1, 3/1 o.s.v. och räkna
hur många olika datum som finns. Tyvärr uppfattade datorprogrammet man använde
de inskrivna datumen som bråktal, så exempelvis räknades 1/3, 2/6, 3/9 och 4/12 som
samma datum eftersom de motsvarar samma tal. Man kom därför fram till det något
sensationella resultatet att året bara har 231 datum, vilket snabbt utlöste en storm av
beställningar från kulturer med andra kalendersystem som också ville kontrollera hur
många datum man egentligen har. Du ska skriva ett datorprogram som frågar efter
antalet månader på året (högst 12) samt antalet dagar i varje månad (högst 40) och beräknar
hur många olika datum det finns, förutsatt att man behandlar dem som bråktal.
Körningsexempel:
Antal månader ? 6 Dagar i månad 1 ? 2 Dagar i månad 2 ? 5 Dagar i månad 3 ? 3 Dagar i månad 4 ? 6 Dagar i månad 5 ? 5 Dagar i månad 6 ? 2 Antal olika datum: 15
Kommentar: De olika datumen är 1/1, 2/1, 1/2, 3/2, 5/2, 1/3, 2/3, 1/4, 3/4, 5/4, 1/5, 2/5, 3/5, 4/5 och 1/6.
Lösning
redigeraEn double är tillräckligt noggrann för att hålla koll på såna här simpla tal:
#include <cstdio>
#include <set>
int main(){
int M, D;
std::set<double> alla_dagar;
printf("Antal månader ? ");
scanf("%d", &M);
for(int i=1; i<=M; i++){
printf("Dagar i månad %d ? ", i);
scanf("%d", &D);
for(int j=1; j<=D; j++){
alla_dagar.insert((double)j/i);
}
}
printf("\nAntal olika datum: %d\n", (int)alla_dagar.size());
}
och om man ändå inte litar på doubles kan man skapa en enkel Fraction-klass som kan jämföra två fractions vilken som är minst/störst, vilket är det enda som behövs för std::set.
#include <cstdio>
#include <set>
struct Fraction {
int t;
int n;
bool operator<(const Fraction& o) const {
return t*o.n < o.t*n;
}
Fraction(int t, int n) : t(t), n(n) {};
};
int main(){
int M, D;
std::set<Fraction> alla_dagar;
printf("Antal månader ? ");
scanf("%d", &M);
for(int i=1; i<=M; i++){
printf("Dagar i månad %d ? ", i);
scanf("%d", &D);
for(int j=1; j<=D; j++){
alla_dagar.insert(Fraction(j, i));
}
}
printf("\nAntal olika datum: %d\n", (int)alla_dagar.size());
}
Jag har använt programmeringsspråket Python. Problemet bilr då väldigt lätt, efterson Python 2.6 stöder både bråktal (Fraction) och mängder (set). Det är bara att lägga in varje datum i mängden, så kommer dubbletter automatiskt försvinna. Det enda man måste tänka på är att listor alltid börjar på 0.
# -*- coding: cp1252 -*-
from fractions import Fraction
n = input("Antal månader ? ")
manader = [] # Lista över längden på varje månad
for manad in range(n):
dagar = input("Dagar i månad " + str(manad + 1) + " ? ")
manader.append(dagar) # Lägg till i månadslistan.
datum = set() # En tom mängd med alla unika datum
# För varje månad (0, 1, ..., n-1) i månader:
for manad in range(len(manader)):
# För varje dag i denna månad:
for dag in range(manader[manad]):
dat = Fraction(dag + 1, manad + 1) # Dagens datum.
# Notera att Fraction(1, 3) == Fraction(2, 6)
datum.add(dat) # Lägg till dat bland datumen.
# Notera att om värdet redan finns läggs det inte till igen.
# Dessa två rader är det som "gör allt arbete"
print "\nAntal olika datum:", len(datum)
Här nedan följer ett lösningsexempel i Java. Det luriga med den här uppgiften är att inte gå i fällan att betrakta varje bråk som en float eller double, för då kommer man få avrundningsfel och följaktligen fel svar för vissa testdata. Så vad gör man då? Hur kollar man att två bråk är lika utan att räkna ut dem? Ja det vi vill undvika men ändå utföra är jämförelsen a/b==c/d, är denna jämförelse ekvivalent med någon jämförelse där man bara har heltal? Ja det är den, nämligen jämförelsen a*d==c*b, vilken skulle fungera utmärkt i programmet.
Dock är det inte så vi har gjort i detta exempel, utan här har vi bara multiplicerat alla bråk med en gemensam nämnare (på så sätt kan vi vara säkra på att divisionen går jämnt ut) och därefter delat den nya täljaren (dagen*gemensam nämnare) med nämnaren (månaden). Sedan behöver vi bara jämföra alla täljare (som är heltal) med varandra och undvika räkna dubbletterna.
Visst skulle vi kunna slänga alla tal i ett HashSet och sedan bara fråga HashSetet hur många element den innehåller för att få svaret, men här kör vi old-school med en vanlig array.
import java.util.*;
public class Datum
{
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal månader: ");
int antal = scan.nextInt();
//Håller reda på antalet dagar varje månad.
int [] dagar = new int [antal];
//Gemensam nämnare. Kommer att bli antal! (läs: fakultet).
//Om antalet månader är 7 kommer cmd = 1*2*3*4*5*6*7.
int cmd = 1;
//Antalet dagar på året.
int totalt = 0;
//Läser in antalet dagar varje månad.
for(int i = 0; i<antal; i++)
{
System.out.print("Dagar i månad " + (i+1) + ": ");
dagar[i] = scan.nextInt();
//Ökar på antalet dagar på året.
totalt += dagar[i];
//Skapar gemensam nämnare.
cmd *= (i+1);
}
//Skapar array för alla bråktal.
int [] frac = new int [totalt];
//Håller reda på var i arrayen vi är.
int f = 0;
//Går igenom alla dagar på året och genererar dess bråk på så
// sätt att man multiplicerar med gemensam nämnare och sedan delar
// med vanliga nämnaren (månaden). På så sätt slipper vi hålla reda på
// varje bråks nämnare eftersom alla har samma (cmd), och vi behöver bara
// jämföra vanliga heltal senare för att kolla om två bråk är lika.
for(int i = 0; i<antal; i++)
{
for(int j = 1; j<=dagar[i]; j++)
{
//Skapar täljaren för bråket.
frac[f] = cmd*j/(i+1);
f++;
}
}
//Sorterar bråken (täljarna).
Arrays.sort(frac);
//Vi har åtminstone ett bråk.
int olika = 1;
//Jämför bråkens täljare för att hitta dubletter.
for(int i = 1; i<frac.length; i++)
{
//Om detta bråk inte är detsamma som föregående bråk.
//Ja då har vi hittat ett nytt bråk.
if(frac[i]!=frac[i-1]) olika++;
}
//Skriver ut svaret.
System.out.println("\nAntal olika datum: " + olika);
}
}
Lösning i Haskell.
-- Datumräkning
module Main where
import IO
import Data.Set
import Data.Ratio
main = do {
putStr "Antal manader: ";
antal <- getLine;
months <- readMonths 1 (read antal);
putStrLn ("Antal olika datum: " ++ (show $ size $ datum months 1))
}
readMonths :: Int -> Int -> IO [Integer]
readMonths _ 0 = return []
readMonths n to = do {
putStr ("Dagar i manad " ++ (show n) ++ " ? ");
days <- getLine;
rest <- readMonths (n+1) (to-1);
return $ (read days):rest
}
datum :: [Integer] -> Integer -> Set Rational
datum [] _ = empty
datum (h:t) n = union (fromList [(%) x n | x <- [1..h]]) (datum t (n+1))