Есть ли лучший алгоритм для этого?(Создание фракций единиц) - PullRequest
Новая
       27

Есть ли лучший алгоритм для этого?(Создание фракций единиц)

2 голосов
/ 28 марта 2019

У меня возникла проблема, когда необходимо добавить дроби между 1/2 - 1/1000, чтобы создать самую длинную последовательность всех уникальных дробей единиц.

Правила построения этих дробей:

Давайте создадим набор: D, D предназначен только для хранения уникальных фракций, субфракции могут составлять одну и ту же дробь, например: 

          1/10             
        /      \
1/110 + 1/11    1/35 + 1/14

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

Цель:

Доли должны бытьсуммируется с точностью до 1. Любые субфракции не могут быть больше 1000, это явно от 2 до 1000, следовательно, дроби, составляющие 1/1000, не будут применяться (1/1004 + 1/251000).

То, что в настоящее время я считаю наиболее эффективным:

Найдите два наименьших множителя, которые составляют текущую долю, на которую я смотрю, например, 1/6 = A =3, B = 2.И теперь мы завершим следующее уравнение: C = (A + B) * A, D = (A + B) * B.Теперь C & D - это подфракции, которые складываются с моей начальной дробью 

              1/6
           /       \
        1/15       1/10

В коде: 

public static int[] provideFactorsSmallest(int n) {
    int k[] = new int[2];

    for(int i = 2; i <= n - 1; i++) { 
        if(n % i == 0) {
            k[0] = i;
            break;
        }
    }

    for(int i = k[0] + 1; i <= n - 1 && k[0] != 0; i++) {
        //System.out.println("I HAVE BEEN ENTERED");
        if(k[0] * i == n) {
            k[1] = i;
            int firstTerm =  k[0];
            int secondTerm = k[1];
            k[0] = (firstTerm + secondTerm) * firstTerm;
            k[1] = (firstTerm + secondTerm) * secondTerm;
            return k;
        }
    }
    return null;
}

Мой вопрос:

Что будетсамый эффективный способ объединения и группировки чисел для достижения максимально возможной дробной последовательности?

Заранее спасибо!

...