日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
全排列的應(yīng)用：正方體的組成與八皇后

前言

給定一個(gè)含有8個(gè)數(shù)字的數(shù)組，判斷有沒(méi)有可能把這8個(gè)數(shù)字分別放到正方體的8個(gè)頂點(diǎn)上，使得正方體上三組相對(duì)面上的4個(gè)頂點(diǎn)的和都相等。

成都創(chuàng)新互聯(lián)擁有一支富有激情的企業(yè)網(wǎng)站制作團(tuán)隊(duì)，在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)深耕十多年，專業(yè)且經(jīng)驗(yàn)豐富。十多年網(wǎng)站優(yōu)化營(yíng)銷(xiāo)經(jīng)驗(yàn)，我們已為超過(guò)千家中小企業(yè)提供了成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)解決方案，按需網(wǎng)站建設(shè)，設(shè)計(jì)滿意，售后服務(wù)無(wú)憂。所有客戶皆提供一年免費(fèi)網(wǎng)站維護(hù)!

本文就跟大家分享下這個(gè)問(wèn)題的解決方案，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

正方體的組成

初次看到這個(gè)問(wèn)題，很多開(kāi)發(fā)者可能會(huì)比較蒙，一時(shí)間無(wú)法找到切入點(diǎn)。那我們就先畫(huà)個(gè)正方體出來(lái)，給每個(gè)頂點(diǎn)標(biāo)記a1, a2 ,a3 ,...., a8。如下圖所示：

iShot_2023-06-26_07.36.45

實(shí)現(xiàn)思路

有了圖之后，我們?cè)谧鲞M(jìn)一步的分析，這個(gè)正方體有6個(gè)面，3組相對(duì)的面（上下、前后、左右）：

  • a1, a2, a4, a3 | a5, a6, a8, a7
  • a1, a5, a6, a2 | a3, a4, a8, a7
  • a1, a3, a7, a5 | a2, a4, a8, a6

有了這些條件后，再次結(jié)合題意，我們可知：只需要將8個(gè)數(shù)字分別放入正方體的8個(gè)頂點(diǎn)中，判斷三組相對(duì)面的頂點(diǎn)和是否都相等，這個(gè)問(wèn)題就解決了。

8個(gè)數(shù)字分別放到8個(gè)頂點(diǎn)上，所有數(shù)字都有可能放入任意一個(gè)頂點(diǎn)。換言之就是求這8個(gè)數(shù)字的所有排列，我的另一篇文章實(shí)現(xiàn)字符串的排列算法詳細(xì)講解了這個(gè)算法的實(shí)現(xiàn)思路，此處不過(guò)多贅述。

分析到這里，我們就得出了一個(gè)完整的實(shí)現(xiàn)思路：

  • 求出給定數(shù)組中8個(gè)數(shù)字的所有排列
  • 遍歷所有排列，將每個(gè)排列中的元素映射到變量中(a1, a2, ..., a8)
  • 判斷8個(gè)點(diǎn)組成的三組相對(duì)面的頂點(diǎn)和是否相等

實(shí)現(xiàn)代碼

分析出思路后，我們就可以將上述思路轉(zhuǎn)換成代碼了，如下所示：

/**
   * 能否構(gòu)成正方體
   * @param nums
   */
  public isCubePossible(nums: Array): boolean {
    if (nums.length !== 8) {
      return false;
    }
    // 獲取8個(gè)點(diǎn)的所有排列
    const list = this.permute(nums.join(""));
    for (let i = 0; i < list.length; i++) {
      // 將當(dāng)前組合中的點(diǎn)轉(zhuǎn)為number類型放入item
      const item: Array = [];
      for (let j = 0; j < list[i].length; j++) {
        item.push(+list[i][j]);
      }
      // 從當(dāng)前組合中獲取正方體的8個(gè)點(diǎn)
      const [a1, a2, a3, a4, a5, a6, a7, a8] = item;
      // 判斷正方體三組相對(duì)面上的點(diǎn)相加是否相等
      if (
        a1 + a2 + a4 + a3 === a5 + a6 + a8 + a7 &&
        a1 + a5 + a6 + a2 === a3 + a4 + a8 + a7 &&
        a1 + a3 + a7 + a5 === a2 + a4 + a8 + a6
      ) {
        return true;
      }
    }
    return false;
  }

上述代碼中沒(méi)有列舉permute方法的具體實(shí)現(xiàn)，對(duì)此感興趣的開(kāi)發(fā)者請(qǐng)移步：ArrayOfStrings.ts

八皇后問(wèn)題

在一個(gè)8*8的棋盤(pán)上放置八個(gè)皇后，使得它們彼此之間不會(huì)互相攻擊（即不在同一行、同一列或同一對(duì)角線上），總共有多少種擺法？如下圖所示列舉了其中一種擺法：

iShot_2023-06-26_11.40.41

實(shí)現(xiàn)思路

分析題目后 ，我們知道了兩個(gè)皇后不能處在同一行，那么肯定是每個(gè)皇后獨(dú)占一行。那我們就先把皇后定義出來(lái)，用一個(gè)數(shù)組來(lái)表示皇后在棋盤(pán)上的列號(hào)，分別用0～7（棋盤(pán)上有8個(gè)皇后）對(duì)這個(gè)數(shù)組進(jìn)行初始化。

棋盤(pán)上每一行所放置的皇后，它都可以放在這一行的任意位置。很顯然，這也需要用到全排列求出它的所有放置組合。因?yàn)槲覀冇玫牟煌瑪?shù)字對(duì)數(shù)組進(jìn)行的初始化，所以任意兩個(gè)皇后肯定不同列。

因此，我們只需要判斷每一組排列對(duì)應(yīng)的8個(gè)皇后是不是在同一條對(duì)角線上，即：對(duì)于數(shù)組的兩個(gè)下標(biāo)i和j，是否有i-j === queens[i] - queens[j] || j-i === queens[j] - queens[i]，這個(gè)問(wèn)題就得到了解決。

我們來(lái)寫(xiě)一下實(shí)現(xiàn)思路：

  • 定義皇后數(shù)組，分別用0～7對(duì)這個(gè)數(shù)組進(jìn)行初始化
  • 求出這個(gè)數(shù)組的所有排列
  • 遍歷所有排列，判斷每一個(gè)排列是否滿足不在同一對(duì)角線的條件
  • 遍歷滿足條件的排列，對(duì)棋盤(pán)進(jìn)行填充（將皇后放置在棋盤(pán)上）

實(shí)現(xiàn)代碼

我們將上述思路轉(zhuǎn)換為代碼，如下所示：

public eightQueens(): Array>> {
    const queens = [0, 1, 2, 3, 4, 5, 6, 7];
    const solutions: Array>> = [];
    // 獲取所有組合
    const list = this.permute(queens.join(""));
    for (let i = 0; i < list.length; i++) {
      // 求出的組合中元素值為string類型的，這里需要將其轉(zhuǎn)為number類型
      const item: Array = [];
      for (let j = 0; j < list[i].length; j++) {
        item.push(+list[i][j]);
      }
      // 不在對(duì)角線上
      if (this.isValidPlacement(item)) {
        const solution: Array> = [];
        // 遍歷此組合，取出皇后的擺放位置
        for (let j = 0; j < item.length; j++) {
          const col = item[j];
          const row: Array = Array(8).fill(0);
          row[col] = 1;
          solution.push(row);
        }
        solutions.push(solution);
      }
    }
    return solutions;
  }
  
   /**
   * 判斷當(dāng)前組合是否滿足排列要求（不在對(duì)角線上）
   * @param queens
   * @private
   */
  private isValidPlacement(queens: Array) {
    for (let i = 0; i < queens.length; i++) {
      for (let j = i + 1; j < queens.length; j++) {
        if (Math.abs(queens[i] - queens[j]) === Math.abs(i - j)) {
          // 在對(duì)角線上
          return false;
        }
      }
    }
    return true;
  }

測(cè)試用例

我們用一個(gè)例子來(lái)校驗(yàn)下上述代碼能否正常執(zhí)行。

const arrayOfStrings = new ArrayOfStrings();
console.log(
  "能否構(gòu)成正方體",
  arrayOfStrings.isCubePossible([1, 2, 3, 4, 5, 6, 7, 8])
);
console.log("八皇后問(wèn)題有", arrayOfStrings.eightQueens().length, "種擺法");

示例代碼

本文用到的代碼完整版請(qǐng)移步：

  • ArrayOfStrings.ts
  • ArrayOfStrings-test.ts

本文標(biāo)題：全排列的應(yīng)用：正方體的組成與八皇后
標(biāo)題URL：http://www.dlmjj.cn/article/cccijcs.html