[请教] 法雷数列[Farey Sequence]

wucaizhen

Farey[2]={1/2};
Farey[3]={1/3,1/2,2/3}
法雷数列其实就是最简分数的集合(从小到大排序的),现在想问的是,给你N,K,问
Farey[N]里第K小的是???N最大是10的9次方,因此打表的方法是行不通了!
比如N=3,K=3;Farey[3]第3小的是2/3,N=2,K=1,Farey[2]第一小的是1/2;N=100,K=68,F[100]第68小的是2/83
不知哪位大侠有好方法来求得F[N]的第K小的数

lknh17

#include <stdio.h>

int f(int a,int b,int n)
{
        for(int i =n; i >= 2; i--)
        {
                if((1 + a * i) % b == 0)
                        return i;
        }
}

int main()
{
        int n = 100;
        int a = 0,b = 1,c,d;
        int i=0,k = 68;
       
        while(i < k)
        {
                d = f(a,b,n);
                c = (1 + a * d) / b;
                i++;
                a = c ;
                b = d ;
        }
        printf("%d/%d\n",a,b);
       
        return 1;
}

soyh8086

是那个和黎曼猜想相关的数列么

lknh17

和那个没什么关系.
法雷数列一般都是考察生成的,可以递归和深度遍历
但是此题N过于大,所以不可能遍历去求出过程所有中间解


不过知道了N,就可以在直接在最底层求 可以转化成一个系数为质数的不定方程
如果只是这样,可以利用一些数学性质去优化程序,但是法雷数列还要求分数按递增顺序排列,那就不能用那些性质了
目前只能想到这个笨办法...不过对于N不是很大,上面程序还是能很快求出来的,即使N达到10^9,k不是特别大也能很快求出

如果有更好的时间复杂度方法,贴下,我没时间去想了..

wucaizhen

暴掉的,10的9次,肯定TLE的,算法还不行啊LS的,还是谢谢了!!!

wzcsoft

2楼的构造用到了法雷的一个性质：若相邻两个元素是a/b 和c/d (a/b<c/d),则这两个数的差为1/bd 算法是O(n^2)的复杂度吧。
法雷还有一种二分的构造法：a/b， c/d （a/b<c/d）是一个n级法雷数列中的两个元素，且b+d<=n, 则可以在a/b, c/d 中间插入一个分数 (a+b)/(c+d)，比如构造f(5)
0/1, 1/1
0/1, 1/2, 1/1
0/1, 1/3, 1/2, 2/3, 1/1
0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1
0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1

0/1  1/1之间的就是数列，这样可以做到O(n)，如果按照顺序好像似乎貌似也不用gcd()了

icylord

这是今年某个赛区的网赛题目嘛

wucaizhen

正是!不过偶不是参加比赛的,偶只是看看的

icylord

http://blog.csdn.net/huangwei1024/archive/2007/09/10/1778592.aspx
这个应该是吧

lknh17

原帖由 wzcsoft 于 2008-10-20 14:16 发表
2楼的构造用到了法雷的一个性质：若相邻两个元素是a/b 和c/d (a/b

N要到10^9,你这样想逐行生成,肯定溢出