Рубрики

Подсчитайте количество способов прыгнуть до конца

Дан массив чисел, где каждый элемент представляет максимальное количество переходов, которые можно сделать вперед от этого элемента. Для каждого элемента массива подсчитайте количество способов перехода из этого элемента для достижения конца массива. Если элемент равен 0, то перемещение через этот элемент невозможно. Элемент, который не может дойти до конца, должен иметь счет «-1».

Примеры:

Input : {3, 2, 0, 1}
Output : 2 1 -1 0
For 3 number of steps or jumps that 
can be taken are 1, 2 or 3. The different ways are:
3 -> 2 -> 1
3 -> 1

For 2 number of steps or jumps that 
can be taken are 1, or 2. The different ways are:
2 -> 1

For 0 number of steps or jumps that 
can be taken are 0. 
One cannot move forward from this point.

For 1 number of steps or jumps that 
can be taken are 1. But the element is at
the end so no jump is required.

Input : {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9}
Output : 52 52 28 16 8 -1 -1 4 2 1 0

Эта проблема является вариацией минимального количества прыжков, чтобы достичь конца (метод 3) . Здесь нам нужно сосчитать все способы достижения конца из каждой клетки.

Решение представляет собой модифицированную версию решения задачи « Минимальное количество переходов до конца» (метод 3) .
Эта задача направлена на подсчет различных способов перехода с каждого элемента, чтобы достичь конца. Для каждого элемента подсчет рассчитывается путем сложения подсчетов всех тех форвардных элементов, которые могут дойти до конца и до которых текущий элемент может достичь + 1 (если элемент может напрямую дойти до конца).

Алгоритм:

countWays(arr, n)
    Initialize array count_jump[n] = {0}

    count_jump[n-1] = 0
    for i = n-2 to 0
        if arr[i] >= (n-i-1)
         count_jump[i]++
        for j=i+1; j < n-1 && j <= arr[i]+i; i++
          if count_jump[j] != -1
             count_jump[i] += count_jump[j]
        if count_jump[i] == 0
         count_jump[i] = -1

    for i = 0 to n-1
        print count_jump[i]

C ++

// C ++ реализация для подсчета числа
// способов прыгнуть до конца
#include <bits/stdc++.h>

using namespace std;

  
// функция для подсчета способов перехода к
// достичь конца для каждого элемента массива

void countWaysToJump(int arr[], int n)

{

    // count_jump [i] сохраняем количество способов

    // arr [i] может дойти до конца

    int count_jump[n];

    memset(count_jump, 0, sizeof(count_jump));

  

    // Последний элемент не требует перехода.

    // Считаем способы прыгнуть за оставшиеся

    // элементы

    for (int i=n-2; i>=0; i--)

    {

        // если элемент может напрямую

        // прыгать до конца

        if (arr[i] >= n - i - 1)

            count_jump[i]++;

  

        // добавляем количество всех элементов

        // который может доходить до конца и arr [i] может

        // добраться до них

        for (int j=i+1; j < n-1 && j <= arr[i] + i; j++)

  

            // если элемент может дойти до конца, то добавить

            // его количество до count_jump [i]

            if (count_jump[j] != -1)

                 count_jump[i] += count_jump[j];

  

        // если arr [i] не может дойти до конца

        if (count_jump[i] == 0)

            count_jump[i] = -1;

    }

  

    // выводим count_jump для каждого

    // элемент массива

    for (int i=0; i<n; i++)

        cout << count_jump[i] << " ";

}

  
// Программа драйвера для тестирования выше

int main()

{

    int arr[] = {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9};

    int n = sizeof(arr) / sizeof(arr[0]);

    countWaysToJump(arr, n);

    return 0;

}

Джава

// Реализация Java для подсчета числа
// способов прыгнуть до конца

import java.util.Arrays;

  

class GFG {

      

    // функция для подсчета способов перехода к

    // достичь конца для каждого элемента массива

    static void countWaysToJump(int arr[], int n)

    {

          

        // count_jump [i] сохраняем количество способов

        // arr [i] может дойти до конца

        int count_jump[] = new int[n];

        Arrays.fill(count_jump, 0);

      

        // Последний элемент не требует перехода.

        // Считаем способы прыгнуть за оставшиеся

        // элементы

        for (int i = n-2; i >= 0; i--)

        {

              

            // если элемент может напрямую

            // прыгать до конца

            if (arr[i] >= n - i - 1)

                count_jump[i]++;

      

            // добавляем количество всех элементов

            // который может доходить до конца и arr [i] может

            // добраться до них

            for (int j = i+1; j < n-1 && j <= arr[i] + i; j++)

      

                // если элемент может дойти до конца, то добавить

                // его количество до count_jump [i]

                if (count_jump[j] != -1)

                    count_jump[i] += count_jump[j];

      

            // если arr [i] не может дойти до конца

            if (count_jump[i] == 0)

                count_jump[i] = -1;

        }

      

        // выводим count_jump для каждого

        // элемент массива

        for (int i = 0; i < n; i++)

            System.out.print(count_jump[i] + " ");

    }

      

    // код драйвера

    public static void main (String[] args)

    {

          

        int arr[] = {1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9};

        int n = arr.length;

          

        countWaysToJump(arr, n);

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Реализация Python3 для подсчета
# количество способов перейти к концу

  
# Функция для подсчета способов перехода к
# достичь конца для каждого элемента массива

def countWaysToJump(arr, n):

  

    # count_jump [i] сохранить количество способов

    # arr [i] может дойти до конца

    count_jump = [0 for i in range(n)]

  

    # Последний элемент не требует

    # прыгать. Считайте способы прыгать для

    # оставшиеся элементы

    for i in range(n - 2, -1, -1):

      

        # если элемент может напрямую

        # прыгать до конца

        if (arr[i] >= n - i - 1):

            count_jump[i] += 1

  

        # Добавить количество всех элементов

        # которые могут доходить до конца и обр

        # может добраться до них

        j = i + 1

        while(j < n-1 and j <= arr[i] + i):

  

            # если элемент может дойти до конца, то

            # добавить свой счетчик count_jump [i]

            if (count_jump[j] != -1):

                count_jump[i] += count_jump[j]

            j += 1

              

        # если arr [i] не может дойти до конца

        if (count_jump[i] == 0):

            count_jump[i] = -1

      

  

    # print count_jump для каждого

    # элемент массива

    for i in range(n):

        print(count_jump[i], end = " ")

  
# Код драйвера

arr = [1, 3, 5, 8, 9, 1, 0, 7, 6, 8, 9]

n = len(arr)

countWaysToJump(arr, n)

  
# Этот код предоставлен Anant Agarwal.

C #

// C # реализация для подсчета числа
// способов прыгнуть до конца

using System;

  

class GFG { 

      

    // функция для подсчета способов перехода к

    // достичь конца для каждого элемента массива

    static void countWaysToJump(int[] arr, int n) 

    

          

        // count_jump [i] сохраняем количество способов

        // arr [i] может дойти до конца

        int[] count_jump = new int[n];

          

        for(int i = 0; i < n; i++)

            count_jump[i] = 0;

          

      

        // Последний элемент не требует перехода.

        // Считаем способы прыгнуть за оставшиеся

        // элементы

        for (int i = n-2; i >= 0; i--) 

        

              

            // если элемент может напрямую

            // прыгать до конца

            if (arr[i] >= n - i - 1) 

                count_jump[i]++; 

      

            // добавляем количество всех элементов

            // который может доходить до конца и arr [i] может

            // добраться до них

            for (int j = i+1; j < n-1 && j <= arr[i] + i; j++) 

      

                // если элемент может дойти до конца, то добавить

                // его количество до count_jump [i]

                if (count_jump[j] != -1) 

                    count_jump[i] += count_jump[j]; 

      

            // если arr [i] не может дойти до конца

            if (count_jump[i] == 0) 

                count_jump[i] = -1; 

        

      

        // выводим count_jump для каждого

        // элемент массива

        for (int i = 0; i < n; i++) 

            Console.Write(count_jump[i] + " "); 

    

      

    // Код драйвера

    public static void Main () 

    

        int[] arr = {1, 3, 5, 8, 9,

                 1, 0, 7, 6, 8, 9}; 

        int n = arr.Length; 

        countWaysToJump(arr, n); 

    

  
// Этот код предоставлен ChitraNayal

PHP

<?php
// Реализация PHP для подсчета числа
// способов прыгнуть до конца

  
// функция для подсчета способов перехода к
// достичь конца для каждого элемента массива

function countWaysToJump($arr, $n)

{

    // count_jump [i] сохраняем количество способов

    // arr [i] может дойти до конца

    $count_jump;

    for($i = 0; $i < $n; $i++)

        $count_jump[$i] = 0;

  

    // Последний элемент не требует перехода.

    // Считаем способы прыгнуть за оставшиеся

    // элементы

    for ($i = $n - 2; $i >= 0; $i--)

    {

        // если элемент может напрямую

        // прыгать до конца

        if ($arr[$i] >= $n - $i - 1)

            $count_jump[$i]++;

  

        // добавляем количество всех элементов

        // который может доходить до конца и arr [i]

        // могу достучаться до них

        for ($j = $i + 1; $j < $n - 1 &&

             $j <= $arr[$i] + $i; $j++)

  

            // если элемент может дойти до конца, то

            // добавляем количество к count_jump [i]

            if ($count_jump[$j] != -1)

                $count_jump[$i] += $count_jump[$j];

  

        // если arr [i] не может дойти до конца

        if ($count_jump[$i] == 0)

            $count_jump[$i] = -1;

    }

  

    // выводим count_jump для каждого

    // элемент массива

    for ($i = 0; $i < $n; $i++)

        echo $count_jump[$i] . " ";

}

  
// Код драйвера

$arr = array(1, 3, 5, 8, 9, 1,

                0, 7, 6, 8, 9);

$n = count($arr);

countWaysToJump($arr, $n);

  
// Этот код предоставлен Rajput-Ji
?>

Выход:

52 52 28 16 8 -1 -1 4 2 1 0

Сложность времени: O (n 2 ) в худшем случае.

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчитайте количество способов прыгнуть до конца

0.00 (0%) 0 votes