C語(yǔ)言回溯法 實(shí)現(xiàn)組合數(shù) 從N個(gè)數(shù)中選擇M個(gè)數(shù)
更新時(shí)間：2018年08月11日 16:19:42 作者：Alger_jhun
在平時(shí)的算法的題目中，時(shí)常會(huì)遇到組合數(shù)相關(guān)的問(wèn)題，暴力枚舉。在N個(gè)數(shù)中挑選M個(gè)數(shù)出來(lái)。利用for循環(huán)也可以處理，但是可拓展性不強(qiáng)，于是寫(xiě)這個(gè)模板供以后參考
前言
在平時(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++實(shí)現(xiàn)二維圖形的打印，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下2022-02-02
牛頓迭代法求多項(xiàng)式在1.5附近的值2*x的3次冪--4x平方+3*x-6=0的實(shí)現(xiàn)代碼
以下代碼是使用了牛頓迭代法求多項(xiàng)式在1.5附近的值 2*x的3次冪 - 4x的平方 + 3*x -6=0的實(shí)例。需要的朋友參考下吧2013-05-05
這篇文章主要介紹了C++中的間接宏函數(shù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
C++經(jīng)典例題之字符串特定規(guī)則反轉(zhuǎn)問(wèn)題的解法
這篇文章主要介紹了如何解決字符串反轉(zhuǎn)問(wèn)題,通過(guò)將字符串按每2k個(gè)字符為一個(gè)區(qū)間進(jìn)行劃分,并使用雙指針?lè)椒▉?lái)確定實(shí)際反轉(zhuǎn)的邊界,最終實(shí)現(xiàn)字符串按特定規(guī)則進(jìn)行反轉(zhuǎn),文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-03-03
C++模擬Linux Shell編寫(xiě)一個(gè)自定義命令
這篇文章主要介紹了C++如何模擬Linux Shell實(shí)現(xiàn)編寫(xiě)一個(gè)自定義命令,本文通過(guò)實(shí)例代碼進(jìn)行命令行解析，代碼簡(jiǎn)單易懂，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-12-12
C++超詳細(xì)實(shí)現(xiàn)二叉樹(shù)的遍歷
本章將會(huì)詳細(xì)講解二叉樹(shù)遍歷的四種方式，分別為前序遍歷、中序遍歷、后續(xù)遍歷和層序遍歷。在學(xué)習(xí)遍歷之前，會(huì)先帶大家回顧一下二叉樹(shù)的基本概念2022-05-05
C語(yǔ)言實(shí)現(xiàn)在windows服務(wù)中新建進(jìn)程的方法
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)在windows服務(wù)中新建進(jìn)程的方法,涉及C語(yǔ)言進(jìn)程操作的相關(guān)技巧,需要的朋友可以參考下2015-06-06
一文詳解C++中動(dòng)態(tài)內(nèi)存管理
這篇文章主要介紹了一文詳解C++中動(dòng)態(tài)內(nèi)存管理，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)孩子沒(méi)需要的朋友可以才可以參考一下2022-07-07
C++實(shí)現(xiàn)批量提取PDF內(nèi)容
這篇文章主要為大家詳細(xì)介紹了如何使用C++批量提取PDF里文字內(nèi)容并導(dǎo)出到表格以及批量給?PDF?文件改名,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-02-02
C++中的多態(tài)問(wèn)題—理解虛函數(shù)表及多態(tài)實(shí)現(xiàn)原理
這篇文章主要介紹了C++中的多態(tài)問(wèn)題—理解虛函數(shù)表及多態(tài)實(shí)現(xiàn)原理，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02