Last active
April 16, 2024 05:57
-
-
Save zyf0330/41a043d56a0577ee711e1999fa3c4b2a to your computer and use it in GitHub Desktop.
给定直角边长,从左上角以逆时针螺旋路径,填充该等腰三角形内的每个整数坐标点
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function fillTriangle(N) { | |
const lines = []; | |
function makeRound() { | |
let x = round - 1; | |
let y = round - 1; | |
let step = 1; | |
try { | |
(lines[y] ??= [])[x] = n; | |
canFinishFill(); | |
while (++step <= N - (round - 1) * 3) { | |
y++; | |
n++; | |
(lines[y] ??= [])[x] = n; | |
canFinishFill(); | |
} | |
step = 1; | |
while (++step <= N - (round - 1) * 3) { | |
x++; | |
y--; | |
n++; | |
(lines[y] ??= [])[x] = n; | |
canFinishFill(); | |
} | |
step = 1; | |
while (++step <= N - (round - 1) * 3 - 1) { | |
x--; | |
n++; | |
(lines[y] ??= [])[x] = n; | |
canFinishFill(); | |
} | |
y++; | |
n++; | |
return true; | |
} catch (e) { | |
return false; | |
} | |
} | |
function canFinishFill() { | |
// 几何解释:N * N / 2 + N / 2 | |
// N 边长的正方形的面积(即内含点的个数)被剖成两半,即等腰直角三角形 N * N / 2,再加上正方形对角线上的点两个三角形一人一半 N / 2 | |
if (n === (N * (N + 1)) / 2) { | |
throw new Error("finish"); | |
} | |
} | |
let round = 1; | |
let n = 1; | |
while (makeRound()) { | |
round++; | |
} | |
for (const line of lines) { | |
console.log( | |
JSON.stringify(line, (k, v) => | |
/* console.log(k,v, typeof v), */ typeof v === "number" | |
? " ".repeat(2 - v.toString().length) + v | |
: v, | |
), | |
); | |
} | |
} | |
fillTriangle(+process.argv[2]); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
这是基于距离的算法
基于坐标的算法就是把对 step 的条件判断改为 x, y 点是否到达顶点
根据坐标直接计算位置处数字的算法:
忽略重复代码片段之类的细节