【題目描述】將整數n分成k份，且每份不能為空，問有多少種分法？
【輸入格式】兩個整數n,m(6<n<=200,2<=m<=6)
【輸出格式】輸出不同的分法數
【樣例輸入】7 3
【樣例輸出】4
對于這種搜索題，關鍵就在于剪枝：確定搜索的順序、搜索的上下界，剪枝函數等等
這道題數據比較小，之間判斷搜索的上下界就可以解決。因為分法是組合，即沒有順序，為了提高效率，我們人為地規定一個順序：從小到大分塊。那么搜索的下界顯然就是前一塊的數量。對于每一塊，他的數量不可能大于剩余數字除剩余塊數（反證法證明：如果大于，那么后面的都不比他小，最終會不夠分）
代碼如下：

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std;int n,k; int a[10]; int ans=0;void dfs(int x,int cur) {if(x==k+1){if(cur==n){ans++;for(int i=1;i<=k;i++){cout<<a[i]<<" ";}cout<<endl;}return;}int m=n-cur;for(int i=a[x-1];i<=m/(k-x+1);i++){a[x]=i;dfs(x+1,cur+a[x]);} }int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;memset(a,0,sizeof(a));a[0]=1;dfs(1,0);cout<<ans;return 0;}

這個程序一開始一直錯，我怎么想都想不明白，讓大佬看后才發現，m設置成了全局變量，那么一個搜索樹分支的子節點就會反過來修改父節點的m，就會出錯。這充分說明了全局變量的危害性，只要不是必要，都應該設置為局部變量，以防止函數的重復調用導致出錯。
標程：

#include<iostream> using namespace std;int n,m,a[8],s=0;void dfs(int k) {if(n==0) return;if(k==m){if(n>=a[k-1]) s++;return;}for(int i=a[k-1];i<=n/(m-k+1);i++){a[k]=i;n-=i;dfs(k+1);n+=i;} } int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;a[0]=1;dfs(1);cout<<s<<endl;return 0; }

總結

以上是生活随笔為你收集整理的深度搜索剪枝——数的划分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。