-9

我试图更好地理解 ZFC 集合论，特别是计算机程序如何模拟无穷大公理以“构造”自然数。我见过的用于构造自然数的典型符号是：“{”、“}”和“,”。

下面的代码有效，但我希望有一个纯粹的递归解决方案。一个给定一个自然数（这里使用 int），递归地将相应的字符串构建到它的集合论编码中，然后返回它。理想情况下，我希望它能够在不使用任何额外数据结构（如当前使用的字符串数组）的情况下工作。

如果运行时间很慢（指数型）也没关系。使用递归有时会使过程的表达更简单，更简洁/优雅且更易于理解，我非常想看看这种解决方案可能是什么样子，无论性能如何。最终，我想更好地理解数学/数字的基础。我有很多问题，但认为这可能是一个很好的开始方式。谢谢！

// Converts an natural number to its ZFC set notation: 
// 0 = {}, 1 = {0} = {{}}, 2 = {0,1} = {{},{{}}},  
// 3 = {0,1,2} = {{},{{}},{{},{{}}}} ...    

import java.util.Scanner;

public class IntToSetNotation {
    private static final String openBrace = "{";
    private static final String closeBrace = "}";
    private static final String seperator = ",";

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        System.out.println(getSetNotationFromInt(n));
    }

    private static String getSetNotationFromInt(int n) {
        String[] nums = new String[n+1];
        nums[0] = openBrace + closeBrace;
        for (int i = 1; i < nums.length; i++) {
            if(i == nums.length-1)
                nums[i] = openBrace + getPrevSets(i,nums) + closeBrace;
            else
                nums[i] = seperator + openBrace + getPrevSets(i,nums) + closeBrace;
        }
        return nums[n];
    }

    private static String getPrevSets(int n, String[] nums) {
        String s = "";
        for (int i = 0; i<n; i++)
            s += nums[i];
        return s;
    }
}
4

3 回答 3

0

所以递归听起来真的很困难，但是一旦你忘记了这个名字，它实际上就很简单了。

递归需要一些东西：停止递归的基本情况，以及做你想做的事情的输出。

假设你想编写一个递归问题，它接受一个数字 x，并返回一个特定的花括号模式：

0 ==（无）

1 == {}

2 == {{}}

3 == {{{}}}

...

因此，您的递归方法将采用一个整数。

现在，让我们看看方法输出。如果我们在 1 上调用递归方法，我们想要返回 {}。简单的。就 java 而言，我们将返回一个字符串。

太好了，现在我们知道了方法的返回类型。

如果我们在 2 上调用递归方法，我们希望该方法首先输出 {}，然后我们希望该方法再次执行，但这一次，我们在 THE BEGINNING 放置一个 curly，在 END 放置一个 curly。

这是很难解释的部分。把递归想象成一个循环。最终，我们希望递归终止。假设我们最初在 3 上调用该方法。我们希望返回 {{{}}}。首先，我们的方法将返回 {}，然后是 {{}}，然后是 {{{}}}。它总共运行3次。

在递归调用中，您必须比初始调用少一个调用。

好的，现在你说，如果我们每次都减 1 并再次调用该方法，我们如何让它停止呢？

这就是所谓的基本情况。如果方法在 0 上被调用，我们不想返回任何东西，因此我们想用一个简单的 return 语句退出方法。

将此应用于您自己的问题，您应该会很好。

String exampleRecursiveMethod(int x){
 if(x==0)return "";
 else return exampleRecursiveMethod(x-1)
}

这是一个让您入门的示例。else之后的return语句称为递归调用，我上面讲过。

于 2015-08-29T21:28:49.260 回答
0

我想出了下面的代码作为递归解决方案。它有效，但我想知道是否有任何方法可以简化它，也许使用更少的方法？欢迎任何想法或评论。

public class IntToSetNotationRecursive {
    private static final String openBrace = "{";
    private static final String closeBrace = "}";
    private static final String seperator = ",";

    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            System.out.println(i + " = " + getSetNotationFromInt(i));
        }
    }

    static String getSetNotationFromInt(int n){
        return helper1(n, n, "");
    }

    static String helper1(int n, int x, String s){
        if(x<=0)
            return openBrace + s + closeBrace;

        return helper1(n, x-1, helper2(x-1) + ((x != n ) ? seperator : "") + s);
    }

    static String helper2(int x){
        if(x<=0)return openBrace+closeBrace;
        else return helper1(x, x, "");
    }
}

打印：
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
4 = {{}, {{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5 = {{},{{}},{{}, {{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{ {}},{{},{{}}}}}}

于 2015-08-30T05:29:03.300 回答
0

第二个辅助方法不是必需的。这是一个缩短的版本。

public class IntToSetNotationRecursive {
    private static final String openBrace = "{";
    private static final String closeBrace = "}";
    private static final String separator = ",";

    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            System.out.println(i + " = " + getSetNotationFromInt(i));
        }
    }

    static String getSetNotationFromInt(int n){
        return helper1(n, n, "");
    }

    static String helper1(int n, int x, String s){
        if(x<=0)
            return openBrace + s + closeBrace;

        return helper1(n, x-1, helper1(x-1,x-1,"") + ((x != n ) ? separator : "") + s);
    }
}

打印：
0 = {}
1 = {{}}
2 = {{},{{}}}
3 = {{},{{}},{{},{{}}}}
4 = {{}, {{}},{{},{{}}},{{},{{}},{{},{{}}}}}
5 = {{},{{}},{{}, {{}}},{{},{{}},{{},{{}}}},{{},{{}},{{},{{}}},{{},{ {}},{{},{{}}}}}}

于 2015-08-30T23:44:39.137 回答