3. 递归与分治法

①. 递归

示例场景：计算阶乘。

import React, { useState } from "react";

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

function FactorialCalculator() {
  const [n, setN] = useState("");
  const [result, setResult] = useState("");

  const calculate = () => {
    const num = parseInt(n, 10);
    if (!isNaN(num) && num >= 0) {
      setResult(factorial(num).toString());
    } else {
      setResult("请输入一个非负整数");
    }
  };

  return (
    <div>
      <input
        type="number"
        placeholder="输入n"
        value={n}
        onChange={(e) => setN(e.target.value)}
      />
      <button onClick={calculate}>计算阶乘</button>
      <p>结果: {result}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>递归 - 计算阶乘</h1>
      <FactorialCalculator />
    </div>
  );
}

export default App;

②. 分治法

示例场景：使用分治法实现归并排序。

import React, { useState } from "react";

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function MergeSorter() {
  const [numbers, setNumbers] = useState([34, 7, 23, 32, 5, 62]);
  const [sortedNumbers, setSortedNumbers] = useState([]);

  const sort = () => {
    setSortedNumbers(mergeSort(numbers));
  };

  return (
    <div>
      <p>原始数组: {numbers.join(", ")}</p>
      <button onClick={sort}>排序</button>
      <p>排序后的数组: {sortedNumbers.join(", ")}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>分治法 - 归并排序</h1>
      <MergeSorter />
    </div>
  );
}

export default App;

③. 动态规划（背包问题）

示例场景：解决 0-1 背包问题，给定一组物品，每种物品都有一个重量和一个价值，求解在不超过总重量限制的情况下，能获得的最大价值。

import React, { useState } from "react";

function knapsack(items, maxWeight) {
  const n = items.length;
  const dp = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= maxWeight; w++) {
      if (items[i - 1].weight > w) {
        dp[i][w] = dp[i - 1][w];
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i - 1][w - items[i - 1].weight] + items[i - 1].value
        );
      }
    }
  }

  return dp[n][maxWeight];
}

function KnapsackSolver() {
  const [items, setItems] = useState([
    { weight: 1, value: 6 },
    { weight: 2, value: 10 },
    { weight: 3, value: 12 },
  ]);
  const [maxWeight, setMaxWeight] = useState(5);
  const [result, setResult] = useState("");

  const solve = () => {
    const maxVal = knapsack(items, maxWeight);
    setResult(`最大价值: ${maxVal}`);
  };

  return (
    <div>
      <h2>0-1背包问题</h2>
      <input
        type="number"
        placeholder="最大重量"
        value={maxWeight}
        onChange={(e) => setMaxWeight(parseInt(e.target.value, 10))}
      />
      <button onClick={solve}>求解</button>
      <p>{result}</p>
      <h3>物品列表</h3>
      <ul>
        {items.map((item, index) => (
          <li key={index}>
            物品 {index + 1}: 重量 {item.weight}, 价值 {item.value}
          </li>
        ))}
      </ul>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>动态规划 - 0-1背包问题</h1>
      <KnapsackSolver />
    </div>
  );
}

export default App;

④. 回溯法（八皇后问题）

示例场景：解决八皇后问题，即在 8×8 的棋盘上放置 8 个皇后，使得任意两个皇后不能在同一行、同一列或同一对角线上。

import React, { useState } from "react";

function isSafe(board, row, col) {
  for (let i = 0; i < col; i++) {
    if (board[row][i] === 1) {
      return false;
    }
  }

  for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 1) {
      return false;
    }
  }

  for (let i = row, j = col; i < 8 && j >= 0; i++, j--) {
    if (board[i][j] === 1) {
      return false;
    }
  }

  return true;
}

function solveNQueens(board, col) {
  if (col >= 8) {
    return true;
  }

  for (let i = 0; i < 8; i++) {
    if (isSafe(board, i, col)) {
      board[i][col] = 1;
      if (solveNQueens(board, col + 1)) {
        return true;
      }
      board[i][col] = 0;
    }
  }

  return false;
}

function NQueensSolver() {
  const [board, setBoard] = useState(
    Array.from({ length: 8 }, () => Array(8).fill(0))
  );
  const [result, setResult] = useState("");

  const solve = () => {
    const solved = solveNQueens(board, 0);
    if (solved) {
      setResult("解决方案找到");
    } else {
      setResult("没有解决方案");
    }
  };

  return (
    <div>
      <h2>八皇后问题</h2>
      <button onClick={solve}>求解</button>
      <p>{result}</p>
      <h3>棋盘</h3>
      <table>
        <tbody>
          {board.map((row, rowIndex) => (
            <tr key={rowIndex}>
              {row.map((cell, colIndex) => (
                <td
                  key={colIndex}
                  style={{ border: "1px solid black", padding: "10px" }}
                >
                  {cell === 1 ? "Q" : ""}
                </td>
              ))}
            </tr>
          ))}
        </tbody>
      </table>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>回溯法 - 八皇后问题</h1>
      <NQueensSolver />
    </div>
  );
}

export default App;

以上是在 React 中使用递归、分治法、动态规划和回溯法。 这些算法在解决复杂问题时非常有效，尤其是在处理组合优化和搜索问题时。