数据结构
网络
关系数据库管理系统(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 次浏览
广告