異なるn個の整数からr個の整数を取り出す組み合わせ

質問

異なるn個の整数からr個の整数を取り出す組み合わせの数
nCrを求める関数
int combination(int n, int r){ /* ・・・ */}
を作成せよ。なおnCrは以下のように定義される。

nCr = n-1Cr-1 + n-1Cr (ただし nC0 = nCn =1、nC1 =n )

(新版 明解C言語　入門編(柴田望洋　著) P.197　演習8-6)

というので答えが

int combination(int n, int r)
{

if((n>r) && (r>0)){
return combination(n-1,r-1) + combination(n-1,r);
}
else if(n==r || r==0){

return 1;
}
}

・という風になると教えてもらったのですがなぜこうなるのかが分かりません。
・else if(n==r || r==0){ というのは削っても正常に動きますが、必要な物なのでしょうか？

・またifを使うときは
if→eise if →else　の順に使って
２つの時は if→else　と使っていたのですが
上のものはif→else ifと書いています。
加えてelse(n==r || r==0){　と書いたらコンパイルエラーになってしまいました
なぜelse ifと書くのでしょうか？

以上３点について教えてください。よろしくお願いいたします。

回答No.5

dennou2000 · ベストアンサー

＞・という風になると教えてもらったのですがなぜこうなるのかが分かりません。

もしかすると、再帰呼び出しという概念がわかっていませんか？
再帰呼び出しというのは、関数がその処理の中で自己の呼び出しを行なう事です。

ところで、
nCr = n-1Cr-1 + n-1Cr (ただし nC0 = nCn =1、nC1 =n ) ・・定義Ａ
と定義されるということは
右辺式の、n-1Cr-1 と n-1Crを求めるのに定義Ａを用なければならないという事です。
そのため、n-1Cr-1 と n-1Crを求める右辺式にもxCyがでてきます。
これが、r=0でnC0か、n=rでnCnになって固定値(=1)になるまで、続きます。

ソースプログラムを見ると、
int combination(int n, int r)
{
　　if((n>r) && (r>0)){
　　　　return combination(n-1,r-1) + combination(n-1,r);　　/* ※ */
　　}
　　else if(n==r || r==0){
　　　　return 1;
　　}
}

1)combination関数は、パラメータｎとｒからnCrを求める関数である。
2)nCrを求めるためには、n-1Cr-1とn-1Crを求める必要がある。
　この二つを求めるために、※の箇所でcombination関数自体をを呼び出している。
3)※で呼び足された二つのcombination関数はそれぞれのパラメータに従い、
　また、combination関数を呼び出す。
4)3)の呼び出しの繰返しは、combination(n-1,r)のr以外は１づつ減っていくので
　(n>r) && (r>0)が成立しないところまで継続する。
　(n>r) && (r>0)が成立しないところまで達すると、combination関数は１を返し
　その結果を持って、3)の呼び出し関係を遡って最初のcombination関数の呼び出し
　まで返って答えをだす。

という事です。

＞・else if(n==r || r==0){ というのは削っても正常に動きますが、
＞必要な物なのでしょうか？

else if(n==r || r==0){　を削るというのは

　　else if(n==r || r==0){
　　　　return 1;
　　}

全体をを削ってますか、それとも

　　else {
　　　　return 1;
　　}

と条件だけを削ってますか？

後者であればこの例題については問題ないと思います。

それは、elseだけにすると、(n>r) && (r>0)　の成立しない(条件が逆）時に、else節に
入ります。
else節に入る時は、(n>r) && (r>0)　が成立しない時 ＝ (n<=r) || (r<=0)　の時なので
削った条件　(n==r || r==0)　を含んでいるからです。

前者であると、(n>r) && (r>0)が成立しなくなった時、combination関数の呼び出しは
止まり、返す値が不定になり、なにが返るかわかりません。その結果計算結果がおかしく
なると思います。
（コンパイラの仕様としてなにか固定値を返すコードを生成していればその値に従った
　計算結果になります。）

＞・またifを使うときは
＞if→eise if →else　の順に使って
＞２つの時は if→else　と使っていたのですが
＞上のものはif→else ifと書いています。
＞加えてelse(n==r || r==0){　と書いたらコンパイルエラーになってしまいました
＞なぜelse ifと書くのでしょうか？

これは、Ｃ言語の文法がそういうもの「elseにはif無しに条件は書けない」からとしか
お答えできません。

回答No.4

nerosuke

int combination(int n, int r)
{

if((n>r) && (r>0)){ //nがrより大きくてrが0よりも大きい場合はこの条件
return combination(n-1,r-1) + combination(n-1,r);
}
else if(n==r || r==0){ //上記の条件に当てはまらずnが0かrが0ならこの条件
return 1;
}
else //上記の全ての条件に当てはまらなかったらこの条件 //必要ありませんがelse ifを使用した場合私は明示的にelseを必ずつけます。
{
return 0;
}

}

else ifはif(…)の条件が多分岐の時使用しますので、こういう文法だとして覚えてしまった方が良いかと思います。

>>else if(n==r || r==0){ というのは削っても正常に動きますが、必要な物なのでしょうか？
削っても動きます。
しかし、上記しましたが、if((n>r) && (r>0))の条件に当てはまらない時に戻り値が定まりません。
まず0が戻り値で返ってくると思いますので試しに削ったプログラムでnかrの値を0にして見ましょう。

>>２つの時は if→else　と使っていたのですが
条件が一つの場合は問題ないと思います。
elseifは条件が多条件である時に使用します。
No3さんが回答していますとおり、基本的にはif とelseの組み合わせです。
しかしelseifは一般的ですし、文法として覚える事をお勧めします。

>>else(n==r || r==0){

No1さんが回答している通りelseに条件式つけられませんので文法エラーです。

回答No.3

BLUEPIXY

>・またifを使うときは
if(…){
} else {
　if(…){
　} else {
　}
}
と書いても
if(…){
} else if(…){
} else {
}
と書いても
if(…){
} else
　if(…){
　} else {
　}
と書いても同じです。
要はelse の内容がが文 かブロックかということですね。
あと、Ｃ言語では、どこで改行するかとかインデントとしてスペースがあるとか 意味的に区切り以上の意味のないホワイトスペース文字は結局無視されますので、人間が読む見た目以上の意味はないです。

回答No.2

Werner

> ・else if(n==r || r==0){ というのは削っても正常に動きますが、必要な物なのでしょうか？
削っても正しく動くのは、この関数を正しく使っている限り、
どちらかの条件が必ず満たされるからでしょうね。

int combination(int n, int r)
{
　　if((n>r) && (r>0)){
　　　　return combination(n-1,r-1) + combination(n-1,r);
　　}
　　else if(n==r || r==0){
　　　　return 1;
　　}
　　else{　　/* n<r || r<0 の時ここに来る*/
　　　　exit(1); /*正しく使用していればここは実行されない。*/
　　}
}

回答No.1

suzukikun

＞・という風になると教えてもらったのですがなぜこうなるのかが分かりません。
これを聞いたらどうしようもない気がしますが、定義通りに関数を作っていますよね。もう一度ゆっくり追いかけてください。

＞・else if(n==r || r==0){ というのは削っても正常に動きますが、必要な物なのでしょうか？
本当ですか？無限ループとかスタックオーバーフローとかになりませんか？

＞なぜelse ifと書くのでしょうか？
else節の後ろに条件式は書けないからです。だからコンパイルエラーになったのです。