C言語関係掲示板

過去ログ

No805 正整数nの分割の個数をP(n,l)で表す再帰的プログラム

[戻る] [ホームページ]
No.10079

再帰的プログラム
投稿者---小心者(2003/10/27 03:14:16)


問題:nを任意の整数とし、正整数からなる組(a1,a2,...al)(ただし、l>=1)がnの分割であるとは、ai=n(i=1〜i=l)が成り立つときを言う。正整数nの分割の個数をP(n)で表す。さらに、lを組(a1,a2,....al)の長さと呼ぶ、正整数nの分割うち、長さがlであるものの個数をP(n,l)で表す再帰的プログラムを作成する。

のですが上手くいきません。
#include<stdio.h>
int F(int n, int l){
  int i,num=0;

  if(n==l)
    return 1;
  else if(n<l)
    return 0;
  else if(n>l)
    for(i=1;i<=l;i++){
 num = num + F(n-i,l);
    }
  return num;
}

int main(void){
  int n,l;
  do{
  printf("n;"); scanf("%d",&n);
  printf("l;"); scanf("%d",&l);
  }while(n<=0 && l<=1);

  printf("%d",F(n,l));
  return(0) ;
}



No.10081

Re:再帰的プログラム
投稿者---YuO(2003/10/27 08:39:28)


>問題:nを任意の整数とし、正整数からなる組(a1,a2,...al)(ただし、l>=1)がnの分割であるとは、
>Σai=n(i=1〜i=l)が成り立つときを言う。正整数nの分割の個数をP(n)で表す。
>さらに、lを組(a1,a2,....al)の長さと呼ぶ、
>正整数nの分割うち、長さがlであるものの個数をP(n,l)で表す再帰的プログラムを作成する。
>のですが上手くいきません。

非常に惜しいのですけどね……。
とりあえず,P(n, l)を再帰で表すことにします。

合計がnで長さがlの正整数の組み,当然P(n, l)個あります。
そのうち,末尾にi(ただし,1<=i<=l)を含む組が何個あるかを考えます。
末尾のiが固定されているのだから,合計はn-iで長さがl-1の正整数の組の個数に等しいですよね。
ということは,末尾がiの組はP(n - i, l - 1)個あることになります。
#↑ここを間違えたようです。

iは正整数かつ,合計がnで長さがlの正整数の組に含まれる数字ですから,
実際には先ほどより条件が厳しく,1<=i<=l-n+1となります。
#最大値は,i以外が全て1の場合の値。
そして,P(n, l)は全てのiについてのP(n - i, l - 1)の和ですから,
P(n, l) = Σ(iは1からl-n+1まで) P(n - i, l - 1)
となります。
#この部分はできているようです。

再帰自体もほとんど間違っていないようなので,
落ち着いてプログラムを見直せば,たぶん発見できたのではないかと思います。
#私はとりあえずF(3, 2)を手で追ってみました。


あと,nとlの入力での条件が間違っています。
do { /* ... */ } while (n <= 0 && l <= 1);

では,n > 0若しくはl > 1を満たすとループから外れます。
若干醜く感じるかもしれませんが,
do { /* ... */ } while (!(n > 0 && l < 1));

のように書いた方が間違いがないです。


No.10089

Re:再帰的プログラム
投稿者---かずま(2003/10/27 15:37:58)


> 正整数nの分割の個数をP(n)で表す。

> 正整数nの分割うち、長さがlであるものの個数をP(n,l)で表す再帰的
> プログラムを作成する。
C では、同じ名前の関数 P(n) と P(n,l) を書けないので、後者を
F(n,l) とするんですね。

具体例として、n = 4 のときを考えてみると、

F(4,1) = 1:  (4)
F(4,2) = 3:  (1,3)  (2,2)  (3,1)
F(4,3) = 3:  (1,1,2)  (1,2,1)  (2,1,1)
F(4,4) = 1:  (1,1,1,1)

P(4) = F(4,1) + F(4,2) + F(4,3) + F(4,4) = 8


#include <stdio.h>

int F(int n, int l)
{
    int i, k = 0;
    if (n == l || l == 1) return 1;
    for (i = n-l+1; i > 0; i--) k += F(n - i, l - 1);
    return k;
}

int main(void)
{
    int n, l;
    while (printf("n, l: "), scanf("%d%*c%d", &n, &l) == 2)
        if (l >= 1 && l <= n) printf("%d\n", F(n, l));
    return 0;
}
結局、F(n,l) は n-1Cl-1 ですね。

No.10101

Re:再帰的プログラム
投稿者---井川(2003/10/27 21:55:52)


>> while (printf("n, l: "), scanf("%d%*c%d", &n, &l) == 2)
if (l >= 1 && l <= n) printf("%d\n", F(n, l));
この部分がわかりません。

No.10110

Re:Re:再帰的プログラム
投稿者---ceybord(2003/10/28 00:15:59)


>>> while (printf("n, l: "), scanf("%d%*c%d", &n, &l) == 2)
> if (l >= 1 && l <= n) printf("%d\n", F(n, l));
>この部分がわかりません。

私が代わりに説明します。
この部分は
printf("n, l: ");
while(scanf("%d%*c%d", &n ,&l)==2){
        if(l>=1&&l<=n){
                printf("%d\n", F(n, l));
        }
        printf("n, l: ");
}

と書いても同じです。scanfに%*cが混じっていますが、
scanfに文字型変数を使う場合は%cよりも%*cの方がいいのです。

No.10113

Re:Re:再帰的プログラム
投稿者---井川(2003/10/28 01:28:22)


>>scanf("%d%*c%d", &n ,&l)==2

ここが特にわかりません。


No.10119

Re:Re:再帰的プログラム
投稿者---かずま(2003/10/28 11:33:10)


> scanfに%*cが混じっていますが、
> scanfに文字型変数を使う場合は%cよりも%*cの方がいいのです。
意味不明です。
scanf("%d%*c%d", &n, &l) には文字型変数は使われていません。

"%c" は 1文字読み込みです。
"%*c" は 1文字読み飛ばしです。

printf("n, l: "); という入力要求に対して、

4 3  と入力しても  4,3  と入力してもかまわないように
"%*c" で 5 の次の 1文字を読み飛ばしています。


No.10124

Re:Re:Re:再帰的プログラム
投稿者---ceybord(2003/10/28 17:41:51)


どうも説明のしかたを考えているうちにわけ分からなくなってしまったようです。
メインページの説明と混同してしまったようです。

No.10129

Re:Re:再帰的プログラム
投稿者---かずま(2003/10/28 18:33:35)


> 4 3  と入力しても  4,3  と入力してもかまわないように
> "%*c" で 5 の次の 1文字を読み飛ばしています。

訂正です。

 "%*c" で 4 の次の 1文字を読み飛ばしています。