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

@HanDi · Регистрация: 11.02.2012

Студворк — интернет-сервис помощи студентам

a1x1+a2x2+...+anxn = k,

Есть алгоритм решения на паскале:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
type
  TVector = array [1..100] of Integer;
 
var
  n, i, a1, ai, tmp: Integer;
  a, x1, xi: TVector;
 
procedure SetUnitVector(var v: TVector; index: Integer);
begin
  FillChar(v, SizeOf(TVector), 0);
  v[index] := 1;
end;
 
procedure CalculateVector(var v1, v2: TVector; q: Integer);
var i, tmp: Integer;
begin
  for i := 1 to n do begin
    tmp := v2[i];
    v2[i] := v1[i] - q * v2[i];
    v1[i] := tmp;
  end;
end;
 
begin
  { Ввод исходных данных }
  Write('Введите количество компонент n: '); ReadLn(n);
  Write('Введите компоненты Ai через пробел: ');
  for i := 1 to n do Read(a[i]);
  ReadLn;
  { Вычисления }
  SetUnitVector(x1, 1);
  a1 := a[1];
  for i := 2 to n do begin
    SetUnitVector(xi, i);
    ai := a[i];
    while ai <> 0 do begin
      CalculateVector(x1, xi, a1 div ai);
      tmp := ai;
      ai := a1 mod ai;
      a1 := tmp;
    end;
  end;
  { Вывод ответа }
  WriteLn('НОД = ', a1);
  for i := 1 to n do Write(x1[i], ' ');
  WriteLn;
end.

Попробовал перевести на C++:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
 
using namespace std;
 
void SetUnitVector(int v[], int index)
{
    for (int i = 0; i < 3; i++)
        v[i] = 0;
 
    v[index] = 1;
}
 
void CalculateVector(int v1[], int v2[], int q)
{
    int i, tmp;
 
    for (i = 1; i < 3; i++)
    {
        tmp = v2[i];
        v2[i] = v1[i] - q * v2[i];
        v1[i] = tmp;
    }
}
 
int main()
{
 
    int n = 3, i, a1, ai, tmp;
    int a[] = { 7, 10, 20 }, x1[100], xi[100];
 
    
    SetUnitVector(x1, 1);
 
    a1 = a[1];
    for (int i = 2; i < n; i++)
    {
        SetUnitVector(xi, i);
        ai = a[i];
 
        while (ai != 0)
        {
        CalculateVector(x1, xi, a1 / ai);
        tmp = ai;
        ai = a1 % ai;
        a1 = tmp;
        }
    }
 
    cout << "NOD: " << a1 << endl;
 
    for (int i = 1; i < n; i++)
        cout << x1[i] << "  ";
 
 
    system("pause");
    return 0;
}

Информация еще есть тут: http://window.edu.ru/resource/... _41-46.pdf

Алгоритм решения:

Кликните здесь для просмотра всего текста

Алгоритм решения диофантова уравнения

Ниже приводится алгоритм решения уравнения a1x1+a2x2+...+anxn=GCD(a1,a2,...,an)
Функция GCD(n, a(), x())

Задать набор N а_1{1,0,…,0}

Цикл i от 2 до n

Задать набор N аi {0,…0,1i,0,…,0}

Пока a(i ) ≠ 0

q = a(1)\a(i)

t = a(i); Nt =_ Nai_ { набор временный }

a(i) = a(1) - q*a(i); Nai_ = Na_1 - q*Nai { покомпонентно}

a (1) = t Na _1 = Nt

Конец пока

{набор Nai содержит решение однородного уравнения}

Конец цикла i

GCD = a(1) {НОД коэффициентов}

x () = Na _1

{набор Na _1 содержит частное решение уравнения}

конец функции

Как ни странно, не могу понять, почему он не работает на C++, может быть что-то не так перевел?

Добавлено через 4 часа 10 минут
Тема все еще актуальна.

@saden · 10.04.2015, 22:27

а что не работает?
ошибка или что?
при быстром просмотре ошибок не видно...

Добавлено через 1 минуту
а на Паскале он работает?

@HanDi · 10.04.2015, 22:32 **[ТС]**

Все, вроде бы поправил.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@saden 184 / 168 / 53 Регистрация: 27.01.2013 Сообщений: 788
	10.04.2015, 22:27
	а что не работает? ошибка или что? при быстром просмотре ошибок не видно... Добавлено через 1 минуту а на Паскале он работает? 0

@HanDi 898 / 345 / 65 Регистрация: 11.02.2012 Сообщений: 1,502
	10.04.2015, 22:32 [ТС]
	Все, вроде бы поправил. 0