C言語関係掲示板

過去ログ

No.914 正の整数nの和に表現する方法が何通りあるか

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

失礼します。
投稿者---☆(2004/01/09 14:19:41)


学校の課題なんですが、
正の整数nを与えるとそれを正の整数の和に表現する方法が何通りあるかを答えるプログラムで
1+1+1+5
1+1+5+1
1+5+1+1
5+1+1+1
はすべて同じとして数えます。
5と入力すると
7と出力されるのですが(7通り、0+5,1+4,2+3,1+2+2,1+1+2,1+1+1+1+1)
どうやったらいいのか方針が立てられず…。
教えてください。よろしくお願いします。

<pre>
#include<stdio.h>

int count(int n){
int i; //カウントした数
/*

この部分です。

*/
return i;
}


int main(){
int n,ans;
while(1){
scanf("%d",&n); //標準入力からnを読み込む
if(n==0) break; //0なら終了
else if(n&gt;0){ //正の整数ならば
ans=count(n); //count関数に代入
printf("%d\n",&ans); //標準出力に出力
}

}
}

</pre>




No.11601

Re:失礼します。
投稿者---宿題はまかせろ!(2004/01/09 18:11:40)


うまくインデントされたないので修正

#include <iostream>

int main(int argc, char* argv[])
{
   for(int i=0; i<10; i++){
      int nInput = i;
      int nBase  = 0;
      int nCalc  = 0;
      int nAns   = 1;
      while(nBase++, (nCalc=nBase*2)<=nInput){
        nAns += nInput - nCalc+1;
      }
      std::cout << i << "は多分" << nAns << "通りじゃね?" << std::endl;
   }
   return 0;
}




No.11602

Re:失礼します。
投稿者---たいちう(2004/01/09 18:13:35)


とりあえず0+5は正の整数の和とは言わないのでは?
1+1+1+2も抜けているし。

プログラムは再帰が良いでしょう。

No.11603

Re:失礼します。
投稿者---ひっこしさかい(2004/01/09 18:36:14)


>7と出力されるのですが(7通り、0+5,1+4,2+3,1+2+2,1+1+2,1+1+1+1+1)

0+5
0は正の整数ではないのですが?
例では6通りしか示してないし、
(この例って課題で示されたの?でしたら
課題自体が不完全です。出した先生に質問が必要)
どういったルールなのでしょう?

まぁ例は無視して、組合せを考えると

4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1

どう考えても6通りしかないようです。

答えはnがあたえられて
nが偶数のとき (n*n)/4
nが奇数のとき (n*n-1)/4
を計算して出力したらいいでしょう。
なぜそうなるかは自分で調べること。
ってどこかの掲示板に投稿することではないよ。
自分の頭で考える。
でも答えだけが出る計算ですので課題の回答としては
NGだと思われます。

課題の回答としては考え方が盛り込まれた物がいい
でしょう。
ヒントは、
nの組合せの数は
(1) 2つの項の和としての個数
(2) 3個以上の項の和:(n-1)の組合せの数
    −>(n-1)の組合せと1の和の組合せのこと
の和になるから。


たとえばn=5のときは
(1)は
1+4
3+2 の2通り
(2)は
n=4の数

n=4の数は
(1)
1+3
2+2 の2通り
(2)
n=3の数

として再帰的に求めていきます。
必然でn=1のときは組合せ0
n=2のときは組合せ1となっているのが前提です。

(1)は整数だけの世界の演算で
nを使って簡単にあらわせることがわかるとおもいます。


No.11620

Re:失礼します。
投稿者---たいちう(2004/01/10 17:03:51)


> 答えはnがあたえられて
> nが偶数のとき (n*n)/4
> nが奇数のとき (n*n-1)/4
> を計算して出力したらいいでしょう。

1 : 6 = 1 + 1 + 1 + 1 + 1 + 1
2 : 6 = 1 + 1 + 1 + 1 + 2
3 : 6 = 1 + 1 + 1 + 3
4 : 6 = 1 + 1 + 2 + 2
5 : 6 = 1 + 1 + 4
6 : 6 = 1 + 2 + 3
7 : 6 = 1 + 5
8 : 6 = 2 + 2 + 2
9 : 6 = 2 + 4
10 : 6 = 3 + 3

とりあえずn=6のときに成り立ちませんが。それ以降も。
NykRさんのソースでも同じ結果です。

No.11669

Re:失礼します。
投稿者---ひっこしさかい(2004/01/11 19:16:37)


> 8 : 6 = 2 + 2 + 2

うひゃ。確かのこのパタンはありですね。
たいちうさんサンキュです。
結構難しい問題ですね。
誤解答法示してすみませんです。>関係者


No.11605

Re:失礼します。
投稿者---NykR(2004/01/09 19:23:33)


答えではありませんが参考までに。

#include <stdio.h>
#include <stdlib.h>

static void comb_sub(int *array, int sum, int min, int idx)
{
    int i;

    if (sum == 0) {
        putchar('[');
        for (i = 0; i < idx; i++) printf("%d,", array[i]);
        printf("\b]");

        if (i == 1) return;
        putchar(',');
        return;
    }

    for (i = min; i <= sum; i++) {
        array[idx] = i;
        comb_sub(array, sum - i, i, idx + 1);
    }
}

void comb(int sum)
{
    int *array = malloc(sizeof(int) * sum);
    if (array == NULL) perror("malloc"),exit(1);

    printf("[");
    if (sum > 0) comb_sub(array, sum, 1, 0);
    puts("]");

    free(array);
}

int main(void)
{
    int i;

    while (scanf("%d", &i) == 1) comb(i);
    return 0;
}


No.11748

Re:失礼します。
投稿者---namani(2004/01/14 15:32:44)


どこにレスしていいかわかんないですが(−−
分割数の問題なのですね
下のページの説明を参考にして書いてみました
理論はそこに書いてあるとおりです
http://www.asahi-net.or.jp/~KC2H-MSM/excel/excel003.htm

以下ソース
--
#include <stdio.h>
int count_r(int,int);

/* nが何個に分割できるか調べる */
int count(int num)
{
    int pattern = 0,i;
    /* 1個に分割からn個に分割までの和を返す */
    for( i=1;i<num+1;i++)
        pattern += count_r(num,i);
    return pattern;
}

/* 数値nをr個に分割 */
int count_r(int n,int r)
{
    /* nをn個に分割、またはnを1個に分割 → 1 */
    if( n == r || r == 1 )
        return 1;
    /* 分割数の方が多い時は0を返す */
    if( n < r )
        return 0;
    /* それ以外は再帰呼び出し */
    return (count_r(n-r,r) + count_r(n-1,r-1));
}

int main()
{
    printf("%d\n",count(5));
    return 0;
}

--
関数名は気分ですので、おかしかったら変えてください
これで5のとき7パターンとかえってくるはずです
5+0は5を1個に分割したときの個数のようですね
main関数内はてきとーなのでてきとーに変えてください・・・

No.11749

Re:失礼します。
投稿者---☆(2004/01/14 16:16:04)


たくさんのレスありがとうございました。
そして、言葉の説明が足りなくて申し訳ありません。

解決しました!
感謝です。

No.11750

Re:失礼します。
投稿者---かずま(2004/01/14 16:18:41)


> これで5のとき7パターンとかえってくるはずです
> 5+0は5を1個に分割したときの個数のようですね
> main関数内はてきとーなのでてきとーに変えてください・・・

その仕様で、こんな風に書いてみました。
/* count(): 整数 n を「m 以上の整数」の和に分割した個数を返す */

int count(int n, int m)
{
    int i, c = 0;
    if (n == 0) return 1;
    for (i = m; i <= n; i++) c += count(n-i, i);
    return c;
}

int main(void)
{
    int i;
    for (i = 1; i <= 10; i++) printf("%2d: %d\n", i, count(i, 1));
    return 0;
}