Эта Java-программа преобразует натуральное число в теоретико-множественное кодирование, используя итерацию. Запросить помощь / стратегии для рекурсивного решения?
Я пытаюсь лучше понять теорию множеств 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;
}
}
3 ответа
Второй вспомогательный метод не требуется. Вот сокращенная версия.
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 = {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}, {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}}
Я придумал приведенный ниже код в качестве рекурсивного решения. Это работает, но мне интересно, есть ли способ его упростить, возможно, использовать меньше методов? Любые мысли или комментарии приветствуются.
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 = {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}, {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}}
Так что рекурсия звучит очень сложно, но на самом деле все просто, когда вы понимаете имя.
Рекурсия нуждается в вещах: базовый случай, чтобы прекратить повторение, и вывод, чтобы делать то, что вы хотите.
Допустим, вы хотите написать рекурсивную задачу, которая принимает число x и возвращает определенный шаблон фигурных скобок:
0 == (ничего)
1 == {}
2 == {{}}
3 == {{{}}}
...
Итак, ваш рекурсивный метод будет принимать одно целое число.
Теперь давайте посмотрим на вывод метода. Если мы вызовем рекурсивный метод для 1, мы хотим вернуть {}. Легко. С точки зрения Java, мы будем возвращать строку.
Отлично, теперь мы знаем тип возвращаемого значения метода.
Если мы вызываем рекурсивный метод для 2, мы хотим, чтобы метод сначала вывел {}, а затем мы хотим, чтобы метод выполнялся ОПЯТЬ, но на этот раз мы помещаем фигурный В НАЧАЛЕ, и один фигурный в КОНЕЦ.
Это та часть, которую трудно объяснить. Вообразите рекурсию как петлю. В конце концов, мы хотим, чтобы рекурсия прекратилась. Скажем, мы вызываем метод изначально на 3. Мы хотим, чтобы {{{}}} был возвращен. Сначала наш метод вернет {}, затем {{}}, затем {{{}}}. Это работает в общей сложности 3 раза.
При рекурсивном вызове вы должны вызывать его на единицу меньше, чем при первоначальном вызове.
Хорошо, теперь вы говорите, что если мы каждый раз вычитаем 1 и снова вызываем метод, как мы можем остановить его?
Это называется базовый случай. Если метод вызывается с 0, мы не хотим ничего возвращать, поэтому мы хотим выйти из метода с помощью простого оператора return.
Примените это к вашей собственной проблеме, и вы должны быть хорошими.
String exampleRecursiveMethod(int x){
if(x==0)return "";
else return exampleRecursiveMethod(x-1)
}
Это пример для начала. Оператор return после else называется рекурсивным вызовом, о котором я говорил выше.