Количество решений диофантова уравнения

Диофантовы уравнения можно решать перебором, как в этом моём сервисе, а что насчёт проверки количества решений без их вычисления?

Небольшая рекурсивная функция, показанная ниже, позволяет решить эту проблему.

Достаточно задать коэффиценты левой части уравнения в массиве coeff, правую часть - значением b и вызвать функцию. Правда, затраты времени будут расти как O(n*b) в зависимости от размерности массива коэффициентов n и значения правой части b, как сделать лучше - вопрос открытый, десятая проблема Гильберта неразрешима :) Все коэффициенты предполагаются положительными.

Код выполнялся в Visual Studio 2015.

#include <iostream>
using namespace std;

int cntSoultions(int coeff[], int start, int end, int b) {
 if (b == 0) return 1;
 int result = 0;
 for (int i = start; i <= end; i++)
  if (coeff[i] <= b) result += cntSoultions(coeff, i, end, b - coeff[i]);
 return result;
}

int main() {
 int coeff[] = { 1, 2, 5 };
 int b = 10;
 int n = sizeof(coeff) / sizeof(coeff[0]);
 cout << cntSoultions(coeff, 0, n - 1, b);
 system("pause > nul"); return 0;
}

12.04.2018, 10:14 [3035 просмотров]