資料結構
網路
關係資料庫管理系統 (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
