整數(shù)分解

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

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

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

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

請(qǐng)問(wèn)，將 2021 分解成五個(gè)正整數(shù)的和，有多少種分解方法?

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

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

11

1

11

1

11

11

答案就可以用數(shù)學(xué)簡(jiǎn)單的排列組合來(lái)計(jì)算就是C₂⁴

這個(gè)題目就可以課成2020個(gè)坑需要4個(gè)隔板拆分，答案就是計(jì)算C₄²⁰²⁰

import java.math.BigInteger;
// 1:無(wú)需package
// 2: 類(lèi)名必須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ù)同理
而對(duì)于最后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速度極慢不建議計(jì)算

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)

動(dòng)態(tài)規(guī)劃

dp[選的數(shù)字] [總數(shù)]
dp[i][j]當(dāng)前（j數(shù)分成i分）
然后從i-1到i選一個(gè)數(shù)到總數(shù)到 j 那么，這個(gè)數(shù)可以是比j小的所有數(shù)
那么dp[i][j] = dp[i-1][j - z]不選這個(gè)數(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還是不寫(xiě)了，差不多一樣的

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

文章名稱(chēng)：藍(lán)橋杯--整數(shù)分解--java--python-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://jinyejixie.com/article12/ccscgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、品牌網(wǎng)站設(shè)計(jì)、企業(yè)建站、品牌網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、動(dòng)態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)