整數分解

• 題目介紹
• 習題解決
• • 隔板模擬法
  • 暴力法
  • 動態規劃

成都創新互聯公司專注于企業營銷型網站、網站重做改版、南票網站定制設計、自適應品牌網站建設、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://vcdvsql.cn/article12/ccscgc.html

成都網站建設公司_創新互聯，為您提供網站導航、品牌網站設計、企業建站、品牌網站建設、網站維護、動態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯