close

Вход

Забыли?

вход по аккаунту

?

Лаб02 Диофантовые

код для вставкиСкачать
Министерство образования и науки Украины
Национальный аэрокосмический университет им.Н.Е.Жуковского
"ХАИ"
Отчёт по лабораторной работе №2
по предмету: "Теория алгоритмов и математическая логика"
на тему: "Диофантовые уравнения"
Сделал:
студент 325 группы
Заярный А.В.
Проверил:
Слепичева М.А
Харьков 2013
Диофантовые уравнения
Диофантовыми уравнениями называют алгебраические уравнения или системы алгебраических уравнений с целыми коэффициентами, для которых надо найти целые или рациональные решения. При этом число неизвестных в уравнениях должно быть не менее двух (если не ограничиваться только целыми числами). Диофантовы уравнения имеют, как правило, много решений, поэтому их называют неопределенными уравнениями. Задание: Написать программу решения Диофантова уравнения для свого варианта.
Решение существует только в том случае, если числа взаимно просты. В таком случае решений бесконечно много. Если найдено решение , то решениями являются также все числа вида . (1) Достаточно найти какое-нибудь частное решение . Общее решение описывается формулой (1).
Для нахождения частного решения воспользуемся алгоритмом Евклида поиска наибольшего общего делителя НОД(a,b). Дополнительное условие : a >b>0. Обозначим .
Нулевой шаг алгоритма Евклида записывается в виде: , или . Аналогичным образом записываются и последующие шаги алгоритма Евклида вплоть до шага с номером n, когда остаток станет равным единице:
iВычисления Цепочка Евклида
(2)12................................................i.......................................n-2n-1n В последнем равенстве введем обозначения: . Тогда оно примет следующий вид: .
Теперь осуществим обратный ход. Из равенств (n-1) и (n) исключим : , где .
Равенство (n-1) приведено к следующему виду:
.
Аналогичным образом исключим , используя равенство (n-2):
, т.е. , где .
Таким образом, возникает цепочка равенств следующего вида:
, .(3) Каждой паре найденных чисел соответствует тождество:
.
Используя последние из чисел найденных последовательностей, приходим к тождеству:
.
Учитывая, что , приходим к выводу, что решением уравнения являются числа .
Решение
// diofant.cpp : Defines the entry point for the console application.
//
#include"stdafx.h"
#include"iostream"
#include"conio.h"
using namespace std;
void main()
{
setlocale(LC_ALL,"russian");
int a,b,x1=1,x2=0,y1=0,y2=1,x,y,f1,f2;
cout<<"Введите коэфициэнты при неизвестных(они должны быть взаимно просты!): \n";
cout<<"a: ";
cin>>a;
cout<<"b: ";
cin>>b;
cout<<endl;
f1=a; f2=b;
do
{
if(a>b)
{
a=a-b;
x1=x1-x2;
y1=y1-y2;
}
if(a==b)
{
x=x1;
y=y1;
}
if(b>a)
{
b=b-a;
x2=x2-x1;
y2=y2-y1;
}
}
while((a!=1) || (b!=1));
cout<<"Ответ:\n";
cout<<"x="<<x1<<" y="<<y1<<endl;
cout<<"\nПроверка: a*x+b*y = "<<f1*x1+f2*y1<<endl;
getch();
}
Результат
ЗаярныйА.В._325 2
Документ
Категория
Рефераты
Просмотров
28
Размер файла
77 Кб
Теги
лаб02, диофантовые
1/--страниц
Пожаловаться на содержимое документа