Tävlingsprogrammering/Uppgifter/Mor och far

Mor och far

Jonatan har insett att man kan referera hur långt bak som helst i släktträdet genom att kombinera “mor” och “far”. Sina föräldrar, som vi kallar nivå 1, kan man skriva mor och far, därefter på nivå 2 kan man skriva mormor, morfar, farmor och farfar och så vidare. Efter ett tag blir orden ganska långa, men de kan förkortas om man tillåter lite matematik att komma in i språket. Vi skriver exempelvis om mormormorfarfarmorfar till mor₃far₂morfar.

Jonatan vill skriva en lista över alla sina förfäder, upp till och med en viss nivå (mellan 1 och 18), på denna form. Hur många heltal behöver han skriva?

Körningsexempel 1

Nivå ? 3
Antal: 8

Körningsexempel 2

Nivå ? 1
Antal: 0

Körningsexempel 3

Nivå ? 10
Antal: 4608

Lösning

Antalet förfäder upp till nivå 18 blir ju 2¹⁹ - 2 = 524286, så vi hinner generera alla förfäderna och räkna hur många tal som behöver användas för var och en av dem. Själva genererandet kan göras med en rekursiv funktion, som i lösningen nedan, eller genom att för varje nivå n loopa igenom heltalen mellan 0 och 2ⁿ - 1 och konvertera till binära tal med bitvisa operatorer, som t.ex. i Järnvägen.

Oavsett vilket sätt man väljer är det ju bekvämt att representera varje person som en array av tal som kan vara t.ex. 0=mor eller 1=far. Då återstår att gå igenom arrayen och titta hur många sammanhängande sekvenser av samma tal och med minst två element som förekommer. Exempelvis, för mormormorfarfarmorfar=0001101 finns två sådana sekvenser: 000 och 11, och det går därmed åt två tal för att skriva hans "namn". Slutligen summerar vi bara antalet över alla personerna.

Den som gillar att hacka talföljder upptäcker snart att svaret på uppgiften ges av (N-1) 2^(N-1). Beviset för detta lämnar vi som en övning.

Lösning i C

#include <stdio.h>

int cnt,n,a[100];

void MLX(int nr) {   //Processa en förfader på nivå nr 
  int i;
  a[nr]=-1;     //Sätt ett dummy-element efter sista talet i arrayen för att garantera att den sista sekvensen avslutas
  for(i=2;i<=nr;i++)          //Loopa över 0/1-elementen i arrayen
     if(a[i]!=a[i-1] && a[i-1]==a[i-2]) cnt++;   //Avslutar detta element en sekvens med längd minst 2 ? 
  if(nr==n)  return;        //Om personen finns på nivå n ska vi inte göra någonting mer...
  for(a[nr]=0;a[nr]<2;a[nr]++) MLX(nr+1);    //...annars ska vi kolla hens föräldrar
}

int main() {
  scanf("%d", &n);
  cnt=0;    //Räknar antalet tal vi behöver skriva
  MLX(0);
  printf("%d\n",cnt);
  return 0;
}