优化Collatz猜想

Question

这是一项工作：

锻炼PSD想到一个25岁以下的数字。把号码写下来。如果数字是偶数，除以两en写下下面的结果。如果这个数字不是偶数(这个数字是奇数)，用3乘以这个数字，再加上1。写下这个数字。重复，直到答案是1。为这个问题写代码。例子: 13 14 40 7 20 22 10 11 34 16 52 8 26 4 13 2 40 1 20 10 5 16 4 2 1

如何优化这段代码？例如，是否有可能将它写得更短或更好？

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        PSD(i);
    }

    public static void PSD(int x) {
        if(x == 1){
            System.out.println(x);
        }
            else if (x % 2 == 0) {
            System.out.println(x);
                PSD((x / 2));
            } else {
            System.out.println(x);
                PSD((x * 3)+1);
            }
        }
    }

Answer 1

函数

打印

一个函数应该只做一件事。你的计算和打印。这使得重用该函数变得困难，而且它也减慢了它的速度。收集函数内部的结果(由于性能原因最好使用StringBuilder )，返回结果，并将其打印到其他地方。

风格

缩进是关闭的，这使您的代码难以阅读。您可以通过任何IDE轻松地修复这个问题。

复制

您的else if和else块包含一些复制。您可以在那里计算传递给PSD的值，并只在外部调用System.out.println和PSD一次。

有了这些点，您的代码可能如下所示：

public static String PSD(int x, StringBuilder result) {
    if (x == 1) {
        result.append(x);
        return result.toString();
    }

    int value;
    if (x % 2 == 0) {
        value = x / 2;
    } else {
        value = (x * 3) + 1;
    }
    result.append(x);
    result.append("\n");
    return PSD(value, result);
}

递归函数

递归函数的性能通常比迭代方法差。迭代方法可能如下所示：

public static String PSD(int x) {
    StringBuilder result = new StringBuilder();
    while (x != 1) {
        result.append(x);
        result.append("\n");
        if (x % 2 == 0) {
            x /= 2;
        } else {
            x = (x * 3) + 1;
        }
    }
    result.append(1);
    return result.toString();
}

Answer 2

您的代码有两个可伸缩性问题。已经提到了过度递归可能产生的StackOverflowError，解决方案是使用循环。

另一个问题是Collatz序列可以增长到出乎意料的大数目。这些有时被称为“冰雹序列”就是因为这个原因。因此，long将是比int更好的选择。

Answer 3

-- Collatz序列

的另一种方法

在下面的实现中，我们利用了这样一个事实:当n作为奇数开始迭代时，n = (n * 3) + 1总是会产生偶数n。因此，我们可以在每次迭代中执行n /= 2，因为当我们到达它时，n总是相等的。

ArrayList

为了给我的实现增加更多的多样性，我想我应该使用ArrayList容器，它具有add(...)在定时间中运行的显著好处。

import java.util.Scanner;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        for (int value : collatz(i)) 
            System.out.println(value);
    }

    public static ArrayList<Integer> collatz(Integer n) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(n);
        while (n != 1) {
            if (n % 2 == 1) {
                n = (n * 3) + 1;
                res.add(n);
            }
            n /= 2;
            res.add(n);
        }
        return res;
    }
}