当涉足算法领域,排列组合应该是最基础的。最近遇到了,作个记录,小白看看,大神绕路
一、补充公式
排列的定义:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列;从n个不同元素中取出m(m≤n)个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号 A(n,m)表示,公式如下:
A(n,m) = n!/(n-m)!
组合的定义:从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示:
C(n,m) = n!/(m!*(n-m)!) (n>=m)
二、代码实现
2.1 c++代码实现排列
话不多说,直接上代码:
#include <iostream>
using namespace std;
//交换函数
void swap(int& a, int& b )
{
int temp = a;
a = b;
b = temp;
}
/*入参:
begin 要排列的起始位置
end 要排列的结束位置
a[] 要排列的数组
*/
void permutate(int begin, int end, int a[])
{
if(begin == end)//已经到了最后一个位置,进行输出
{
for(int i=0; i < end;i++)
{
cout<<a[i];
}
cout<<endl;
}
for(int i= begin; i < end; i++)
{
swap(a[begin],a[i]);
permutate(begin + 1,end,a);//递归下一个位置
swap(a[i],a[begin]);//回溯
}
}
int main()
{
int a[5] = {1,2,3,4,5};
permutate(0,3,a);//对数组中前三个数进行排列
return 0;
}
输出为:
123
132
213
231
321
312
当然也可进行简单的优化:
template<class T,int N>
void permutate(int begin, int end, T (&a)[N])
{
if(0 > begin || begin > end || end > N)
{
cout<<"输入参数错误"<<endl;
return;
}
//输出情况
if(begin == end)
{
for(int i=0; i < end;i++)
{
cout<<a[i];
}
cout<<endl;
}
for(int i= begin; i < end; i++)
{
swap(a[begin],a[i]);
permutate(begin + 1,end,a);
swap(a[i],a[begin]);
}
}
2.2 c++代码实现组合
代码:
#include <iostream>
using namespace std;
void combinate(int iPos, int iProc, int iTol, int iKey, int data[],int des[])
{
if(iProc > iTol)
{
return;
}
if(iPos == iKey)
{
for(int i = 0;i < iKey; i++)
{
cout<<des[i]<<" ";
}
cout<<endl;
return;
}
else
{
combinate(iPos,iProc+1,iTol,iKey,data,des);
des[iPos] = data[iProc];
combinate(iPos+1,iProc+1,iTol,iKey,data,des);
}
}
int main()
{
int a[6] = {1,2,3,4,5,6}, b[5];
combinate(0, 0, 5, 3 , a,b);
//如果需要终端输入
/*
cin>>n>>k;
if(n > k > 0)
{
int data[n],temp[n];
for(i = 0; i < n; i++ )
{
data[i] = i+1;
}
combinate(0, 0, n, k, data, temp);
}
*/
return 0;
}
输出为:
3 4 5
2 4 5
2 3 5
2 3 4
1 4 5
1 3 5
1 3 4
1 2 5
1 2 4
1 2 3
平时工作一般用不到这些,最近自己琢磨发现虽然逻辑简单,但是写起来还确实不知道怎么下手。。。
所以不能羡慕算法大神年薪几十万上百万,毕竟得脑子好用不是?
===============
想分一杯羹,还是尽早学习,共勉!
今天的文章C++之——实现排列组合分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/13016.html