24难题的解决之道

Question

我正在通过处理不同的问题来刷新我的C++，我决定尝试一种24局的解决方案。基本上给出4个数字，尝试使用运算符+、-、*、/、^达到24。但是，对于我的解决方案，我想使用一个通用的目标号、运算符和输入数。

速度很好，所以我更关心C++约定、STL的使用和干净的代码。

问题：

1. 这是否符合C++的标准约定？我来自Java，所以很多这样的习惯经常会延续到我的C++中。
2. 有什么更好的方法来利用STL吗？
3. 这代码干净吗？变量名有多清楚？现在，这个项目只是main的*.cpp文件、实用程序的*.hpp文件和CMake文件，但是如果要进行扩展，我需要更好的组织方法。

其中，flip_map( map )返回带交换键和值的新映射，map_keys( map )和map_values( map )分别返回键和值的新向量。

以下是代码：

#include <iostream>
#include <array>
#include <vector>
#include <random>
#include <map>
#include "Utilities.hpp"

typedef int Digit;

constexpr Digit numDigits{4};
constexpr Digit target{24};

typedef float (*Operator)(float, float);
typedef std::map<char, Operator> Operators;

// operators
float add(float a, float b) {return a+b;}
float subtract(float a, float b) {return a-b;}
float multiply(float a, float b) {return a*b;}
float divide(float a, float b) {return a/b;}
float power(float a, float b) {return powf(a,b);}

const Operators operators = {{'+', add}, {'-', subtract}, {'*', multiply}, {'/', divide}, {'^', power}};
const std::map<Operator, char> operators_inverse = flip_map(operators);

typedef std::array<Digit, numDigits> digits;
digits d;

void print_solution(const std::array<Digit, numDigits>& nums, std::vector<char> &ops) {
    std::string accum (numDigits-1, '(');
    for(unsigned i=0; i<numDigits-1; ++i) {
        accum += std::to_string(nums[i]);
        if (i!=0) accum += ')';
        accum += std::string(&ops[i], 1);
    }
    accum += std::to_string(nums[numDigits-1]);
    printf("%s\n",accum.c_str());
}

int main() {

    d = {8, 5, 6, 2};

    if(std::accumulate(d.begin(), d.end(), 0) == target) {
        std::vector<char> v(numDigits-1,'+');
        print_solution(d, v);
    }
    if(std::accumulate(d.begin(), d.end(), 1, multiply) == target) {
        std::vector<char> v(numDigits-1,'*');
        print_solution(d, v);
    }

    auto keys = map_keys(operators);
    auto ops = map_values(operators);
    std::sort(d.begin(), d.end());
    std::sort(ops.begin(), ops.end());
    do {
        do{
            float last = ops[0](d[0], d[1]);   // init with inner-most value

            for(unsigned i=1; i<numDigits-1; ++i) {  
                last = ops[i](d[i+1], last);
            }

            if(last == target) {
                std::vector<char> v;
                for(Operator o : ops) {
                    v.push_back(operators_inverse.at(o));
                }
                print_solution(d, v);
            }
        } while (std::next_permutation(d.begin(), d.end()));
    } while (std::next_permutation(ops.begin(), ops.end()));



    return 0;
}

以下是Utilities.hpp的来源：

#ifndef INC_24_SOLVER_UTILITIES_HPP
#define INC_24_SOLVER_UTILITIES_HPP

#include "stddef.h"
#include <array>
#include <map>
#include <vector>

// unused currently
template<size_t N, class T>
std::array<T, N> make_array(const T &v) {
    std::array<T,N> arr;
    arr.fill(v);
    return arr;
};

template<class T, class K>
std::map<T,K> flip_map(const std::map<K,T> &m) {
    std::map<T,K> flipped;
    for (auto i=m.begin(); i!=m.end(); ++i)
        flipped[i->second] = i->first;
    return flipped;
};

template<class T, class K>
std::vector<T> map_values(const std::map<K,T> &m) {
    std::vector<T> v;
    for(auto it = m.begin(); it != m.end(); ++it) {
        v.push_back(it->second);
    }
    return v;
};

template<class T, class K>
std::vector<K> map_keys(const std::map<K,T> &m) {
    std::vector<K> v;
    for(auto it = m.begin(); it != m.end(); ++it) {
        v.push_back(it->first);
    }
    return v;
};

#endif //INC_24_SOLVER_UTILITIES_HPP

Answer 1

让我感到奇怪的是，输入和目标都是整数，但是代码通过计算与float一起工作。我认为最好只处理整数类型(可能是unsigned long)，并拒绝不可表示的部分结果。忽略这样的结果是可以的，就像它们构成了一个正确解的一部分，它可以被重新排序，而没有分数或负的中间结果。

例如，目标为5，输入为3,6,10，那么(10/6)*3就会被忽略，但是程序仍然会找到(10*3)/6。

您可能需要编写一个等效于powf的整数(虽然在必要时可以使用std::pow，但您希望将结果舍入最近而不是截断)。

使用float的一个特殊问题是对成功的测试：

        if(last == target)

因为last是浮点数，所以target将被转换为浮点数以进行比较，计算中的任何不精确都可能导致拒绝有效的解决方案。