首页 > 代码库 > [算法]组合类问题

[算法]组合类问题

2024-07-27 09:45:15   220人阅读

1，组合相关公式

C(n,m)=n*(n-1)*(n-2)...*(n-m-1)/m!=n!/(m!*(n-m)!)

C(n,m)=C(n,n-m)

C(n+1,m)=C(n,m)+C(n,m-1)

C(n,1)+C(n,2)+…+C(n,n)=2^n;

 

2，相关算法

Question 1: 输入一个字符串，打印出该字符串中字符的所有组合。

算法1：同样可以按照文章http://www.cnblogs.com/orchid/p/4025172.html中提到的思路，有长度为strlen(s)个盒子，每个盒子里面有0和1，总共有几种不同的排列方法？

void Combination::GetCombination(int* holders,int end){    for(int i=0;i<2;i++)    {        holders[end]=i;        if(end==strlen(elements)-1)   //elements是const char*类型，        {            print(holders);        }        else{            GetCombination(holders,end+1);        }    }}

算法2，不用递归，直接循环。

void Combination::PrintAllCombination2(){    vector<string> holder;    holder.push_back("");    for(int i=0;i<strlen(elements);i++)    {        int lastOne=holder.size();        for(int j=0;j<lastOne;j++)        {            string temp=holder.at(j)+elements[i];            holder.push_back(temp);            cout << temp << ",";        }    }}

假设一次循环之后vector里面的元素是,"" "a" "b" "ab"，那么下次循环需要将第三个字符c加入序列中，即在vector中插入"c","ac","bc","abc" --- 字符c与vector中现有子串的和。

 

[算法]组合类问题


联系
我们