分割数の表示

Python Perl Programming

数学ガールを読んだら分割数というものがのっていたのでそれを表示するためのプログラム。
まずはじめに作ったのがこれです。

#!/usr/bin/env perl
use strict;
use warnings;

sub min{
	my($x,$y) = (@_);
	if($x > $y){
		return $y;
	}else{
		return $x;
	}
}

my $count = 0;
my $space = 0; #スペース（タブ）を出力したかどうか

sub pertitionNum{
	my($i,$n,$sum,$num) = (@_);
	#$n:今までに出力した数字の数　$sum:今までの合計
	if($sum >= $num){
		$count++;
		$space = 0;
		print "\n"; 
		return;
	}

	for(;$i > 0;$i--){
		next if($sum + $i > $num);
		if($space == 0){
			print "\t" x (2*$n);
			$space = 1;
		}
		print $sum == 0 ? "\r\t=\t" : "\t+\t";
		print $i;
		&pertitionNum(min($num-$i,$i),$n+1,$sum + $i,$num);
	}
}

print "num: ";
chomp(my $num = <STDIN>);
print "\n$num";
&pertitionNum($num,0,0,$num);
print "\ncount: $count\n";


再帰で余裕でしょって思いましたが表示にてこずりました。とりあえず\rを使うことで解決。min()は高速化のためです（ない方がはやかったりして）。これを実行するとこんな感じです。

5 = 5
  = 4 + 1
  = 3 + 2
  =   + 1 + 1
  = 2 + 2 + 1
  = 2 + 1 + 1 + 1
  = 1 + 1 + 1 + 1 + 1

count: 7

再帰で実行しているので当たり前ですが、４行目は完全に表示させることができません。それに同じ数字の繰り返しをn*iみたいに表すこともできません。ということで配列を使うように書き直しました(python勉強中なのでpythonで）。

#!/usr/bin/env python

def printnum(x):
    plus = False
    print "\t",
    for i in xrange(len(x)-1,0,-1):
        if x[i] > 0:
            if plus: print "+",
            else: plus = True

            if x[i] > 1: print str(i) + "x" + str(x[i]),
            else: print i,
    print 


def partitionNum(i,sum,num):
    global count
    if sum >= num:
        count += 1
        printnum(x)
        return

    for i in xrange(i,0,-1):
        if sum + i > num : continue 
        x[i] += 1
        dividednum(i,sum+i,num)
        x[i] -= 1


if __name__ == "__main__":
    count = 0
    num = int(raw_input('num: '))
    x = [0]*(num+1)
    if num > 0 :print num,"=",
    partitionNum(num,0,num)
    print "count:",count

これを実行するとこんな感じです。

5 = 5
  = 4 + 1
  = 3 + 2
  = 3 + 1x2
  = 2x2 + 1
  = 2 + 1x3
  = 1x5
count: 7

min()はいらないような気がしたので削除。こっちの方がさっきより全然いいですね。


「考えて分からなかったら手を使ってプログラムで解くしかないでしょ」