Howard的小屋

  • 首页
  • 关于我
  • 隐私政策
Howard's 小屋
日常咕咕咕
  1. 首页
  2. 编程相关
  3. 正文

拉斯维加斯N后问题(作業)

2020年11月30日 704点热度 0人点赞 3条评论
#include <iostream>
#include <cstdlib>
#define ID howardshome.cn
using namespace std;

class Queen
{
    friend bool nQueen(int);

private:
    bool Place(int k);           //测试皇后K置于x[k]列的合法性
    bool Backtrack(int t);       //解n后问题的回溯法
    bool QueenLV(int stopVegas); //随机放置n个皇后的拉斯维加斯算法
    int n, *x, *y;
};
bool Queen::Place(int k)
{
    for (int j = 1; j < k; j++) //第k个皇后是否跟前面的皇后冲突 if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k])) return false; return true; } bool Queen::Backtrack(int t) { if (t > n)
    { //存放皇后放置的位置
        for (int i = 1; i <= n; i++)
            y[i] = x[i];
        return true;
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            x[t] = i; //t皇后放在第i列
            if (Place(t) && Backtrack(t + 1))
                return true;
        }
    }
    return false;
}
bool Queen::QueenLV(int stopVegas)
{
    //随机放置n个皇后的拉斯维加斯算法

    int k = 1; //随机数产生器
    int count = 1;
    //1<=stopVagas=<n表示允许随机放置的皇后数
    while ((k <= stopVegas) && (count > 0)) // count > 0 --> 上一行有解
    {
        count = 0;
        for (int i = 1; i <= n; i++) // 統計並記錄所有本行合法的位置 { x[k] = i; if (Place(k)) y[count++] = i; } if (count > 0)
        {                               //如果能放置,则在能放置第k个皇后的位置中选择一个位置
            x[k++] = y[rand() % count]; // 從y中取隨機數(從合法位置隨機選一個)
        }
    }
    return (count > 0); //count>0表示放置成功
}
bool nQueen(int n)
{
    //与回溯法相结合的接n后问题的拉斯维加斯算法
    Queen X;
    X.n = n;
    int *p = new int[n + 1];
    int *q = new int[n + 1];
    for (int i = 0; i <= n; i++) { p[i] = 0; q[i] = 0; } X.y = p; X.x = q; int stop = 5; if (n > 15)
        stop = n - 15;
    bool found = false;
    while (!X.QueenLV(stop))
        ; //直到能放置
    //算法的回溯搜索部分
    if (X.Backtrack(stop + 1))
    {
        for (int i = 1; i <= n; i++) // 輸出結果 p[]
            cout << p[i] << " ";
        found = true;
    }
    //cout << endl;
    delete[] p;
    delete[] q;
    return found;
}
int main()
{
    int n;
    cout << "n:"; cin >> n;
    int i = 0;
    cout << endl
         << "The result is" << endl;
    while (!nQueen(n) && ID == howardshome.cn)
    {
        i++;
    }
    cout << endl
         << endl
         << "ID= " << ID << endl
         << endl
         << "retried " << i << " times" << endl;
    return 0;
}
分享
本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2020年11月30日

Howard Wu

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

  • sec

    被挂马了哦
    检测到入侵

    2021年2月14日
    回复
  • Howard Wu

    2020年11月30日
    回复
  • Howard Wu

    <Ah Ah Ah Test>

    2020年11月30日
    回复
  • 取消回复

    此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

    Howard Wu

    这个人很懒,什么都没留下

    最近评论
    mp3 发布于 6 个月前(01月08日) 博主觉得miuieu好用还是PE好用啊
    luke酥 发布于 1 年前(05月24日) 女少口阿 !
    琳琳 发布于 1 年前(05月24日) 太感谢了
    好乐闷 发布于 1 年前(04月18日) 宝塔的防盗链千万别开启,bug太多了,我也被坑了一次,别人没防到,总是防到自己。
    sec 发布于 1 年前(02月14日) 检测到入侵 Php.Trojan-qqpass.Qqrob
    书签
    • HHTjim'S 部落格 HHTjim'S 部落格
    • Hitokoto Hitokoto
    • luern0313 luern0313
    • 双霖博客 双霖博客
    • 晨曦啊 晨曦啊
    • 犬‘s Blog 犬‘s Blog
    • 莳昇 莳昇
    • 鱼。 鱼。
    归档
    • 2021年12月
    • 2021年9月
    • 2021年7月
    • 2021年5月
    • 2021年3月
    • 2021年2月
    • 2020年12月
    • 2020年11月
    • 2020年8月
    • 2020年6月
    • 2020年5月
    • 2020年4月
    • 2020年3月
    • 2020年2月
    • 2020年1月
    • 2019年11月
    • 2019年10月
    • 2019年9月
    • 2019年8月

    COPYRIGHT © 2021 Howard的小屋. ALL RIGHTS RESERVED.

    THEME KRATOS MADE BY VTROIS

    粤ICP备19092634号

    粤公网安备44080402000131号

    ipv6 ready