資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 24 點遊戲
假設我們有四張卡片，這些卡片上分別寫著 1 到 9 之間的某個數字。我們需要檢查是否可以透過一些運算子（如 +、-、*、/）來得到 24。例如，如果我們有一些數字，比如 [4, 9, 2, 6]，那麼我們可以透過 (4 * 9) – (2 * 6) 得到 24，答案將為真。
為了解決這個問題，我們將遵循以下步驟：
- epsilon := 10.0^-5
- 定義一個函式 solve()，它將接收一個數組 v 作為引數。
- 如果 v 的大小為 1，則：
- 當 |v[0] - 24.0| <= epsilon 時返回 true
- 初始化 i := 0，當 i < v 的大小，更新 (i 增加 1)，執行：
- 初始化 j := 0，當 j < v 的大小，更新 (j 增加 1)，執行：
- 如果 i 等於 j，則：忽略以下部分，跳到下一個迭代
- 定義一個數組 res
- 初始化 k := 0，當 k < v 的大小，更新 (k 增加 1)，執行：
- 如果 i 不等於 k 且 j 不等於 k，則：
- 將 v[k] 插入到 res 的末尾
- 如果 i 不等於 k 且 j 不等於 k，則：
- 初始化 k := 0，當 k < 4，更新 (k 增加 1)，執行：
- 如果 operators[k] 等於 '+'，則：
- 將 v[i] + v[j] 插入到 res 的末尾
- 否則，如果 operators[k] 等於 '-'，則：
- 將 v[i] - v[j] 插入到 res 的末尾
- 否則，如果 operators[k] 等於 '*'，則：
- 將 v[i] * v[j] 插入到 res 的末尾
- 否則
- 將 v[i] / v[j] 插入到 res 的末尾
- 如果 solve(res) 返回 true，則：
- 返回 true
- 從 res 中刪除最後一個元素
- 如果 operators[k] 等於 '+'，則：
- 初始化 j := 0，當 j < v 的大小，更新 (j 增加 1)，執行：
- 返回 false
- 從主方法執行以下步驟：
- 定義一個數組 v
- 初始化 i := 0，當 i < nums 的大小，更新 (i 增加 1)，執行：
- 將 nums[i] 插入到 v 的末尾
- 返回 solve(v)
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char operators[4] = {'+', '-', '/', '*'};
double epsilon = pow(10.0, -5);
bool judgePoint24(vector<int>& nums) {
vector <double> v;
for(int i = 0; i < nums.size(); i++){
v.push_back(nums[i]);
}
return solve(v);
}
bool solve(vector <double> v){
if(v.size() == 1){
return abs(v[0] - 24.0) <= epsilon;
}
for(int i = 0; i < v.size(); i++){
for(int j = 0; j < v.size(); j++){
if(i == j) continue;
vector <double> res;
for(int k = 0; k < v.size(); k++){
if(i != k && j != k){
res.push_back(v[k]);
}
}
for(int k = 0; k < 4; k++){
if(operators[k] == '+'){
res.push_back(v[i] + v[j]);
}else if(operators[k] == '-'){
res.push_back(v[i] - v[j]);
}else if(operators[k] == '*'){
res.push_back(v[i] * v[j]);
}else{
res.push_back(v[i] / v[j]);
}
if(solve(res)) return true;
res.pop_back();
}
}
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {4,9,2,6};
cout << (ob.judgePoint24(v));
}輸入
{4,9,2,6}輸出
1
更新於: 2020年6月1日
1K+ 閱讀量
廣告