数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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]之后且可以从当前元素到达的元素到达数组末尾的方式的数量。如果我们可以从arr[i]直接一步跳到末尾，则为arr[i]的方式计数加1。
取一个整数数组arr[]。
函数reach_end(int arr[], int size)接收一个数组并返回跳跃到达末尾的方式数量。
取数组arr_2[]来存储从arr[]的每个元素到达末尾的方式。
使用memset(arr_2, 0, sizeof(arr_2))将整个arr_2[]初始化为0。
使用for循环从i=size-2遍历到i=0，因为最后一个元素不会被考虑。
取temp = size − i − 1。如果temp>=arr[i]，那么我们可以使用一步直接到达末尾。使用arr_2[i]++递增arr[i]的方式计数。
现在，对于所有其他可以到达末尾且可以从arr[i]到达的元素，将方式计数添加到arr_2[i]。
对于上面的遍历，使用for循环从j=i+1到j<size−1和j<=arr[i]+i。如果任何arr[j]不是-1，则将其添加到arr_2[i]。
如果arr_2[i]仍然为0，则将其设置为-1，这意味着它无法到达末尾。
在所有循环结束时，arr_2[]将包含arr[]每个元素到达末尾的方式。
使用for循环打印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;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of number of ways to jump to reach end are: 8 5 3 1 1 0
更新于：2021年1月5日
271 次查看
广告