Капенов Ермек Уахапович
руководитель
КГКП «Павлодарский бизнес-колледж» отдела образования

управления образования Павлодарской области, акимата Павлодарской области

Старинная задача. Сколько можно купить быков, коров и телят, если бык стоит 10 алтын, корова – 5 алтын, теленок – полалтына (0,5 алтына), при условии, что на 100 алтын надо купить 100 голов скота.

Решение

Обозначим через b количество быков, через k количество коров, через t количество телят. После этого, исходя из условия задачи, можно записать два уравнения

10b+5k+0,5t=100     и      b+k+t=100

Для того, чтобы не использовать дробные числа приведем первое уравнение к следующему виду:

20b+10k+t=200

На 100 алтын можно купить:

• не более 10 быков (0<=b<=10)
• не более 20 коров (0<=k<=20)
• не более 200 телят (0<=t<=200)

Таким образом получаем:

Program Myprog1;

var b,k,t:integer;

begin

for b:=0 to 10 do

for k:=0 to 20 do

for t:=0 to 200 do

if (20*b+10*k+t=200) and (b+k+t=100) then

Writeln(’Быков ’,b:4, ’ Коров’,k:4, ’ Телят’,t:4);

end.

Сколько раз будет проверяться  условие?

11*21*200=46431 раз.

Это слишком много. Попробуем оптимизировать алгоритм. Если известна сумма трех чисел и два слагаемых, то найти третье можно путем вычитания из суммы двух известных слагаемых: t=100-(b+k) и цикл по переменной t можно исключить.

Program Myprog11;

var b,k,t:integer;

begin

for b:=0 to 10 do

for k:=0 to 20 do

begin

t:=100-(b+k);

if 20*b+10*k+t=200 then

Writeln(‘Быков ‘,b:4,’ Коров’,k:4,’ Телят’,t:4);

end;

end.

Сколько раз будет проверяться условие?

11*21=231 раз, а ведь вначале было 46 431. Почувствуйте разницу.

Задание для самостоятельного решения

Попробуйте еще уменьшить количество проверок. И помните, что хороший алгоритм значит не меньше вычислительной мощности компьютера.

Рассмотрим еще одну задачу.

Найти все положительные четырехзначные числа abcd, для которых выполняются следующие условия:

1) a,b,c,d — разные цифры;

2) ab–cd=a+b+c+d (здесь ab и cd — двузначные числа)

Решение

Принципиально ясно, что надо перебирать варианты и искать требуемые значения. Простейший способ заключается в переборе всех четырехзначных чисел и отборе среди них искомых. На выбор два варианта решения: использовать единственный цикл от 1000 до 9999 или использовать четыре цикла, каждый по своей цифре. Если вы выбрали первый вариант, вы заблуждаетесь, потому что для проверки условий текущее значение параметра цикла придется раскладывать на отдельные цифры. Но зачем делать лишнюю работу, когда этого можно избежать. А теперь будьте внимательны:

Program pas_abcd_1;

var a,b,c,d: byte;

p:longint;

begin

for a:=1 to 9 do

for b:=0 to 9 do

for c:=0 to 9 do

for d:=0 to 9 do

begin

p:=(a-b)*(a-c)*(a-d)*(b-c)*(b-d)*(c-d);

if (p<>0) and (10*a+b-10*c-d=a+b+c+d) then writeln(a,b,c,d);

end;

end.

 

Решение оказалось совсем легким. Однако легкие задачи иногда требуют высокой квалификации. Знаете сколько вариантов перебирает эта программа?   9000 (девять тысяч). Многовато, однако. Попробуем оптимизировать алгоритм.

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

10*a+b-(10*c+d)=a+b+c+d (1)

9*a-11*c=2*d                           (2)

Заметьте, b сократилось и исчезло. Значит, для этого условия значение b может быть любым. Поэтому цикл по b можно убрать. Но в задаче требуется найти ЧЕТЫРЕХЗНАЧНЫЕ числа. Следовательно, совсем обойтись без b невозможно. Наверно, о нем следует вспомнить при переходе на строку Writeln и выводить найденное число уже при всех значениях b, отличных от a,c,d. Программа теперь будет выглядеть так:

 

Program pas_abcd_2;

var a,b,c,d: byte;

p:longint;

begin

for a:=1 to 9 do

for c:=0 to 9 do

for d:=0 to 9 do

begin

p:=(a-c)*(a-d)*(c-d);

if (p<>0) and (9*a-11*c=2*d) then

for b:=0 to 9 do

if (b<>a)and(b<>c)and(b<>d) then writeln(a,b,c,d);

end;

end.

Казалось бы ничего не изменилось: те же четыре цикла, а программа усложнилась.

Но это совсем не так! Цикл по b включается только тогда, когда набор из трех цифр a,c,d уже найден и остается только печатать порцию из семи ответов (вопрос: почему из семи?) при различных значениях b. Стало быть, на самом деле мы имеет три вложенных цикла и просматриваем гораздо меньше чисел, чем в превом алгоритме. Насколько меньше? Это можно узнать, добавив несколько строк (они подчеркнуты):

…

begin

p:=(a-c)*(a-d)*(c-d);

if (p<>0) and (9*a-11*c=2*d) then

begin

k:=k+1;

for b:=0 to 9 do

if (b<>a)and(b<>c)and(b<>d) then writeln(a,b,c,d);

end;

end;

writeln(’Количество вариантов: ’,900+k*10);

…

Результат 980 вариантов. Сравните с 9000 в первом алгоритме.

Если вы думаете, что это все, то вы ошибаетесь.

Продолжим оптимизацию алгоритма. При преобразовании и приведении подобных мы получили такое условие:

9*a-11*c=2*d                           (2)

Оно связывает цифры a,c,d. Выразим одну из цифр (например, d) через две другие:

d=(9*a-11*c)/2                        (3)

То есть мы можем отказаться от цикла по d! Конечно при этом следует все же убедиться, что вычисленное d  есть цифра, т.е. целое число в диапазоне от 0 до 9.

Program pas_abcd_3;

var a,b,c,d,f: byte;

p,k:longint;

begin

k:=0;

for a:=1 to 9 do

for c:=0 to 9 do

if a<>c then

begin

f:=9*a-11*c;

if f mod 2 =0 then

begin

d:=f div 2;

if (d>=0) and (d<=9) and (d<>a) and (d<>c) then

begin

k:=k+1;

for b:=0 to 9 do

if (b<>a)and(b<>c)and(b<>d) then

writeln(a,b,c,d);

end;

end;

end;

writeln(90+k*10);

end.

Итак, эффективность алгоритма повысилась почти на порядок: общее число анализируемых вариантов равно 170.

Можно ли еще что-нибудь оптимизировать? Как это не удивительно, да.

Припомните вычисление  из второго условия

d=(9*a-11*c)/2                        (3)

Учитывая, что число a  лежит в диапазоне от 1 до 9, а числа d и c — в диапазоне от 0 до 9, можно утверждать, что c не может быть больше a. Действительно, при любом c больше a, значение d становится отрицательным, что противоречит условию задачи. Значит, цикл по c можно записать так:

…

for c:=0 to a-1 do

…

Это, во-первых, уменьшает количество циклов проверки, а, во-вторых, позволяет не сравнивать a и c между собой — они заведомо не равны.

Общее количество анализируемых вариантов сократилось до 125. Полный текст программы:

 

Program pas_abcd_4;

var a,b,c,d,f: byte;

p,k:longint;

begin

k:=0;

for a:=1 to 9 do

for c:=0 to a-1 do

begin

f:=9*a-11*c;

if f mod 2 =0 then

begin

d:=f div 2;

if (d>=0) and (d<=9) and (d<>a) and (d<>c) then

begin

k:=k+1;

for b:=0 to 9 do

if (b<>a)and(b<>c)and(b<>d) then

writeln(a,b,c,d);

end;

end;

end;

writeln(45+k*10);

end.

И, если я вас еще не утомил, последний штрих.

Посмотрим еще раз на второе условие в виде

2*d=9*a-11*c                        (2.1)

Так как в левой части уравнения мы имеем выражение 2*d, то можно смело утверждать, что выражение 9*a-11*c при любых a и c является четным.

Так как d лежит в диапазоне от 0 до 9, то можно также утверждать, что значение выражения (9*a-11*c) лежит в диапазоне от от 0 до 18. (То есть, имеет место неравенство: 0<=9*a-11*c<=18)

Кроме того, мы выяснили что c не  может быть больше a. То есть c=a-1,или c=a-2,или c=a-3 и т.д. Исходя из требования четности для d*2, можно утверждать, что a и c  должны быть одной четности. В самом деле, только в том случае, если a и c оба четны или оба нечетны, выражение (9*a-11*c)   четное. Тогда допустимы значения , c=a-2 или c=a-4, или c=a-6 и т.д. Запишем в общем виде c=a-x и подставим в неравенство 0<=9*a-11*c<=18, получим :

0<=11*x-2*a<=18                     (4)

Теперь видно, что при x>3 неравенство (4) ни при каком значении a не может быть удовлетворено. То есть единственное допустимое значение для c есть c=a-2, а наименьшее допустимое значение a при этом равно 2. Это позволяет избавиться и от цикла по с.

Итак, мы имеем два уравнения:

2*d=9*a-11*c                        (2.1)

c=a-2                                          (5)

Подставив (5) в (2.1), получим   d=11-a.

При таком раскладе (c=a-2, d=11-a) ясно, что ни a, ни c, ни d не совпадают друг с другом и проверять их на различие излишне.

Оптимизированная программа будет выглядеть примерно так:

 

Program pas_abcd_5;

var a,b,c,d: byte;

begin

for a:=2 to 9 do

begin

с:=a-2;

d:=11-a;

for b:=0 to 9 do

if (b<>a)and(b<>c)and(b<>d) then

writeln(a,b,c,d);

end;

end.

 

Общее число анализируемых чисел в этом алгоритме всего 80, то есть он эффективнее первоначального более чем в 100 раз!

А если вы смогли разобраться со всем вышеизложенным материалом, то предлагаем для самостоятельного решения задачу. Постарайтесь использовать в своей программе оптимальный алгоритм:

Найти число “счастливых” билетов в лотерейном барабане, где имеется 1 млн. билетов с шестизначными номерами. (“Счастливым” считается билет, у которого суммы трех первых и трех последних цифр совпадают.)