RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1375494
Accepted
Mikhailo
Mikhailo
Asked:2022-06-27 02:05:47 +0000 UTC2022-06-27 02:05:47 +0000 UTC 2022-06-27 02:05:47 +0000 UTC

比较器的错误在哪里?

  • 772

为了好玩,我通过枚举所有排列来勾勒出一个关于 N 个皇后排列的问题。一切都很完美,获得了常规棋盘所需的 92 个排列。

我想得到一组排列——嗯,有多少根本不同的排列不是通过对称或旋转获得的。为此,我还添加map了一个比较向量的比较器,如果可以从另一个获得,则在比较时表示false。审查了测试示例 - 它似乎工作正常。但是map排列结果是通过对称获得的——他说总共有 46 个组。这显然是错误的——应该是 12!

我只是看不到我的错误,有人可以帮助我了解我到底在哪里做错了吗?Comporator有问题吗?

这是代码,它很小:

#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>

using namespace std;

// Создание всех возможных расстановок с помощью симметрий
vector<vector<int>> makeV(const vector<int>& a) {
    const size_t N = a.size();
    vector<vector<int>> p(7, vector<int>(N));

    for (int i = 0; i < N; ++i) {
        p[0][i]            = int(N - 1 - a[i]); // H
        p[1][N - 1 - i]    = int(a[i]);         // V
        p[2][N - 1 - i]    = int(N - 1 - a[i]); // O
        p[3][a[i]]         = int(i);            // \s
        p[4][a[i]]         = int(N - 1 - i);    // ->
        p[5][N - 1 - a[i]] = int(i);            // <-
        p[6][N - 1 - a[i]] = int(N - 1 - i);    // /s
        }
    return p;
    }

// Класс для сравнения двух векторов (можно ли получить один
// из второго симметриями - тогда равны)
struct lessVec {

    bool operator()(const vector<int>& a, const vector<int>& b) const {
        if (a == b) return false;

        vector<vector<int>> p = makeV(a);

        // Если получается хоть одной симметрией - равны, вернуть false
        for (int i = 0; i < 7; ++i) if (b == p[i]) return false;

        // Обычное сравнение
        return a < b;
        }
    };

// true, если есть пара бьющих ферзей
bool fight(const vector<int>& p) {
    for (unsigned int i = 0; i < p.size() - 1; ++i) {
        for (unsigned int j = i + 1; j < p.size(); ++j) {
            if (int(j - i) == abs(p[j] - p[i])) return true;
            }
        }

    return false;
    }

// Решение для доски NxN
pair<int, int> solve(int N) {
    map<vector<int>, int, lessVec> m; // Сбор групп решений
    // Проверяю все перестановки
    vector<int> p(N);

    for (int i = 0; i < N; ++i) p[i] = i;

    int count = 0;  // Количество решений

    do {
        if (!fight(p)) {
            ++count;
            m[p]++;    // Сколько в группе решений
            }
        } while (next_permutation(p.begin(), p.end()));

    return make_pair(count, int(m.size()));
    }

int main() {
    for (int i = 8; i <= 8; ++i) {
        auto p = solve(i);
        cout << setw(2) << i << "  "
             << setw(7) << p.first << "  "
             << setw(7) << p.second << endl;
        }
    }
c++
  • 1 1 个回答
  • 10 Views

1 个回答

  • Voted
  1. Best Answer
    Stanislav Volodarskiy
    2022-06-27T02:24:57Z2022-06-27T02:24:57Z

    您在比较器中有错误。例如,您可以想出四个不同的位置a, b, c, d, a = b, c = d, a < c。d < b你在哪里可以推断出什么a < a。

    正确的比较器可以这样安排:

    def less(a, b):
        p_min = min(makeV(a))
        q_min = min(makeV(b))
        return p_min < q_min
    

    让我们引入一个等价关系。如果一个位置可以通过旋转和反射转换为另一个位置,则两个位置是等效的。所有位置都可以分组到等价类中。在每个班级中,我们挑选出一个典型的代表。稍后,当我们需要比较两个元素时,我们将比较它们的规范代表。

    选择规范代表的方式并不重要。重要的是两个等效位置具有相同的规范代表,而两个非等效位置具有不同的典型代表。例如,您可以选择通常意义上的班级中的最小位置。

    由于每个元素都有一个规范代表,并且由于规范代表的顺序满足所有必需的属性(传递性、反自反性、不对称性),因此新顺序也得到了很好的定义。

    • 6

相关问题

  • 编译器和模板处理

  • 指针。找到最小数量

  • C++,关于枚举类对象初始化的问题

  • 函数中的二维数组

  • 无法使用默认构造函数创建类对象

  • C++ 和循环依赖

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    我看不懂措辞

    • 1 个回答
  • Marko Smith

    请求的模块“del”不提供名为“default”的导出

    • 3 个回答
  • Marko Smith

    "!+tab" 在 HTML 的 vs 代码中不起作用

    • 5 个回答
  • Marko Smith

    我正在尝试解决“猜词”的问题。Python

    • 2 个回答
  • Marko Smith

    可以使用哪些命令将当前指针移动到指定的提交而不更改工作目录中的文件?

    • 1 个回答
  • Marko Smith

    Python解析野莓

    • 1 个回答
  • Marko Smith

    问题:“警告:检查最新版本的 pip 时出错。”

    • 2 个回答
  • Marko Smith

    帮助编写一个用值填充变量的循环。解决这个问题

    • 2 个回答
  • Marko Smith

    尽管依赖数组为空,但在渲染上调用了 2 次 useEffect

    • 2 个回答
  • Marko Smith

    数据不通过 Telegram.WebApp.sendData 发送

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5