資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告