Pommitaja

Pommitajal on 2 vaenlase sihtmärki X ja Y. Rünnates X-i on tulemuseks murdosa r1 vaenlase sihtmärgi hävimine või pommitaja allatulistamine enne kui ta suudab kahju tekitada. Tõenäosus, et pommitaja jääb ellu rünnates X-i on p1. Y-il on samamoodi r2 ja p2. Vaenlase sihtmärgid on X ja Y. Probleem on maksimum kahju tekitada vaenlase sihtmärkidele. Kahju arvutatakse põhimõtteliselt nii f(x,y)= max[p1*r1*X, p2*r2*Y]. Lisaks on veel antud maksimum N õhurünnakut. Esialgu on vaenlasel X ja Y “elu”.

Tüüpülesanne, esialgu tundub jabur(DP). Ainuke probleem on, et inimene ei suuda tõenäosusi kunagi täpselt määrata.

// Bomber.c

float max(float a, float b)
{
	return a  > b ? a: b;
}

float expected_damage(int n, float p1, float p2, float r1, float r2, float x, float y)
{
	if(n == 1)
		return max(p1 * r1 * x, p2 * r2 * y);
	return max(p1 * (r1 * x + expected_damage(n - 1, p1, p2, r1, r2, (1 - r1) * x, y)), p2 * (r2 * y + expected_damage(n-1, p1, p2, r1, r2, x, (1 - r2) * y)));
}
float X = 60;
float Y = 6;
int _tmain(int argc, _TCHAR* argv[])
{
	float dam = expected_damage(4, 0.9f, 0.9f, 0.55f, 0.6f, X, Y);
	return 0;
}


Advertisements