当前位置:首页 » Project Euler » 详细页

Investigating the behaviour of a recursively defined sequence 题号:197 难度: 45 中英对照

Given is the function f(x) = ⌊230.403243784-x2⌋ × 10-9 ( ⌊ ⌋ is the floor-function),
the sequence un is defined by u0 = -1 and un+1 = f(un).

Find un + un+1 for n = 1012.
Give your answer with 9 digits after the decimal point.

Solution

# p197 本题从标题中知道它是考察**递归定义序列(Recursively Defined Sequence)**的定义和用法。 递归序列满足以下性质: $$ F(n+mk)=F(n) $$ 其表示序列中的第$(n+mk)$个值和第$n$个值是一样的,其中$k$表示最小的递归单元的长度,$m$表示相差递归单元的个数。 解决此问题,经典常用的算法是**Floyd判圈算法**(**Floyd Cycle Detection Algorithm**),又称**龟兔赛跑算法**。是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,求出该环的起点与长度的算法。 如果有限状态机、迭代函数或者链表上存在环,那么在某个环上以不同速度前进的2个指针必定会在某个时刻相遇。同时显然地,如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇,那么可以判定存在一个环,且可以求出2者相遇处所在的环的起点与长度。 假设起点到环的起点距离为$m$,已经确定有环,环的周长为$n$,(第一次)相遇点距离环的起点的距离是$k$。那么当两者相遇时,慢指针移动的总距离为$i$,有: $$ i = m + a \* n + k $$ 因为快指针移动速度为慢指针的两倍,那么快指针的移动距离为$2i$,有: $$ 2i = m + b \* n + k $$ 其中,$a$和$b$分别为慢指针和快指针在第一次相遇时转过的圈数。我们让两者相减(快减慢),那么有: $$ i = (b - a) \* n $$ 即$i$是圈长度的倍数。 设总的迭代数为 $iteration$,那么剩余需要迭代的长度$remain$表示为: $$ remain = (iteration - i) mod \ i $$ 这里的$(iteration-remain)$ 表示为倍数圈长$i$的倍数,也即经过$(iteration-remain)$ 步迭代又回到了起点, 接着,我们对![](https://ooo.0o0.ooo/2017/05/13/5916d992ebcab.png)  进行$remain$ 次迭代,有 ![](https://ooo.0o0.ooo/2017/05/13/5916d9b115e40.png) 最后将迭代完成的表达式代入 $f(x)$函数求出结果,再格式化输出为题设要求的保留九位小数即完成求解。 ***引申***: *面试中的经典问题:* 1. *如何快速判断一个链表是循环链表,也即判断链表中是否有环?* 2. *若确定链表中存在环,怎样快速确定环的长度?*

Code

public class p197 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        double result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
    }


    private static long ITERATIONS = 1000000000000L;


    public static double run() {
        // Floyd's cycle-finding algorithm
        double x = -1;
        double y = -1;
        long i = 0;
        for (; i < ITERATIONS; i++) {
            // Here at the top of the loop, x = f^i(-1) and y = f^{2i}(-1)
            if (i > 0 && x == y)  // 此时x,y 值相等,表示在圈中相遇,(2i - i) = i 是圈长度的倍数
                break;
            // x y 预先设置不同的步速, y 比x 快i步
            x = f(x);
            y = f(f(y));
        }

        // 剩下的 (ITERATIONS - i)  步数对i取余数
        long remain = (ITERATIONS - i) % i;
        // 对余数进行f函数迭代
        for (; remain > 0; remain--)
            x = f(x);
        double answer = x + f(x);
        // 代入函数f(x)
        answer = Math.floor(answer * 1e9) / 1e9;  // Truncate to 9 digits after the decimal point
        String str = String.format("%.9f", answer);  // 调整输出格式
        double result = Double.parseDouble(str); // 转化为double 类型
        return result;
    }


    private static double f(double x) {
        return Math.floor(Math.pow(2, 30.403243784 - x * x)) / 1e9;
    }
}
1.710637717
21ms