양수 배열이 제공됩니다. 각 요소는 해당 인덱스에서 배열의 끝에 도달하기 위해 수행할 수 있는 최대 점프 수를 나타냅니다. 목표는 해당 요소에서 끝까지 도달할 수 있는 점프 수를 찾는 것입니다. arr[]이 [ 1,2,3 ]이면 1개의 점프는 1이 될 수 있고 2개의 점프는 1 또는 2가 될 수 있고 3개의 점프는 1, 2 또는 3이 될 수 있습니다.
예를 들어
입력
arr[] = {1,2,3} 출력
Count of number of ways to jump to reach end are: 1 1 0
설명
For 1 we have jumps : 1, For 2 we have jumps 1 or 2, to reach the end we need just one jump of 1. For 3 we have jumps 1,2 or 3, as at its end we need no jumps.
입력
arr[] = {4,3,6,2} 출력
Count of number of ways to jump to reach end are: 4 2 1 0
설명
For 4 we have jumps : 1, 2, 3 or 4. To reach the end we need only 1,2 or 3. Ways will be 4−3−6−2, 4−6−2, 4−2, 4−3−2. Total 4. For 3 we have jumps 1, 2 or 3 to reach the end we need both. Ways will be 3−6−2, 3−2. Total 2. For 6 we have jumps 1 to 5, to reach the end we need 1. Ways will be 6−2. Total 1. For 2 we have jumps 1or 2, as at its end we need no jumps.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
각 요소 arr[i]에 대한 이 접근 방식에서 우리는 arr[i] 앞에 있고 현재 요소에서 도달할 수 있는 모든 요소에 대해 배열의 끝에 도달하는 방법의 수를 추가합니다. 한 번의 점프로 arr[i]에서 끝까지 직접 도달할 수 있는 경우 arr[i]의 방법에 대해 이 수에 1을 추가합니다.
-
정수 배열 arr[]를 가져옵니다.
-
Reach_end(int arr[], int size) 함수는 배열을 받아서 끝까지 점프하는 방법의 수를 반환합니다.
-
arr[]의 각 요소에서 끝에 도달하는 방법을 저장하려면 배열 arr_2[]를 사용하세요.
-
memset(arr_2, 0, sizeof(arr_2))를 사용하여 전체 arr_2[]를 0으로 초기화합니다.
-
마지막 요소가 고려되지 않으므로 i=size-2에서 i=0까지 for 루프를 사용하여 arr[]을 트래버스합니다.
-
temp =size − i − 1을 취하십시오. temp> =arr[i]이면 한 번의 점프로 끝 부분에 직접 도달할 수 있습니다. arr_2[i]++를 사용하여 arr[i]에 대한 증분 방법.
-
이제 끝에 도달할 수 있고 우리가 arr[i]에서 도달할 수 있는 다른 모든 요소에 대해 방법의 수를 arr_2[i]에 추가합니다.
-
j=i+1에서 j
-
여전히 arr_2[i]가 0이면 -1로 설정합니다. 이는 끝에 도달할 수 없음을 의미합니다.
-
모든 루프의 끝에서 우리는 arr[]의 각 요소에 대해 끝에 도달하는 방법을 갖는 rr_2[]를 갖게 됩니다.
-
결과로 for 루프를 사용하여 rr_2를 인쇄합니다.
예시
#include <bits/stdc++.h>
using namespace std;
void reach_end(int arr[], int size){
int arr_2[size];
memset(arr_2, 0, sizeof(arr_2));
for (int i = size−2; i >= 0; i−−){
int temp = size − i − 1;
if (arr[i] >= temp){
arr_2[i]++;
}
for (int j = i+1; j < size−1 && j <= arr[i] + i; j++){
if (arr_2[j] != −1){
arr_2[i] = arr_2[i] + arr_2[j];
}
}
if(arr_2[i] == 0){
arr_2[i] = −1;
}
}
cout<<"Count of number of ways to jump to reach end are: ";
for (int i=0; i < size; i++){
cout<<arr_2[i] << " ";
}
}
int main(){
int arr[] = {2, 3, 7, 1, 8, 9};
int size = sizeof(arr) / sizeof(arr[0]);
reach_end(arr, size);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of number of ways to jump to reach end are: 8 5 3 1 1 0