Farey序列是为n阶生成的序列。该序列将[0/0到1/1]范围内的所有有理数按递增顺序排序，以使分母小于或等于n，并且所有数字都以简化形式存在，即4/4不能存在，因为它可以简化为1/1。 例如：
null
F1 = 0/1, 1/1F2 = 0/1, 1/2, 1/1F3 = 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
Farey序列用于无理数、ford圆和 在黎曼假设中（参见 这 更多细节） 如何生成给定订单的票价序列？ 这个想法很简单，我们考虑每一个可能的有理数从1/1到n/n，并且对于每一个生成的有理数，我们检查它是否是简化形式。如果是，那么我们将其添加到票价序列中。有理数是约化形式的，如果 GCD 分子和分母之和为1。 下面是基于上述思想的实现。
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 << " " ; // explicitly printing last term cout << "1/1" ; } // Driver program int main() { int n = 7; cout << "Farey Sequence of order " << n << " is" ; 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 = " " ) # explicitly 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+ " " ) // explicitly 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> |
输出：
Farey Sequence of order 7 is0/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. logn），其中O（logn）是 GCD的欧几里德算法 . Farey序列具有以下属性[参见 维基 详细信息] 一个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++
// 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" ; 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" ); 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" ; 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" ); farey(n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Efficient javascript 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 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> |
输出：
Farey Sequence of order 7 is0/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 本文由Utkarsh Trivedi撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
