Tävlingsprogrammering/Uppgifter/Sfinx-sex

Lägg till länkar
Från Wikibooks

Sfinx-sex (PO-kvalet 2008)

En sfinx är en varelse med ett lejons kropp och en människas huvud. Liknande kombinationer återfinns i andra kulturer, t.ex. faunen (get+människa) och gripen (örn+lejon). Man skulle kunna tro att den ringa förekomsten av sådana arter i naturen beror på viss svårighet i fortplantningen, men i denna uppgift antar vi raka motsatsen.

Med hänvisning till genetikens lagar antar vi att när två kombinationsvarelser parar sig så ärver avkomman framkroppen från den ena föräldern och bakkroppen från den andra. En grodmus som parar sig med en fiskhöna kan alltså ge upphov till antingen en grodhöna eller en fiskmus.

Skriv ett program som, givet en grupp kombinationsvarelser (somliga hannar och andra honor) beräknar antalet olika arter som kan existera i nästa generation om alla par av hanne-hona antas få ungar. Svaret ska också inkludera de arter som ingår i den ursprungliga gruppen.

Programmet ska fråga efter antalet hannar och vilken art varje hanne tillhör, samt likadant för honorna. Arten anges som en sträng med två bokstäver (valda bland A-Z), där första bokstaven beskriver framkroppen och andra bokstaven bakkroppen (t.ex. ML för människolejon). Programmet ska skriva ut det totala antalet olika arter som kan finnas när parning har skett. Observera att ordningen på bokstäverna spelar roll – MF och FM är olika arter.

Körningsexempel: 

Antal hannar ? 2  
Hanne 1 ? ML  
Hanne 2 ? FG 
Antal honor ? 3 
Hona 1 ? VM 
Hona 2 ? FM 
Hona 3 ? VF 
Antal arter: 11

Kommentar: Förutom de fem arterna i ursprungsgruppen kan följande arter ha uppkommit: FF, FL, MF, MM, VG och VL.

Lösning[redigera]

Den enda svårigheten i uppgiften är att undvika att räkna dubletter. Detta är dock lätt att fixa eftersom det finns ett begränsat antal arter, nämligen 26*26=676 stycken. Så man kan helt enkelt "markera" de möjliga arterna i en 26*26 tabell och sedan gå igenom tabellen och räkna hur många som blivit markerade. Ett annat enkelt sätt att hantera dubletter är att använda standardklassen set i C++.

Lösningsexempel i C 

#include <stdio.h>

int main(){
  char djur[10][2];
  int i,j,nhan,nhon,exist[200][200],cnt;
  printf("Antal hannar ? ");
  scanf("%d", &nhan);
  for(i=0;i<nhan;i++) {
    printf("Hanne %d ? ", i+1);
    scanf("%s", djur[i]);
  }
  printf("Antal honor ? ");
  scanf("%d", &nhon);
  for(i=0;i<nhon;i++) {
    printf("Hona %d ? ", i+1);
    scanf("%s", djur[nhan+i]);
  }
  for(i=0;i<26;i++) for(j=0;j<26;j++) exist[i][j]=0; //Nollställ alla arter
  for(i=0;i<nhan+nhon;i++) exist[djur[i][0]-'A'][djur[i][1]-'A']=1;  //Markera de ursprungliga arterna
  for(i=0;i<nhan;i++) for(j=nhan;j<nhan+nhon;j++) { //För varje föräldrapar:
    exist[djur[i][0]-'A'][djur[j][1]-'A']=1;       //Markera de två möjliga arterna för avkomman
    exist[djur[j][0]-'A'][djur[i][1]-'A']=1;
  }
  cnt=0;
  for(i=0;i<26;i++) for(j=0;j<26;j++) if(exist[i][j]) cnt++; //Räkna hur många som är markerade
  printf("Antal arter: %d\n", cnt);
  return 0;
}

Här är ett lösningsexempel i Java som använder sig av standardklassen HashSet för att lagra de olika arterna. Det som är så praktiskt med HashSet är att den inte kan innehålla dubbletter. Lägger man till ett (likadant) objekt (i detta fall en art) som redan finns sparad i vårt HashSet, så struntar den i att lägga till den. Så allt vi behöver göra är bara att generera alla arter och spara dem, så fixar HashSet problemet med dubbletter åt oss helt automatiskt. Sedan när vi är klara behöver vi bara anropa metoden size() för att få reda på hur många arter som finns. Lätt som en plätt. 

import java.util.*;

public class Sfinx
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		//Här sparar vi alla arter som kommer att uppstå.
		HashSet <String> arter = new HashSet <String> ();

		/*** Läser in alla hannar. ***/
		System.out.print("Antal hannar: ");
		int hane = scan.nextInt();

		//Sparar alla hannar.
		String [] hannar = new String [hane];

		for(int i = 0; i<hane; i++)
		{
			System.out.print("Hanne "+(i+1)+": ");
			hannar[i] = scan.next();

			//Varje ursprunglig art skulle också räknas.
			arter.add(hannar[i]);
		}
		/****************************/

		/*** Läser in alla honor. ***/
		System.out.print("Antal honor: ");
		int hona = scan.nextInt();

		//Sparar alla honor.
		String [] honor = new String [hona];

		for(int i = 0; i<hona; i++)
		{
			System.out.print("Hona "+(i+1)+": ");
			honor[i] = scan.next();

			//Varje ursprunglig art skulle också räknas.
			arter.add(honor[i]);
		}
		/*****************************/


		/*** Löser Problemet. ***/
		for(int i = 0; i<hane; i++)
		{
			//Tar en hannes framdel...
			char frontMale = hannar[i].charAt(0);

			//...och parar den med varje honas bakdel.
			for(int j = 0; j<hona; j++)
			{
				char backFemale = honor[j].charAt(1);

				//Lägger till barnet bland de nya arterna.
				//"" finns med för att casta om till String.
				arter.add(frontMale + "" + backFemale);
			}

			//Tar hannens bakdel...
			char backMale = hannar[i].charAt(1);

			//...och parar den med varje honas framdel.
			for(int j = 0; j<hona; j++)
			{
				char frontFemale = honor[j].charAt(0);

				arter.add(frontFemale + "" + backMale);
			}
		}
		/**************************/

		//Skriver ut svaret.
		System.out.println("Antal arter: " + arter.size());
	}
}

Om man nu inte känner sig bekväm med märkliga klasser som HashSet, så går det givetvis bra att använda en ArrayList, men om man inte heller känner sig bekväm med den (eller inte känner till den), så går det givetvis också bra att bara använda en vanlig array. Dock finns det en del saker man måste tänka på då. Ett lösningsexempel med den metoden finns här nedan i Java. (Observera och ta lärdom av djungelknepet att sortera en array för att lättare kunna kolla dubbletter.) 

import java.util.*;

public class Sfinx2
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		//Här sparar vi alla arter som kommer att uppstå.
		String [] arter = new String [900];
		//(Vi valde 900 bara för att det är tillräckligt stort.)

		//Vi fyller arrayen med ZZZZZ, så att vi undviker
		// NullPointerException sedan när vi ska sortera.
		Arrays.fill(arter, "ZZZZZ");
		//ZZZZZ är också ett bra val, eftersom dem kommer att lägga
		// sig sist i arrayen vid sorteringen.

		//Håller reda på var i arrayen vi ska spara nästa art.
		int artIndex = 0;

		/*** Läser in alla hannar. ***/
		System.out.print("Antal hannar: ");
		int hane = scan.nextInt();

		//Sparar alla hannar.
		String [] hannar = new String [hane];

		for(int i = 0; i<hane; i++)
		{
			System.out.print("Hanne "+(i+1)+": ");
			hannar[i] = scan.next();

			//Varje ursprunglig art skulle också räknas.
			arter[artIndex] = hannar[i];
			artIndex++;
		}
		/****************************/

		/*** Läser in alla honor. ***/
		System.out.print("Antal honor: ");
		int hona = scan.nextInt();

		//Sparar alla honor.
		String [] honor = new String [hona];

		for(int i = 0; i<hona; i++)
		{
			System.out.print("Hona "+(i+1)+": ");
			honor[i] = scan.next();

			//Varje ursprunglig art skulle också räknas.
			arter[artIndex] = honor[i];
			artIndex++;
		}
		/*****************************/


		/*** Löser Problemet. ***/
		for(int i = 0; i<hane; i++)
		{
			//Tar en hannes framdel...
			char frontMale = hannar[i].charAt(0);

			//...och parar den med varje honas bakdel.
			for(int j = 0; j<hona; j++)
			{
				char backFemale = honor[j].charAt(1);

				//Lägger till barnet bland de nya arterna.
				//"" finns med för att casta om till String.
				arter[artIndex] = frontMale + "" + backFemale;
				artIndex++;
			}

			//Tar hannens bakdel...
			char backMale = hannar[i].charAt(1);

			//...och parar den med varje honas framdel.
			for(int j = 0; j<hona; j++)
			{
				char frontFemale = honor[j].charAt(0);

				arter[artIndex] = frontFemale + "" + backMale;
				artIndex++;
			}
		}
		/**************************/

		//Sorterar arrayen. Varför? För att det blir enklare att
		// undvika att räkna dubletter då.
		Arrays.sort(arter);

		//Vi kan i alla fall anta att det åtminstone finns en art.
		int antal = 1;

		//Går igenom arrayen fram tills det att det inte finns några
		// fler arter att räkna. I övriga arrayen ligger bara "ZZZZZ".
		for(int i = 1; i<artIndex; i++)
		{
			//Om elementet innan inte är detsamma som detta, då
			// är detta en ny art, som vi bör räkna.
			if(!arter[i].equals(arter[i-1])) antal++;

			//Om det däremot skulle vara samma art som den som låg
			// framför/innan, ja då skiter vi att räkna den.
		}

		//Skriver ut svaret.
		System.out.println("Antal arter: " + antal);
	}
}

Lösning i Haskell. 

-- Sfinx-Sex
module Main where
import IO
import Data.Set

main = do {
	putStr "Antal hannar: ";
	antal1 <- getLine;
	males <- readMales (read antal1);
	
	putStr "Antal honor: ";
	antal2 <- getLine;
	females <- readFemales (read antal2);
	
	arter <- return (haveSex males females);
	
	putStrLn ("Antal arter: " ++ (show $ size arter))
}

readMales :: Int -> IO [String]
readMales 0 = return []
readMales n = do {
		putStr "Hanne ? ";
		sfinx <- getLine;
		rest <- readMales $ n-1;
		return (sfinx:rest)
}

readFemales :: Int -> IO [String]
readFemales 0 = return []
readFemales n = do {
		putStr "Hona ? ";
		sfinx <- getLine;
		rest <- readFemales $ n-1;
		return (sfinx:rest)
}

haveSex :: [String] -> [String] -> Set String
haveSex males females = unions [baseSet, set1, set2]
	where
	baseSet = union (fromList males) (fromList females)
	set1 = fromList [ m1:f2:[] | (m1:_:[]) <- males, (_:f2:[]) <- females]
	set2 = fromList [ f1:m2:[] | (_:m2:[]) <- males, (f1:_:[]) <- females]
Hämtad från ”https://sv.wikibooks.org/w/index.php?title=Tävlingsprogrammering/Uppgifter/Sfinx-sex&oldid=49523”