Форум АНТИЧАТ - Подскажите алгоритм написания программы

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)

- PHP, PERL, MySQL, JavaScript (https://forum.antichat.xyz/forumdisplay.php?f=37)

- - Подскажите алгоритм написания программы (https://forum.antichat.xyz/showthread.php?t=93912)

Подскажите алгоритм написания программы

Задачка такая есть 100 рублей корова стоит 5 рублей, бык- 10, теленок - 0.5. надо купить сто голов скота.

"в лоб" - т.е. начать со всех быков, и если голов < 100, то заменять 1 быка на 2 коровы или корову на 10 телят, в зависимости от того, насколько меньше

zip1990

PHP код:


		
			
<?

for ($y=0;$y<=10;$y++)

for ($x=0;$x<=20;$x++)

for ($z=0;$z<=100;$z++)

if ($x+$y+$z==100 && 5*$x+10*$y+0.5*$z==100) {printf('Коров: %d; Быков: %d; Телят: %d',$x,$y,$z); die();}

?>

Как-то так

А соотношение не важно?
Допустим если 90 процентов скота, будут телятами, я думаю много с такой фермы много не сделаешь.

Решение:
5х+10y+0.5z=100, где x,y,z - целые и не отрицательные>0 (натуральные вроде, уже не помню...)
Это плоскость - алгебраическая поверхность первого порядка: в декартовой системе координат плоскость может быть задана уравнением первой степени. Соответсвенно все решения - точки с целыми координатами, принадлежащие этой плоскости.
Частное решение:

Берём X=10
Тогда 10y+0.5z=50
z=(50-10y)*2
z=100-20y
Берём y=1, тогда z=80

Итого: 10 коров, 1 бык, 80 телят. (одного быка хватит на 10 коров? ;) )
проверка:
5*10+10*1+80*0.5=50+10+40=100

Так как цена быка самая большая, то перебор всех частных решений начинаем подставляя Y=1,2,3 и т.д.
потом перебираем X=1,2,3 и т.д (при каждом y) находя Z (z должно получатся целым, неотрицательным>0, остальные решения отбрасываем). Думаю алгоритм ясен.

Готовый рабочий код, выдающий все возм. решения:

PHP код:


		
			
<?

for ($y=1;$y<10;$y++)

    {

        for ($x=1;$x<20;$x++)

            {

            $z=(100-5*$x-10*$y)*2;

            if ($z==round($z) and $z>0) echo "коров:".$x.", быков:".$y.", телят:".$z." проверка:".($x*5+10*$y+0.5*$z)."<br>";

            }

    }

?>

- ну а дальше выбирайте оптимальное ;)

UP: забыл про второе условие: что всего должно быть 100 голов скота, т.е. x+y+z=100 - подправьте код сами вообщем... ;)

Ответ: коров:9, быков:1, телят:90 проверка:100
P.S. Задачка на пересечение двух плоскостей (как известно решение, это прямая, если плоскости не параллельны, не совпадают, а пересекаются). В нашем случае это отрезок, а так как X,Y,Z целые, ненулевые, положительные, то на этой прямой есть лишь одна точка, имеющая все три координаты целые значения, не нулевые, положительные.

-=lebed=- Ну давайте изгаляться, если все же вспомнить про второе условие - то имеем систему:

Код:

x+y+z=100

10x+5y+0.5z=100

Прямым ходом метода гаусса получаем неоднородную систему с одним свободным членом:

Код:

x+y+z=100

5x-4.5z=-400

Примем за свободный член - количество быков, по нему и будем перебирать:

PHP код:


		
			
for ($x=0;$x<=10;$x++)

{$z=(5*$x+400)/4.5;

$y=100-$x-$z;

if ($z==round($z) && $z>0 && $y>0) {printf('Коров: %d; Быков: %d; Телят: %d',$y,$x,$z); die();}

}

З.Ы. ваш код, кстати не правильный без второго условия, вы просто находите все точки лежащие на этой плоскости, в первом квадранте и при этом целые
З.Ы.Ы. А прирост скорости в 100 раз однако. У кого нить есть алгоритм как решать уравнения методом гаусса на пхп? ^^