DouKaku?beta

challenge 自然数の分割 

自然数nとm(n>=m>0)が与えられたとき，nをm個の非負の整数の和で表すやり方を全て出力してください．
その際，和の組(x_1, ..., x_m)は大きい順に出力してください．
ここでm = 3の時の「(a, b, c)が(A, B, C)より大きい」とは
(a > A)
(a == A) かつ (b > B)
(a == A) かつ (b == B) かつ (c > C)
のいずれかが成り立つとき(つまりは辞書的順序)とします．

例:n = 5, m = 3が与えられたときは
5, 0, 0,
4, 1, 0,
4, 0, 1,
3, 2, 0,
3, 1, 1,
...
0, 1, 4,
0, 0, 5,
を出力する．
post comment

Posted feedbacks - Java

普通に再帰で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
public class PartNumber {
    public static void main(String[] args) {
        System.out.println(part(5, 3));    // => [[5, 0, 0], [4, 1, 0], ..., [0, 1, 4], [0, 0, 5]]
    }
    private static List<List<Integer>> part(int n, int m) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> item;
        if (m == 1) {
            item = new ArrayList<Integer>();
            item.add(n);
            res.add(item);
            return res;
        }
        for (int i = n; i >= 0; i--) {
            List<List<Integer>> r = part(n - i, m - 1);
            for (List<Integer> l : r) {
                item = new ArrayList<Integer>();
                item.add(i);
                item.addAll(l);
                res.add(item);
            }
        }
        return res;
    }
}

動的計画法で。
(n, m) = (32, 8)で実行した場合。
----
234[ms]
[4, 4, 4, 4, 4, 4, 4, 4]
[3, 4, 4, 4, 4, 4, 4, 5]
[3, 3, 4, 4, 4, 4, 5, 5]
   :
[0, 0, 0, 0, 0, 0, 1, 31]
[0, 0, 0, 0, 0, 0, 0, 32]
3319 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.*;

public class PartNumber {
    private static final Map<Key, Answer> answerTable = new HashMap<Key, Answer>();
    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Answer answer = execute(32, 8);
        System.out.printf("%d[ms]%n", System.currentTimeMillis() - begin);
        for (int[] a : answer.set) {
            System.out.println(Arrays.toString(a));
        }
        System.out.println(answer.set.size());
    }
    
    public static Answer execute(int n, int m) {
        Key key = new Key(n, m);
        if(answerTable.containsKey(key)) {
            return answerTable.get(key);
        }
        Answer answer = new Answer(key);
        if(m <= 2) {
            for (int i = 0; i <= n/2; i++) {
                answer.set.add(new int[]{i, n-i});
            }
        } else {
            for (int i = 0; i <= n/m; i++) {
                answer.set.addAll(execute(n-i, m-1).marge(key, i).set);
            }
        }
        answerTable.put(key, answer);
        return answer;
    }
     
    static class Key {
        final int n;
        final int m;

        Key(int n, int m) {
            this.n = n;
            this.m = m;
        }
        
        @Override
        public int hashCode() {
            return 17 * n ^ m;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Key)) return false;
            Key target = (Key) obj;
            return (this.n == target.n && this.m == target.m);
        }
    }
    
    static class Answer {
        private final Key k;
        private TreeSet<int[]> set;

        Answer(Key k) {
            this.k = k;
            this.set = new TreeSet<int[]>(
                new Comparator<int[]>() {
                    public int compare(int[] o1, int[] o2) {
                        assert o1.length == o2.length;
                        if(o1 == o2) return 0;
                        for (int i = 0; i < o1.length; i++) {
                            if(o1[i] != o2[i]) return o2[i] - o1[i];
                        }
                        return 0;
                    }
                });
        }
        boolean add(int x, int[] a) {
            assert a.length + 1 == k.m;
            int[] a2 = new int[k.m];
            a2[0] = x;
            System.arraycopy(a, 0, a2, 1, a.length);
            Arrays.sort(a2);
            return set.add(a2);
        }
        Answer marge(Key k, int x) {
            Answer answer = new Answer(k);
            for (int[] a : this.set) {
                answer.add(x, a);
            }
            return answer;
        }
    }
}

Javaが無いからと思ったのに、 完成したときには投稿されていたよ。 残念。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Bunkatsu {
    public static void main(String[] args) {
        printSum( 6, 3 );
    }

    public    static void printSum( int n, int m) {
        if( m <= 0 || n < m )
            return;
        
        int[]    prints = new int[m];
        subPrintSum( prints, 0, n, m );
    }
    
    public static void subPrintSum( int[] prints, int p, int zan, int m ) {
        if( p == m -1 ) {
            prints[p] = zan;

            for( int print : prints ) {
                System.out.print( print );
                System.out.print( "," );
            }
            System.out.println();
        }
        else
        {
            for( int i = zan ; i >= 0 ; --i ) {
                prints[p] = i;
                subPrintSum( prints, p+1, zan - i, m );
            }
        }
    }
}

修正。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package doukaku;

import java.util.*;

public class PartNumber {
    private static final Map<Key, Answer> answerTable = new HashMap<Key, Answer>();
    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Answer answer = execute(32, 8);
        System.out.printf("%d[ms]%n", System.currentTimeMillis() - begin);
        for (Integer[] a : answer.set) {
            System.out.println(Arrays.toString(a));
        }
        System.out.println(answer.set.size());
    }
    
    public static Answer execute(int n, int m) {
        Key key = new Key(n, m);
        if(answerTable.containsKey(key)) {
            return answerTable.get(key);
        }
        Answer answer = new Answer(key);
        if(m <= 2) {
            for (int i = 0; i <= n/2; i++) {
                answer.set.add(new Integer[]{i, n-i});
            }
        } else {
            for (int i = 0; i <= n/m; i++) {
                answer.set.addAll(execute(n-i, m-1).marge(key, i).set);
            }
        }
        answerTable.put(key, answer);
        return answer;
    }
     
    static class Key {
        final int n;
        final int m;

        Key(int n, int m) {
            this.n = n;
            this.m = m;
        }
        
        @Override
        public int hashCode() {
            return 17 * n ^ m;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Key)) return false;
            Key target = (Key) obj;
            return (this.n == target.n && this.m == target.m);
        }
    }
    
    static class Answer {
        private final Key k;
        private TreeSet<Integer[]> set;

        Answer(Key k) {
            this.k = k;
            this.set = new TreeSet<Integer[]>(
                new Comparator<Integer[]>() {
                    public int compare(Integer[] o1, Integer[] o2) {
                        assert o1.length == o2.length;
                        if(o1 == o2) return 0;
                        for (int i = 0; i < o1.length; i++) {
                            if(o1[i] != o2[i]) return o2[i] - o1[i];
                        }
                        return 0;
                    }
                });
        }
        boolean add(int x, Integer[] a) {
            assert a.length + 1 == k.m;
            Integer[] a2 = new Integer[k.m];
            a2[0] = x;
            System.arraycopy(a, 0, a2, 1, a.length);
            Arrays.sort(a2, Collections.reverseOrder());
            
            return set.add(a2);
        }
        Answer marge(Key k, int x) {
            Answer answer = new Answer(k);
            for (Integer[] a : this.set) {
                answer.add(x, a);
            }
            return answer;
        }
    }
}


Javaはもうあるけど，短いのができたので載せてみる。

java PartNumber 5 3
みたいにして実行。

各行の最後のカンマは余分だと思うのだけど，
問題文にあわせてつけてみた。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class PartNumber {
    public static void main(String[] args) throws Exception {
        part("", Integer.parseInt(args[0]), Integer.parseInt(args[1]));
    }
    private static void part(String s, int n, int m) {
        if (m == 1) {
            System.out.println(s + n + ",");
        } else for (int i = n; i >= 0; i--) {
            if (n - i >= 0) part(s + i + ", ", n - i, m - 1);
        }
    }
}

しまった。if文がよぶんだった。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class PartNumber {
    public static void main(String[] args) throws Exception {
        part("[", Integer.parseInt(args[0]), Integer.parseInt(args[1]));
    }
    private static void part(String s, int n, int m) {
        if (m == 1) {
            System.out.println(s + n + "]");
        } else for (int i = n; i >= 0; i--) {
            part(s + i + ", ", n - i, m - 1);
        }
    }
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]