问大家一道我儿子一年级的数学题:求图形里包含多少个矩形

CaixK
  • 496

这种题数也能数出来,但是有没有规律性的解题思路....因为在程序里硬数是绝对不行的,哈哈
里面包含多少个长方形,(包含正方形)

1646363583(1).png

回复
阅读 6.4k
12 个回答
qinjianxiang
  • 5.9k
✓ 已被采纳

image.png

1 写程序暴力穷举是能实现的

证明如下:

1.1 已知

  1. 每个点的坐标
  2. 哪两个点之间有连线

为什么条件2也是必须的,如图,A和D之间有没有连线,H和K之间有没有连线,必须题目给出。

1.2 计算

  1. 穷举所有的线段。题目给的可能是CF,FD两个线段,实际CD也是一个线段。题目给的3个小线段连成一个大线段也是有的:AMEB
  2. 穷举哪4条线段构成一个4边形,判断4个线段是否有且仅有4个公共点即可
  3. 判断上述4边形是否构成矩形,判断4个顶点的横坐标和纵坐标的相等关系即可

如图:

  • 横坐标相等:A和C,B和D
  • 纵坐标相等:A和B,C和D

则ABCD必为矩形

2 小学一年级的暴力破解法

就是硬数。但要有条理。

  • 1个矩形组成的矩形:5个
  • 2个矩形合并成的矩形:4个
  • 3个矩形合并成的矩形:2个
  • 4个矩形合并成的矩形:0个
  • 5个矩形合并成的矩形:1个

总计:12个

但这个方法只能应对矩形数量少的图形,如果数量多一点,大学生也要数错,各位不信的话,数一下这个围棋棋盘,有多少个矩形(正方形也算矩形)

image.png

3 小学三年级的速算法

3.1 删除干扰线速算

我把线段MN称作干扰线,忽略它,得到这个图:
image.png

在水平方向,有3条线段,即:AE,EB,AB
在竖直方向,有3条线段,即:AG,GC,AC

则这些线段(以及和他们平行且相等的线段)可以组成3x3=9个矩形

用这个方法,算一下围棋棋盘有多少矩形,是不是快多了?
横向纵向各有18x19/2=171条线段,一共可以组成171x171=29241个矩形

3.2 计算干扰线带来的矩形

3个:AGMN,MNEK,MNBH
再加上9

共计9+3=12个

4 别问我怎么知道的

我是无证小学奥数讲师

转换成坐标点,遍历求取

var points = [
    [[0, 4], [1, 4], [2, 4], [4, 4]],
    [[0, 2], [1, 2], [2, 2], [4, 2]],
    [[0, 0], [2, 0], [4, 0]]
]
let count = 0
for(let i = 0; i < points.length - 1; i++){
    for(let j = 0; j < points[i].length - 1; j++){
        // 左上角坐标
        let point00 = points[i][j]
        for(let k = j + 1; k < points[i].length; k++){
            // 右上角坐标
            let point10 = points[i][k]
            for(let l = i + 1; l < points.length; l++){
                // 下面两个角坐标
                let point01 = points[l].find(point => point[0] == point00[0])
                let point11 = points[l].find(point => point[0] == point10[0])
                if(point01 && point11){
                    console.log([...point00, ...point11])
                    count++
                }
            }
        }
    }
}
console.log(count)
边城
  • 54.7k

规律是有

  1. 单行(列)n 个矩形组成的,有 1 + 2 + ... + n 个,即
    $$\frac{n \times (n + 1)}{2}$$
  2. 规则的多行,因为列行都是上面的算法,所以是
    $$\frac{n \times (n + 1)}{2} \times \frac{m \times (m + 1)}{2}$$

但这个问题有个特殊区域(不规则的),

先算规则的部分是 (1 + 2)(1 + 2) = 9
再算不规则的部分(不用算纵向,只有横向),得先把之前算过的减掉 -(1 + 2) = -3,再加上 1 + 2 + 3 = 6

结果是 9 - 3 + 6 = 12

不出意外应该是算对了。写程序大概也是这个思路,但是要判断特殊的部分。

_usw
  • 3.7k

image.png
四根红线,任选两根都能组成一个矩形,那么就是C(4,2) 有六个,大概就是这么个规律。然后竖线差不多也是,去掉横线用过的场景

想到另外一个更佳的描述。任意一点A,如果可以按“L”路径到达点B,且AB的连线的斜率是负数,算作一个解。

提供一个暴力思路

  1. 输入所有点的位置,类似一个二维数组 (x, y)[]
  2. 任取 4 点,进行遍历,判断是否能组成矩形(可以区分正方形、长方形)
  3. 。。。 优化算法

其实就是个数学建模的问题,你能用数学的方式把你给的那个图形描述出来,那离数的方法也就不远了

我的神
  • 978

image.png

受上面 @冯恒智 这句话启发。【其实就是个数学建模的问题,你能用数学的方式把你给的那个图形描述出来,那离数的方法也就不远了】

我的思路是这样的:图形用水平线和竖直线的点集合数组能表示出来: ["AMEB", "GNKH", "CFD", "AGC", "MN", "EKF", "BHD"]

所以以水平线和竖直线的点集合作为输入,每一条水平线和竖直线的点以个数2进行组合得出所有水平和竖直线段(无斜线),线段集合再以个数4进行组合 得出所有的4边形,然后遍历判断4边形是否是首尾相连的且不在一条直线上的长方形。

// 所有水平线和竖直线
let allLines = ["AMEB", "GNKH", "CFD", "AGC", "MN", "EKF", "BHD"]; 

//存储所有两个点的线段 ["AM","AE","ME",...]
let segmentArr = []; 

//遍历所有水平线和竖直线,收集所有线段。
allLines.forEach((line) => {
    //每条线的点以个数2 进行组合,构成所有线段集合。 
    //generateCombinations 计算组合情况 放在最后。
  let lineSegments = generateCombinations(line.split(""), 2).map((seg) =>
    seg.join("")
  ); 
  segmentArr.push(...lineSegments);
});
 // 所有线段以个数4进行组合,构成所有4边形集合。
let allSegmentCom = generateCombinations(segmentArr, 4).map((item) =>
  item.join("")
);

//每条线的点重新排序,便于后面去重。
let sortAllLines = allLines.map((line) => line.split("").sort().join("")); 
//判断一个4个线段组成的点集合,是否是首尾相连的4边形。   "AMAEABME"
function isRectangle(str) {
  let result = {};
  let len = str.length;
  for (let i = 0; i < len; i++) {
    let dot = str[i];
    if (result[dot]) {
      result[dot]++;
    } else {
      result[dot] = 1;
    }
  }
  let dots = Object.keys(result).sort(); //排序是为了便于去重。

  // 有4个点,每个点出现两次。证明是个首尾相连的4边形。
  if (dots.length == 4 && dots.every((dot) => result[dot] == 2)) {
    
    let target = dots.join("");

    //target这4个点要排除在在同一条直线里的情况。判断target是否包含在初始条件列出的所有水平和竖直线里。
    if (!sortAllLines.find((item) => item.includes(target))) {
      if (!goodCase.includes(target)) {
        //收集目标
        goodCase.push(target);
      }
    }
  }
}

let goodCase = [];
allSegmentCom.forEach((str) => {
  isRectangle(str);
});

console.log(goodCase);
// ["AGMN","AEGK","ACEF","ABGH","ABCD","EKMN","BHMN","BEHK","BDEF","CFGK","CDGH","DFHK"]
//12个




/**
 工具函数: 计算数组的所有组合情况。
 * Generate all combinations of an array.
 * @param {Array} sourceArray - Array of input elements.
 * @param {number} comboLength - Desired length of combinations.
 * @return {Array} Array of combination arrays.
 */
function generateCombinations(sourceArray, comboLength) {
  const sourceLength = sourceArray.length;
  if (comboLength > sourceLength) return [];

  const combos = []; // Stores valid combinations as they are generated.

  // Accepts a partial combination, an index into sourceArray,
  // and the number of elements required to be added to create a full-length combination.
  // Called recursively to build combinations, adding subsequent elements at each call depth.
  const makeNextCombos = (workingCombo, currentIndex, remainingCount) => {
    const oneAwayFromComboLength = remainingCount == 1;

    // For each element that remaines to be added to the working combination.
    for (
      let sourceIndex = currentIndex;
      sourceIndex < sourceLength;
      sourceIndex++
    ) {
      // Get next (possibly partial) combination.
      const next = [...workingCombo, sourceArray[sourceIndex]];

      if (oneAwayFromComboLength) {
        // Combo of right length found, save it.
        combos.push(next);
      } else {
        // Otherwise go deeper to add more elements to the current partial combination.
        makeNextCombos(next, sourceIndex + 1, remainingCount - 1);
      }
    }
  };

  makeNextCombos([], 0, comboLength);
  return combos;
}

tiyee
  • 1.8k

其实就是有向图的遍历。

每个顶点遍历后,必须回到这个顶点,找出符合条件的"走法"即可。
边是有向的,上下左右 4方向种。
这个路径必须只能“转向”3次。

你的标题以及内容没体现出任何问题.
我猜你是想用程序来数长方形是吧.

可以把这些图形转换成坐标,就可以数了

张末虎
  • 2
新手上路,请多包涵

使用对角线加坐标的方法,应该是最简单的。
任意两个不同的坐标(x1,y1),(x2,y2),若存在坐标(x1,y2)与坐标(x2,y1),则这两个坐标的连线是一个对角线。
遍历循环一下,得到对角线个数,除以2即可。

跟上面的 @张末虎 思路差不多。

遍历找出所有可能的左上、右下两个点,然后再剩余的点找是否存在对应的左下、右上两个点

做一些优化:

  1. 第一个遍历的点作为左上角点,第二个遍历的点必须在第一个点的右下角
  2. Set存所有点,后面剩余的左下、右上两个点的复杂度就是O(1)

这样复杂度就是O(n^2)

const points = [
  [0, 0],
  [1, 0],
  [2, 0],
  [4, 0],
  [0, 1],
  [1, 1],
  [2, 1],
  [4, 1],
  [0, 3],
  [2, 3],
  [4, 3],
]

/**
 * 
 * @param {Array<number[]>} points 
 */
function calc(points) {
  let count = 0
  // O(1)
  const set = new Set()
  function isExist(point) {
    return set.has(point.join(','))
  }
  points.forEach(([x, y]) => {
    set.add(`${x},${y}`)
  })

  for (let i = 0; i < points.length - 1; i++) {
    // 左上角
    const [x0, y0] = points[i]
    for (let j = i + 1; j < points.length; j++) {
      // 右下角
      const [x1, y1] = points[j]
      if (x1 > x0 && y1 > y0) {
        // 查找左下,右上是否有
        if (isExist([x0, y1]) && isExist([x1, y0])) {
          count++
        }
      }
    }
  }
  return count
}

console.log(calc(points))
Fall
  • 4
新手上路,请多包涵

我尝试了用点转换为二维数组,一对,有的边长,有的边段,不正确,所以只能考虑用边
[ [1,1,1,1],
[1,1,1,1],
[1,0,1,1],
[1,1,1,1],]
用边,发现有的边多,有的边少
[ [1,1,1],
[1,1,1],
[1,1,1],]
换!
我把矩形转为点坐标给大家画出来了,大家试试
[[1,1,1,1,1,1,1],
[1,0,1,0,1,0,1],
[1,1,1,1,1,1,1],
[1,0,0,0,1,0,1],
[1,1,1,1,1,1,1]]
我觉得这个从图到图应该也是问题的一部分,所以我把图画出来了供大家验证,对了我挺支持两个点确定一个矩形的方法。

宣传栏