ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ 
ИНСТИТУТ ИНФОРМАТИЗАЦИИ ОБРАЗОВАНИЯ РАО
АДМИНИСТРАЦИЯ ГОРОДСКОГО ОКРУГА ТРОИЦК В ГОРОДЕ МОСКВЕ 
РЕГИОНАЛЬНЫЙ ОБЩЕСТВЕННЫЙ ФОНД НОВЫХ ТЕХНОЛОГИЙ В ОБРАЗОВАНИИ «БАЙТИК»
АНО «ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ОБРАЗОВАНИИ» 
 XXV МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ
 «ПРИМЕНЕНИЕ НОВЫХ ТЕХНОЛОГИЙ В ОБРАЗОВАНИИ»  
«ИТО-Троицк-2014»
25-26 июня 2014 года, г.Москва, г.о. Троицк

ЗАДАЧИ ПРИКЛАДНОГО ХАРАКТЕРА, ДИОФАНТОВЫ УРАВНЕНИЯ И ПРОГРАММЫ ПЕРЕБОРА

Автор: Карташян Марсел Вардгесович, Почётная грамота министерства общего и профессионального образования Ростовской области
Муниципальное бюджетное общеобразовательное учреждение лицей №6 г. Шахты Ростовской области
Повышение прикладной направленности преподавания математики в средних образовательных учреждениях является одним из важных требований. Задача преподавателей – создать условие для развития у учащихся умений и навыков практического применения теоретических знаний. Здесь рассматриваются задачи прикладного характера на составление диофантовых уравнений первой степени, решаемых программами перебора.

На занятиях по математике часто решаемые задания: упростить выражение, решить уравнение или неравенство, решить систему уравнений или неравенств, построить график функции, вычислить производную и т. д. - приводят к тому, что у учащихся возникает вопрос: «Где же всё это можно применить?» В результате у них падает активность, и многие из них отстаивают свою позицию, пока учитель его не убедит в обратном.

Решение задач прикладного характера часто приводится к диофантовым уравнениям. Применяя известные в теории утверждения, тем не менее, во многих случаях возникает необходимость рассмотрения многочисленных случаев для нахождения всех решений. Перебирая все возможные значения переменных (как правило, целые неотрицательные), программа находит все решения диофантового уравнения. Такие программы называются программами перебора.

Например, для школьной библиотеки были куплены книги стоимостью по 210, 120 и 92 рублей. Всего заплатили 3020 рублей. Требуется найти количество купленных книг каждой стоимости. Введём переменные x, yи z, где x– число книг стоимостью 210 рублей, y– 120 и z– 92. Тогда получим диофантово уравнение 210x+120y+92z=3020 или 105x+60y+46z=1510, где x, y, z– целые неотрицательные числа. Запишем уравнение в общем виде Ax+By+Cz=Dи составим программу перебора значений x, yи zна языке программирования QBASIC.

INPUT“D, А, В, С”; D, A, B, C

FOR X=0 TO D\A

FOR Y=0 TO D\B

FOR Z=0 TO D\C

IF A*X+B*Y+C*Z=D THEN PRINT X; Y; Z

NEXTZ, Y, X

Для решения нашей задачи необходимо задавать с экрана D, A, B, Cзначения 1510, 105, 60, 46 соответственно. Тогда получим ответ (2, 14, 10), (6, 7, 10), (0, 6, 25)  и (10, 0, 10).

Теперь изменим некоторые данные задачи. Пусть третья книга стоит не 92 рубля, а 91 рубль, а всего заплатили 3021 рубль. В любом случае, число 210x+120y оканчивается цифрой 0, значит, число 91z оканчивается цифрой 1. Отсюда получаем, что последняя цифра числа z также равна 1. Тогда в программе вместо простого перебора можно сократить число проверок, заменяя соответствующую строку FOR Z=1 TO 3921\91 STEP 10. Результат работы программы (3, 4, 21).

Четыре класса, всего 113 человек, обратились в туристическую фирму, чтобы поехать на экскурсию. В автопарке имеются туристические микроавтобусы «FordTransit», «VolkswagenCrafter» и «IvecoDaily» общей вместимостью соответственно 16, 21 и 26 человек. По сколько каждой марки машин необходимо выделить, чтобы мест хватило всем и, одновременно, число свободных мест осталось наименьшим (может быть, ни одного).

Свободных мест не останется, если найдём хотя бы одно решение уравнения 26x+21y+16z=113 в неотрицательных целых числах. Однако выше приведённая программа завершается безрезультатно. Это означает, что решения не получаем, следовательно, свободные места будут в любом случае. Будем искать вариант с наименьшим числом свободных мест.

Обозначим число всех свободных и несвободных мест через E. Тогда число свободных мест будет равно     E-D. Если числа A, Bи С задавать в порядке убывания, то наибольшее возможное число свободных мест будет равно С-1. С возрастанием числа Dэта оценка может быть улучшена. Выполним некоторые изменения в выше приведённой программе. После задания с экрана значения D, A, Bи C, можно продолжить так:

FOR E=D TO D+C-1

FOR X=0 TO E\A

FOR Y=0 TO E\B

FOR Z=0 TO E\C

P=A*X+B*Y+C*Z

IF P=E THEN GOTO 10

NEXT Z, Y, X, E

10 X1=X

FOR X=X1 TO E\A

FOR Y=0 TO E\B

FOR Z=0 TO E\C

P=A*X+B*Y+C*Z

IF P<>E THEN GOTO 20

PRINT X; Y; Z

PRINT“Число свободных мест:”; E-D

20 NEXTZ, Y, X

В нашей задаче D=113, A=26, B=21, C=16. Программа выдаёт ответ (2, 3, 0) или (3, 1, 1) при двух свободных местах.

Добавим ещё одно требование – чтобы число всех выделяемых машин было по возможности меньше. Программа составлена так, что если в ответах отличается общее число микроавтобусов, то наименьшее число получим в последних ответах (в последнем ответе). Например, при D=208 получим два ответа: (0, 0, 13) и (8, 0, 0) при отсутствии свободных мест, то есть разница пять микроавтобусов. Такую же разницу получаем при D=224: (0, 0, 14), (7, 2, 0) и (8, 0, 1). Если имели бы две марки микроавтобусов, то можно было бы решить с введением функции (см. [2, стр. 54]).

В выше приведённых задачах число неизвестных было равно трём, но может быть меньше или больше. В цепи последовательно соединены сопротивления 1,7 ом, 1,9 ом, 2,3 ом и 2,9 ом.  По сколько сопротивлений каждого вида соединено, если известно, что всего получили 13,6 ом? Число сопротивлений каждого вида обозначим соответственно x, y, zи uв приведённом порядке. Получаем  уравнение 17x+19y+23z+29u=136. Если в первой программе выполнить небольшие изменения и запустить, то получим все решения полученного уравнения: (0, 2, 3, 1), (1, 2, 1, 2), (8, 0, 0, 0).

Можно составить много других задач прикладного характера на составление диофантового уравнения: минимизации отходов сырья, эффективного использования времени, грузоперевозки с учётом грузоподъёмности машин и т. д. 

Список использованных источников
  1. Болтянский В. Г. Программы перебора. Журнал "Квант", №1, 1988 г.
  2. Карташян М. В. Прикладные задачи на внеурочных занятиях по математике. Международный образовательный форум "Глобальное образование: взгляд из Италии": сборник трудов. - М.: АНО "ИТО", 2014 г.
Вид представления доклада  Публикация
Уровень  Основное общее образование
Ключевые слова  Прикладные задачи, диофантово уравнение, программы перебора

В статусе «Черновик» Вы можете производить с тезисами любые действия.

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

В статусе «Рекомендован к публикации» тезис публикуется на сайте. Статус «Черновик» может быть возвращен либо по запросу участника, либо при неоплате публикации, если она предусмотрена, либо если тезисы превышают требуемый объем.

Статус «Опубликован» означает, что издана бумажная версия тезиса и тезис изменить нельзя. В некоторых крайне редких ситуацих участник может договориться с Оргкомитетом о переводе тезисов в статус «Черновик».

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.