WEB开发网
开发学院软件开发C++ C++中的23种算法 阅读

C++中的23种算法

 2012-05-29 11:10:16 来源:WEB开发网   
核心提示:return 0;}23.数字拆解说明这个题目来自于数字拆解,我将之改为C语言的版本,C++中的23种算法(18),并加上说明,题目是这样的:3 = 2+1 = 1+1+1 所以3有三种拆法4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种5 = 4 + 1 = 3 +

return 0;

}

23.数字拆解

说明

这个题目来自于数字拆解,我将之改为C语言的版本,并加上说明。

题目是这样的:

3 = 2+1 = 1+1+1 所以3有三种拆法

4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种

5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

共七种

依此类推,请问一个指定数字NUM的拆解方法个数有多少个?

解法

我们以上例中最后一个数字5的拆解为例,假设f( n )为数字n的可拆解方式个数,而f(x, y)为使

用y以下的数字来拆解x的方法个数,则观察:

5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

使用函式来表示的话:

f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)

其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1),但是使用大于1的数字来拆解1没有意义,所以f(1, 4) =f(1, 1),而同样的,f(0, 5)会等于f(0, 0),所以:

f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)

依照以上的说明,使用动态程式规画(Dynamic programming)来进行求解,其中f(4,1)其实就

是f(5-1, min(5-1,1)),f(x, y)就等于f(n-y, min(n-x, y)),其中n为要拆解的数字,而min()表示取两

者中较小的数。

使用一个二维阵列表格table[x][y]来表示f(x, y),刚开始时,将每列的索引0与索引1元素值设定

为1,因为任何数以0以下的数拆解必只有1种,而任何数以1以下的数拆解也必只有1种:

for(i = 0; i < NUM +1; i++){

table[i][0] = 1; // 任何数以0以下的数拆解必只有1种

table[i][1] = 1; // 任何数以1以下的数拆解必只有1种

}

接下来就开始一个一个进行拆解了,如果数字为NUM,则我们的阵列维度大小必须为NUM x

(NUM/2+1),以数字10为例,其维度为10 x 6我们的表格将会如下所示:

1 1 0 0 0 0

1 1 0 0 0 0

1 1 2 0 0 0

1 1 2 3 0 0

1 1 3 4 5 0

1 1 3 5 6 7

1 1 4 7 9 0

1 1 4 8 0 0

1 1 5 0 0 0

1 1 0 0 0 0

实作

C

#include <stdio.h>

#include <stdlib.h>

#define NUM 10 // 要拆解的数字

#define DEBUG 0

int main(void) {

int table[NUM][NUM/2+1] = {0}; // 动态规画表格

int count = 0;

int result = 0;

int i, j, k;

printf("数字拆解\n");

printf("3 = 2+1 = 1+1+1 所以3有三种拆法\n");

printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");

printf("共五种\n");

printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");

printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");

printf("共七种\n");

printf("依此类推,求%d 有几种拆法?", NUM);

// 初始化

for(i = 0; i < NUM; i++){

table[i][0] = 1; // 任何数以0以下的数拆解必只有1种

table[i][1] = 1; // 任何数以1以下的数拆解必只有1种

}

// 动态规划

for(i = 2; i <= NUM; i++){

for(j = 2; j <= i; j++){

if(i + j > NUM) // 大于NUM

continue;

count = 0;

for(k = 1 ; k <= j; k++){

count += table[i-k][(i-k >= k) ? k : i-k];

}

table[i][j] = count;

}

}

// 计算并显示结果

for(k = 1 ; k <= NUM; k++)

result += table[NUM-k][(NUM-k >= k) ? k : NUM-k];

printf("\n\nresult: %d\n", result);

if(DEBUG) {

printf("\n除错资讯\n");

for(i = 0; i < NUM; i++) {

for(j = 0; j < NUM/2+1; j++)

printf("%2d", table[i][j]);

printf("\n");

}

}

return 0;

上一页  13 14 15 16 17 18 

Tags:算法

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接