Tävlingsprogrammering/Uppgifter/Släktträffen

Släktträffen

Det är släktträff för ättlingar till Ida-Ottilia Isaksson. För enkelhets skull har man upprättat ett släktträd och numrerat alla ättlingarna från 1 till N, samt givit Ida-Ottilia själv numret 0. Bland de M personerna vid ditt bord uppkommer en diskussion om vem som är er närmaste gemensamma släkting. Skriv ett program som räknar ut detta.

FIGUR 1. Släktträden för de två körningsexemplen.

Programmet ska fråga efter antalet ättlingar, N, (2≤ N ≤ 20) och därefter fråga efter numret på varje persons förälder, vilket naturligtvis alltid är mellan 0 och N. Därefter ska programmet fråga efter antalet personer vid bordet, M (2≤ M ≤ N), och läsa in numret på var och en av dem. Programmet ska skriva ut numret på den person som är närmast gemensam släkting (uppåt i trädet) till alla vid bordet. Observera att detta ibland kan vara någon vid bordet.

Körningsexempel 1

Antal ättlingar ? 8
Förälder till nr 1 ? 6
Förälder till nr 2 ? 0
Förälder till nr 3 ? 0
Förälder till nr 4 ? 2
Förälder till nr 5 ? 0
Förälder till nr 6 ? 5
Förälder till nr 7 ? 6
Förälder till nr 8 ? 5
Antal vid bordet ? 3
Person 1 vid bordet ? 1
Person 2 vid bordet ? 5
Person 3 vid bordet ? 8

Närmaste släkting: 5

Körningsexempel 2

Antal ättlingar ? 4
Förälder till nr 1 ? 2
Förälder till nr 2 ? 0
Förälder till nr 3 ? 0
Förälder till nr 4 ? 3 
Antal vid bordet ? 2
Person 1 vid bordet ? 4
Person 2 vid bordet ? 1

Närmaste släkting: 0

Lösning

Svårigheten här kan vara att representera datastrukturen träd. Men det behövs ingen effektiv algoritm så det räcker faktiskt att spara föräldrarna precis som de läses in.

#include <stdio.h>

int p[1000];

int hitta(int m, int n) {  //Hittar närmsta gemensamma anfader till m och n.
  int k;
  for(;m>0;m=p[m])   //Gå uppåt från ena personen.
     for(k=n;k>0;k=p[k])    //Gå uppåt från andra personen.
        if(k==m) return k;     //Ta första bästa.
}


int main() {
  int N,M,i,anf,g[1000];
  scanf("%d", &N);
  for(i=1;i<=N;i++) scanf("%d", &p[i]);
  scanf("%d", &M);
  for(i=0;i<M;i++) scanf("%d", &g[i]);
  anf=g[0];
  for(i=1;i<M;i++) anf=hitta(anf,g[i]);   //Väljer närmsta gemensamma anfader mellan den hittills hittade och var och en av personerna vid bordet.
  printf("%d\n", anf);
  return 0;
}

Lösning i Java som bygger på idén att vi kan markera avståndet mellan en person och en förfader i en matris och sedan kolla för vilken förfader det totala avståndet till denna för personerna vid bordet blir som minst.

import java.util.*;

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

		System.out.print("Antal ättlingar: ");
		int N = scan.nextInt();

		//Där vi sparar föräldern till vardera ättling.
		int [] parents = new int [N+1];

		//Ida-Ottilda får ha förälder -1.
		parents[0] = -1;

		//Läser in föräldrar.
		for(int i = 1; i<=N; i++)
		{
			System.out.print("Förälder till nr " + i + ": ");
			parents[i] = scan.nextInt();
		}

		System.out.print("Antal vid bordet: ");
		int antal = scan.nextInt();

		//Sparar vilka som sitter vid bordet.
		int [] bord = new int [antal];

		//Läser in personerna vid bordet.
		for(int i = 0; i<antal; i++)
		{
			System.out.print("Person " + (i+1) + " vid bordet: ");
			bord[i] = scan.nextInt();
		}

		//Vårt "släktträd". Där den vänstra "haken" beskriver personen
		//i fråga, t.ex. person 4. Och den andra "haken" beskriver en
		//annan person. Siffran som lagras på en viss plats beskriver
		//avståndet mellan personen i vänstra "haken" och personen i
		//högra "haken". Avståndet mellan förälder och barn är 1, osv.
		int [][] trad = new int [N+1][N+1];

		//Beräknar avståndet för varje person vid bordet till deras
		//respektive förfäder.
		for(int i = 0; i<antal; i++)
		{
			//Vem vi behandlar för tillfället.
			int person = bord[i];

			//Avståndet vi ska börja med.
			//Vi ska ju börja med avstånde1 mellan förälder och barn
			//och det är avståndet är ju 1.
			int distance = 1;

			//Så länge personen i fråga inte är person #0 kör vi på.
			while(person!=0)
			{
				//Avståndet mellan personen vid bordet och 'personen
				//vi för tillfället behandlar's förälder är distance.
				trad[bord[i]][parents[person]] = distance;

				//Avståndet till nästa förfader kommer vara ett längre.
				distance++;

				//Nu går vi vidare och kollar på förälderns förälder.
				person = parents[person];
			}
		}

		//Minsta avståndet (vilket inte är större än 21 i alla fall).
		int min = 21;

		//Vem är den närmaste gemensamma släktingen?
		int svar = 0;

		//Finner svaret. Vi går igenom varje person i släkten.
		for(int i = 0; i<=N; i++)
		{
			//Summan av alla avstånden för personerna vid bordet
			//till denna släkting.
			int summa = 0;

			//Går igenom personerna vid bordet.
			for(int j = 0; j<antal; j++)
			{
				//Om avståndet till personen är 0 och denna person
				//inte är oss själva, så är detta överhuvudtaget ingen
				//gemensam släkting, varför det orimligt höga avståndet
				//21 tilldelas.
				if(trad[bord[j]][i]==0 && bord[j]!=i)
				{
					summa += 21;
				}
				else
				{
					//Annars är detta en förfader till person bord[j] vid
					//bordet och avståndet mellan dessa adderas till summan.
					summa += trad[bord[j]][i];
				}
			}

			//Om denna gemensamma släkting var närmare än tidigare bästa
			//gemensamma släkting, så uppdaterar vi.
			if(summa<min)
			{
				//Avstånd.
				min = summa;

				//Vem var släktingen?
				svar = i;
			}
		}

		//Skriver ut svaret.
		System.out.println("\nNärmaste släkting: " + svar);
	}
}