Farey-Sequenz
Farey-Folge ist eine Folge, die für Ordnung n erzeugt wird. Die Folge hat alle rationalen Zahlen im Bereich [0/0 bis 1/1] in aufsteigender Reihenfolge sortiert, so dass die Nenner kleiner oder gleich n sind und alle Zahlen in reduzierter Form vorliegen, dh 4/4 kann nicht vorhanden sein, wie es kann auf 1/1 reduziert werden.
Beispiele:
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
Die Farey -Folge wird in rationalen Annäherungen an irrationale Zahlen, Ford-Kreise und
in der Riemann-Hypothese verwendet
.
Die Idee ist einfach, wir betrachten jede mögliche rationale Zahl von 1/1 bis n/n. Und für jede generierte rationale Zahl prüfen wir, ob sie in reduzierter Form vorliegt. Wenn ja, dann fügen wir es der Farey-Sequenz hinzu. Eine rationale Zahl ist in reduzierter Form, wenn ggT von Zähler und Nenner 1 ist.
Unten ist die Implementierung basierend auf der obigen Idee.
C++
// C++ program to print Farey Sequence of given order
#include <bits/stdc++.h>
using namespace std;
// class for x/y (a term in farey sequence
class Term {
public:
int x, y;
// Constructor to initialize x and y in x/y
Term(int x, int y)
: x(x), y(y)
{
}
};
// Comparison function for sorting
bool cmp(Term a, Term b)
{
// Comparing two ratio
return a.x * b.y < b.x * a.y;
}
// GCD of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to print Farey sequence of order n
void farey(int n)
{
// Create a vector to store terms of output
vector<Term> v;
// One by one find and store all terms except 0/1 and n/n
// which are known
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j)
// Checking whether i and j are in lowest term
if (gcd(i, j) == 1)
v.push_back(Term(i, j));
}
// Sorting the term of sequence
sort(v.begin(), v.end(), cmp);
// Explicitly printing first term
cout << "0/1 ";
// Printing other terms
for (int i = 0; i < v.size(); ++i)
cout << v[i].x << "/" << v[i].y << " ";
// explicitely printing last term
cout << "1/1";
}
// Driver program
int main()
{
int n = 7;
cout << "Farey Sequence of order " << n << " is\n";
farey(n);
return 0;
}
Python3
# Python3 program to print
# Farey Sequence of given order
# class for x/y (a term in farey sequence
class Term:
# Constructor to initialize
# x and y in x/y
def __init__(self, x, y):
self.x = x
self.y = y
# GCD of a and b
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
# Function to print
# Farey sequence of order n
def farey(n):
# Create a vector to
# store terms of output
v = []
# One by one find and store
# all terms except 0/1 and n/n
# which are known
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
# Checking whether i and j
# are in lowest term
if gcd(i, j) == 1:
v.append(Term(i, j))
# Sorting the term of sequence
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]
# Explicitly printing first term
print("0/1", end = " ")
# Printing other terms
for i in range(len(v)):
print("%d/%d" % (v[i].x,
v[i].y), end = " ")
# explicitely printing last term
print("1/1")
# Driver Code
if __name__ == "__main__":
n = 7
print("Farey sequence of order %d is" % n)
farey(n)
# This code is contributed by
# sanjeev2552
Javascript
<script>
// Javascript program to print
// Farey Sequence of given order
// class for x/y (a term in farey sequence
class Term
{
// Constructor to initialize
// x and y in x/y
constructor(x, y)
{
this.x = x;
this.y = y;
}
}
// GCD of a and b
function gcd(a, b)
{
if(b == 0)
return a
return gcd(b, a % b)
}
// Function to print
// Farey sequence of order n
function farey(n)
{
// Create a vector to
// store terms of output
let v = []
// One by one find and store
// all terms except 0/1 and n/n
// which are known
for(let i=1;i<n + 1;i++)
{
for(j=i+1;j<n + 1;j++)
{
// Checking whether i and j
// are in lowest term
if (gcd(i, j) == 1)
v.push(new Term(i, j))
}
}
// Sorting the term of sequence
for(let i=0;i<(v).length;i++)
{
for(let j=i + 1; j<(v).length; j++)
{
if (v[i].x * v[j].y > v[j].x * v[i].y)
{
let temp = v[j];
v[j] = v[i];
v[i] = temp;
}
}
}
// Explicitly printing first term
document.write("0/1 ")
// Printing other terms
for(let i=0;i<(v).length;i++)
document.write(v[i].x+"/"+v[i].y+" ")
// explicitely printing last term
document.write("1/1")
}
// Driver Code
let n = 7;
document.write("Farey sequence of order "+n+ " is<br>" );
farey(n)
// This code is contributed by patel2127
</script>
Ausgabe:
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
Die Zeitkomplexität des obigen Ansatzes ist O(n 2 Log n), wobei O(log n) eine obere Zeitgrenze ist, die von Euklids Algorithmus für GCD genommen wird .
Die Farey-Sequenz hat die folgenden Eigenschaften [siehe Wiki für Details]
Ein Term x/y kann rekursiv unter Verwendung der vorherigen zwei Terme ausgewertet werden. Unten ist die Formel zur Berechnung von x n+2 /y n+2 aus x n+1 /y n+1 und 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]
Wir können die obigen Eigenschaften zur Optimierung verwenden.
C++
// Efficient C++ program to print Farey Sequence of order n
#include <bits/stdc++.h>
using namespace std;
// Optimized function to print Farey sequence of order n
void farey(int n)
{
// We know first two terms are 0/1 and 1/n
double x1 = 0, y1 = 1, x2 = 1, y2 = n;
printf("%.0f/%.0f %.0f/%.0f", x1, y1, x2, y2);
double x, y = 0; // For next terms to be evaluated
while (y != 1.0) {
// Using recurrence relation to find the next term
x = floor((y1 + n) / y2) * x2 - x1;
y = floor((y1 + n) / y2) * y2 - y1;
// Print next term
printf(" %.0f/%.0f", x, y);
// Update x1, y1, x2 and y2 for next iteration
x1 = x2, x2 = x, y1 = y2, y2 = y;
}
}
// Driver program
int main()
{
int n = 7;
cout << "Farey Sequence of order " << n << " is\n";
farey(n);
return 0;
}
Java
// Efficient Java program to print
// Farey Sequence of order n
class GFG
{
// Optimized function to print
// Farey sequence of order n
static void farey(int n)
{
// We know first two terms are 0/1 and 1/n
double x1 = 0, y1 = 1, x2 = 1, y2 = n;
System.out.printf("%.0f/%.0f %.0f/%.0f", x1, y1, x2, y2);
double x, y = 0; // For next terms to be evaluated
while (y != 1.0)
{
// Using recurrence relation to find the next term
x = Math.floor((y1 + n) / y2) * x2 - x1;
y = Math.floor((y1 + n) / y2) * y2 - y1;
// Print next term
System.out.printf(" %.0f/%.0f", x, y);
// Update x1, y1, x2 and y2 for next iteration
x1 = x2;
x2 = x;
y1 = y2;
y2 = y;
}
}
// Driver program
public static void main(String[] args)
{
int n = 7;
System.out.print("Farey Sequence of order " + n + " is\n");
farey(n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Efficient Python3 program to print
# Farey Sequence of order n
import math
# Optimized function to print Farey
# sequence of order n
def farey(n):
# We know first two terms are
# 0/1 and 1/n
x1 = 0;
y1 = 1;
x2 = 1;
y2 = n;
print(x1, end = "")
print("/", end = "")
print(y1, x2, end = "")
print("/", end = "")
print(y2, end = " ");
# For next terms to be evaluated
x = 0;
y = 0;
while (y != 1.0):
# Using recurrence relation to
# find the next term
x = math.floor((y1 + n) / y2) * x2 - x1;
y = math.floor((y1 + n) / y2) * y2 - y1;
# Print next term
print(x, end = "")
print("/", end = "")
print(y, end = " ");
# Update x1, y1, x2 and y2 for
# next iteration
x1 = x2;
x2 = x;
y1 = y2;
y2 = y;
# Driver Code
n = 7;
print("Farey Sequence of order", n, "is");
farey(n);
# This code is contributed by mits
PHP
<?php
// Efficient php program to print
// Farey Sequence of order n
// Optimized function to print
// Farey sequence of order n
function farey($n)
{
// We know first two
// terms are 0/1 and 1/n
$x1 = 0;
$y1 = 1;
$x2 = 1;
$y2 = $n;
echo $x1, "/", $y1,
" ", $x2, "/",
$y2, " ";
// For next terms
// to be evaluated
$x;
$y = 0;
while ($y != 1.0)
{
// Using recurrence relation to
// find the next term
$x = floor(($y1 + $n) / $y2) * $x2 - $x1;
$y = floor(($y1 + $n) / $y2) * $y2 - $y1;
// Print next term
echo $x, "/", $y, " ";
// Update x1, y1, x2 and
// y2 for next iteration
$x1 = $x2;
$x2 = $x;
$y1 = $y2;
$y2 = $y;
}
}
// Driver Code
$n = 7;
echo "Farey Sequence of order ", $n, " is\n";
farey($n);
// This code is contributed by ajit
?>
C#
// Efficient C# program to print
// Farey Sequence of order n
using System;
public class GFG
{
// Optimized function to print
// Farey sequence of order n
static void farey(int n)
{
// We know first two terms are 0/1 and 1/n
double x1 = 0, y1 = 1, x2 = 1, y2 = n;
Console.Write("{0:F0}/{1:F0} {2:F0}/{3:F0}", x1, y1, x2, y2);
double x, y = 0; // For next terms to be evaluated
while (y != 1.0)
{
// Using recurrence relation to find the next term
x = Math.Floor((y1 + n) / y2) * x2 - x1;
y = Math.Floor((y1 + n) / y2) * y2 - y1;
// Print next term
Console.Write(" {0:F0}/{1:F0}", x, y);
// Update x1, y1, x2 and y2 for next iteration
x1 = x2;
x2 = x;
y1 = y2;
y2 = y;
}
}
// Driver program
public static void Main(String[] args)
{
int n = 7;
Console.Write("Farey Sequence of order " + n + " is\n");
farey(n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Efficient javascript program to prvar
// Farey Sequence of order n
// Optimized function to print
// Farey sequence of order n
function farey(n)
{
// We know first two terms are 0/1 and 1/n
var x1 = 0, y1 = 1, x2 = 1, y2 = n;
document.write(x1+"/"+y1+" "+x2+"/"+y2+" ");
var x, y = 0; // For next terms to be evaluated
while (y != 1.0)
{
// Using recurrence relation to find the next term
x = Math.floor((y1 + n) / y2) * x2 - x1;
y = Math.floor((y1 + n) / y2) * y2 - y1;
// Print next term
document.write(x+"/"+ y+" ");
// Update x1, y1, x2 and y2 for next iteration
x1 = x2;
x2 = x;
y1 = y2;
y2 = y;
}
}
// Driver program
var n = 7;
document.write("Farey Sequence of order " + n + " is<br/>");
farey(n);
// This code is contributed by gauravrajput1
</script>
Ausgabe:
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
Die Zeitkomplexität dieser Lösung ist O(n)
Referenzen:
https://en.wikipedia.org/wiki/Farey_sequence
Dieser Artikel wurde von Utkarsh Trivedi beigesteuert. Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .