資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究在 C++ 中計算置亂數（不出現元素的原位排列）
置亂數是指 N 個數字的排列，使得沒有數字出現在其原始位置處。例如，{ 1,2,3 } 可能出現的置亂數為 { 2,1,3 }。其中沒有一個元素在原始位置處。我們的目的是計算 N 個數字可能出現的置亂數。
我們將使用遞迴解法。對於以下元素數 −
- N=0，無置亂數，返回 1
- N=1，只有一個數字，返回 0
- N=2，只可能進行一次位置交換，{ 1,2 } → { 2,1 }，返回 1
- N=3，2 種可能的置亂數，如 { 1,2,3 } → { 2,3,1 }，{ 3,1,2 }，計數 2
- N=4，9 種可能的置亂數
- .......................
- N，(N-1)*( permutation(N-1) + permutation(N-2) )
對於陣列中的所有元素來說，
位於索引 0 處的元素有 n-1 個可能的位置，
如果索引 i 處的任何元素位於索引 0 處，則 arr[i] 和 arr[0] 被交換。現在還有 n-2 個元素需要計算。
如果索引 i 處的元素沒有位於索引 0 處，則對於 n-1 個元素來說，有 n-2 種選擇。
圖表
輸入
Arr[] = { 1, 2 }輸出
No. of derangements : 1
解釋 - 位置 1 和 2 的索引為 0 和 1。它們能取得的唯一位置是互換原來的位置。{ 2,1 }
輸入
Arr[] = { 1, 2, 3 }輸出
No. of derangements : 2
解釋 - 位置 1、2 和 3 的索引為 0、1、2。
1 可以放置在索引 1 和 2，2 可以放置在索引 0 和 3，3 可以放置在索引 0 和 1。
{ 2,3,1 } 和 { 3,1,2 } 是 2 個錯位排列。
在以下程式中，採用的方法如下
整數 Num 儲存存在數字的數量。
遞迴函式 derangements(int N) 以數字數量作為輸入並返回錯位排列的數量。
N=0,1,2 的 return 語句處理基準案例，其中排列已計算為 1、0 和 1。
如果 N>2，則使用以下公式對 derangements() 進行遞迴呼叫：
(N-1)* ( derangements ( N-1) + derangements ( N-2) )。
當開始回溯時，計算並返回數量。
示例
#include <bits/stdc++.h>
using namespace std;
int derangements(int N){
if (N == 0)
return 1;
if (N == 1)
return 0;
if (N == 2)
return 1;
return (N - 1) * (derangements(N - 1) + derangements(N - 2));
}
int main(){
int Numbers=5;
cout<<"Number of Derangements :"<<derangements(Numbers);
}輸出
Number of Derangements :44
更新於: 03-8-2020
538 瀏覽量
廣告