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