Нахождение дроби натурального числа, равной дроби действительного числа - PullRequest
Новая
       26

Нахождение дроби натурального числа, равной дроби действительного числа

0 голосов
/ 18 мая 2018

Это больше похоже на математическую задачу, но я думаю, что здесь есть место, где можно спросить, и это может быть полезно кому-то.

Вот то, о чем просит проблема:

Учитывая два действительных числа (rA и rB), найдите наименьшие два натуральных числа (nA и nB), так что

rA / rB = nA / nB

Для тех, кто сделалнеправильно понимают, проблема в том, чтобы запросить неприводимую дробь , которая равна некоторому заданному действительному числу.

Моя проблема возникает, когда она становится проблемой точности, и для этого требуется много временинайдите эти числа (например: rA = 665.32 и rB = 875.1), и я даже не знаю, существует ли такая комбинация натуральных чисел для решения проблемы.

Я также реализовал немного KeyPress, чтобы вывсе еще можно проверить, сколько nA и nB получено, не заполняя вашу консоль.

Самый эффективный способ, которым я пришел, это: 

#include <iostream>
#include <windows.h> // just for GetAsyncKeyState()

int main()
{
    /** The two natural numbers*/
    unsigned long long nA=1;
    unsigned long long nB=1;

    /** The two real numbers*/
    double rA;
    double rB;

    std::cin >> rA >> rB;

    bool bPairFound = false;

    /** The maximum of which nA or nB could go. */
    /** If the value is set to 0, the algorithm will stop when nA or nB overflows */
    #define NUMBER_LIMIT 0x0

    if ((double) nA / nB == rA / rB) bPairFound = true;

    while(bPairFound == false)
    {
        if ((double) nA / nB > rA / rB) nB++;
        if ((double) nA / nB < rA / rB) nA++;
        if ((double) nA / nB == rA / rB) bPairFound = true;

        /** A little keyPress that will show you how much nA and nB got. */
        /** Press space while the program is running. */
        if (GetAsyncKeyState(VK_SPACE) & 0x8000)
            std::cout << "nA: "<<nA<<"   nB: " << nB << "  ---> "<< (double) nA / nB << "   " << rA / rB << std::endl;

        if (nA <= NUMBER_LIMIT || nB <= NUMBER_LIMIT) break;
    }

    if (bPairFound == false) std::cout << "No pair could be found in the set limit." << std::endl;
    if (bPairFound == true) std::cout << "nA: "<<nA<<"   nB: " << nB << std::endl;
    return 0;
}

Мои вопросы:

  1. Могу ли я сделать этот алгоритмболее эффективно?

  2. Как мне установить precision сравнения на 6 цифр?

  3. Можно ли с самого начала определить, есть ли такая пара внутри диапазона unsigned long long?

РЕДАКТИРОВАТЬ: Вот некоторыедругие примеры, решение которых занимает слишком много времени или являются неразрешимыми.

rA = 1426.33 rB = 12.7

rA = 764342.33 rB = 98.02001

rA = 1.0001 rB = 1.010001

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

Кроме вопросов точности (a) , вы можете сделать это наиболее эффективно, просто убедившись, что числа являются целыми числами, а затем разделив их на наибольший общий делитель.

В частности, псевдо-код, такой как: 

tA = rA
tB = rB
while tA != int(tA) or tB != int(tB):
    tA = tA * 10
    tB = tB * 10
gcd = calcGcd(tA, tB)
nA = tA / gcd
nB = tB / gcd

Реализации GCD должно быть довольно легко найти здесь при переполнении стека.

Фактически, вот тот, который я подготовил ранее :-)

(a) Проблемы точности могут быть решены с использованием арифметической библиотеки произвольной точности, такой как MPIR .

0 голосов
/ 18 мая 2018

Я считаю, что это будет более эффективно. 

while(bPairFound == false)
{
    double left=(double)nA*rB;
    double right=(double)nB*rA;

    if(left>right){
         double quotient=left/right;
         unsigned long long prevB=nB;
         nB*=quotient;
         if(prevB==nB){
              nB++;
         }
    }else if(right>left){
         int quotient=right/left;
         unsigned long long prevA=nA;
         nA*=quotient;
         if(prevA==nA){
              nA++;
         }
    }else{
         bPairFound = true;
    }
    /** A little keyPress that will show you how much nA and nB got. */
    /** Press space while the program is running. */
    if (GetAsyncKeyState(VK_SPACE) & 0x8000)
        std::cout << "nA: "<<nA<<"   nB: " << nB << "  ---> "<< (double) nA / nB << "   " << rA / rB << std::endl;

    if (nA <= NUMBER_LIMIT || nB <= NUMBER_LIMIT) break;
}

Поскольку вы увеличиваете число на частное, вы пропустите немало шагов в начале процесса.Также эта реализация имеет больше умножений и меньше делений.Поскольку умножение требует меньших затрат, этот метод будет более эффективным.

Надеюсь, это поможет.

edit 1: я нашел способ повысить точность системы 

double left=(double)nA*rB;
double right=(double)nB*rA;
double quotient=left/right;
unsigned long long test;
if(quotient>=1){
   test=quotient*1000000;
}else{
   test=100000/quotient;
}
if(test==1000000){
    bPairFound = true;
}else if(left>right){
    unsigned long long prevB=nB;
    nB*=quotient;
    if(prevB==nB){
        nB++;
    }
}else if(right>left){
    unsigned long long prevA=nA;
    nA*=1/quotient;
    if(prevA==nA){
        nA++;
    }
}
...