英文:
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, "" );
}
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 + " ");
}
}
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 >= 1; i--) {
partition(n - i, i, prefix + " " + i);
}
We just need to make that loop run backwards:
for (int i = 1; i <= Math.min(max, n); i++) {
partition(n - i, i, prefix + " " + i);
}
The complete source:
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);
}
}
OUTPUT
> java Partition
5
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5
>
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 < 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;
}
}
}
}
}
OUTPUT
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论