使用迭代器实现降序斐波那契数的技术问题求助

嘿，这个问题我太懂了——用迭代器就是要追求按需生成元素的优雅，要是先把数存数组再排序，那确实违背了迭代器的核心初衷，完全没必要这么干！

其实关键在于利用斐波那契数列的反向递推关系：我们都知道正向是 F(n) = F(n-1) + F(n-2)，反过来推导的话，就可以得到 F(n-2) = F(n) - F(n-1)。基于这个公式，我们可以从用户输入的起始数开始，一步步反向算出前一个斐波那契数，完全不需要预先存储整个序列。

具体实现步骤 #

• 初始化迭代器：首先需要找到小于等于用户输入值的最大斐波那契数作为起始的current，同时找到它的前一个斐波那契数作为prev（这一步需要正向遍历一次斐波那契数列，直到超过输入值为止）。
• 按需生成元素：每次调用next()时，返回当前的current，然后通过反向公式更新current和prev：新的current变成原来的prev，新的prev变成原来的current - prev。
• 终止条件：当current小于0时，停止迭代（因为斐波那契数列都是非负的）。

代码示例 #

import java.util.Iterator;

public class ReverseFibonacciIterator implements Iterator<Integer> {
    private int current;
    private int prev;

    public ReverseFibonacciIterator(int start) {
        if (start < 0) {
            throw new IllegalArgumentException("起始数必须是非负整数");
        }

        // 处理边界情况
        if (start == 0) {
            current = 0;
            prev = -1; // 标记迭代即将结束
            return;
        }
        if (start == 1) {
            current = 1;
            prev = 0;
            return;
        }

        // 正向遍历找到小于等于start的最大斐波那契数对
        int prevPrev = 0;
        int prevCurr = 1;
        int curr = 1;

        while (curr <= start) {
            int next = prevCurr + curr;
            if (next > start) {
                break;
            }
            prevPrev = prevCurr;
            prevCurr = curr;
            curr = next;
        }

        this.current = curr;
        this.prev = prevCurr;
    }

    @Override
    public boolean hasNext() {
        return current >= 0;
    }

    @Override
    public Integer next() {
        int result = current;
        // 反向递推更新数值
        int temp = current;
        current = prev;
        prev = temp - prev;
        return result;
    }
}

测试代码 #

public class Main {
    public static void main(String[] args) {
        // 测试输入13的情况
        ReverseFibonacciIterator iterator = new ReverseFibonacciIterator(13);
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        // 输出结果：13 → 8 → 5 → 3 → 2 → 1 → 1 → 0
    }
}

额外说明 #

• 这个实现完全遵循迭代器的懒加载特性，每次next()才计算下一个元素，不会占用额外的内存存储整个序列，尤其适合处理大起始数的场景。
• 如果用户输入的不是标准斐波那契数，代码会自动从小于等于输入值的最大斐波那契数开始生成序列，保证输出的都是合法的斐波那契数。
• 已经处理了边界情况：输入0时只输出0，输入1时输出1、1、0，输入负数时直接抛出异常。

内容的提问来源于stack exchange，提问作者Ih8th3c0ld