0

作业：寻找更好的策略或方法而不是完整的代码。

当我试图确定这个问题的递归案例时，我完全糊涂了。我必须编写一个接受整数参数“n”的方法，然后打印出总共“n”个字符。中间字符应始终为 ' ' 或 ' *' 取决于原始整数是奇数还是偶数。下面是几个不同的方法调用和输出应该是这样的：

writeChars(1) -> *
writeChars(2) -> **
writeChars(3) -> <*>
writeChars(4) -> <**>
writeChars(5) -> <<*>>
writeChars(6) -> <<**>>
writeChars(7) -> <<<*>>>
writeChars(8) -> <<<**>>>

我什至如何尝试识别递归案例？

4

5 回答 5

2

你有两个基本情况：n == 1 和 n == 2。除此之外，递归规则是发出一个“<”，用 n-2 递归（考虑到你要在这个级别发出的两个字符)，然后发出一个“>”。

于 2013-02-24T05:57:16.340 回答
1

要识别递归，首先考虑如何解决给定 n 值的问题，假设您有一种方法可以解决较小情况的问题。尺寸 n 的解决方案与尺寸 n-1 的解决方案有何关系？

这样做之后，您会发现一个或多个您无法以这种方式解决的小案例。这些是你的基本情况。

最后，编写一个直接执行每个基本情况的方法。对于大于基本情况的 n，它调用自身为 n-1，然后修改该结果以获得大小为 n 的解。

于 2013-02-24T06:10:14.573 回答
0

我考虑递归的方式是传递两个状态（pos，string：s），它们在每个递归调用中都会发生变化，而三个状态（n，mid1，mid2）有助于决定如何实现下一个状态。

    public static void main(String... arg) {
        int n = 10, mid1, mid2;
        if (n % 2 == 0) {
            mid1 = n / 2;
            mid2 = n / 2 + 1;
        } else {
            mid1 = mid2 = n / 2 + 1;
        }

        System.out.println(recursion(1, n, mid1, mid2, ""));
    }

    private static String recursion(int pos, final int n, final int mid1, final int mid2, String s) {
        if (pos > n)
            return s;
        else if (pos == mid1 || pos == mid2)
            return recursion(pos + 1, n, mid1, mid2, s + "*");
        else if (pos < mid1)
            return recursion(pos + 1, n, mid1, mid2, s + "<");
        else
            return recursion(pos + 1, n, mid1, mid2, s + ">");
    }
于 2013-02-24T06:24:40.113 回答
0

我只假设两种基本情况，一种用于 n 为偶数时，一种用于 n 为奇数时。

现在在递归调用中我通过 n - 2; 在奇数 n 的情况下，它以 1 结尾，对于偶数 n，它以 2 结尾。

public static void writeChars(int n) {
    if(n < 1) 
        throw new IllegalArgumentException();
        
    if(n == 1)          //odd base case
        System.out.print("*");

    else if(n == 2)     //even base case
        System.out.print("**");
        
    else {              //recursive case
        System.out.print("<");
        writeChars(n - 2);
        System.out.print(">");
    }
}
于 2015-03-22T01:24:29.297 回答
0

我可能会将问题分为 3 个部分 1. 打印< 2. 打印* 3. 打印>

基于此，我们可以创建一个递归解决方案来打印每个组件。<和的数量>基于一个公式i % 2 == 1 ? i / 2 : (i - 2) / 2，然后我们可以编写一个函数以递归方式打印它们，然后再编写一个函数来打印*s。

public class SO15049082 {

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            print(i);
        }
    }

    private static void print(int i) {
        if (i > 0) {
            System.out.print("writeChars(" + i + ") --> ");
            int c = i % 2 == 1 ? i / 2 : (i - 2) / 2;
            printleft(c);
            printstar(c % 2);
            printright(c);
        }
        System.out.println();
    }

    private static void printright(int i) {
        if (i > 0) {
            System.out.print(">");
            printright(i - 1);
        }
    }

    private static void printstar(int i) {
        if (i == 1) {
            System.out.print("*");
        } else {
            System.out.print("**");
        }
    }

    private static void printleft(int i) {
        if (i > 0) {
            System.out.print("<");
            printleft(i - 1);
        }
    }

}
于 2013-02-24T06:14:38.827 回答