分治法求假币非递归算法C++

分治法求假币的非递归算法可以使用迭代的方式来实现。具体步骤如下：

1. 定义一个栈，用于存储待处理的硬币序列。

2. 将原始硬币序列压入栈中。

3. 循环处理栈中的硬币序列，直到栈为空。

4. 取出栈顶的硬币序列，判断其长度是否大于1。

5. 如果长度大于1，则将该序列拆分成三等份，分别计算每份的重量。

6. 根据三份重量的大小关系，确定假币所在的范围。

7. 将假币所在范围的硬币序列压入栈中。

8. 重复步骤3-7，直到找到假币或者栈为空。

以下是C++代码实现：

#include <iostream>
#include <stack>
using namespace std;

int findFakeCoin(int n, int* coins) {
    stack<pair<int, int>> s;
    s.push(make_pair(0, n - 1)); // 将整个硬币序列入栈
    while (!s.empty()) {
        int left = s.top().first;
        int right = s.top().second;
        s.pop();
        if (left == right) return left; // 只剩一个硬币，即为假币
        int len = right - left + 1;
        int third = len / 3;
        int mid1 = left + third - 1;
        int mid2 = right - third + 1;
        int w1 = mid1 - left + 1; // 左侧硬币重量
        int w2 = mid2 - mid1; // 中间硬币重量
        int w3 = right - mid2 + 1; // 右侧硬币重量
        if (w1 > w2) { // 假币在左侧
            s.push(make_pair(left, mid1));
        } else if (w2 > w3) { // 假币在中间
            s.push(make_pair(mid1 + 1, mid2 - 1));
        } else { // 假币在右侧
            s.push(make_pair(mid2, right));
        }
    }
    return -1; // 未找到假币
}

int main() {
    int coins[] = { 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 };
    int n = sizeof(coins) / sizeof(int);
    int fakeCoin = findFakeCoin(n, coins);
    cout << "The fake coin is at position " << fakeCoin << endl;
    return 0;
}