C++에서 값이 다른 연속 요소가 있는 배열 수

<시간/>

3개의 변수 크기, max_val, last_element가 입력으로 주어집니다. 목표는 크기 요소를 갖고 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 ].

입력 - 크기 =3 max_val =2 last_element =2

출력 - 다른 값을 가진 연속 요소가 있는 배열의 개수는 다음과 같습니다. 0

설명 - 3개의 요소와 [ 1, _, 2 ]를 연속 요소로 갖는 배열은 불가능합니다. 중간 요소에 대해 1 또는 2를 제외하고는 아무것도 채울 수 없고 이것은 연속적인 다른 요소의 조건을 위반할 것이기 때문입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서 우리는 이러한 배열 개수를 찾기 위해 동적 프로그래밍 및 조합을 사용할 것입니다.
첫 번째와 마지막 요소는 1과 last_element로 고정됩니다. 모든 크기의 배열에 대해 채우는 방법은 크기 2 요소에만 해당됩니다.
[1 ~ max_val] 요소를 크기 2자리에 채울 때 사용합니다. 방법은 way(max_val)=way(size) / (max_val - 1)
각 범위 1에서 i에 대해 way는 way(i)=ways(size) / (max_val - 1) [ way(size) =마지막 요소가 2에서 max_val까지의 숫자로 채워질 수 있는 방법의 수입니다.
last_element가 1이면 마지막 요소는 1일 수 있으므로 way는 way(크기-1)가 됩니다.
마지막 두 번째 요소는 항상 1과 max_val 사이일 수 있습니다.
두 번째 마지막 요소가 1이 아니면 way는 (max_val-2)*ways(i-1)가 됩니다. arr_i는 1 또는 arr_i-1
마지막 두 번째 요소가 1이면 way는 (max_val-1)*ways(i-1) as arr_i-1입니다. 는 1이고 arr_i-2입니다. 1이 아닙니다.
Ways(i):- (max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)
변수 크기, 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 까지 순회
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[크기 - 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 << "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