华师一附中OI组

标题: 经典的M选N程序及其变形 [打印本页]

作者: diggersun 时间: 2014-10-18 18:29
标题: 经典的M选N程序及其变形
首先，我们用递归做一个标准的m选n程序：
#include <iostream>
using namespace std;
const int m=5,n=3;  //假设5选3
int a[n];  //每个位置上面存放的数字
bool b[m]; //B数组表示某个数字是否被用过
void mysearch(int i)
{
int j,k;
if (i==n)
{
      for (j=0; j<=n-1; j++) cout<<a[j];
      cout<<endl;
}
else for (k=0; k<=m-1; k++)
         if (b[k])
         {
            a[i]=k;
            b[k]=false;
            mysearch(i+1);
            b[k]=true;
         }
}
int main()
{
for (int i=0; i<=m-1; i++) b[i]=true;
mysearch(0);
return 0;
}

作者: diggersun 时间: 2014-10-18 18:32
本帖最后由 diggersun 于 2014-10-18 18:39 编辑

现在我们将它改成5个数字（0,1,2,3,4）中选3个的组合，所谓组合，就是没有顺序，我们也可以认为，是后面一个数字大于前面一个数字的排列。

#include <iostream>
using namespace std;
const int m=5,n=3;
int a[n];
void mysearch(int i)
{
int j,k;
if (i==n)
{
for (j=0; j<=i-1; j++) cout<<a[j];
cout<<endl;
}
else for (k=(i==0?0:a[i-1]+1); k<=m-1; k++)
{
a[i]=k;
mysearch(i+1);
}
}
int main()
{
mysearch(0);
return 0;
}

复制代码

因为后面一个数字比前面一个大，所以绝对不会有重复，可以省略B数组，程序13行是控制循环变量K的值，做法比较特殊，当i==0的时候说明是第一个位置上的数字，从0起步，否则，从上一个数字+1 起步，这个小技巧请大家学会。

作者: hr567 时间: 2014-10-18 18:34
标题: 沙发
本帖最后由 hr567 于 2014-10-18 18:43 编辑

顶！！！！抢沙发了……

char *s = "Good!";
std::cout << s << endl;
return 0;

复制代码

作者: hr567 时间: 2014-10-18 18:41
顶！！！！抢沙发

char *s = "Good!";
std::cout << s << endl;
return 0;

复制代码

作者: diggersun 时间: 2014-10-18 18:42
今年初中组初赛有个题目是问8个球装在5个袋子里有多少种装法，其中袋子可以为空。可以用这种方法来做，尽管笨了一点，但是很好理解。
#include <iostream>
using namespace std;
const int m=8,n=5;
int a[n];
void mysearch(int i)
{
int j,k,s=0;
if (i==n)
{
      for (j=0; j<=n-1; j++) s+=a[j];
      if (s==10) {for (j=0; j<=n-1; j++) cout<<a[j];cout<<endl;}
}
else for (k=(i==0?0:a[i-1]); k<=m-1; k++)
      {
         a[i]=k;
         mysearch(i+1);
      }
}
int main()
{
mysearch(0);
return 0;
}

作者: wsk12345 时间: 2014-10-18 18:48

printf("\110\105\99\101\33");

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)