Приближение десятичной дроби к иррациональной - PullRequest
Новая
       8

Приближение десятичной дроби к иррациональной

7 голосов
/ 31 марта 2012

Я реализовал алгоритм приближения десятичной дроби к рациональной дроби с плавающей запятой (пример: 0,333 -> 1/3), и теперь мне интересно, есть ли способ найти иррациональное число, которое удовлетворяет условию.Например, учитывая ввод 0,282842712474, я хочу, чтобы результат был sqrt (2) / 5, а не 431827/1526739, который выдает мой алгоритм.Единственное условие - первые цифры результата (преобразованные обратно в число с плавающей запятой) должны быть цифрами ввода, остальные не имеют значения.Заранее спасибо!

1 Ответ

3 голосов
/ 31 марта 2012

Я пришел к решению, что из заданного набора возможных знаменателей и знаменателей находит наилучшее приближение данного числа.

Например, этот набор может содержать все числа, которые могут быть созданы:
1 <= радиканд <= 100000 <br> 1 <= root_index <= 20 </p>

Если множество имеет N элементов, то это решение находит наилучшее приближение в O (N log N).

В этом решении X представляет знаменатель, а Y - знаменатель.

  1. сортировка номеров из набора
  2. для каждого числа 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");
}
...