DouKaku? 4494 みよ: Javaでやってみました。 MacOS...(自然数の分割（別表現）)

Comment detail

Javaでやってみました。 MacOSX 10.5、2.5GHz PowerPC G5です。

java -Xmx256m Yang 50 > result 52.79s user 58.27s system 97% cpu 1:53.38 total

出力ルーチンが遅いようで列挙するだけの場合の処理時間は、

java -Xmx256m Yang 50 4.34s user 0.49s system 98% cpu 4.882 total

総数は、204226個でした。メモリの使用効率はもう少し考えないといけません...

import java.util.*;

public class Yang{

  ArrayList[] table;

  public Yang(int a){
    table = new ArrayList[a+1];
  }

  public ArrayList partitions(int value){
    ArrayList list = new ArrayList();
    ArrayList l0;
    l0 = new ArrayList();
    l0.add(new Integer(value));
    list.add(l0);
    for(int i = 1; i < value; i++){
      int v = value  - i;
      ArrayList l;
      if(table[i] != null){
     l = table[i];
      }else{
     l = partitions(i);
    table[i] = l;
      }
      Iterator it = l.iterator();
      while(it.hasNext()){
    l0 = (ArrayList)(it.next());
    if(((Integer)(l0.get(0))).intValue() <= v){
      ArrayList l1 = new ArrayList();
      l1.addAll(l0);
      l1.add(0, new Integer(v));
      list.add(l1);
    }
      }
    }
    return list;
  }

  public static void output(ArrayList list){
    Iterator it = list.iterator();
    while(it.hasNext()){
      int v = ((Integer)(it.next())).intValue();
      for(int i = 0; i < v; i++){
    System.out.print("□");
      }
      System.out.println();
    }
  }

  public static void main(String[] args){
    int a = Integer.parseInt(args[0]);
    Yang yang = new Yang(a);
    ArrayList l = yang.partitions(a);
    //System.err.println(l.size());
    Iterator it = l.iterator();
    while(it.hasNext()){
      output((ArrayList)(it.next()));
      System.out.println();
    }
  }

}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq