整數(shù)分解

• 題目介紹
• 習(xí)題解決
• • 隔板模擬法
  • 暴力法
  • 動態(tài)規(guī)劃

成都創(chuàng)新互聯(lián)公司專注于企業(yè)營銷型網(wǎng)站、網(wǎng)站重做改版、南票網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5網(wǎng)站設(shè)計、成都做商城網(wǎng)站、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為南票等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。題目介紹

將3分解成兩個正整數(shù)的和，有兩種分解方法
分別是3=1+2和3=2+1。注意順序不同算不同的方法。

將 5 分解成三個正整數(shù)的和, 有 6 種分解方法,
它們是 1+1+3=1+2+2=1+3+1=2+1+2=2+2+1=3+1+1 。

請問，將 2021 分解成五個正整數(shù)的和，有多少種分解方法?

習(xí)題解決 隔板模擬法

我們可以使用隔板來進(jìn)行解決。
如5就可以看成5個1用2個隔板來拆分成3份

11

1

11

1

11

11

答案就可以用數(shù)學(xué)簡單的排列組合來計算就是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)

暴力法

因?yàn)樽钌贋?則第一位范圍在1-2017
后面位數(shù)同理
而對于最后2位數(shù)
我們可以看到倒數(shù)第二位確定了則倒數(shù)第一位確定。
所以可以得到如果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)

動態(tài)規(guī)劃

dp[選的數(shù)字] [總數(shù)]
dp[i][j]當(dāng)前（j數(shù)分成i分）
然后從i-1到i選一個數(shù)到總數(shù)到 j 那么，這個數(shù)可以是比j小的所有數(shù)
那么dp[i][j] = dp[i-1][j - z]不選這個數(shù)的所有和

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還是不寫了，差不多一樣的

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：藍(lán)橋杯--整數(shù)分解--java--python-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://weahome.cn/article/ccscgc.html