问大家一道我儿子一年级的数学题:求图形里包含多少个矩形
这种题数也能数出来,但是有没有规律性的解题思路....因为在程序里硬数是绝对不行的,哈哈
里面包含多少个长方形,(包含正方形)
回答:
1 写程序暴力穷举是能实现的
证明如下:
1.1 已知
- 每个点的坐标
- 哪两个点之间有连线
为什么条件2也是必须的,如图,A和D之间有没有连线,H和K之间有没有连线,必须题目给出。
1.2 计算
- 穷举所有的线段。题目给的可能是CF,FD两个线段,实际CD也是一个线段。题目给的3个小线段连成一个大线段也是有的:AMEB
- 穷举哪4条线段构成一个4边形,判断4个线段是否有且仅有4个公共点即可
- 判断上述4边形是否构成矩形,判断4个顶点的横坐标和纵坐标的相等关系即可
如图:
- 横坐标相等:A和C,B和D
- 纵坐标相等:A和B,C和D
则ABCD必为矩形
2 小学一年级的暴力破解法
就是硬数。但要有条理。
- 1个矩形组成的矩形:5个
- 2个矩形合并成的矩形:4个
- 3个矩形合并成的矩形:2个
- 4个矩形合并成的矩形:0个
- 5个矩形合并成的矩形:1个
总计:12个
但这个方法只能应对矩形数量少的图形,如果数量多一点,大学生也要数错,各位不信的话,数一下这个围棋棋盘,有多少个矩形(正方形也算矩形)
3 小学三年级的速算法
3.1 删除干扰线速算
我把线段MN称作干扰线,忽略它,得到这个图:
在水平方向,有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)
回答:
规律是有
- 单行(列)
n
个矩形组成的,有1 + 2 + ... + n
个,即
$$\frac{n \times (n + 1)}{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
不出意外应该是算对了。写程序大概也是这个思路,但是要判断特殊的部分。
回答:
四根红线,任选两根都能组成一个矩形,那么就是C(4,2) 有六个,大概就是这么个规律。然后竖线差不多也是,去掉横线用过的场景
想到另外一个更佳的描述。任意一点A,如果可以按“L”路径到达点B,且AB的连线的斜率是负数,算作一个解。
回答:
提供一个暴力思路
- 输入所有点的位置,类似一个二维数组
(x, y)[]
- 任取 4 点,进行遍历,判断是否能组成矩形(可以区分正方形、长方形)
- 。。。 优化算法
回答:
其实就是个数学建模的问题,你能用数学的方式把你给的那个图形描述出来,那离数的方法也就不远了
回答:
受上面 @冯恒智 这句话启发。【其实就是个数学建模的问题,你能用数学的方式把你给的那个图形描述出来,那离数的方法也就不远了】
我的思路是这样的:图形用水平线和竖直线的点集合数组能表示出来: ["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;
}
回答:
其实就是有向图的遍历。
每个顶点遍历后,必须回到这个顶点,找出符合条件的"走法"即可。
边是有向的,上下左右
4方向种。
这个路径必须只能“转向”3次。
回答:
你的标题以及内容没体现出任何问题.
我猜你是想用程序来数长方形是吧.
可以把这些图形转换成坐标,就可以数了
回答:
使用对角线加坐标的方法,应该是最简单的。
任意两个不同的坐标(x1,y1),(x2,y2),若存在坐标(x1,y2)与坐标(x2,y1),则这两个坐标的连线是一个对角线。
遍历循环一下,得到对角线个数,除以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))
回答:
我尝试了用点转换为二维数组,一对,有的边长,有的边段,不正确,所以只能考虑用边
[ [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]]
我觉得这个从图到图应该也是问题的一部分,所以我把图画出来了供大家验证,对了我挺支持两个点确定一个矩形的方法。
以上是 问大家一道我儿子一年级的数学题:求图形里包含多少个矩形 的全部内容, 来源链接: utcz.com/p/937371.html