Re: 分解數求法

[cying (應)]

※ 引述《[e-mail] (有矜持的少…)》之銘言：
:        就我啦~~
:        人家不會了!!!
:     各位帥哥哥!!
:       救救我:
:   請問要如何計算
:   一個數的分解數(整數)
:     如 5=4+1
:         =3+2
:         =3+1+1
:         =2+2+1
:         =2+1+1+1
:         =1+1+1+1+1 (共六種)
:     謝謝啦!!
/*
  To solve the problem, we need to define a function as follows:

  f(x, L) = number of combination to divide the given integer x with
            only number less than or equal the given integer L could
            be used to divide x.

  So if we wish to obtain number of division methods of '5', we should
  calculate the value of f(5, 4).

  One might ask: why is the second parameter is needed? Can't we only
  write the function as f(x) instead of f(x, L)? The answer is negative.
  Because we're calculating number of combinations, instead of
  "permutation". So that same elements with different order should be
  avoided. For the example of "5", we might not expect to get a
  combination of "5 = 2+1+2", which should be the same as
  "5 = 2+2+1". Clearly, we want the sequence to be "sorted" sequence.
  Therefore, we need to define another parameter L to restrict the
  element selection.

  For a given x and L, we could use recursive method to obtain the
  following relation:

  f(x, L) = f(x-1, 1) +
            f(x-2, 2) +
            f(x-3, 3) +
            .
            .
            .
            f(x-L, L)

  In alternating form:

  f(x, L) = sum(f(x-k,k), where 1<=k<=L)

  Note that when we write f(x, L) = f(x-1, 1) + ..., we mean that
  the number of division mehtods of f(x, L) is the summation of
  number of division method that we choose to take "1" out of x and
  number of division method that we choose to take "2" out of x and
  so on. Of course, if we take "1" out of x, then x will be subtracted
  by 1 in the subsequent calculation. So we write f(x-1, 1). Here
  L equals 1 because we don't want to meet subsequent calculation that
  take integers more than 1 or duplicates will result as described
  above.

  Clearly, L must be less than or equal to x, or we will be asked to
  calculate some f(-3, -5) which, in the sense, is not meaningful.

  Knowing the formula above, there's still something missing: the
  terminal condition.

  Consider one condition: if we only have "0" to divide, we won't
  have any choice which means the only choice is to choose "0" and
  therefore f(0, k) = 1, where k is any integer.

  Using the induction above, we could write a simple C++ function as
  follows:

  int f(int x, int L)
  {
    if (x == 0)
      return 1;
    int k;
    int result = 0;
    for(k=1;k<=L;k++)
      if (k <= x)
        result += f(x-k, k); // sum up these recursively collected values
    return result;
  }

  But if we only write program as above, the efficiency will be low.
  Because redundant calculation will be performed resulting in low speed.
  So that we might want to "remember" what we have calculated.

  The full source code is therefore produced using "recursive remembrance"

  (article and source code written by Cherng-yann Ing. All rights reserved)

*/

#include <iostream.h>

#define MaxValues 50
#define MaxLastSelect 50

int funcValues[MaxValues][MaxLastSelect];

int getDivCount(int value, int lastSelect)
{
        int result = funcValues[value][lastSelect];
        if (result == 0)
        {
                if (value == 0)
                        cout << "u";

                int i;
                for(i=1;i<=lastSelect;i++)
                {
                        if (i <= value)
                                result += getDivCount(value-i, i);
                }

                funcValues[value][lastSelect] = result;
        }
        return result;
}

int main()
{
        int i;
        // setting the initial value
        for(i=0;i<MaxLastSelect;i++)
                funcValues[0][i] = 1;
        cout << getDivCount(5, 4);
}

--
Chaos is the best description of the constant state of human society.
Therefore, dynamic balance is required for us to to survive when vital fault
occurrs. So in the society, we don't chase for peace and order, but existence
and survival, instead.

--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: h124.s79.ts30.h

> -------------------------------------------------------------------------- <

作者: alang (Wrong Answer >_<) 看板: C_and_CPP
標題: Re: 愛我就教我
時間: Sun May  9 02:38:28 1999

※ 引述《[e-mail] (行雲)》之銘言：
: ※ 引述《adox (有矜持的少…)》之銘言：
: :        就我啦~~
: :        人家不會了!!!
: :     各位帥哥哥!!
: :       救救我:
: :   請問要如何計算
: :   一個數的分解數(整數)
: :     如 5=4+1
: :         =3+2
: :         =3+1+1
: :         =2+2+1
: :         =2+1+1+1
: :         =1+1+1+1+1 (共六種)
: :     謝謝啦!!

        上一個po的程式有問題
        我po一個我寫的 寫的不好 多見諒

#include <iostream.h>

const int MAX = 200;
int n;
int stack[MAX];
int top;
int printBefore;

void PrintStack()
{
  for ( int i = 0 ; i <= top ; i++)
    cout << stack[i] << "+";
}

void R(int n , int lead, int lev)
{
  if ( n == 0 )
  {
    cout << endl;
    printBefore = 1;
    return;
  }

  for ( int i = lead ; i > 0 ; i --)
   if ( n >= i )
   {
      if ( lev == 0 ) printBefore = 0;
      if (printBefore)
      {
        PrintStack();
        printBefore = 0;
      }
      if ( n == i )
        cout << i << ' ';
      else
        cout << i << '+';

      stack[++top] = i;
      R( n - i , i, lev + 1);
      top --;
    }
}

int main(void)
{
  top = -1;
  cin >> n;
  R(n,n-1, 0);
  return 0;
}