क्रांतिकारी अंश अनुमान के लिए दशमलव

Question

मैंने तर्कसंगत बिंदु दशमलव के लिए तर्कसंगत बिंदु दशमलव के लिए एक एल्गोरिदम लागू किया है (उदाहरण: 0.333 -> 1/3) और अब मुझे आश्चर्य है, क्या एक तर्कहीन संख्या खोजने का कोई तरीका है जो इस स्थिति को पूरा करता है। उदाहरण के लिए, इनपुट 0.282842712474 दिया गया है, मैं परिणाम एसकर्ट (2)/5 होना चाहता हूं और 431827/1526739 नहीं जो मेरा एल्गोरिदम उत्पन्न करता है। एकमात्र शर्त यह है कि परिणाम के पहले अंक (फ़्लोटिंग पॉइंट पर वापस परिवर्तित) इनपुट के अंक होना चाहिए, शेष कोई फर्क नहीं पड़ता। अग्रिम में धन्यवाद!

Answer 1

मैं समाधान के साथ आया, कि संभावित denominators और nominators के दिए गए सेट से दिए गए नंबर का सबसे अच्छा अनुमान मिलता है।

उदाहरण के लिए इस सेट सभी नंबरों कि द्वारा बनाया जा सकता हो सकते हैं:
= radicand < = 100000
= root_index < = 20

सेट एन तत्वों, इस समाधान पाता है की तुलना में है, तो ओ (एन लॉग एन) में सबसे अच्छा अनुमान।

इस समाधान में एक्स denominator और वाई नामांकनकर्ता का प्रतिनिधित्व करता है। सेट

से

1. प्रकार संख्या सेट से प्रत्येक संख्या एक्स के लिए:
   का उपयोग कर बाइनरी पाते हैं सबसे छोटी वाई ऐसी है कि हां/X> = input_number
   तुलना Y/एक्स 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"); 
}