Учебник Turbo Pascal. Введение - Решение диофантовых уравнений

Written on . Posted in Pascal

ОГЛАВЛЕНИЕ

Страница 16 из 29

Решение диофантовых уравнений

Следующая программа предназначена для решения диофантовых уравнений. Таким образом мы попадаем в один из сложных разделов математики. Не стоит этого пугаться, ведь мы вооружены компьютером и знанием, правда, еще далеко не полным, языка программирования. Маленькая историческая справка. Открытие диофантовых уравнений связано с именем греческого математика Диофанта, личности полулегендарной. О его жизни практически ничего не известно, но сегодня диофантов анализ — это обширная и важная область математики. Полная математическая теория разработана только для линейных уравнений, а общий метод решения нелинейных диофантовых уравнений все еще неизвестен. Иногда анализ простого на вид нелинейного диофантова уравнения может представлять огромные трудности даже для математика высокой квалификации. Используя компьютер, оснащенный системой программирования на Турбо Паскале, мы сможем применить его возможности для решения как линейных, так и нелинейных диофантовых уравнений.

Самое простое линейное диофантово уравнение имеет вид ах + by = с, где а, Ъ и с — заданные числа, а х и у — неизвестные. Особенность этих уравнений заключается в том, что для них ищутся целочисленные решения. Это можно сделать методом перебора.

Для того чтобы немного оживить наше повествование, решим следующую старинную задачу из области экономики сельского хозяйства. Зажиточный крестьянин потратил 100 рублей на покупку 100 различных домашних животных. Каждая корова обошлась ему в 10 рублей, свинья в 3 рубля, а овца в 50 копеек. Предполагая, что крестьянин приобрел по крайней мере по одному животному каждого вида, найдем, сколько голов скота каждого вида он купил. Условие задачи записывается в виде двух уравнений:

10х + % + г/2 - 100;

х + у + z = 100,

где х, у, z — количество коров, свиней и овец соответственно. Избавимся от знаменателя в первом уравнении, умножив его на 2. Из полученного таким образом уравнения вычтем второе. Это позволяет исключить переменную z. Получаем уравнение 19х + 5у = 100. Решениями данного уравнения должны быть целые положительные числа (видел ли кто-нибудь отрицательное число коров?), меньшие 100. Следующая программа предназначена для решения данного уравнения.

Листинг 1.5. Решение линейного диофантова уравнения

program diophantine_equation_l;
var
    x, y: Integer;
begin
    WriteLn('Целые решения уравнения 19х + 5y = 100 из диапазона');
    WriteLn('l <= x <= 100, 1 <= у <= 100: ');
    for x := 1 to 100 do 
        for у := 1 to 100 do 
            if 19*x + 5*y = 100 then
                WriteLn('(x, y) = (', x, ', ', y, ')');
    Write('Нажмите <Enter>'); 
    ReadLn;
end.

Эта программа знакомит нас с новыми элементами. Здесь имеется двойной вложенный цикл for. Внутренний цикл содержит условный оператор if... then.... Оператор WriteLn выполняется только в том случае, когда истинно условие в операторе if. В данном случае это условие 19*х+5*у=100. Обратим внимание на то, что знак равенства обозначает здесь не оператор присваивания, а логическое отношение равенства двух значений. Результатом такого сравнения может быть или True (истина), если условие выполнено, или False (ложь), если условие не выполнено. Оператор вывода

WriteLn('(x, y) = (', x, ', ', y, ')');

используется для вывода на экран четырех элементов, которые разделяются запятыми. Последовательности символов, начинающиеся и заканчивающиеся одиночными кавычками ('), являются строками текста (строковыми константами). В нашем примере это '(х, у) = (', ', ' и ')'. На экран будет выведен тот набор символов, который находится между кавычками. Нетекстовыми элементами списка вывода являются идентификаторы переменных х и у. На экран будут выведены значения этих переменных.

форум pascal