【ACM】组合数 - 全排列
2024-10-20 16:05:50
组合数
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
- 找出从自然数1、2、... 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。
- 输入
- 输入n、r。
- 输出
- 按特定顺序输出所有组合。
特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。 - 样例输入
-
5 3
- 样例输出
-
543
542
541
532
531
521
432
431
421
321
思路:就是全排列嘛,可以衍生为八皇后问题
#include <iostream>
#include <cmath>
#include <cstdio> using namespace std;
int count = ;
int sum = ; bool rule(int *a, int num){ for (int i = ; i < num ; i++)
{
if (a[i-]<a[i])
{
return false;
}
}
return true; } void AllLine(int *a, int n, int k, int num){ if (k==n-)
{
if (count % sum== && rule(a,num))
{
int i;
for (i = ; i < num- ; i++)
{
cout<<a[i];
}
cout<<a[i]<<endl;
}
count++;
return;
}
else
{
for (int z = k ; z < n ; z++)
{
swap(a[z],a[k]);
AllLine(a,n,k+,num);
swap(a[z],a[k]);
}
} } int main(){ int n,num;
while(scanf("%d%d",&n,&num)!=EOF){ for (int k = ; k <= n-num ; k++)
{
sum *= k;
} int *a = new int[n];
for (int i = ; i < n ; i++)
{
a[i] = n-i;
}
AllLine(a,n,,num); } return ;
}
全排列基本模型(注:根据题型,可以将 int 数组换成 char 等):
#include <iostream>
#include <cmath>
using namespace std; void foo(int n,int k,int *a){
if(k==n-)
{
for(int i = ;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return;
}else{
for(int j = k; j < n; j++){
int temp=a[k];
a[k]=a[j];
a[j]=temp;
foo(n,k+,a);
temp=a[k];
a[k]=a[j];
a[j]=temp;
}
} } int main() {
int n=;
int *a = new int[n];
for(int i=;i<n;i++){
a[i]=i+;
}
for(int i=;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"begin"<<endl;
foo(n,,a);
cout<<"end"<<endl;
return ;
}
输出:
begin end
最新文章
- hibernate报错Unknown integral data type for ids : java.lang.String
- #查看Linux的版本信息
- C# 获取磁盘空间大小的方法
- puppet安装配置及使用
- IOS AutoLayout 遍历修改约束
- bzoj3620 似乎在梦中见过的样子
- 微软TTS示例
- 怎么在android的XML文件里加入凝视
- Oracle索引语句整理
- 前端双引号单引号,正则反向引用,js比较jq
- 为何写flash的时候要地址左移一位?
- poj2778(AC自动机+矩阵快速幂)
- 关于Grid Layout
- idea中git常见使用场景
- java注解XML
- linux lftp
- 关于文件的INode与Java中的文件操作接口
- Mysql 用户权限管理--从 xxx command denied to user xxx
- eclipse svn 以一种访问权限不允许的方式做了一个访问套接字的尝试
- C++之STL迭代器(iterator)