C語言回溯法 實現(xiàn)組合數(shù) 從N個數(shù)中選擇M個數(shù)
更新時間：2018年08月11日 16:19:42 作者：Alger_jhun
在平時的算法的題目中，時常會遇到組合數(shù)相關(guān)的問題，暴力枚舉。在N個數(shù)中挑選M個數(shù)出來。利用for循環(huán)也可以處理，但是可拓展性不強，于是寫這個模板供以后參考
前言
在平時的算法的題目中，時常會遇到組合數(shù)相關(guān)的問題，暴力枚舉。在N個數(shù)中挑選M個數(shù)出來。利用for循環(huán)也可以處理，但是可拓展性不強，于是寫這個模板供以后參考。
兩個函數(shù)和全局變量可以直接用。
代碼：
#include<iostream>
#include<cstdio>
#define N 10 //被選擇的數(shù)目
#define M 5 //要選出來的數(shù)目
using namespace std;
int vis[N+1]; //標(biāo)志，
int ans=0; //含有的組合數(shù) 的數(shù)量
int num[M+1]; //選出來的數(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個數(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); //回溯開始
cout<<endl<<ans;
return 0;
}
可以發(fā)現(xiàn)利用回溯法挑選的有一個優(yōu)勢在于，輸出的數(shù)組是經(jīng)過排序的。
相關(guān)文章
這篇文章主要介紹了VC中刪除類的兩種操作方法,較為詳細(xì)的描述了在VC中實現(xiàn)刪除類的具體步驟,非常具有實用價值,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了使用WindowsAPI獲取錄音音頻的方法,非常實用的功能,需要的朋友可以參考下2014-08-08
C語言位段(位域)機制結(jié)構(gòu)體的特殊實現(xiàn)及解析
這篇文章主要為大家介紹了C語言位段位域機制結(jié)構(gòu)體的特殊實現(xiàn)講解有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2022-02-02
大家好，本篇文章主要講的是C++制作鼠標(biāo)連點器實例代碼，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
C++深入分析數(shù)據(jù)在內(nèi)存中的存儲形態(tài)
使用編程語言進行編程時，需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著，當(dāng)您創(chuàng)建一個變量時，就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息，操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型，來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2023-01-01
這篇文章主要介紹了C語言中的各種文件讀寫方法小結(jié),是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-07-07
這篇文章主要介紹了C++存儲方案和動態(tài)分配，2021-12-12
C 語言中的多維數(shù)組（multidimensional array）其實就是元素為數(shù)組的數(shù)組。多維指針根據(jù)聲明的維數(shù)需要進行多次地址轉(zhuǎn)換才能夠取到目標(biāo)數(shù)據(jù)。但指針作為數(shù)據(jù)變量，可以多次賦值，使其成為對數(shù)組操作訪問的一大利器，所以指針和數(shù)組的結(jié)合才是重中之重2022-04-04
在C語言中，常量和變量都是可以用來存儲和表示數(shù)據(jù)的，常量值在程序執(zhí)行的過程中是不可變的，而變量是可變的2017-10-10
在C++的STL中,vector是一個動態(tài)數(shù)組,可以在運行時調(diào)整大小,本文介紹了vector的初始化、元素訪問、修改、迭代器操作、容量管理以及性能優(yōu)化技巧,通過這些操作,可以有效地使用vector管理數(shù)據(jù),本文介紹C++ vector 操作,感興趣的朋友一起看看吧2024-10-10