如何使用Java中的递归打印出附上图像中所示的图案。

huangapple go评论71阅读模式
英文:

How to print pattern shown in the image attached using recursion in java

问题

以下是您要翻译的部分:

"Output I want and Output I am getting" 和 "Please see the image I wanted to print a similar pattern and I am succeeded to some extent. I am not able to get rid of similar addends like 1 4 and 4 1. I only need 4 1 and I didn't want 1 4 to be printed. Can anyone suggest some modification to my code to achieve the desired output?"

我的代码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = 5;
    partition(n);
}

public static void partition(int n) {
    partition(n, 1, "");
}

public static void partition(int n, int max, String prefix) {
    if (n == 0) {
        System.out.println(prefix);
        return;
    }

    for (int i = Math.min(max, n); i <= n; i++) {
        partition(n-i, i, prefix + i + " ");
    }
}

请帮忙!

英文:

Output I want and Output I am getting
Please see the image I wanted to print a similar pattern and I am succeeded to some extent. I am not able to get rid of similar addends like 1 4 and 4 1. I only need 4 1 and I didn't want 1 4 to be printed.
Can anyone suggest some modification to my code to achieve the desired output?

MY CODE

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = 5;
    partition(n);
}

 public static void partition(int n) {
    partition(n, 1, &quot;&quot; );
}

public static void partition(int n, int max, String prefix) {
    if (n == 0) {
        System.out.println(prefix);
        return;
    }

    for (int i = Math.min(max, n); i &lt;= n; i++) {
        partition(n-i, i, prefix + i + &quot; &quot;);
    }
}

please help!!!

答案1

得分: 2

这并不是关于递归的问题,而是关于迭代的问题。考虑你提供的递归起始代码中的循环:

for (int i = Math.min(max, n); i >= 1; i--) {
    partition(n - i, i, prefix + " " + i);
}

我们只需要使这个循环以反向运行:

for (int i = 1; i <= Math.min(max, n); i++) {
    partition(n - i, i, prefix + " " + i);
}

完整的源代码:

import java.util.Scanner;

public class Partition {

    public static void partition(int n) {
        partition(n, n, "");
    }

    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            System.out.println(prefix);
            return;
        }

        for (int i = 1; i <= Math.min(max, n); i++) {
            partition(n - i, i, prefix + " " + i);
        }
    }

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

输出结果

> java Partition
5
 1 1 1 1 1
 2 1 1 1
 2 2 1
 3 1 1
 3 2
 4 1
 5
>

我相信你把问题想得比它实际上要困难。

英文:

This isn't a problem in recursion but rather iteration. Given the loop in the recursive starting code you linked:

for (int i = Math.min(max, n); i &gt;= 1; i--) {
	partition(n - i, i, prefix + &quot; &quot; + i);
}

We just need to make that loop run backwards:

for (int i = 1; i &lt;= Math.min(max, n); i++) {
	partition(n - i, i, prefix + &quot; &quot; + i);
}

The complete source:

import java.util.Scanner;

public class Partition {

	public static void partition(int n) {
		partition(n, n, &quot;&quot;);
	}

	public static void partition(int n, int max, String prefix) {
		if (n == 0) {
			System.out.println(prefix);
			return;
		}

		for (int i = 1; i &lt;= Math.min(max, n); i++) {
			partition(n - i, i, prefix + &quot; &quot; + i);
		}
	}

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

OUTPUT

&gt; java Partition
5
 1 1 1 1 1
 2 1 1 1
 2 2 1
 3 1 1
 3 2
 4 1
 5
&gt; 

I believe you were making the problem harder than it is.

答案2

得分: 0

我还无法想出递归解决方案但这段代码应该能完成任务

public static void main(String[] args) {
    int n = 5;
    int[] arr = new int[n]; 
    int[] idx = new int[n];
    int currSize = n;
    for(int i = 0; i < n; i++) {arr[i] = 1; idx[i] = i + 1;}
    
    while(true) {
        
        for(int i = 0; i < n; i = idx[i]) System.out.print(arr[i] + " ");
        System.out.println();
        
        boolean changed = false;
        
        for(int i = 0; idx[i] < n; i = idx[i]){
            if(arr[i] == arr[idx[i]]){
                arr[i]++;
                arr[idx[i]]--;
                if(arr[idx[i]] == 0) {
                    idx[i] = idx[idx[i]];
                    currSize--;
                }
                changed = true;
                break;
            }
        }
        
        if(!changed && currSize > 1){
            arr[0]++;
            arr[idx[0]]--;
            if(arr[idx[0]] == 0) {
                idx[0] = idx[idx[0]];
                currSize--;
                if(currSize == 1) {
                    System.out.println(arr[0]);
                    break;
                }
            }
        }
    }
}

**输出结果**

    1 1 1 1 1 
    2 1 1 1 
    2 2 1 
    3 1 1 
    3 2 
    4 1 
    5
英文:

I couldn't figure out a recursive solution yet, but this should do the job:

public static void main(String[] args) {
int n = 5;
int[] arr = new int[n]; 
int[] idx = new int[n];
int currSize = n;
for(int i = 0; i &lt; n; i++) {arr[i] = 1; idx[i] = i + 1;}
while(true) {
for(int i = 0; i &lt; n; i = idx[i]) System.out.print(arr[i] + &quot; &quot;);
System.out.println();
boolean changed = false;
for(int i = 0; idx[i] &lt; n; i = idx[i]){
if(arr[i] == arr[idx[i]]){
arr[i]++;
arr[idx[i]]--;
if(arr[idx[i]] == 0) {
idx[i] = idx[idx[i]];
currSize--;
}
changed = true;
break;
}
}
if(!changed &amp;&amp; currSize &gt; 1){
arr[0]++;
arr[idx[0]]--;
if(arr[idx[0]] == 0) {
idx[0] = idx[idx[0]];
currSize--;
if(currSize == 1) {
System.out.println(arr[0]);
break;
}
}
}
}
}

OUTPUT

1 1 1 1 1 
2 1 1 1 
2 2 1 
3 1 1 
3 2 
4 1 
5

huangapple
  • 本文由 发表于 2020年7月24日 23:41:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/63076898.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定