回答編集履歴
7
追記3
answer
CHANGED
|
@@ -93,4 +93,31 @@
|
|
|
93
93
|
}
|
|
94
94
|
```
|
|
95
95
|
|
|
96
|
-
gen の呼び出し回数も減ります。
|
|
96
|
+
gen の呼び出し回数も減ります。
|
|
97
|
+
|
|
98
|
+
**追記3**
|
|
99
|
+
xebme さんのコードに刺激されて、for文を再帰呼出しに変えてみました。
|
|
100
|
+
```Java
|
|
101
|
+
import java.util.Arrays;
|
|
102
|
+
|
|
103
|
+
class Main {
|
|
104
|
+
public static void main(String []args){
|
|
105
|
+
int n = 6;
|
|
106
|
+
gen(new int[n], 0, n, n);
|
|
107
|
+
}
|
|
108
|
+
|
|
109
|
+
static void gen(int[] a, int i, int j, int r) {
|
|
110
|
+
if (r == 0) // 和ができたので表示
|
|
111
|
+
System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
|
|
112
|
+
else { // まだ和に達していない
|
|
113
|
+
a[i] = j = Math.min(j, r);
|
|
114
|
+
gen(a, i + 1, j, r - j);
|
|
115
|
+
if (--j > 0) gen(a, i, j, r);
|
|
116
|
+
}
|
|
117
|
+
}
|
|
118
|
+
}
|
|
119
|
+
```
|
|
120
|
+
|
|
121
|
+
和の n は、ハードコーディングしました。
|
|
122
|
+
Scanner による標準入力や、args によるコマンドライン引数に
|
|
123
|
+
変えるのは簡単でしょう。
|
6
追記2
answer
CHANGED
|
@@ -78,4 +78,19 @@
|
|
|
78
78
|
[2, 2]
|
|
79
79
|
[2, 1, 1]
|
|
80
80
|
[1, 1, 1, 1]
|
|
81
|
-
```
|
|
81
|
+
```
|
|
82
|
+
**追記2**
|
|
83
|
+
`Math.min` を使うと、`else if (r > 0)` が `else` で済みますね。
|
|
84
|
+
```Java
|
|
85
|
+
static void gen(int[] a, int i, int j, int r) {
|
|
86
|
+
if (r == 0) // 和ができたので表示
|
|
87
|
+
System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
|
|
88
|
+
else // まだ和に達していない
|
|
89
|
+
for (j = Math.min(j, r); j > 0; j--) {
|
|
90
|
+
a[i] = j;
|
|
91
|
+
gen(a, i + 1, j, r - j); // 再帰呼出し
|
|
92
|
+
}
|
|
93
|
+
}
|
|
94
|
+
```
|
|
95
|
+
|
|
96
|
+
gen の呼び出し回数も減ります。
|
5
copyOfRange を copyOf に変更
answer
CHANGED
|
@@ -57,7 +57,7 @@
|
|
|
57
57
|
|
|
58
58
|
static void gen(int[] a, int i, int j, int r) {
|
|
59
59
|
if (r == 0) // 和ができたので表示
|
|
60
|
-
System.out.println(Arrays.toString(Arrays.
|
|
60
|
+
System.out.println(Arrays.toString(Arrays.copyOf(a, i)));
|
|
61
61
|
else if (r > 0) // まだ和に達していない
|
|
62
62
|
for (; j > 0; j--) {
|
|
63
63
|
a[i] = j;
|
4
追記のコードの表示を Arrays を使うものに変更
answer
CHANGED
|
@@ -44,21 +44,20 @@
|
|
|
44
44
|
gen を static にして、Sumクラスを使わずに、
|
|
45
45
|
さらに、和を引数で与えるようにしてみました。
|
|
46
46
|
```Java
|
|
47
|
+
import java.util.Arrays;
|
|
48
|
+
|
|
47
49
|
class Main {
|
|
48
50
|
public static void main(String []args){
|
|
49
|
-
for (
|
|
51
|
+
for (int i = 0; i < args.length; i++) {
|
|
50
|
-
int n = Integer.parseInt(
|
|
52
|
+
int n = Integer.parseInt(args[i]);
|
|
51
|
-
|
|
53
|
+
if (i > 0) System.out.println();
|
|
52
54
|
gen(new int[n], 0, n, n);
|
|
53
55
|
}
|
|
54
56
|
}
|
|
55
57
|
|
|
56
58
|
static void gen(int[] a, int i, int j, int r) {
|
|
57
|
-
if (r == 0)
|
|
59
|
+
if (r == 0) // 和ができたので表示
|
|
58
|
-
String s = "";
|
|
59
|
-
for (j = 0; j < i; j++) s += " " + a[j];
|
|
60
|
-
System.out.println(
|
|
60
|
+
System.out.println(Arrays.toString(Arrays.copyOfRange(a, 0, i)));
|
|
61
|
-
}
|
|
62
61
|
else if (r > 0) // まだ和に達していない
|
|
63
62
|
for (; j > 0; j--) {
|
|
64
63
|
a[i] = j;
|
|
@@ -70,14 +69,13 @@
|
|
|
70
69
|
実行例
|
|
71
70
|
```text
|
|
72
71
|
$ java Main 3 4
|
|
73
|
-
3
|
|
72
|
+
[3]
|
|
74
|
-
3
|
|
75
|
-
|
|
73
|
+
[2, 1]
|
|
76
|
-
|
|
74
|
+
[1, 1, 1]
|
|
75
|
+
|
|
77
|
-
4
|
|
76
|
+
[4]
|
|
78
|
-
4
|
|
79
|
-
|
|
77
|
+
[3, 1]
|
|
80
|
-
|
|
78
|
+
[2, 2]
|
|
81
|
-
|
|
79
|
+
[2, 1, 1]
|
|
82
|
-
|
|
80
|
+
[1, 1, 1, 1]
|
|
83
81
|
```
|
3
追記
answer
CHANGED
|
@@ -39,4 +39,45 @@
|
|
|
39
39
|
}
|
|
40
40
|
}
|
|
41
41
|
}
|
|
42
|
+
```
|
|
43
|
+
**追記**
|
|
44
|
+
gen を static にして、Sumクラスを使わずに、
|
|
45
|
+
さらに、和を引数で与えるようにしてみました。
|
|
46
|
+
```Java
|
|
47
|
+
class Main {
|
|
48
|
+
public static void main(String []args){
|
|
49
|
+
for (String s : args) {
|
|
50
|
+
int n = Integer.parseInt(s);
|
|
51
|
+
System.out.println(n);
|
|
52
|
+
gen(new int[n], 0, n, n);
|
|
53
|
+
}
|
|
54
|
+
}
|
|
55
|
+
|
|
56
|
+
static void gen(int[] a, int i, int j, int r) {
|
|
57
|
+
if (r == 0) { // 和ができたので表示
|
|
58
|
+
String s = "";
|
|
59
|
+
for (j = 0; j < i; j++) s += " " + a[j];
|
|
60
|
+
System.out.println(s);
|
|
61
|
+
}
|
|
62
|
+
else if (r > 0) // まだ和に達していない
|
|
63
|
+
for (; j > 0; j--) {
|
|
64
|
+
a[i] = j;
|
|
65
|
+
gen(a, i + 1, j, r - j); // 再帰呼出し
|
|
66
|
+
}
|
|
67
|
+
}
|
|
68
|
+
}
|
|
69
|
+
```
|
|
70
|
+
実行例
|
|
71
|
+
```text
|
|
72
|
+
$ java Main 3 4
|
|
73
|
+
3
|
|
74
|
+
3
|
|
75
|
+
2 1
|
|
76
|
+
1 1 1
|
|
77
|
+
4
|
|
78
|
+
4
|
|
79
|
+
3 1
|
|
80
|
+
2 2
|
|
81
|
+
2 1 1
|
|
82
|
+
1 1 1 1
|
|
42
83
|
```
|
2
説明の修正 (0 -> 1)
answer
CHANGED
|
@@ -1,6 +1,6 @@
|
|
|
1
1
|
要素の和を n とすると、全部 1 が一番長い部分集合になるので、
|
|
2
2
|
大きさ n の配列を用意して、大きい数から詰め込んで行くことにします。
|
|
3
|
-
まだ和に達していなければ、左側以下の値を大きいものから順に
|
|
3
|
+
まだ和に達していなければ、左側以下の値を大きいものから順に 1 になるまで
|
|
4
4
|
詰め込んで、次に行くというのを繰り返せばよいでしょう。
|
|
5
5
|
|
|
6
6
|
ヒントとして書くのが難しいので、コードで書きます。
|
1
コードの修正
answer
CHANGED
|
@@ -20,10 +20,9 @@
|
|
|
20
20
|
}
|
|
21
21
|
|
|
22
22
|
class Sum {
|
|
23
|
-
int
|
|
23
|
+
int a[];
|
|
24
24
|
|
|
25
25
|
Sum(int n) {
|
|
26
|
-
this.n = n;
|
|
27
26
|
a = new int[n];
|
|
28
27
|
}
|
|
29
28
|
|
|
@@ -33,8 +32,8 @@
|
|
|
33
32
|
System.out.print(" " + a[j]);
|
|
34
33
|
System.out.println();
|
|
35
34
|
}
|
|
36
|
-
else if (r > 0
|
|
35
|
+
else if (r > 0) // まだ和に達していない
|
|
37
|
-
for (int j = k; j >
|
|
36
|
+
for (int j = k; j > 0; j--) {
|
|
38
37
|
a[i] = j;
|
|
39
38
|
gen(i+1, j, r - j); // 再帰呼出し
|
|
40
39
|
}
|