-9

私は、ZFC 集合論、特にコンピュータ プログラムが無限公理をモデル化して自然数を「構築」する方法をよりよく理解しようとしています。自然数を構成するために使用される典型的な記号は、「{」、「}」、および「,」です。

以下のコードは機能しますが、純粋に再帰的なソリューションを望んでいます。自然数 (ここでは int を使用) を指定すると、対応する文字列を集合論的エンコーディングに再帰的に構築し、それを返します。理想的には、現在使用されている String 配列のような余分なデータ構造を使用せずに機能することを願っています。

ランタイムが遅い (指数関数的) 場合は問題ありません。再帰を使用すると、プロセスの表現がより単純で、より凝縮/エレガントになり、理解しやすくなることがあります。パフォーマンスに関係なく、このような解決策がどのように見えるかを非常に知りたいです。最終的には、数学/数の基礎をよりよく理解したいと思います。たくさんの質問がありますが、これは始めるのに良い方法かもしれないと思いました. ありがとう！

// 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 つの整数を取ります。

次に、メソッドの出力を見てみましょう。1 で再帰メソッドを呼び出す場合は、{} を返します。簡単。Javaに関しては、文字列を返します。

これで、メソッドの戻り値の型がわかりました。

2 で再帰メソッドを呼び出す場合、メソッドに最初に {} を出力させ、次にそのメソッドに AGAIN を実行させたいのですが、今回は先頭にカーリーを配置し、最後にカーリーを 1 つ配置しています。

これは説明が難しい部分です。再帰をループと想像してください。最終的に、再帰を終了させたいと考えています。最初に 3 でメソッドを呼び出したとします。{{{}}} が返されるようにします。まず、メソッドは {} を返し、次に {{}}、{{{}}} を返します。全部で3回実行されます。

再帰呼び出しでは、最初の呼び出しよりも 1 つ少なく呼び出す必要があります。

さて、毎回 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

2 番目のヘルパー メソッドは必要ありません。ここに短縮版があります。

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 に答える