c++ 跳一跳 贪心
时间: 2023-10-17 20:06:41 浏览: 55
贪心算法是一种基于贪心原则的算法,每一步都选择当前状态下最优的解,以期望最终能够得到全局最优解。关于c跳一跳游戏的贪心算法,有很多种实现方法。以下是一种可能的实现方法:
首先,需要定义一个阈值来确定什么时候跳跃。在c跳一跳游戏中,跳跃的目标是跳到方块的中心位置,因此可以通过测量当前方块和下一个方块的距离来决定跳跃的时机。当距离超过设定的阈值时,就可以执行跳跃。
接下来,遍历游戏中的所有方块。对于每个方块,计算当前方块和下一个方块的距离,如果距离超过阈值,则执行跳跃操作。然后更新当前方块位置为下一个方块位置。
重复上述步骤直到游戏结束。
相关问题
跳跃游戏c++贪心算法
跳跃游戏是一个贪心算法问题。在这个问题中,我们需要判断是否能够从数组的第0个位置跳跃到数组的最后一个位置。
我们可以使用贪心算法来解决这个问题。我们从第0个位置开始,一直跳到最后一个位置,每次选择能够跳跃最远的位置作为下一个跳跃点。我们使用一个变量max_index来记录当前能够跳到的最远位置。
具体步骤如下:
1. 创建一个空数组index,用于存储每个位置能够跳到的最远位置。
2. 遍历给定的数组nums,计算每个位置能够跳到的最远位置,并将其存入index数组。
3. 初始化变量jump为0,表示当前所在的位置。
4. 初始化变量max_index为index,表示当前能够跳到的最远位置。
5. 使用while循环,当jump小于index数组的大小且jump小于等于max_index时,执行循环体。
6. 在循环体中,如果max_index小于index[jump],则更新max_index为index[jump],表示当前能够跳得更远。
7. 每次循环结束后,将jump自增1。
8. 在循环结束后,判断jump是否等于index数组的大小,如果等于,则表示能够跳到最后一个位置,返回true,否则返回false。
代码如下所示:
```cpp
bool CanJump(std::vector<int>& nums) {
std::vector<int> index;
for (unsigned int i = 0; i < nums.size(); i++) {
index.push_back(i + nums[i]);
}
unsigned int jump = 0;
int max_index = index[0];
while (jump < index.size() && jump <= max_index) {
if (max_index < index[jump]) {
max_index = index[jump];
}
jump++;
}
if (jump == index.size()) {
return true;
}
return false;
}
```
单源最短路径贪心算法用c++写一份
下面是单源最短路径贪心算法的C++实现,使用了Dijkstra算法:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int, int> P;
vector<P> G[1001];
int d[1001];
void dijkstra(int s) {
memset(d, INF, sizeof(d));
d[s] = 0;
priority_queue<P, vector<P>, greater<P>> que;
que.push(P(0, s));
while(!que.empty()) {
P p = que.top(); que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0; i < G[v].size(); i++) {
int u = G[v][i].first, w = G[v][i].second;
if(d[u] > d[v] + w) {
d[u] = d[v] + w;
que.push(P(d[u], u));
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for(int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
G[a].push_back(P(b, c));
}
dijkstra(s);
for(int i = 1; i <= n; i++) {
if(d[i] == INF) cout << "INF" << endl;
else cout << d[i] << endl;
}
return 0;
}
```
其中,`G`是邻接表,`d`是存储最短路径的数组。在`dijkstra`函数中,首先将所有节点到源点的距离初始化为INF,将源点加入最小堆中。然后重复以下步骤:从最小堆中取出距离源点最近的节点,如果该节点已经更新过最短路径,跳过;否则,将该节点的相邻节点更新到最小堆中。最后,遍历所有节点,输出到源点的最短路径。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)