นับจำนวนวิธีกระโดดถึงปลายอาร์เรย์ด้วย C++

ได้รับอาร์เรย์จำนวนบวก แต่ละสมาชิกแทนจำนวนกระโดดสูงสุดที่ทำได้จาก index นั้นเพื่อไปถึงปลายอาร์เรย์ เป้าหมายคือหาจำนวนวิธีกระโดดจากสมาชิกนั้นๆ เพื่อไปถึงปลาย ถ้า arr[] = [1,2,3] แล้วสำหรับ 1 กระโดดได้ 1 ครั้ง สำหรับ 2 กระโดดได้ 1 หรือ 2 ครั้ง สำหรับ 3 กระโดดได้ 1, 2 หรือ 3 ครั้ง

ตัวอย่าง

Input

arr[] = {1,2,3}

Output

Count of number of ways to jump to reach end are: 1 1 0

Explanation

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.

Input

arr[] = {4,3,6,2}

Output

Count of number of ways to jump to reach end are: 4 2 1 0

Explanation

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 1 or 2, as at its end we need no jumps.

วิธีการที่ใช้ในโปรแกรม

สำหรับแต่ละสมาชิก arr[i] จะบวกจำนวนวิธีไปถึงปลายของสมาชิกที่อยู่ข้างหน้าและเข้าถึงได้จากสมาชิกปัจจุบัน บวก 1 เข้าไปสำหรับวิธีของ arr[i] ถ้าสามารถกระโดดถึงปลายได้ในครั้งเดียว

• รับอาร์เรย์จำนวนเต็ม arr[]
• ฟังก์ชัน reach_end(int arr[], int size) คืนค่าจำนวนวิธีกระโดดถึงปลาย
• สร้างอาร์เรย์ arr_2[] เก็บวิธีไปถึงปลายจากแต่ละสมาชิก
• กำหนด arr_2[] ทั้งหมดเป็น 0 ด้วย memset
• วนลูป arr[] จาก i=size-2 ถึง i=0 (สมาชิกสุดท้ายไม่พิจารณา)
• คำนวณ temp = size - i - 1 ถ้า temp >= arr[i] แสดงว่ากระโดดถึงปลายได้ในครั้งเดียว เพิ่ม arr_2[i]++
• สำหรับสมาชิกอื่นที่ไปถึงปลายได้และเข้าถึงได้จาก arr[i] บวกจำนวนวิธีเข้า arr_2[i]
• วนลูป j=i+1 ถึง j<size-1 และ j<=arr[i]+i ถ้า arr_2[j] != -1 บวกเข้า arr_2[i]
• ถ้ายังเป็น 0 ตั้งเป็น -1 (ไม่สามารถไปถึงปลายได้)
• เมื่อลูปจบ arr_2[] จะมีจำนวนวิธีสำหรับแต่ละสมาชิก
• พิมพ์ arr_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;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of number of ways to jump to reach end are: 8 5 3 1 1 0