整数分解

• 题目介绍
• 习题解决
• • 隔板模拟法
  • 暴力法
  • 动态规划

成都创新互联公司专注于企业营销型网站、网站重做改版、南票网站定制设计、自适应品牌网站建设、H5网站设计、成都做商城网站、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为南票等各大城市提供网站开发制作服务。题目介绍

将3分解成两个正整数的和，有两种分解方法
分别是3=1+2和3=2+1。注意顺序不同算不同的方法。

将 5 分解成三个正整数的和, 有 6 种分解方法,
它们是 1+1+3=1+2+2=1+3+1=2+1+2=2+2+1=3+1+1 。

请问，将 2021 分解成五个正整数的和，有多少种分解方法?

习题解决 隔板模拟法

我们可以使用隔板来进行解决。
如5就可以看成5个1用2个隔板来拆分成3份

11

1

11

1

11

11

答案就可以用数学简单的排列组合来计算就是C₂⁴

这个题目就可以课成2020个坑需要4个隔板拆分，答案就是计算C₄²⁰²⁰

import java.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {public static void main(String[] args) {//在此输入您的代码...
        BigInteger b1 = new BigInteger("2017");
        BigInteger b2 = new BigInteger("2020");
        BigInteger b3 = new BigInteger("2019");
        BigInteger b4 = new BigInteger("2018");
        int i = 3*4*2;
        System.out.println(b1.multiply(b2).multiply(b3).multiply(b4).divide(new BigInteger(String.valueOf(i))));
    }
}

python

print(2020*2019*2018*2017//4//3//2//1)

暴力法

因为最少为1则第一位范围在1-2017
后面位数同理
而对于最后2位数
我们可以看到倒数第二位确定了则倒数第一位确定。
所以可以得到如果a+b=c则有c-1种情况

long ans = 0;
for (int i = 1; i<= 2017; i++) {int n = 2021-i;
    for (int j = 1; j<= n-3; j++) {  int m = n-j;
      for (int d = 1; d<= m-2; d++) { ans += m - d -1;
      }
   }
}
assert (ans == 691677274345L);

python速度极慢不建议计算

ans = 0
for i in range(2017):
    n = 2021 - i - 1
    for j in range(n-3):
        m = n - j - 1
        for d in range(m-2):
            ans += m - d - 1
print(ans)

动态规划

dp[选的数字] [总数]
dp[i][j]当前（j数分成i分）
然后从i-1到i选一个数到总数到 j 那么，这个数可以是比j小的所有数
那么dp[i][j] = dp[i-1][j - z]不选这个数的所有和

long[][] dp = new long[7][2022];
Arrays.fill(dp[1],1);
for (int i = 2; i< 6; i++)
   for (int j = 1; j< 2022; j++)
      for (int z = 1; z< j; z++)
          dp[i][j] += dp[i-1][j-z];
System.out.println(dp[5][2021]);

python还是不写了，差不多一样的

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享文章：蓝桥杯--整数分解--java--python-创新互联
标题来源：http://kswsj.cn/article/ccscgc.html