C ++中具有不同值的连续元素的数组计数
给定三个变量大小,即max_val,last_element作为输入。目标是找到可以以某种方式形成的不同数组的数量,以使它们具有size元素,具有介于1和max_val之间的元素,并且第一个元素始终为1,最后一个元素始终为max_val。还要确保没有两个连续的元素相同。
让我们通过示例来理解。
例如
输入-大小=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]。
输入- 大小=3max_val=2last_element=2
输出-具有不同值的连续元素的数组计数为:0
说明-不可能有3个元素并将[1,_,2]作为连续元素的数组,因为我们不能为中间元素填充1或2以外的任何内容,这将违反连续的不同元素的条件。
以下程序中使用的方法如下
在这种方法中,我们将使用动态编程和组合技术来查找此类数组的数量。
第一个和最后一个元素将固定为1和last_element。对于任何大小的数组,填充方法仅适用于大小为2的元素。
用于填充要在size-2位置填充的[1到max_val]个元素。方式将是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将为ways(size-1),因为last元素只能为1。
倒数第二个元素可以始终在1到max_val之间。
如果倒数第二个元素不是1,则方法将为(max_val-2)*ways(i-1),因为arri</sub>不能为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(intsize,intmax_val,intlast_element)接受所有输入,并返回包含具有不同值的连续元素的数组的计数。
将初始计数设为0。
以数组arr[Max_N]={0}存储填充数组的方式的数量。用0初始化arr[0],用1初始化arr[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]。
最后返回结果作为计数。
示例
#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 << "具有不同值的连续元素的数组的计数为: " << diff_val(size, max_val, last_element); return 0; }
如果我们运行上面的代码,它将生成以下输出-
输出结果
具有不同值的连续元素的数组的计数为: 5