【アルゴリズム】整数分割を再帰的に解く
1204 ワード
説明
正の整数nは、n=n 1+n 2+...+nkの一連の正の整数の和として表され、ここでn 1≧n 2≧...≧nk≧1、k≧1である.正の整数nのこの表現を正の整数nの区分と呼ぶ.正の整数nの異なる分割個数を求める.
例えば、正の整数6には、6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1.
分析:
数字6の区分は最大値6の区分+最大値5の区分+...+と見なすことができる最大値が1の区分
値が1の場合、または最大値が1の場合は1を返します.
分類は次のとおりです.
規定数字はaで、最大値はbである.
a==1||b==1 return 1;
a>b return a,b−1の区分+a−b,bの区分
aa==b return a-1の分割+1
正の整数nは、n=n 1+n 2+...+nkの一連の正の整数の和として表され、ここでn 1≧n 2≧...≧nk≧1、k≧1である.正の整数nのこの表現を正の整数nの区分と呼ぶ.正の整数nの異なる分割個数を求める.
例えば、正の整数6には、6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1.
分析:
数字6の区分は最大値6の区分+最大値5の区分+...+と見なすことができる最大値が1の区分
値が1の場合、または最大値が1の場合は1を返します.
分類は次のとおりです.
規定数字はaで、最大値はbである.
a==1||b==1 return 1;
a>b return a,b−1の区分+a−b,bの区分
aa==b return a-1の分割+1
#include
#define RUN_COUNT 10
#define NUM_MAX 10
int run_test(int nNum);
int f(int a,int b);
int main(void)
{
int nNum = 0;
int i = 0;
for (i = 0; i < RUN_COUNT; i++)
{
nNum = rand() % NUM_MAX + 1;
printf("The number of integer %d division method is %d
", nNum, run_test(nNum));
}
return 0;
}
int run_test(int nNum)
{
return f(nNum,nNum);
}
// a b
// ： ：
// a b b
int f(int a,int b)
{
if (a == 1 || b == 1)
return 1;
if (a == b)
return f(a,b-1)+1;
if (a > b)
return f (a,b-1)+f(a-b,b);
if (a < b)
return f(a,a);
return 0;
}