Cho một mảng các số dương. Mỗi phần tử đại diện cho số bước nhảy tối đa có thể được thực hiện từ chỉ mục đó để đến cuối mảng. Mục đích là để tìm số lần nhảy có thể được thực hiện từ phần tử đó để đạt được điểm cuối cùng. Nếu arr [] là [1,2,3] thì đối với 1 lần nhảy có thể là 1, đối với 2 lần nhảy có thể là 1 hoặc 2 và đối với 3 lần nhảy có thể là 1, 2 hoặc 3.
Ví dụ
Đầu vào
arr[] = {1,2,3} Đầu ra
Count of number of ways to jump to reach end are: 1 1 0
Giải thích
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.
Đầu vào
arr[] = {4,3,6,2} Đầu ra
Count of number of ways to jump to reach end are: 4 2 1 0
Giải thích
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.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này đối với mỗi phần tử arr [i], chúng tôi sẽ thêm số lượng các cách để đến cuối mảng cho tất cả các phần tử đứng trước arr [i] và có thể truy cập được từ phần tử hiện tại. Thêm 1 vào số này để biết các cách cho arr [i] nếu chúng ta có thể trực tiếp đến điểm kết thúc từ arr [i] trong một bước nhảy.
-
Lấy một mảng số nguyên arr [].
-
Hàm reach_end (int arr [], int size) nhận một mảng và trả về số lượng các cách để nhảy đến kết thúc.
-
Lấy mảng arr_2 [] để lưu trữ các cách đi đến cuối mỗi phần tử của arr [].
-
Khởi tạo toàn bộ arr_2 [] bằng 0 bằng memset (arr_2, 0, sizeof (arr_2)).
-
Traverse arr [] bằng cách sử dụng vòng lặp for từ i =size-2 đến i =0, vì phần tử cuối cùng sẽ không được xem xét.
-
Lấy temp =size - i - 1. Nếu temp> =arr [i] thì chúng ta có thể trực tiếp đến phần cuối bằng một bước nhảy. Số cách tăng dần cho arr [i] bằng arr_2 [i] ++.
-
Bây giờ đối với tất cả các phần tử khác có thể tiếp cận đến cuối và chúng ta có thể tiếp cận từ arr [i], hãy thêm số lượng các cách vào arr_2 [i].
-
Đối với thao tác trên bằng cách sử dụng vòng lặp for từ j =i + 1 đến j
-
Nếu arr_2 [i] vẫn là 0 thì hãy đặt nó thành −1, có nghĩa là nó không thể kết thúc.
-
Ở cuối tất cả các vòng lặp, chúng ta sẽ có arr_2 [] có nhiều cách để đạt được kết thúc cho mỗi phần tử của arr [].
-
Kết quả là in arr_2 bằng vòng lặp for.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of number of ways to jump to reach end are: 8 5 3 1 1 0