首页 > 其他分享 >P1157 组合的输出

P1157 组合的输出

时间:2024-04-13 13:56:11浏览次数:22  
标签:输出 cnt 组合 二进制 元素 int P1157

P1157 组合的输出

题目

排列与组合是常用的数学方法,其中组合就是从 \(n\) 个元素中抽出 \(r\) 个元素(不分顺序且 \(r \le n\)),我们可以简单地将 \(n\) 个元素理解为自然数 \(1,2,\ldots,n\),从中任取 \(r\) 个数。

现要求你输出所有组合。

例如 \(n=5,r=3\),所有组合为:

\(123,124,125,134,135,145,234,235,245,345\)。

输入

一行两个自然数 \(n,r(1<n<21,0 \le r \le n)\)。

输出

所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个字符的位置,所有的组合也按字典顺序。

注意哦!输出时,每个数字需要 \(3\) 个场宽。以 C++ 为例,你可以使用下列代码:

cout << setw(3) << x;

输出占 \(3\) 个场宽的数 \(x\)。注意你需要头文件 iomanip

样例

输入

5 3

输出

  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

思路一

我们构造一个 \(n\) 位的二进制数,二进制数的第 \(i\) 位代表第 \(i\) 个元素的选取状态。枚举全集 \(\lbrack 0,2^n-1 \rbrack\) 共 \(2^n\) 种状态,代码为

for (int S = 0; S <= (1 << n) - 1; S ++ )

其中 1 << n 表示二进制数 \(1\) 向左移 \(n\) 位,即十进制数 \(2^n\),(1 << n) - 1 是由 \(n\) 个 \(1\) 构成的二进制数。二进制数从右向左依次为第 \(0\) 位,第 \(1\) 位,\(\cdots\),第 \(n - 1\) 位,分别表示每个位置对应的元素的选取状态,如果该位置为 \(1\),表示对应位置的元素被选取,如果为 \(0\),表示没有被选取。若某个状态 \(S(S\) 有 \(n\) 位 \()\) 的二进制数含有 \(r\) 个 \(1\),那么它二进制为 \(1\) 的位对应的元素就是我们要选取的。

如何判断 \(S\) 中某一位是否为 \(1\) 呢?可以借助 \(1\) 左移 \(i\) 位得到的二进制数与 \(S\) 进行“\(\&\)”运算,如果结果为正数,则第 \(i\) 位为 \(1\)。例如:“\(S=10000100,S \& (1<<2)=00000100\)”,则说明 \(S\) 中第 \(2\) 位为 \(1\),表示题意中第 \(n-i\) 个元素要被选取。

代码

#include <bits/stdc++.h>

using namespace std;

int a[30], n, r, cnt;

int main()
{
	cin >> n >> r;
	for (int S = (1 << n) - 1; S >= 0; S -- )
	{
		cnt = 0;
		for (int i = 0; i < n; i ++ )
		{
			if (S & (1 << i))
				a[cnt ++] = i;
		}
		if (cnt == r)
		{
			for (int i = r - 1; i >= 0; i -- )
				printf("%3d", n - a[i]);
			cout << '\n';
		}
	}
	return 0;
}

思路二

题目从 \(n\) 个数中选 \(r\) 个数字的组合,且 \(n\) 小于 \(21\),我们构造一个 \(n\) 位的二进制数,二进制数的第 \(i\) 位代表第 \(i\) 个元素的选取状态,与前面的方法相同。如果 __builtin_popcount(x) 函数等于 \(r\),则说明二进制数 \(x\) 含有 \(r\) 个 \(1\),是题目需要的状态。可以对 \(x\) 进行数位分离,将数字为 \(1\) 的位置用数组储存下来,分离结束后按要求输出 \(x\) 中每个 \(1\) 的位置。

这道题需要注意的是输出格式,要求按照字典序输出。因此不能从小到大枚举二进制数,例如“\(01101\)”这个二进制数表示第 \(1,3,4\) 个数字被选择。“\(10011\)”这个二进制数表示第 \(1,2,5\) 个数字被选择。而二进制数“\(01101\)”\(<\)“\(10011\)”,因此“\(1,3,4\)”这种状态会先被枚举到,但“\(1,2,5\)”的字典序小于“\(1,3,4\)”。因此为了让“\(1\)”尽可能靠前出现以满足字典序要求,我们可以将状态从大到小枚举。

代码

#include <bits/stdc++.h>

using namespace std;

int n, r, cnt, a[50], S, x, p;

int main()
{
	cin >> n >> r;
	S = (1 << n) - 1;
	for (int i = S; i >= 0; i -- )
	{
		cnt = 0;
		if (__builtin_popcount(i) == r)
		{
			x = i;
			p = 1;
			while (x)
			{
				if (x & 1)
					a[++ cnt] = n - p + 1;
				x >>= 1;
				p ++;
			}
			for (int j = cnt; j >= 1; j -- )
				printf("%3d", a[j]);
			cout << '\n';
		}
	}
	return 0;
}

标签:输出,cnt,组合,二进制,元素,int,P1157
From: https://www.cnblogs.com/IronMan-PZX/p/18132771

相关文章

  • 基础组合数学
    byTheBigYellowDuck联赛前恶补知识点...排列数&组合数从\(n\)元集合中选出\(m\)个元素的有序排列数记为\(A_n^m\)。计算公式为\[\displaystyleA_n^m=n(n-1)(n-2)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}\]从\(n\)元集合中选出\(m\)个元素的无序排列数记为\(C_n^m\),......
  • VS studio上查看标准cout输出
    VSstudio上查看标准cout输出网上的方法在解决方案管理器中,单击选中项目后,点击菜单【视图】->【属性页】在生成事件->生成后事件->命令行(BuildEvents->Post-BuildEvent->Command)Line)中增加$(OutDir)$(ProjectName).exe顾名思义,这个方法是在生成结束后,使用命令行执行生成的......
  • 【数学】组合数学 - 排列组合
    父级页面:【数学】组合数学排列组合可重排列可重组合隔板法盒子可以为空隔板法:x个相同的小球,有y个不同的盒子,每个盒子可以为空,求有多少种方案数?把y个不同的盒子视作y-1个不同的隔板,然后把小球视作不同的,全排列有\(A_{x+y-1}^{x+y-1}\)种,然后除以隔板的全排列(隔板之间没有......
  • 【数学】组合数学 - 卡特兰数
    父级页面:【数学】组合数学卡特兰数记号为\(H_n\)第n个卡特兰数,下面的n就是指这个。\(H_0=1,H_1=1,H_2=2,H_3=5,H_4=14,H_5=42\)卡特兰数最常见的场景是合法的括号序,还有栈进出的方案。他们的特点就是“右括号”、“出栈”的次数不能超过剩余的“左括号”、“入栈”的次......
  • 回溯-组合
    回溯-组合回溯法的本质是穷举,其主要是为了解决n个for循环的问题,在for循环中套着递归从而不断实现for循环。回溯法解决的问题都可以抽象为树形结构,一般是在给定集合是取出符合一定规则的数据。集合的大小构成树的宽度,也即第一层的for循环遍历的范围,递归的深度构成树的深度,也就暴力......
  • 组合数学
    逆元若\(i\cdotx=1\),则\(i^{-1}=x\)。递推求乘法逆元\[令模数为p,正整数i,a=\lfloor\frac{p}{i}\rfloor,b=p\operatorname{mod}i,且b\ne0。\\a\cdoti+b=p\\\Downarrow\\a\cdoti+b\equiv0(\operatorname{mod}p)\\\frac{i}{b}+\frac{1}{a}\equiv0(\o......
  • 6-1 使用函数输出指定范围内Fibonacci数的个数
    本题要求实现一个计算Fibonacci数的简单函数,并利用其实现另一个函数,输出两正整数m和n(0<m<n≤100000)之间的所有Fibonacci数的数目。所谓Fibonacci数列就是满足任一项数字是前两项的和(最开始两项均定义为1)的数列,fib(0)=fib(1)=1。其中函数fib(n)须返回第n项Fibonacci数;函数Prin......
  • 锂电池3.7V转3.3V神器:PW2224升降压芯片,稳定输出1A
    描述:PW2224是一款专为锂电池供电设备设计的高效单电感降压-升压转换器。这款转换器能够在3V至4.2V的锂电池输入电压范围内工作,实现升降压模式自动切换,稳定输出3.3V电压,并持续提供高达1A的负载电流。此外,PW2224的工作频率高达2.4MHz,并且可以与2.2MHz至2.6MHz的外部频率同步,确保设备......
  • 加入预测新数据,最小二乘支持向量机(lssvm)回归预测(多输入单输出)-附代码
    最小二乘支持向量机(lssvm)回归预测最小二乘支持向量机(LeastSquaresSupportVectorMachine,LS-SVM)是支持向量机(SupportVectorMachine,SVM)的一种变体,用于回归问题。其原理基本上与标准的支持向量机相似,但在损失函数和优化过程上有所不同。最小二乘支持向量机(LS-SVM)回归预......
  • 在eclipse上写第一个java项目,输出hello world
    第一步:创建一个JavaProject第二步:创建一个java类第三步:执行代码,输出helloworld......