資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中具有不同值連續元素的陣列計數
給定三個變數size、max_val、last_element作為輸入。目標是找到可以形成的不同陣列的數量，這些陣列具有size個元素，元素在1到max_val之間，第一個元素始終為1，最後一個元素始終為max_val。還要確保沒有兩個連續元素相同。
讓我們透過例子來理解。
例如
輸入 - size = 5, max_val = 3, last_element = 3
輸出 - 具有不同值連續元素的陣列數量為：5
說明 - 陣列將是：
[ 1, 2, 3, 1, 3 ], [ 1, 2, 3, 2, 3 ], [ 1, 2, 1, 2, 3 ], [ 1, 3, 1, 2, 3 ], [ 1, 3, 2, 1, 3 ].
輸入 - size = 3 max_val = 2 last_element = 2
輸出 - 具有不同值連續元素的陣列數量為：0
說明 - 不可能有3個元素的陣列，並且具有[1, _, 2]作為連續元素，因為我們不能填充中間元素除了1或2以外的任何內容，這將違反連續不同元素的條件。
下面程式中使用的方法如下
- 在這種方法中，我們將使用動態規劃和組合數學來查詢此類陣列的數量。
- 第一個和最後一個元素將固定為1和last_element。對於任何大小的陣列，填充它的方法僅適用於size-2個元素。
- 對於填充[1到max_val]元素到size-2個位置，方法將是ways(max_val)= ways(size) / (max_val - 1)
- 對於每個範圍1到i，方法將是ways(i)=ways(size) / (max_val - 1) [ ways(size) = 最後一個元素可以用數字2到max_val填充的方法數量）。
- 如果last_element為1，則方法將為ways(size-1)，因為最後一個元素只能為1。
- 倒數第二個元素始終可以在1到max_val之間。
- 如果倒數第二個元素不是1，則方法將是(max_val-2)*ways(i-1)，因為arri不能為1或arri-1。
- 如果倒數第二個元素為1，則方法將是(max_val-1)*ways(i-1)，因為arri-1為1，而arri-2不為1。
- Ways(i)將是：(max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)
- 將變數size、max_val和last_element作為輸入。
- 函式diff_val(int size, int max_val, int last_element)獲取所有輸入並返回具有不同值連續元素的陣列數量。
- 將初始計數設定為0。
- 取陣列arr[Max_N] = { 0 }，儲存填充陣列的方法數量。將arr[0]初始化為0，arr[1]初始化為1。
- 從i=2遍歷到i<size。
- 取temp_1 = (max_val - 2) * arr[i - 1] 和 temp_2 = (max_val - 1) * arr[i - 2]
- 設定 arr[i] = temp_1 + temp_2。
- 如果last_element == 1，則設定count = (max_val - 1) * arr[size - 2]。
- 否則返回arr[size - 1]。
- 最後返回count作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
#define Max_N 109
int diff_val(int size, int max_val, int last_element) {
int count = 0;
int arr[Max_N] = {
0
};
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < size; i++) {
int temp_1 = (max_val - 2) * arr[i - 1];
int temp_2 = (max_val - 1) * arr[i - 2];
arr[i] = temp_1 + temp_2;
}
if (last_element == 1) {
count = (max_val - 1) * arr[size - 2];
} else {
return arr[size - 1];
}
return count;
}
int main() {
int size = 5;
int max_val = 3;
int last_element = 3;
cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
return 0;
}如果我們執行上述程式碼，它將生成以下輸出：
輸出
Count of arrays having consecutive element with different values are: 5
更新於：2021年1月29日
347 次瀏覽
廣告