数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中计数先递减后递增的排列
我们有一个变量num。目标是找到[1,num]之间数字的排列数，这些排列中的数字先递减后递增。例如，如果num=3，则数字为1,2,3。排列将是[3,1,2]和[2,1,3]，计数为2。
我们知道，在每个排列中，数字从递减到递增的变化将取决于最小值1的位置。在每个1之后，数字将开始递增。对于一个先递减后递增的排列，1应该位于位置2和num-1之间。[ → ...1…. → ]。
如果1在开头，则序列将完全递增[1.. → ]，如果它在结尾，则序列将完全递减[ … → 1 ]。
假设我们有num=4，则
将1放在第二个位置，[ - , 1, - , - ]。对于第一个位置，我们可以从(2,3,4)中选择，假设我们选择2，则序列将是[2,1,3,4]。因此，在这种情况下，有3C1种排列。
将1放在第三个位置，[ -, -, 1, - ]。对于第一和第二个位置，从三个(2,3,4)中选择任意两个。总排列数将是3C2。
因此，对于num=4，总排列数将是 = 3C1 + 3C2
对于任何数字x，计数将是 = x-1C1 + x-1C2+.....+x-1Cx-2 = 2x-1 - 2 (根据二项式定理)。
让我们用例子来理解
输入 − num=4
输出 − 先递减后递增的排列数为：6
解释 − 排列将是 −
[ 2, 1, 3, 4 ], [ 3, 1, 2, 4 ], [ 4, 1, 2, 3 ] → 1 at 2nd position [ 2, 3, 1, 4 ], [ 2, 4, 1, 3 ], [ 3, 4, 1, 2 ] → 1 at 3rd position
输入 − num=6
输出 − 先递减后递增的排列数为 − 30
解释 − 一些排列将是 −
[ 2, 1, 3, 4, 5, 6 ], [ 3, 1, 2, 4, 5, 6 ], [ 4, 1, 2, 3, 5, 6 ], [ 5, 1, 2, 3, 4, 6 ], [ 6, 1, 2, 3, 4, 5 ] ……[ 6, 5, 4, 3, 1, 2].
下面程序中使用的方法如下
在这种方法中，我们将使用二项式定理根据上述公式直接计算排列。我们还将创建一个函数value(long long i, long long num)，它返回inum
将变量num作为输入。
函数permutations_increase_decrease(int num)接收num并返回从1到num的数字中先递减后递增的排列数。
函数value(long long i, long long num)用于计算(inum) % temp。其中temp=1000000007。
在permutations_increase_decrease(int num)内部，设置temp=1000000007。
如果num为1，则没有可能的排列，因此返回0。
否则，使用公式设置count = (value(2, num - 1) - 2) % temp );
返回count作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
long long value(long long i, long long num){
int temp = 1000000007;
if (num == 0){
return 1;
}
long long j = value(i, num / 2) % temp;
j = (j * j) % temp;
if(num & 1){
j = (j * i) % temp;
}
return j;
}
int permutations_increase_decrease(int num){
int temp = 1000000007;
if (num == 1){
return 0;
}
int count = (value(2, num - 1) - 2) % temp;
return count;
}
int main(){
int num = 4;
cout<<"Count of permutations that are first decreasing then increasing are: "<<permutations_increase_decrease(num);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of permutations that are first decreasing then increasing are: 6
浏览量157
