#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> using namespace std; vector<vector<float>> findStonePairs(const vector<float> &stones, float D) { vector<vector<float>> result; unordered_set<float> set; for (int i = 0; i < stones.size(); i++) { float target1 = stones[i] - D; if (set.count(target1)) { result.push_back(vector<float>{target1, stones[i]}); // weight } float target2 = stones[i] + D; if (set.count(target2)) { result.push_back(vector<float>{target2, stones[i]}); // weight } set.insert(stones[i]); } return result; } int main() { float d = 2; vector<float> weights_test1 = {1.2, 3.2, 1.3, 3.3, 6, 5.2}; vector<vector<float>> result_test1 = findStonePairs(weights_test1, d); cout << "test1:" << endl; for (int i = 0; i < result_test1.size(); i++) { for (int j = 0; j < result_test1[i].size(); j++) { cout << result_test1[i][j] << " "; } cout << endl; } return 1; }为什么结果与预期不同

可能是因为你在比较浮点数时使用了相等运算符，这在计算机中是不准确的。你可以使用一个足够小的数值epsilon来代替相等运算符，例如：

bool isEqual(float a, float b, float epsilon = 0.0001) {
    return fabs(a - b) < epsilon;
}

然后在比较浮点数时，使用这个函数来代替相等运算符。此外，你可能还需要按照一定的顺序对石头进行排序，以便在比较时能够保证正确的结果。

相关问题

优化这段代码#include <iostream> #include <iomanip> #include <stdio.h> #include <fstream> #include <string> #include <algorithm> #include <unordered_map> #include <map> #include <stack> #include <set> #include <vector> using namespace std; struct Production { char left; // 产生式的左部非终结符 string right; // 产生式的右部字符串 }; map<char, set<char>> firstSets; int main() { vector<Production> productions; ifstream infile("grammar.txt"); char left; string right; while (infile >> left >> right) { productions.push_back({ left, right }); } for (auto p : productions) { char left = p.left; string right = p.right; char firstChar = right[0]; if (isupper(firstChar)) { // 如果是非终结符 // 计算非终结符的first集合 set<char> firstSet = firstSets[firstChar]; for (int i = 0; i < right.length(); i++) { char ch = right[i]; if (isupper(ch)) { // 如果是非终结符 firstSet.insert(firstSets[ch].begin(), firstSets[ch].end()); if (firstSets[ch].find('$') == firstSets[ch].end()) { // 如果该非终结符没有空串 break; } } else { // 如果是终结符 firstSet.insert(ch); break; } } firstSets[left].insert(firstSet.begin(), firstSet.end()); } else { // 如果是终结符 firstSets[left].insert(firstChar); } } for (auto p : productions) { char left = p.left; cout << "First(" << left << ") = {"; for (auto ch : firstSets[left]) { cout << ch << ", "; } cout << "}" << endl; } }使得能正确求出frist集

以下是优化后的代码：

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

// 产生式结构体
struct Production {
    char left;  // 产生式的左部非终结符
    string right;  // 产生式的右部字符串
};

// 计算first集合
set<char> calcFirstSet(char ch, const vector<Production>& productions, map<char, set<char>>& firstSets) {
    // 如果该字符已经计算过first集合，直接返回
    if (firstSets.find(ch) != firstSets.end()) {
        return firstSets[ch];
    }

    set<char> result;

    // 遍历所有产生式，查找该字符作为左部的产生式
    for (auto p : productions) {
        if (p.left == ch) {
            // 如果右部第一个字符是终结符，则加入该字符
            if (!isupper(p.right[0])) {
                result.insert(p.right[0]);
            }
            // 如果右部第一个字符是非终结符，则计算该非终结符的first集合
            else {
                set<char> subResult = calcFirstSet(p.right[0], productions, firstSets);
                result.insert(subResult.begin(), subResult.end());

                // 如果该非终结符的first集合中包含空串，则计算下一个字符的first集合
                for (int i = 1; i < p.right.length() && subResult.find('$') != subResult.end(); i++) {
                    if (!isupper(p.right[i])) {
                        result.insert(p.right[i]);
                        break;
                    } else {
                        subResult = calcFirstSet(p.right[i], productions, firstSets);
                        result.insert(subResult.begin(), subResult.end());
                    }
                }
            }
        }
    }

    // 将计算得到的first集合插入到map中
    firstSets.insert(make_pair(ch, result));

    return result;
}

int main() {
    vector<Production> productions;
    ifstream infile("grammar.txt");

    // 读取产生式
    char left;
    string right;
    while (infile >> left >> right) {
        productions.push_back({ left, right });
    }

    map<char, set<char>> firstSets;

    // 计算每个非终结符的first集合
    for (auto p : productions) {
        if (isupper(p.right[0])) {
            set<char> result = calcFirstSet(p.left, productions, firstSets);
            firstSets.insert(make_pair(p.left, result));
        } else {
            firstSets.insert(make_pair(p.left, set<char>{p.right[0]}));
        }
    }

    // 输出每个非终结符的first集合
    for (auto p : productions) {
        char left = p.left;
        cout << "First(" << left << ") = {";
        for (auto ch : firstSets[left]) {
            cout << ch << ", ";
        }
        cout << "}" << endl;
    }
}

优化后的代码主要是将计算first集合的部分提取出来，封装成了一个函数`calcFirstSet`。在计算每个非终结符的first集合时，只需调用该函数进行计算即可。同时，在计算非终结符的first集合时，使用了递归的方式，可以很方便地计算出包含空串的情况。

代码#include <iostream> #include <unordered_set> #include <algorithm> #include <vector> using namespace std; vector<pair<int, int>> findStonePairs(vector<int> &weights, int d) { unordered_set<int> stoneSet; vector<pair<int, int>> pairs; for (int i = 0; i < weights.size(); i++) { int weight = weights[i]; if (stoneSet.find(weight - d) != stoneSet.end()) { auto j = find(weights.begin(), weights.end(), weight - d) - weights.begin(); pairs.push_back({weights[j], weights[i]}); } if (stoneSet.find(weight + d) != stoneSet.end()) { auto j = distance(weights.begin(), find(weights.begin(), weights.end(), weight + d)); pairs.push_back({weights[j], weights[i]}); } stoneSet.insert(weight); } return pairs; } int main() { int d = 2; vector<int> weights = {1, 3, 3, 5, 4, 2, 7, 1}; vector<pair<int, int>> pairs = findStonePairs(weights, d); for (auto p : pairs) { cout << "[" << p.first << ", " << p.second << "]" << endl; } // for (auto p : pairs) // { // cout << "[" << weights[p.first] << ", " << weights[p.second] << "]" << endl; // } return 0; }的时间复杂度

这段代码的时间复杂度为 O(n^2)，其中 n 为 weights 数组的长度。因为代码中使用了一个循环遍历 weights 数组，再在内部使用了两次 find 或 distance 函数查找 stoneSet 中是否存在特定的元素，这两个函数本质上也是一个循环遍历，因此总的时间复杂度就是 O(n^2)。