資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究最少跳躍次數問題
此問題給出正整數列表。每個整數表示從當前元素可以進行的最大步數。從第一個元素開始，我們必須找到到列表末尾項的最少要跳的次數。
對於動態規劃方法，可以定義一個 jumps 陣列來儲存所需的最少跳躍次數。類似 jumps[i] 的值，它表示從第 0 個索引需要多少最少跳躍次數來達到陣列的第 i 個索引。
輸入和輸出
Input:
A list of integers. {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output:
The minimum number of jumps to reach the end location. It is 3.
Start from value 1, go to 3. then jumps 3 values and reach 8. then jump 8 values and reach the last element.演算法
minPossibleJump(list, n)
輸入：數字陣列、陣列中的元素數量。
輸出：到末尾所需的最少跳躍次數。
Begin define an array named jump of size n if n = 0 or list[0] = 0, then return ∞ jump[0] := 0 for i := 1 to n, do jumps[i] := ∞ for j := 0 to i, do if i <= j + list[j] and jump[j] ≠ ∞, then jump[i] := minimum of jump[i] and (jump[j] + 1) break the loop done done return jump[n-1] End
示例
#include<iostream>
using namespace std;
int min(int x, int y) {
return (x < y)? x: y;
}
int minPossibleJump(int list[], int n) {
int *jumps = new int[n]; // dynamically create jumps array to store steps
if (n == 0 || list[0] == 0)
return INT_MAX;
jumps[0] = 0;
for (int i = 1; i < n; i++) {
jumps[i] = INT_MAX; //initially set jumps as infinity
for (int j = 0; j < i; j++) {
if (i <= j + list[j] && jumps[j] != INT_MAX) {
jumps[i] = min(jumps[i], jumps[j] + 1);
break;
}
}
}
return jumps[n-1];
}
int main() {
int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int size = 11;
cout << "Minimum number of jumps to reach end is: "<< minPossibleJump(list,size);
return 0;
}輸出
Minimum number of jumps to reach end is: 3
更新於： 17-6 月 -2020
755 次瀏覽
廣告