Decimal to approational fraction xấp xỉ

Question

Tôi đã thực hiện một thuật toán cho dấu thập phân dấu phẩy động đến xấp xỉ tỉ lệ hợp lý (ví dụ: 0.333 -> 1/3) và bây giờ tôi tự hỏi, có cách nào để tìm một số không hợp lý thỏa mãn điều kiện. Ví dụ, với đầu vào 0.282842712474 Tôi muốn kết quả là sqrt (2)/5 và không phải là 431827/1526739 mà thuật toán của tôi tạo ra. Điều kiện duy nhất là các chữ số đầu tiên của kết quả (được chuyển đổi ngược về dấu phẩy động) phải là các chữ số của đầu vào, phần còn lại không quan trọng. Cảm ơn trước!

Answer 1

Tôi đã đưa ra giải pháp, từ tập hợp các mẫu số và đề cử có thể tìm được gần đúng nhất của số đã cho.

Ví dụ thiết lập này có thể chứa tất cả các số có thể được tạo ra bởi:
= radicand < = 100000
= root_index < = 20

Nếu bộ có các yếu tố N, so với giải pháp này phát hiện xấp xỉ tốt nhất trong O (N log N).

Trong giải pháp này X đại diện cho mẫu số và chỉ định Y.

1. số loại từ bộ
2. cho mỗi số X từ bộ:
   sử dụng nhị phân tìm nhỏ Y như rằng Y/X> = input_number
   so sánh Y/X với xấp xỉ hiện tốt nhất của input_number

tôi không thể cưỡng lại và tôi thực hiện nó:

#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"); 
}