Рубрики

Farey Sequence

Последовательность Фарея — это последовательность, которая генерируется для порядка n. Последовательность имеет все рациональные числа в диапазоне от [0/0 до 1/1], отсортированные в возрастающем порядке, так что знаменатели меньше или равны n, и все числа находятся в сокращенных формах, то есть 4/4 не может быть там, как может быть уменьшено до 1/1.

Примеры:

F1 = 0/1, 1/1
F2 = 0/1, 1/2, 1/1
F3 = 0/1, 1/3, 1/2, 2/3, 1/1
.
.
F7 = 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5,
     3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5,
     5/6, 6/7, 1/1

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

Как сгенерировать последовательность Фаре данного заказа?
Идея проста, мы рассматриваем все возможные рациональные числа от 1/1 до n / n. И для каждого сгенерированного рационального числа мы проверяем, находится ли оно в сокращенной форме. Если да, то мы добавляем его в Farey Sequence. Рациональное число приводится в сокращенной форме, если GCD числителя и знаменателя равен 1.

Ниже приведена реализация, основанная на представленной выше идее.

C ++

// C ++ программа для печати Farey Sequence заданного порядка
#include <bits/stdc++.h>

using namespace std;

  
// класс для х / у (термин в платной последовательности

class Term {

public:

    int x, y;

  

    // Конструктор для инициализации x и y в x / y

    Term(int x, int y)

        : x(x), y(y)

    {

    }

};

  
// функция сравнения для сортировки

bool cmp(Term a, Term b)

{

    // Сравнение двух соотношений

    return a.x * b.y < b.x * a.y;

}

  
// GCD a и b

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return gcd(b, a % b);

}

  
// Функция для печати последовательности Фарея порядка n

void farey(int n)

{

    // Создать вектор для хранения условий вывода

    vector<Term> v;

  

    // По одному находим и сохраняем все термины, кроме 0/1 и n / n

    // которые известны

    for (int i = 1; i <= n; ++i) {

        for (int j = i + 1; j <= n; ++j)

  

            // Проверка, находятся ли i и j в самом низком сроке

            if (gcd(i, j) == 1)

                v.push_back(Term(i, j));

    }

  

    // Сортировка члена последовательности

    sort(v.begin(), v.end(), cmp);

  

    // Явная печать первого члена

    cout << "0/1 ";

  

    // Печать других терминов

    for (int i = 0; i < v.size(); ++i)

        cout << v[i].x << "/" << v[i].y << " ";

  

    // явно печатать последний член

    cout << "1/1";

}

  
// Драйвер программы

int main()

{

    int n = 7;

    cout << "Farey Sequence of order " << n << " is\n";

    farey(n);

    return 0;

}

python3

# Python3 программа для печати
# Фарея Последовательность данного заказа

  
# класс для х / у (термин в платной последовательности

class Term:

  

    # Конструктор для инициализации

    # х и у в х / у

    def __init__(self, x, y):

        self.x = x

        self.y = y

  
# GCD a и b

def gcd(a, b):

    if b == 0:

        return a

    return gcd(b, a % b)

  
# Функция для печати
# Последовательность Фарея порядка n

def farey(n):

  

    # Создать вектор для

    # хранить условия вывода

    v = []

  

    # Один за другим найти и сохранить

    # все условия кроме 0/1 и н / п

    # которые известны

    for i in range(1, n + 1):

        for j in range(i + 1, n + 1):

  

            # Проверка, я и J

            # находятся в низшем сроке

            if gcd(i, j) == 1:

                v.append(Term(i, j))

  

    # Сортировка по порядку следования

    for i in range(len(v)):

        for j in range(i + 1, len(v)):

            if (v[i].x * v[j].y > v[j].x * v[i].y):

                v[i], v[j] = v[j], v[i]

  

    # Явная печать первого члена

    print("0/1", end = " ")

  

    # Печать других терминов

    for i in range(len(v)):

        print("%d/%d" % (v[i].x, 

                         v[i].y), end = " ")

  

    # явная печать последнего семестра

    print("1/1")

  
Код водителя

if __name__ == "__main__":

    n = 7

    print("Farey sequence of order %d is" % n)

    farey(n)

  
# Этот код предоставлен
# sanjeev2552


Выход:

Farey Sequence of order 7 is
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 
3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1

Временная сложность описанного выше подхода составляет O (n 2 Log n), где O (log n) — верхняя граница времени, взятая алгоритмом Евклида для GCD .

Farey Sequence имеет свойства ниже [см. Вики для подробностей]

Термин x / y может быть рекурсивно оценен с использованием двух предыдущих терминов. Ниже приведена формула для вычисления x n + 2 / y n + 2 из x n + 1 / y n + 1 и x n / y n .

x[n+2] = floor((y[n]+n) / y[n+1])x[n+1]– x[n]      
y[n+2] = floor((y[n]+n) / y[n+1])y[n+1]– y[n]    

Мы можем использовать вышеуказанные свойства для оптимизации.

C ++

// Эффективная программа C ++ для печати последовательности Фарея порядка n
#include <bits/stdc++.h>

using namespace std;

  
// Оптимизированная функция для печати последовательности Фарея порядка n

void farey(int n)

{

    // Мы знаем первые два слагаемых: 0/1 и 1 / n

    double x1 = 0, y1 = 1, x2 = 1, y2 = n;

  

    printf("%.0f/%.0f %.0f/%.0f", x1, y1, x2, y2);

  

    double x, y = 0; // Для следующих сроков, которые будут оценены

    while (y != 1.0) {

        // Использование рекуррентного отношения, чтобы найти следующий термин

        x = floor((y1 + n) / y2) * x2 - x1;

        y = floor((y1 + n) / y2) * y2 - y1;

  

        // Распечатать следующий термин

        printf(" %.0f/%.0f", x, y);

  

        // Обновляем x1, y1, x2 и y2 для следующей итерации

        x1 = x2, x2 = x, y1 = y2, y2 = y;

    }

}

  
// Драйвер программы

int main()

{

    int n = 7;

    cout << "Farey Sequence of order " << n << " is\n";

    farey(n);

    return 0;

}

python3

# Эффективная программа Python3 для печати
# Последовательность Фарея порядка n

import math

  
# Оптимизирована функция печати Фарея
# последовательность порядка n

def farey(n):

      

    # Мы знаем, что первые два условия

    # 0/1 и 1 / n

    x1 = 0

    y1 = 1

    x2 = 1

    y2 = n;

      

    print(x1, end = "") 

    print("/", end = "")

    print(y1, x2, end = "") 

    print("/", end = "") 

    print(y2, end = " ");

  

    # Для следующих сроков, которые будут оценены

    x = 0;

    y = 0

    while (y != 1.0):

          

        # Использование рекуррентного отношения к

        # найти следующий термин

        x = math.floor((y1 + n) / y2) * x2 - x1;

        y = math.floor((y1 + n) / y2) * y2 - y1;

  

        # Распечатать следующий термин

        print(x, end = "")

        print("/", end = "")

        print(y, end = " ");

  

        # Обновите x1, y1, x2 и y2 для

        # следующая итерация

        x1 = x2; 

        x2 = x; 

        y1 = y2; 

        y2 = y;

  
Код водителя

n = 7;

print("Farey Sequence of order", n, "is");

farey(n);

  
# Этот код предоставлен mits

PHP

<?php
// Эффективная программа php для печати
// Последовательность Фарея порядка n

  
// Оптимизированная функция для печати
// последовательность Фарея порядка n

function farey($n)

{

      

    // Мы знаем первые два

    // термины 0/1 и 1 / n

    $x1 = 0; 

    $y1 = 1; 

    $x2 = 1; 

    $y2 = $n;

      

        echo $x1, "/", $y1

             " ", $x2, "/"

             $y2, " ";

  

    // Для следующих сроков

    // подлежит оценке

    $x;

    $y = 0; 

    while ($y != 1.0)

    {

          

        // Использование рекуррентного отношения к

        // найти следующий термин

        $x = floor(($y1 + $n) / $y2) * $x2 - $x1;

        $y = floor(($y1 + $n) / $y2) * $y2 - $y1;

  

        // Распечатать следующий термин

        echo $x, "/", $y, " ";

  

        // Обновляем x1, y1, x2 и

        // y2 для следующей итерации

        $x1 = $x2

        $x2 = $x

        $y1 = $y2

        $y2 = $y;

    }

}

  

    // Код драйвера

    $n = 7;

    echo "Farey Sequence of order ", $n, " is\n";

    farey($n);

  
// Этот код предоставлен ajit
?>


Выход:

Farey Sequence of order 7 is
0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 
3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1

Сложность времени этого решения O (n)

Ссылки:
https://en.wikipedia.org/wiki/Farey_sequence

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

Рекомендуемые посты:

Farey Sequence

0.00 (0%) 0 votes