人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

整数の分割というものに興味があり、自分で色々調べたいのですがプログラムが組めないのでどなたか
次の出力結果が得られるプログラムのソースを作ってください。
((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

●質問者: kokudou
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:Excel WindowsXP サイト ソース プログラム
○ 状態 :終了
└ 回答数 : 5/5件

▽最新の回答へ

1 ● b-wind
●150ポイント ベストアンサー

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番の回答が出るようになっています。

◎質問者からの返答

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

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.

対処法をお願いします。


2 ● koutaro_yuzuki
●0ポイント

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

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

まずHello Worldから始めなさい

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

◎質問者からの返答

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

申し訳ありません。


3 ● b-wind
●0ポイント

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

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

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

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

◎質問者からの返答

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


ただ、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つ作っていただきたいということになります。


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


4 ● b-wind
●0ポイント

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

[A] については

perl part.pl > part.csv

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


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


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

◎質問者からの返答

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


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

例)入力が9の場合

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

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

が出力されない。


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


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


5 ● b-wind
●0ポイント

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

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


26行目を

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

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

◎質問者からの返答

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ