如何用C++实现最高效的金额（纸币/筹码）分配功能？

问题背景 #

我正在优化自己开发的C++ Craps游戏，其中筹码分配模块需要处理12种不同类型的筹码，当前代码约90行，希望简化实现。由于纸币分配逻辑与筹码分配几乎一致，且仅需处理4种纸币类型，以此为示例提出问题：

目前我有两种实现方式：一种是通过if/else链判断适配的纸币面额；另一种基于map和map.upper_bound实现，但效率不如前者（可能对该概念不够熟悉）。两种方式似乎都需要使用floor向下取整、fmod取余来循环处理金额直至分配完成，但不确定是否必要。

我想了解：

• 实现该功能的最高效方式是什么？
• if/else链是否是通用最优方案？
• map是否有未掌握的特性可优化实现？
• 是否存在其他更优的实现思路？

当前两种实现方式 #

方式一：if/else链判断 #

#include <iostream>
#include <map>
#include <math.h>
#include <iomanip>
using namespace std;

int main()
{
    int dollar1 = 0;
    int dollar5 = 0;
    int dollar10 = 0;
    int dollar100 = 0;
    float money;
    int itFirst;
    int itSecond;
    float moneyhold;
    std::cout << "What is the amount in $ you want?" << endl;
    cin >> money;
    while (money) {
        if (money / 100 >= 1) {
            moneyhold = floor(money / 100);
            std::cout << std::fixed;
            std::cout << std::setprecision(0);
            money = fmod(money, 100);
        }
        else if (money / 10 >= 1) {
            moneyhold = floor(money / 10);
            std::cout << std::fixed;
            std::cout << std::setprecision(0);
            money = fmod(money, 10);
        }
        else if (money / 5 >= 1) {
            moneyhold = floor(money / 5);
            std::cout << std::fixed;
            std::cout << std::setprecision(0);
            money = fmod(money, 5);
        }
        else if (money / 1 >= 1) {
            moneyhold = floor(money / 1);
            std::cout << std::fixed;
            std::cout << std::setprecision(0);
            money = fmod(money, 1);
        }
        if (money < 1) {
            money = 0;
        }
    }
    cout << "You have " << dollar1 << " one dollar bills, " << dollar5 << " five dollar bills, " << dollar10 << " ten dollar bills, and " << dollar100 << " hundred dollar bills";
}

方式二：基于map的实现 #

#include <iostream>
#include <map>
#include <math.h>
#include <iomanip>
using namespace std;

int main()
{
    int dollar1 = 3;
    int dollar5 = 5;
    int dollar10 = 7;
    int dollar100 = 10;
    std::map<int, int> am{
    { 1,dollar1 },
    { 5,dollar5 },
    { 10,dollar10 },
    { 100,dollar100}
};
    float money;
    int itFirst;
    int itSecond;
    float placehold;
    std::cout << "What is the amount in $ you want?" << endl;
    cin >> money;
    while (money) {
        auto iter = am.upper_bound(money);

        if (iter != am.begin())
        {
            --iter;
            itFirst = iter->first;
            itSecond = iter->second;
        }
        placehold = floor(money / itFirst);
        money = fmod(money, itFirst);
        if (itFirst == 1) {
            dollar1 = itSecond + placehold;
        }
        else if (itFirst == 5) {
            dollar5 = itSecond + placehold;
        }
        else if (itFirst == 10) {
            dollar10 = itSecond + placehold;
        }
        else if (itFirst == 100) {
            dollar100 = itSecond + placehold;
        }
        if (money < 1) {
            money = 0;
        }

    }
    cout << "You have " << dollar1 << " one dollar bills, " << dollar5 << " five dollar bills, " << dollar10 << " ten dollar bills, and " << dollar100 << " hundred dollar bills";}

优化方案与解答 #

首先解决核心问题：避免浮点数精度误差 #

原代码用float处理金额会导致精度问题（比如100.0可能被存储为99.9999999），进而影响floor和fmod的结果。正确的做法是用整数表示金额：将美元转换为分（比如$100.50转为10050分），用int或long long处理，这样除法和取余都是整数运算，不需要floor和fmod，效率更高且无精度问题。

最高效的实现方式：预定义降序面额数组 #

对于固定面额的分配场景（比如纸币、筹码），贪心算法+降序面额数组是最优解，兼具效率和可维护性：

• 效率：数组遍历是CPU缓存友好的线性操作，分支少，比if/else链更简洁，比map的红黑树查找高效得多。
• 可维护性：新增或修改面额只需修改数组，12种筹码也不会导致代码膨胀。

优化后的代码示例（纸币分配）

#include <iostream>
#include <vector>
#include <utility> // for pair

using namespace std;

int main() {
    // 存储面额与对应数量，按面额降序排列
    vector<pair<int, int>> denominations = {
        {100, 10}, // 初始10张100美元
        {10, 7},   // 初始7张10美元
        {5, 5},    // 初始5张5美元
        {1, 3}     // 初始3张1美元
    };

    cout << "请输入要分配的金额（美元）：";
    float input_money;
    cin >> input_money;

    // 转换为整数分，避免浮点数误差
    long long total_cents = static_cast<long long>(input_money * 100 + 0.5);

    for (auto& [value, count] : denominations) {
        if (total_cents <= 0) break;

        // 计算当前面额可分配的数量（注意转换为美元的分：1美元=100分）
        long long value_cents = value * 100;
        long long num = total_cents / value_cents;

        if (num > 0) {
            count += num;
            total_cents -= num * value_cents;
        }
    }

    // 输出结果
    cout << "分配后：\n";
    for (const auto& [value, count] : denominations) {
        cout << count << " 张 " << value << " 美元纸币\n";
    }

    return 0;
}

对问题的逐一解答 #

1. if/else链是否是通用最优方案？
   不是。对于少量面额（比如4种），if/else的分支预测效率可能不错，但当面额数量增加到12种时，代码会变得冗长、重复，维护成本极高。而且新增面额需要新增分支，扩展性差。

2. map是否有未掌握的特性可优化实现？
   原代码的map用法存在两个问题：

   • std::map是升序存储的红黑树，upper_bound后需要往前迭代，查找开销大；
   • 没有利用map存储数量的特性，还要额外写if/else更新外部变量。
     如果一定要用有序容器，推荐用vector<pair<int, int>>按降序排序，直接遍历，效率远高于map。map仅适合动态增减面额的场景，但你的筹码/纸币面额是固定的，完全不需要map。

3. 其他更优思路？

   • 用std::array代替vector：如果面额数量固定（比如12种筹码），std::array比vector更高效，因为是栈分配，无堆内存开销。
   • 预计算面额的分单位：提前把所有面额转换为分，避免循环中重复计算。

内容的提问来源于stack exchange，提问作者Dragon Lord