algorithm - 小数到无理分数近似

我已经实现了一种浮点十进制到有理数分数逼近的算法(例如:0.333-> 1/3)，现在我想知道是否有找到符合条件的无理数的方法。例如，给定输入0.282842712474，我希望结果为sqrt(2)/5，而不是算法生成的431827/1526739。唯一的条件是结果的前几位(转换回浮点数)应该是输入的数位，其余的都没有关系。提前致谢!

最佳答案

我想出了一个解决方案，即从给定的可能分母和提名者集中找到给定数的最佳近似。

例如，此集合可以包含可以通过以下方式创建的所有数字:
1 1
如果set具有N个元素，则此解决方案将在O(N log N)中找到最佳近似值。

在该解决方案中，X表示分母，Y表示分母。

对集合

中的数字进行排序
集合中每个数字X的

:
使用二进制找到最小的Y，使得Y/X> = input_number
将Y/X与input_number

的当前最佳近似值进行比较

我无法抗拒，并实现了它:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct Number {
  // number value
  double value;

  // number representation
  int root_index;
  int radicand;

  Number(){}
  Number(double value, int root_index, int radicand)
    : value(value), root_index(root_index), radicand(radicand) {}

  bool operator < (const Number& rhs) const {
    // in case of equal numbers, i want smaller radicand first
    if (fabs(value - rhs.value) < 1e-12) return radicand < rhs.radicand;
    return value < rhs.value;
  }

  void print() const {
    if (value - (int)value < 1e-12) printf("%.0f", value);
    else printf("sqrt_%d(%d)",root_index, radicand);
  }
};

std::vector<Number> numbers;
double best_result = 1e100;
Number best_numerator;
Number best_denominator;

double input;

void compare_approximpation(const Number& numerator, const Number& denominator) {
   double value = numerator.value / denominator.value;

   if (fabs(value - input) < fabs(best_result - input)) {
      best_result = value;
      best_numerator = numerator;
      best_denominator = denominator;
   }
}

int main() {

  const int NUMBER_LIMIT = 100000;
  const int ROOT_LIMIT = 20;

  // only numbers created by this loops will be used
  // as numerator and denominator
  for(int i=1; i<=ROOT_LIMIT; i++) {
     for(int j=1; j<=NUMBER_LIMIT; j++) {
        double value = pow(j, 1.0 /i);
        numbers.push_back(Number(value, i, j));
     }
  }

  sort(numbers.begin(), numbers.end());

  scanf("%lf",&input);

  int numerator_index = 0;

  for(int denominator_index=0; denominator_index<numbers.size(); denominator_index++) {
    // you were interested only in integral denominators
    if (numbers[denominator_index].root_index == 1) {
      // i use simple sweeping technique instead of binary search (its faster)
      while(numerator_index < numbers.size() && numbers[numerator_index].root_index &&
    numbers[numerator_index].value / numbers[denominator_index].value <= input) {
      numerator_index++;
      }

      // comparing approximations
      compare_approximpation(numbers[numerator_index], numbers[denominator_index]);
      if (numerator_index > 0) {
    compare_approximpation(numbers[numerator_index - 1], numbers[denominator_index]);
      }
    }
  }

  printf("Best approximation %.12lf = ", best_numerator.value / best_denominator.value);
  best_numerator.print();
  printf(" / ");
  best_denominator.print();
  printf("\n");
}

关于algorithm - 小数到无理分数近似，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9956218/