資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中游戲中最後一個怪物的最小最終生命值
問題陳述
給定 N 個怪物，每個怪物都有初始生命值 h[i]，它是一個整數。如果怪物的生命值大於 0，則該怪物還活著。
在每一輪中，一個隨機怪物會殺死另一個隨機怪物，被攻擊的怪物的生命值會減少攻擊怪物的生命值的數量。這個過程會持續到只剩下一個怪物為止。最後一個剩下的怪物的最小可能生命值是多少。
示例
如果輸入陣列是 {2, 14, 28, 56}，則輸出將是 2，因為當只有第一個怪物持續攻擊其餘 3 個怪物時，最後一個怪物的最終生命值將是 2，這是最小的。
演算法
我們可以使用以下 GCD 公式獲得最終答案：
H(min) = gcd(h1, h2, …, hn)
示例
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int getPossibleHealth(int* health, int n) {
int currentGcd = gcd(health[0], health[1]);
for (int i = 2; i < n; ++i) {
currentGcd = gcd(currentGcd, health[i]);
}
return currentGcd;
}
int main() {
int health[] = { 4, 6, 8, 12 };
int n = sizeof(health) / sizeof(health[0]);
cout << "Possible final health = " << getPossibleHealth(health, n) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Possible final health = 2
更新於: 2019-11-22
346 次瀏覽
廣告