当前位置：首页 > JavaScript

js实现折纸问题

2026-02-02 20:46:03JavaScript

折纸问题简介

折纸问题通常指通过编程模拟纸张折叠的过程，计算折叠后的层数或方向。常见的折纸问题包括计算折叠n次后的折痕方向序列（如山谷折或山折）。

方法一：递归生成折痕序列

递归方法可以模拟每次折叠后折痕的变化规律。每次折叠后，新的折痕序列是在原有序列中间插入一个“山折”，并在两侧对称复制原有序列的逆序。

js实现折纸问题

function foldPaper(n) {
    if (n === 0) return [];
    const prev = foldPaper(n - 1);
    return [...prev, '山', ...prev.reverse().map(d => d === '山' ? '谷' : '山')];
}

// 示例：折叠3次
console.log(foldPaper(3)); // ["山", "山", "谷", "山", "山", "谷", "谷"]

方法二：迭代生成折痕序列

迭代方法通过循环逐步构建折痕序列，适合较大的n值以避免递归栈溢出。

js实现折纸问题

function foldPaperIterative(n) {
    let sequence = [];
    for (let i = 0; i < n; i++) {
        const newSequence = [...sequence, '山', ...sequence.map(d => d === '山' ? '谷' : '山').reverse()];
        sequence = newSequence;
    }
    return sequence;
}

// 示例：折叠2次
console.log(foldPaperIterative(2)); // ["山", "山", "谷"]

方法三：二进制位运算

折痕序列的规律与二进制表示有关。奇数位置为“山”，偶数位置为“谷”，具体方向可通过位运算判断。

function foldPaperBinary(n) {
    const totalFolds = Math.pow(2, n) - 1;
    const result = [];
    for (let i = 1; i <= totalFolds; i++) {
        result.push((i & (i - 1)) === 0 ? '山' : '谷');
    }
    return result;
}

// 示例：折叠1次
console.log(foldPaperBinary(1)); // ["山"]

方法四：二叉树中序遍历

折痕序列可以看作二叉树的中序遍历结果，左子节点为“谷”，右子节点为“山”。

function buildTree(height, direction) {
    if (height === 0) return null;
    const node = { direction };
    node.left = buildTree(height - 1, '谷');
    node.right = buildTree(height - 1, '山');
    return node;
}

function inOrderTraversal(node, result) {
    if (!node) return;
    inOrderTraversal(node.left, result);
    result.push(node.direction);
    inOrderTraversal(node.right, result);
}

function foldPaperTree(n) {
    const root = buildTree(n, '山');
    const result = [];
    inOrderTraversal(root, result);
    return result;
}

// 示例：折叠2次
console.log(foldPaperTree(2)); // ["谷", "山", "谷"]