C語(yǔ)言回溯法 實(shí)現(xiàn)組合數(shù) 從N個(gè)數(shù)中選擇M個(gè)數(shù)
前言
在平時(shí)的算法的題目中,時(shí)常會(huì)遇到組合數(shù)相關(guān)的問(wèn)題,暴力枚舉。在N個(gè)數(shù)中挑選M個(gè)數(shù)出來(lái)。利用for循環(huán)也可以處理,但是可拓展性不強(qiáng),于是寫(xiě)這個(gè)模板供以后參考。
兩個(gè)函數(shù)和全局變量可以直接用。
代碼:
#include<iostream> #include<cstdio> #define N 10 //被選擇的數(shù)目 #define M 5 //要選出來(lái)的數(shù)目 using namespace std; int vis[N+1]; //標(biāo)志, int ans=0; //含有的組合數(shù) 的數(shù)量 int num[M+1]; //選出來(lái)的數(shù)放在num數(shù)組里面 void solve() { //在solve函數(shù)里面處理 for(int i=1; i<M+1; i++) cout<<num[i]<<" "; cout<<endl; } void dfs(int index) { //挑選的第index+1個(gè)數(shù) if(index == M) { solve(); ans++; return ; } for(int i=num[index]+1; i<N+1; i++) { if(!vis[i]) { vis[i] = 1; num[index+1] = i; dfs(index+1); vis[i] = 0; } } } int main() { dfs(0); //回溯開(kāi)始 cout<<endl<<ans; return 0; }
可以發(fā)現(xiàn)利用回溯法挑選的有一個(gè)優(yōu)勢(shì)在于,輸出的數(shù)組是經(jīng)過(guò)排序的。
相關(guān)文章
C語(yǔ)言位段(位域)機(jī)制結(jié)構(gòu)體的特殊實(shí)現(xiàn)及解析
這篇文章主要為大家介紹了C語(yǔ)言位段位域機(jī)制結(jié)構(gòu)體的特殊實(shí)現(xiàn)講解有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪2022-02-02C++制作鼠標(biāo)連點(diǎn)器實(shí)例代碼
大家好,本篇文章主要講的是C++制作鼠標(biāo)連點(diǎn)器實(shí)例代碼,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下,方便下次瀏覽2022-01-01C++深入分析數(shù)據(jù)在內(nèi)存中的存儲(chǔ)形態(tài)
使用編程語(yǔ)言進(jìn)行編程時(shí),需要用到各種變量來(lái)存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著,當(dāng)您創(chuàng)建一個(gè)變量時(shí),就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類(lèi)型的信息,操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類(lèi)型,來(lái)分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么2023-01-01C語(yǔ)言菜鳥(niǎo)基礎(chǔ)教程之常量和變量
在C語(yǔ)言中,常量和變量都是可以用來(lái)存儲(chǔ)和表示數(shù)據(jù)的,常量值在程序執(zhí)行的過(guò)程中是不可變的,而變量是可變的2017-10-10