首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++经典算法题-数字拆解

C++经典算法题-数字拆解

作者头像
cwl_java
发布2020-02-13 23:23:24
1.1K0
发布2020-02-13 23:23:24
举报
文章被收录于专栏:cwl_Javacwl_Java

31.Algorithm Gossip: 数字拆解

说明

这个题目来自于 数字拆解,我将之改为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

代码示例

#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;
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-01-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 31.Algorithm Gossip: 数字拆解
    • 说明
      • 代码示例
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档