整数の分割というものに興味があり、自分で色々調べたいのですがプログラムが組めないのでどなたか

次の出力結果が得られるプログラムのソースを作ってください。
((1)だけではだめです。)

言語はCが望ましいですが、
WindowsXP上での実行の仕方がわかるサイトなどを教えてくだされば言語は何でもよいです。
出力はEXCELで取り込むことを考えています。

(1)任意の整数の分割(参考http://www.asahi-net.or.jp/~KC2H-MSM/excel/excel003.htm)を全て出力するプログラム。入力は1以上の整数とする。出力は以下のように大きい数字から並べる。
(例)入力:4 
   出力:4(Enter)3,1(Enter)2,2(Enter)2,1,1(Enter)1,1,1,1

(2)上記の分割のうち、次の(a),(b)2つの条件を満たす分割を全て出力するプログラム。
 (a)1から最大数(例えば3,1の場合3)までの全ての数を含む(つまり5,3,2,1等は出力しない)
 (b)1の個数≧2の個数≧・・・≧最大数の個数(つまり3,2,2,1等は出力しない)
(例)入力:9 
   出力:3,2,2,1,1(Enter)3,2,1,1,1,1(Enter)2,2,2,1,1,1(Enter)2,2,1,1,1,1,1(Enter),1,1,1,1,1,1,1(Enter)1,1,1,1,1,1,1,1,1

回答の条件
  • 1人10回まで
  • 登録:2006/12/31 20:49:13
  • 終了:2007/01/03 11:17:24

ベストアンサー

id:b-wind No.1

b-wind回答回数3344ベストアンサー獲得回数4402006/12/31 23:00:33

ポイント150pt

Perl で作りました。

Windows だと ActivePerl が使えます。

http://pocketstudio.jp/win/activeperl/

以下の内容をファイルに保存してください。(仮に part.pl とします)

#!perl

use strict;
use warnings;

while(<STDIN>) {
  chomp;
  my $x = int $_;
  for(my $i=1; $i<=$x; $i++) {
    my $result = partition_number($x,$i);
    my $combination_result = combination_result($result);
    $combination_result = term_result($combination_result) if @ARGV;
    print_result($combination_result);
  }
}

sub partition_number {
  my ( $n,$i ) = @_;
  my @result = ();
  if ( $n < $i ) {
  } elsif ( $i == 1 ) {
     push @result,[$n];
  } elsif( $n == $i ) {
     push @result, [(1) x $n];
  } else {
     for(my $j=1; $j<=$n &amp;&amp; $j<=$i; $j++ ) {
	 my @sub = @{partition_number($n-$j,$i-1)};
	 foreach ( @sub ) {
	    push @result , [$j,@{$_}];
	 }
     }
  }
  return \@result;
}

sub combination_result {
   my $result = shift;
   my %uniq = ();
   my @combination_result = ();
   foreach my $set ( @{$result} ) {
      my @combination = sort {$b<=>$a} @{$set};
      my $normalize = join ',',@combination;
      next if $uniq{$normalize}++;
      push @combination_result,\@combination;
   }
   return \@combination_result;
}

sub term_result {
   my $result = shift;
   my @term_result = ();
   TERM: foreach my $set ( @{$result} ) {
	my $max = (sort{ $b <=> $a } @{$set} )[0];
	my %term_count = ();
	$term_count{$_}++ for @{$set};
	my $check_count = 0;
	foreach my $term ( reverse 1..$max ) {
	   my $term_count =  $term_count{$term};
	   next TERM unless $term_count;
	   next TERM unless $check_count <= $term_count;
	   $check_count = $term_count;
	}
	push @term_result,$set;
   }
   return \@term_result;
}

sub print_result {
    my $result = shift;
    foreach my $set (@{$result}) {
	 print join(',',@{$set}),"\n";
    }
}


保存したディレクトリでコマンドプロンプトを開き、

perl part.pl

と実行すると入力待ちになり、入力するごとに1番の回答が、

perl part.pl 2

と後ろに何でもいいので文字列を付け加えると同じく入力するごとに2番の回答が出るようになっています。

id:kokudou

実行したところ、以下のようなエラーが出てしまいました。

Microsoft Windows XP [Version 5.1.2600]

(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\***>perl part.pl

Operator or semicolon missing before &amp at part.pl line 26.

Ambiguous use of & resolved as operator & at part.pl line 26.

Possible precedence problem on bitwise & operator at part.pl line 26.

syntax error at part.pl line 26, near "&"

Execution of part.pl aborted due to compilation errors.

対処法をお願いします。

2007/01/01 11:25:09

その他の回答(4件)

id:b-wind No.1

b-wind回答回数3344ベストアンサー獲得回数4402006/12/31 23:00:33ここでベストアンサー

ポイント150pt

Perl で作りました。

Windows だと ActivePerl が使えます。

http://pocketstudio.jp/win/activeperl/

以下の内容をファイルに保存してください。(仮に part.pl とします)

#!perl

use strict;
use warnings;

while(<STDIN>) {
  chomp;
  my $x = int $_;
  for(my $i=1; $i<=$x; $i++) {
    my $result = partition_number($x,$i);
    my $combination_result = combination_result($result);
    $combination_result = term_result($combination_result) if @ARGV;
    print_result($combination_result);
  }
}

sub partition_number {
  my ( $n,$i ) = @_;
  my @result = ();
  if ( $n < $i ) {
  } elsif ( $i == 1 ) {
     push @result,[$n];
  } elsif( $n == $i ) {
     push @result, [(1) x $n];
  } else {
     for(my $j=1; $j<=$n &amp;&amp; $j<=$i; $j++ ) {
	 my @sub = @{partition_number($n-$j,$i-1)};
	 foreach ( @sub ) {
	    push @result , [$j,@{$_}];
	 }
     }
  }
  return \@result;
}

sub combination_result {
   my $result = shift;
   my %uniq = ();
   my @combination_result = ();
   foreach my $set ( @{$result} ) {
      my @combination = sort {$b<=>$a} @{$set};
      my $normalize = join ',',@combination;
      next if $uniq{$normalize}++;
      push @combination_result,\@combination;
   }
   return \@combination_result;
}

sub term_result {
   my $result = shift;
   my @term_result = ();
   TERM: foreach my $set ( @{$result} ) {
	my $max = (sort{ $b <=> $a } @{$set} )[0];
	my %term_count = ();
	$term_count{$_}++ for @{$set};
	my $check_count = 0;
	foreach my $term ( reverse 1..$max ) {
	   my $term_count =  $term_count{$term};
	   next TERM unless $term_count;
	   next TERM unless $check_count <= $term_count;
	   $check_count = $term_count;
	}
	push @term_result,$set;
   }
   return \@term_result;
}

sub print_result {
    my $result = shift;
    foreach my $set (@{$result}) {
	 print join(',',@{$set}),"\n";
    }
}


保存したディレクトリでコマンドプロンプトを開き、

perl part.pl

と実行すると入力待ちになり、入力するごとに1番の回答が、

perl part.pl 2

と後ろに何でもいいので文字列を付け加えると同じく入力するごとに2番の回答が出るようになっています。

id:kokudou

実行したところ、以下のようなエラーが出てしまいました。

Microsoft Windows XP [Version 5.1.2600]

(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\***>perl part.pl

Operator or semicolon missing before &amp at part.pl line 26.

Ambiguous use of & resolved as operator & at part.pl line 26.

Possible precedence problem on bitwise & operator at part.pl line 26.

syntax error at part.pl line 26, near "&"

Execution of part.pl aborted due to compilation errors.

対処法をお願いします。

2007/01/01 11:25:09
id:koutaro_yuzuki No.2

koutaro_yuzuki回答回数580ベストアンサー獲得回数12006/12/31 22:48:59

3000ポイントいただければ私が作りましょう

ポイントが惜しければ自分で作りましょう

まずHello Worldから始めなさい

http://ja.wikipedia.org/wiki/Hello_world

id:kokudou

ちょっと3000ポイントは払えないです。

申し訳ありません。

2007/01/01 17:05:56
id:b-wind No.3

b-wind回答回数3344ベストアンサー獲得回数4402007/01/01 11:42:45

Operator or semicolon missing before &amp at part.pl line 26.

なんか変にエスケープされてますね。

26行目の&amp;を&に置き換えてください。

エスケープされないように全角で書いてますが、実際には半角です。

id:kokudou

実行できました。ありがとうございます。


ただ、3つほど追加で要望があります。


[A]入力が大きくなると全ての出力がコマンドプロンプト上で表示されないようなので、

(1),(2)とも出力結果を別ファイルに出力するようなプログラムに変更していただくようお願いします。


[B]出力の順序が想定していたものではないので、(1),(2)とも以下のように出力するよう作り変えてください。


つまり、(1)の場合

入力:7\

出力:7\6,1\5,2\5,1,1\4,3\4,2,1\4,1,1,1\3,3,1\3,2,2\3,2,1,1\3,1,1,1,1\2,2,2,1\2,2,1,1,1\2,1,1,1,1,1\1,1,1,1,1,1,1\ (注 \はEnterの意味)


というように最大数が大きい順(最大数が同じ場合は2番目に大きい数が大きい順、以下同じ)に並ぶようにしていただけないでしょうか。


[C]入力が大きくなると時間がかかり、出力数も膨大になってくるので

(1),(2)とも以下のように入力、出力を変更したバージョンも追加で作って頂けないでしょうか?


つまり、(1)の場合

入力:k m,n

出力:正の整数kの分割のうち、最大数がmからnまでの値であるような分割

(ここで、k≧m≧n. nを省略した場合、最大数がmから1までの分割を出力する)

というようなものです。入力の形式はある程度変えてもらってかまいません。


(1)の場合

(例1)

入力:7 5,3\

出力:5,2\5,1,1\4,3\4,2,1\4,1,1,1\3,3,1\3,2,2\3,2,1,1\3,1,1,1,1\


(例2)

入力:7 5\

出力:5,2\5,1,1\4,3\4,2,1\4,1,1,1\3,3,1\3,2,2\3,2,1,1\3,1,1,1,1\2,2,2,1\2,2,1,1,1\2,1,1,1,1,1\1,1,1,1,1,1,1\


[C]は[B]も兼ねることが出来ると思いますので、要は[A],[B],[C]を満たすプログラムを1つ作っていただきたいということになります。


少し面倒かもしれませんが、よろしくお願いします。

2007/01/01 15:53:06
id:b-wind No.4

b-wind回答回数3344ベストアンサー獲得回数4402007/01/01 15:49:44

コメントが出来ないので解答欄で失礼します。

[A] については

perl part.pl > part.csv

等として実行すればファイルに保存できます。


[B] に関しては出力を Excel 等で加工すればよいかと。


[C] に関しては当初の質問にはなく、だいぶ面倒なので遠慮させていただきます。

id:kokudou

わかりました。どうもありがとうございました。


今一度、出力結果を見てみたらプログラムに不備があるようです。可能であれば修正をお願いします。

例)入力が9の場合

上のプログラムを実行すると

6,3\5,4\4,4,1\3,3,3

が出力されない。


ちなみにコメント出来るように設定の変更をしておきました。


ただ、[B]に関してはEXCELで加工するのは面倒なので、引き続き[A],[B],[C]を満たすプログラムを募集します。

2007/01/01 17:45:04
id:b-wind No.5

b-wind回答回数3344ベストアンサー獲得回数4402007/01/01 23:59:33

今一度、出力結果を見てみたらプログラムに不備があるようです。可能であれば修正をお願いします。

なるほど、確認が甘かったようです。


26行目を

for(my $j=1; $j<=$n; $j++ ) {

に変更すれば大丈夫かと。

id:kokudou

ありがとうございました。直りました。

2007/01/03 11:11:54

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません