組み合わせ

[キリコ]

再びすみません。
再起呼び出しのnCr(rの値は適当）からn!を求めるプログラムなんですが、難しいらしいのですが、どういったプログラムになるのでしょうか？よかったら教えてください。お願いします。
今のところ前回の複素数はほぼできあがりそうで今回のこれはまだ検討中です。

[管理人]

キリコさん、こんにちは。
以前の問題は順調に進んでらっしゃるようで、よかったです。

組み合わせの問題は「再帰関数」で計算できます。

組み合わせ　再帰関数

などをキーワードで検索すると解決できるはずですよ。

再帰関数をご存知なかったらクイックソートの紹介ページをみてみてください。

再帰関数は難しくなく、逆にすごく「処理を書くのが簡単」です。

再帰関数のプログラムは数学の「一般式通りに書けばいい」という特徴をもっており、なれると非常に便利です。

しかし結構特殊な書き方になるので、慣れるまで書き方がよくわからないと思います。

多くの場合「処理がどのように行われているのか目でおえない」状況になります。

普段端から端まで処理をおいかけながらプログラムを組んでいる人にとってはかなり考え方を改めてみる必要があるので、慣れるまで少し大変かもしれませんが、

一度クイックソート解説アプリを使っていただけたら解るのではないかと思います。

調べてもわからなかったり、つまづいたらまた聞いてください。

[管理人]

組み合わせは別に再帰関数じゃないと計算できないわけではありません。
それに再帰関数は無駄な処理が多く、簡単に実装できるという利点はありますが、
処理に無駄があるため、あまり勧められない点もあります。

しかし一応勉強しておくべき分野です。
もし再帰で求めないのならばまず、数式を書いてみましょう。

m * (m-1) * .. * (m-n+1)
	c(m,n) = --------------------------
		  1 *   2   * .. *   n

ですね。
分母はmからm-n+1までかけあわせ、分子は1からnまでかけあわせ計算すればいいだけです。
for文で簡単に計算できますね。
再帰よりこちらの計算方法の方がずっと早いです。

[管理人]

プログラムの予測は立ちましたか？

scanfでmＣnのmとnを読み取ります。

m * (m-1) * .. * (m-n+1)
	c(m,n) = --------------------------
		  1 *   2   * .. *   n

この理論で、iをmからm-n+1までデクリメントしながらループさせ、全てかけあわせた値をbunsiに格納します。

for(int i=m;i>=m-n+1;i--)
		bunsi *= i;

同様にiを1からnまでインクリメントしながらループさせ、全て掛け合わせた値をbunboに格納します。

for(int i=1;i<=n;i++)
		bunbo *= i;

たったそれだけで終わりです。簡単ですね？

完成品サンプルはこちら

#include <stdio.h>
int main(){
	int m,n,bunbo=1,bunsi=1;
	scanf("%d%d",&m,&n);
	for(int i=m;i>=m-n+1;i--)
		bunsi *= i;
	for(int i=1;i<=n;i++)
		bunbo *= i;
	printf("%dＣ%d = %d\n",m,n,bunsi/bunbo);
	return 0;
}

再帰のやり方も勉強してみてください。

[キリコ]

管理人さん返信ありがとうございます。
私の説明が悪かったようですみません。nCrを求めるプログラムはなんとかわかるのですが、nCr(rの値は適当）からn!を求めるプログラムがどうも思いうかばないのです。これはどうにもお手上げです。

[管理人]

すみません、私は文章の最初だけみて意味を理解しようとするくせがあるのでよく誤読してしまいます；

nCrから求めるという意味がよくわかりません。

nCrの答えから求めるのですか？

nCrのアルゴリズムを使って求めるのですか？

いずれにしても出来ないように思います‥。

#include <stdio.h>

int comb( int m, int n ){
	if( m>n  && n>0 )
		return	comb(m-1,n-1) + comb(m-1,n);
	else
		return	1;
}

int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%dＣ%d = %d\n",m,n,comb(m,n));
	return 0;
}

組み合わせを求めるプログラムはこうですね。
一方階乗を計算するプログラムはこうなので

#include <stdio.h>

int	comb( int n ){
	if(n>0 )
		return n*comb(n-1);
	else 
		return	1;
}

int main(){
	int n;
	scanf("%d",&n);
	printf("%d\n",comb(n));
	return 0;
}

別物になると思います。
同じ再帰でプログラムをかけという課題なのならわかるのですが。。

[キリコ]

nCrの値（ｒは適当）ｎ！を求めるアルゴリズム　を求めるみたいです。

[管理人]

すみません、意味がわかりません・・・。

nCrとn!の値は同じものだと解釈されてらっしゃるのでしょうか？

nCrの値の計算のしかたは上の式のとおりです。

例えば

4C2なら 4*3 / 2*1 ですから6ですね？
4!は 4*3*2*1=24です。

4C2から4!を求める・・というのが意味がよくわかりません。

もう少し問題文をよく読んでみてください。

私の誤解釈でしたらお許しください。

[管理人]

nCrを求めるプログラムもn!を求めるプログラムもすでに上で紹介したのでご覧ください。

[キリコ]

すみません間違いました。
nCrの値（ｒは適当）から、ｎ！を求めるアルゴリズム　を求めるみたいです。

[管理人]

すみません、考えても意味がよくわからないのです・・・。

nは同じnですよね？

先ほども言いましたが、

4C2なら 4*3 / 2*1 ですから6ですね？
4!は 4*3*2*1=24です。

つまり値からn!を求めるということは6から24を導けということでしょうか。
rの値を1からnまで１つずつ増やしてその値をかけていけばn!になりますが、

rの値は適当な値で何が入るかわからないとすると、推測のしようがありません・・。

適当というニュアンスが、1からnまで変化させていっていいというのならわかりますが、
それでは何の意味ももたないプログラムになってしまいます。

再帰を使う必要もありませんし、組み合わせのプログラムを使う必要もありません・・。

[Justy]

　まさかとは思いますが、こういうことだったり・・・。

　　n! = nCr * r! * (n - r)!

　これなら、 nCrを元にして幾つか計算するだけで、n!が求まります・・・。

[キリコ]

＜すみません、考えても意味がよくわからないのです・・・。
申し訳ないです。


ｒは自分で適当に決めていいということだと思います。
この問題の前でｎ！からｎＣｒを求める再帰関数呼び出しでプログラムをしたので、その逆のｎＣｒからn！を求めることをするのだと思います。


＜6から24を導けということでしょうか
多分そういうことだと思います。

ｒ＝５のを作ろうすると、
「ｎＣ５からｎ！をもとめるプログラム」を作ればいいと思います。

[管理人]

＞この問題の前でｎ！からｎＣｒを求める再帰関数呼び出しでプログラムをしたので

え？どうやったらそんな事出来るんですか？

[キリコ]

つまりｒは定数としていいことです。

値aを入力。
a*5!=n!/(n-5)!
ここからどうn!を求めたらいいのか、やっぱりちょっと見当つかないですね。

[キリコ]

ｎ！からというか、さきほど管理人さんが示されたように、関数である値のｎ！をもとめて、ｎＣｒをもとめただけです。

[管理人]

＞＞6から24を導けということでしょうか
＞多分そういうことだと思います。

6から24はもとまらないですよ～；
Justyさんのおっしゃるように計算するのなら求まりますが、そんなことして意味があるんでしょうか・・。

＞r＝５のを作ろうすると、
＞「ｎＣ５からｎ！をもとめるプログラム」を作ればいいと思います。

とりあえず、紙とペンで計算してみましょうよ。

nが7、r=5だとすると7C5は　7*6 / 2 = 21ですよね？そこから7!を求めて意味があるんでしょうか？
また、求まるとは思えません・・。「値から求める」というからには数字そのものから推測しろという意味ですよね。
とても21という数字をみて7の階乗が計算できるとは思えません・・。

しかし、話の流れから行くと、作った組み合わせの再帰関数の中で計算に手を加えて違う結果を出そうとしている趣旨に聞こえます。

う～ん、こんなやり取りをいつまでもしていても質問者さんも困ってしまうと思うので

一応あってそうな答えを推測して作ってみます。

[管理人]

とりあえず私の100倍問題の要旨理解の正しいJustyさんのおっしゃる通りに実装してみました。

困ったときはJustyさんのおっしゃる通りにやれば正解だろうというのが勝手な持論です(笑


n! = nCr * r! * (n - r)!

という式の通り計算しています。

ものすごい無駄な意味の無い計算に思います・・。

combは階乗を計算する関数でcomb2は組み合わせを計算する関数です。

#include <stdio.h>

int comb( int n ){
	if(n>0 )
		return n*comb(n-1);
	else 
		return	1;
}

int comb2( int m, int n ){
	if( m>n  && n>0 )
		return	comb2(m-1,n-1) + comb2(m-1,n);
	else
		return	1;
}

int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%d\n",comb2(m,n)*comb(n)*comb(m-n));
	return 0;
}

先ほど紹介したプログラムと同じです。

[Justy]

＞困ったときはJustyさんのおっしゃる通りにやれば正解だろうというのが勝手な持論です(笑
　いやいや、今回はかなり半信半疑です（ｗ
　どちらかと言えば管理人さんの推測通り「nCrの再帰計算に手を加えて n!を計算する関数を作成する」方だと思っていますが。

　でもひょっとすると数学的に何か凄い公式があったりするのかもしれません。

[管理人]

色々考えてみたものの、やはりわからない・・・。
値から計算するのは論外でしょうし、Justyさんのおっしゃる計算で、似たような計算で階乗を求める方法以外に思いつきません。

他に思い当たる計算はまるでnをかけてその後nで割るような計算になってしまいます・・。

あきらかに意味の無いプログラムになってしまいますが、結局再帰関数をいじくることで勉強になっただろっていう結論なのなら
無理やりうなずくことも出来るかも・・。

[キリコ]

Justyさん、管理人さんどうもありがとうございます。
たしかに私もこの問題は微妙だとおもいます。
私の遥か上にいるお二人のおっしゃるこれで多分あっているでしょう。
今日実行してみます。

[管理人]

なんかだらだらした回答になってしまってごめんなさいね。
頑張ってください☆

[フリオ]

　
　わかりました。
きっと、スターリング数のことではないでしょうか。
http://homepage2.nifty.com/PAF00305/mat ... ation.html

#include<stdio.h>

int Combi(int n, int r)
{
	if(n < r) return 0;
	if(n == r || r == 0) return 1;
	return Combi(n - 1, r) + Combi(n - 1, r - 1);
}

int Stiring(int n, int r)
{
	if(n == r) return 1;
	if(n < r || r == 0) return 0;
	return (n - 1) * Stiring(n - 1, r) + Stiring(n - 1, r - 1);
}

int Fact(int n)
{
	int sum, r;
	
	for(sum = r = 0; r <= n; r ++) sum += Stiring(n, r);
	return sum;
}

int Fact0(int n)
{
	if(!n) return 1;
	return n * Fact0(n - 1);
}

int main()
{
	int n = 10, r = 3;
	
	printf("n == %d, r == %d\n", n, r); 
	printf("C(n, r) == %d\n", Combi(n, r));
	printf("S(n, r) == %d(Stiring Number)\n", Stiring(n, r));
	printf("     n! == %d(by Stiring Number)\n", Fact(n));
	printf("     n! == %d\n", Fact0(n));
	return 0;
}

[管理人]

へ～ヤング図形ですかぁ。テトリスみたいですねｗ

ベル数とかスターリング数とか知らない言葉ばかりで…。

勉強になりました＾＾；