Переборный метод решения задач

Метод перебора состоит в том, что алгоритм генерирует все возможные комбинации исходных данных задачи и отбирает те из них, которые удовлетворяют заданным условиям. В математике этот метод не приветствуется, к тому же часто прямое применение этого метода приводит к очень большому количеству вариантов, перебрать которые за обозримое время не может даже современный компьютер. Однако, применение этого метода в программировании оправдано тем, что для многих задач построить ее решение с помощью перебора гораздо проще, чем с помощью других методов. В результате очень сложные задачи, решить которые мог только хорошо подготовленный математик, поддаются усилиям человека со средними способностями.

Задача 13. Эта задача была сформулирована поэтом Антанасом Баранаускасом, который интересовался теорией чисел. Это любимая задача его детства, над которой он бился две недели: сколько можно купить быков, коров и телят, платя за быка 10 руб., за корову - 5 руб., а за теленка - полтинник, если на 100 рублей надо купить 100 голов скота?

Решение. Условие этой задачи можно представить в виде системы:

или после преобразования ,

где b - количество быков, k - количество коров, t - количество телят. Необходимо организовать три цикла для перебора всех возможных значений количества быков, коров и телят. Причем, можно заметить, что на 100 рублей можно купить не более 10 быков, 20 коров и 200 телят.

var a, b, c: 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 (‘на 100 рублей можно купить’,b,‘быков’,k,‘коров’,t, ‘телят’);

end.

Попытайтесь уменьшить количество циклов для решения данной задачи.

Задача 14. Найдите все трехзначные числа, сумма цифр которых кратна 3.

Решение. Задача решается путем перебора всех трехзначных чисел. Причем перебор чисел можно организовать по-разному: 1) перебирать трехзначные числа, выделять цифры из числа и находить сумму цифр; 2) организовать три цикла для перебора цифр сотен, десятков и единиц и находить сумму этих цифр.

Вариант 1.

var i: integer;

begin

for i:= 100 to 999 do {перебор всех трехзначных чисел}

if (i div 100 + i div 10 mod 10 + i mod 10) mod 3 = 0

then write (i, ‘ ’);

end.

Вариант 2.

var i, j, k: integer;

begin

for i:= 1 to 9 do {перебор цифр сотен}

for j:= 0 to 9 do {перебор цифр десятков}

for k:= 0 to 9 do {перебор единиц}

if (i + j + k) mod 3 = 0 then write (i*100 + j*10 + k, ‘ ‘);

end.

Упражнения.

Напишите программу для решения следующих задач.

1. Сегодня утром я видел в парке людей, собак и кошек. Собак было больше, чем людей. У собак и людей вместе было 100 голов и ног. А собак и людей вместе было втрое больше, чем кошек. Сколько я видел кошек? (Ответ - 8 кошек).

2. Джон Смит сообщил своей семье, что отныне каждый месяц им следует экономить вдвое больше, чем в предыдущем месяце. Они сэкономят 1 доллар в первый месяц, 2 доллара во второй месяц, 4 доллара в третий месяц и т.д. Сколько они сэкономят за год? Через сколько месяцев сумма сэкономленных долларов превысит 10000 долларов?

3. Преподаватели Калифорнийского университета удивлялись на своего нового коллегу. Когда ему сказали, что его месячный оклад составит сумму **** и через 6 месяцев будет повышен до 3 тысяч долларов, он ответил: “Какое чудесное число! Если разделить его на 10, то остаток будет равен 9, если разделить на 9, то остаток будет 8 и т.д. В конце концов остаток будет 1, когда мы разделим эту сумму на 2. Каков был первоначальный оклад нового преподавателя? (Ответ - 2519 долларов).

4. Найдите все натуральные пятизначные числа вида 67m1n (m и n-цифры), которые делятся на 36. Для представления натуральных чисел разрешается использовать короткие целые, меньшие или равные 32767. (Ответ - 67212 и 67716).

5. Для каждого четырехзначного числа составляется дробь: отношение суммы цифр числа к самому числу. Укажите четырехзначное число, для которого эта дробь наибольшая.

Поиск по сайту: