นับจำนวนวิธีที่จะข้ามไปยังจุดสิ้นสุดใน C++

กำหนดอาร์เรย์ของจำนวนบวก แต่ละองค์ประกอบแสดงถึงจำนวนการกระโดดสูงสุดที่สามารถทำได้จากดัชนีนั้นเพื่อไปถึงจุดสิ้นสุดของอาร์เรย์ เป้าหมายคือการหาจำนวนการกระโดดที่สามารถทำได้จากองค์ประกอบนั้นจนถึงจุดสิ้นสุด ถ้า 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] และสามารถเข้าถึงได้จากองค์ประกอบปัจจุบัน เพิ่ม 1 ในการนับนี้สำหรับวิธีสำหรับ arr[i] หากเราสามารถไปถึงจุดสิ้นสุดจาก arr[i] ได้โดยตรงด้วยการกระโดดเพียงครั้งเดียว

• ใช้อาร์เรย์จำนวนเต็ม arr[].

• ฟังก์ชัน reach_end(int arr[], int size) ใช้อาร์เรย์และส่งกลับจำนวนวิธีที่จะข้ามไปยังจุดสิ้นสุด

• นำอาร์เรย์ arr_2[] มาเก็บวิธีที่จะไปถึงจุดสิ้นสุดจากแต่ละองค์ประกอบของ arr[]

• เริ่มต้น arr_2[] ทั้งหมดด้วย 0 โดยใช้ memset(arr_2, 0, sizeof(arr_2))

• Traverse arr[] โดยใช้ a for loop จาก i=size-2 ถึง i=0 เนื่องจากจะไม่พิจารณาองค์ประกอบสุดท้าย

• ใช้ temp =size − i − 1 หาก temp> =arr[i] เราสามารถไปถึงจุดสิ้นสุดได้โดยตรงด้วยการกระโดดเพียงครั้งเดียว วิธีที่เพิ่มขึ้นนับสำหรับ arr[i] โดยใช้ arr_2[i]++

• สำหรับองค์ประกอบอื่นๆ ทั้งหมดที่สามารถไปถึงจุดสิ้นสุดและที่เราสามารถเข้าถึงได้จาก arr[i] ให้เพิ่มจำนวนวิธีใน arr_2[i]

• สำหรับการเคลื่อนที่ด้านบนโดยใช้ a for loop จาก j=i+1 ถึง j

• หาก arr_2[i] ยังคงเป็น 0 ให้ตั้งค่าเป็น -1 ซึ่งหมายความว่าไม่สามารถไปถึงจุดสิ้นสุดได้

• ในตอนท้ายของลูปทั้งหมดเราจะมี arr_2[] มีวิธีที่จะสิ้นสุดสำหรับแต่ละองค์ประกอบของ arr[]

• พิมพ์ arr_2 โดยใช้ for loop เป็นผลลัพธ์

ตัวอย่าง

#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