Tävlingsprogrammering/Uppgifter/Fotbollsmatchen

Fotbollsmatchen

Två lag ska spela en fotbollsmatch, och vi ska räkna ut sannolikheten att lag 1 vinner över lag 2.

Fotbollsplanen som de spelar på är inte symmetrisk, utan målen är olika stora, så vilken planhalva man har kan vara avgörande för resultatet. Samtidigt är givetvis inte nödvändigtvis heller de två lagen exakt lika starka. Lagen spelar tills något av lagen har gjort n mål och då har detta lag vunnit. Du får givet i indata sannolikheten att lag 1 gör nästa mål. Denna sannolikhet beror endast på vilken planhalva laget spelar på.

Spelarna kom på att man kan kompensera orättvisan med planhalvorna genom att växelvis byta planhalva. Man bestämde att efter att något lag gjort 5 mål byter man planhalva, sedan byter man tillbaka vid 10, återigen vid 15, 20, 25 o.s.v.. Lag 1 börjar alltid spela på planhalva 1. Notera att man alltså granskar maxvärdet av lagens mål, inte summan! T.ex. byter man inte då det blir (3-2), utan vid t.ex. (5-2). Inte heller vid (5-5), utan först vid t.ex. (7-10).

Programmet ska fråga efter heltalet n (där 1 ≤ n ≤ 100), antalet mål ett lag måste göra innan det vinner. Därefter ska det fråga efter flyttalet P1, sannolikheten att lag 1 gör nästa mål när de har planhalva 1, och slutligen efter flyttalet P2, sannolikheten att lag 1 gör nästa mål när de har planhalva 2. Självklart gäller att 0 ≤ P1, P2 ≤ 1. Observera att sannolikheten att lag 2 gör nästa mål lätt kan beräknas: den är 1 − P1 eller 1 − P2, beroende på om lag 1 spelar på planhalva 1 eller 2. Programmet ska skriva ut sannolikheten att lag 1 vinner matchen. Formatet spelar ingen roll men svaret ska vara korrekt med minst 6 decimaler.

Körningsexempel 1

n ? 1
P1 ? 0.55
P2 ? 1.0

Svar: 0.55

Här spelar det ingen roll att lag 1 är överlägsna på den andra planhalvan, i och med att de bara spelar tills det blivit ett mål.

Körningsexempel 2

n ? 6
P1 ? 0.55
P2 ? 1.0

Svar: 1.0

Man byter sida när ändra laget har hälften av sina spelare kvar.

Körningsexempel 3

n ? 17
P1 ? 0.75
P2 ? 0.3

Svar: 0.5819179

Lösning

En förhållandevis enkel sista uppgift.

import java.util.*;

public class Fotboll
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in).useLocale(Locale.US); //Så att flyttal med punkt läses.

		System.out.print("n ? ");
		final int n = scan.nextInt();
		System.out.print("P1 ? ");
		final double P1 = scan.nextDouble();
		System.out.print("P2 ? ");
		final double P2 = scan.nextDouble();

		//p[i][j] = sannolikheten att vi når ställningen i:j.
		//Där i är lag 1:s mål och j lag 2:s mål.
		double [][] p = new double [n+1][n+1];

		//Att vi når 0:0 är säkert.
		p[0][0] = 1;

		//Fyller i matrisen på diagonalen.
		for(int tot = 1; tot<2*n; tot++) //tot = totala antalet mål.
		for(int t1 = 0; t1<=tot && t1<=n; t1++) //t1 = lag 1:s mål.
		{
			int t2 = tot - t1; //lag 2:s mål.
			if(t2>n) continue; //fler än n mål är ej OK.

			//Vi kan nå t1:t2 på två sätt.
			//Antingen gör lag 1 mål, givet ställningen (t1-1):t2.
			//Eller så gör lag 2 mål, givet ställningen t1:(t2-1).
			//(Math.max(x,y)/5&1)==0 avgör vilken planhalva lag 1 hade vid föregående ställning.
			//Är antalet mål om fem som passerat jämnt, så har lag 1 planhalva 1, annars planhalva 2.
			//Matchen är dessutom avslutad om något lag gjort n mål.
			if(t1>0 && t2<n) p[t1][t2] += (Math.max(t1-1,t2)/5&1)==0 ? p[t1-1][t2]*P1 : p[t1-1][t2]*P2;
			if(t2>0 && t1<n) p[t1][t2] += (Math.max(t1,t2-1)/5&1)==0 ? p[t1][t2-1]*(1-P1) : p[t1][t2-1]*(1-P2);
		}

		double svar = 0;
		//Summerar sannolikheterna för alla ställningar där lag 1 vinner.
		for(int i = 0; i<n; i++) svar += p[n][i];

		System.out.println("\nSvar: " + svar);
	}
}