ALGO-22算法訓(xùn)練 數(shù)的劃分
問(wèn)題描述
將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同（不考慮順序）。例如：n=7,k=3,下面三種分法被認(rèn)為是相同的：1，1，5； 1，5，1； 5，1，1。問(wèn)有多少種不同的分法。輸入：n,k(6<n<=200,2<=k<=6)輸出：一個(gè)整數(shù)，即不同的分法。
輸入輸出樣例
輸入：7 3輸出：4
分析：遞歸問(wèn)題，step表示當(dāng)前剩余的數(shù)需要分成的份數(shù)~~把n分成k份，只需第一個(gè)數(shù)等于i，計(jì)算從i等于1一直到i等于n/k，然后把剩余的n-i分成k-1份的種類數(shù)…front為剩余的要?jiǎng)澐值臄?shù)的前一個(gè)數(shù)，每次i從front開(kāi)始一直到n/step結(jié)束，這樣才能保證得到的劃分方式是不遞減的，才能保證不會(huì)有重復(fù)的情況產(chǎn)生~#include <iostream>
using namespace std;int cnt =0;void dfs(int front, int n,int step) { if(step==1) { cnt++;return;}for(int i=front;i<=n/step;i++)
dfs(i,n-i,step-i);
}int main(){int n,k;cin>>n>>k;dfs(1,n,k);cout <<cnt;return 0;}
其他的解題思路： 點(diǎn)擊打開(kāi)鏈接 點(diǎn)擊打開(kāi)鏈接
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
