'use client'; import React, { useState, useEffect, useRef, useMemo } from 'react'; // ========================================== // 常量与配置 // ========================================== const VIEW_WIDTH = 1200; const VIEW_HEIGHT = 600; const BG_COLOR = '#7b92c6'; const DISK_COLORS = ['#FF6B6B', '#FFD93D', '#6BCB77', '#4D96FF', '#9D4EDD']; const DISK_COUNT = 4; // 碟子数量 const ANIMATION_SPEED = 1.5; // 速度系数 // 贝塞尔缓动函数 const easeInOutCubic = (t: number) => t < 0.5 ? 4 * t * t * t : 1 - Math.pow(-2 * t + 2, 3) / 2; // ========================================== // 算法逻辑：生成事件流 // ========================================== type HanoiEvent = | { type: 'CALL'; n: number; from: string; to: string; aux: string; depth: number; id: string } | { type: 'MOVE'; disk: number; from: number; to: number; depth: number } | { type: 'RETURN'; depth: number }; const generateHanoiEvents = (n: number, from: string, to: string, aux: string, fromIdx: number, toIdx: number, auxIdx: number, depth: number = 0, events: HanoiEvent[] = []) => { const id = `${depth}-${n}-${from}-${to}`; // 函数调用入栈 events.push({ type: 'CALL', n, from, to, aux, depth, id }); if (n === 1) { // 基本情况：移动盘子 events.push({ type: 'MOVE', disk: 1, from: fromIdx, to: toIdx, depth }); } else { // 递归步骤 1: 将 n-1 从 from 移到 aux generateHanoiEvents(n - 1, from, aux, to, fromIdx, auxIdx, toIdx, depth + 1, events); // 移动第 n 个盘子 events.push({ type: 'MOVE', disk: n, from: fromIdx, to: toIdx, depth }); // 递归步骤 2: 将 n-1 从 aux 移到 to generateHanoiEvents(n - 1, aux, to, from, auxIdx, toIdx, fromIdx, depth + 1, events); } // 函数返回出栈 events.push({ type: 'RETURN', depth }); return events; }; // ========================================== // 主组件 // ========================================== export const HanoiRecursionView = () => { // ---------------- State ---------------- const [events, setEvents] = useState([]); const [currentStep, setCurrentStep] = useState(0); // 物理状态：三个柱子上的盘子 [ [4,3,2,1], [], [] ] const [pegs, setPegs] = useState([[], [], []]); // 动画状态 const [movingDisk, setMovingDisk] = useState<{ val: number, x: number, y: number } | null>(null); const [stack, setStack] = useState([]); // 调用栈可视化 // 引用，用于动画循环 const requestRef = useRef(); const startTimeRef = useRef(); const isResetting = useRef(false); // ---------------- 初始化 ---------------- useEffect(() => { // 生成事件序列 const evts = generateHanoiEvents(DISK_COUNT, 'A', 'C', 'B', 0, 2, 1); setEvents(evts); resetGame(); return () => cancelAnimationFrame(requestRef.current!); }, []); const resetGame = () => { const initialPegs: number[][] = [[], [], []]; for (let i = DISK_COUNT; i >= 1; i--) { initialPegs[0].push(i); } setPegs(initialPegs); setCurrentStep(0); setStack([]); setMovingDisk(null); startTimeRef.current = undefined; isResetting.current = false; // 启动动画循环 requestRef.current = requestAnimationFrame(animate); }; // ---------------- 动画核心循环 ---------------- const animate = (time: number) => { if (isResetting.current) return; if (!startTimeRef.current) startTimeRef.current = time; // 这里的逻辑稍微复杂：我们需要根据当前 step 的类型来决定动画时长 // CALL/RETURN 很快，MOVE 需要物理时间 // 由于 React State 在 requestAnimationFrame 中更新会有闭包陷阱， // 我们这里主要依靠 step 的递增来驱动，每一帧检查是否完成当前 step // 实际上，为了简化 React 中的动画流，我们使用 setTimeout 的链式调用或者 useEffect 监听 step 变化更好。 // 但为了极致流畅，我们在这里做一点混合处理。 }; // 使用 useEffect 驱动步骤步进 (Step Sequencer) useEffect(() => { if (events.length === 0) return; if (currentStep >= events.length) { // 动画结束，等待后重置 const timer = setTimeout(() => { isResetting.current = true; resetGame(); }, 3000); return () => clearTimeout(timer); } const evt = events[currentStep]; let duration = 0; if (evt.type === 'CALL') { duration = 600 / ANIMATION_SPEED; setStack(prev => [...prev, evt]); } else if (evt.type === 'RETURN') { duration = 600 / ANIMATION_SPEED; setStack(prev => prev.slice(0, -1)); } else if (evt.type === 'MOVE') { duration = 1200 / ANIMATION_SPEED; // 触发物理移动动画 performMoveAnimation(evt, duration); } const timer = setTimeout(() => { // 只有非 MOVE 事件或者 MOVE 动画完成后才推进 // MOVE 事件在 performMoveAnimation 内部处理状态更新 if (evt.type !== 'MOVE') { setCurrentStep(prev => prev + 1); } }, duration); return () => clearTimeout(timer); }, [currentStep, events]); // 处理物理移动动画 const performMoveAnimation = (evt: any, duration: number) => { const { from, to, disk } = evt; const startPegIndex = from; const endPegIndex = to; // 从源柱子移除 setPegs(prev => { const newPegs = [...prev]; const sourcePeg = [...newPegs[startPegIndex]]; sourcePeg.pop(); // 移除栈顶 newPegs[startPegIndex] = sourcePeg; return newPegs; }); // 计算坐标 const startX = getPegX(startPegIndex); const endX = getPegX(endPegIndex); const startY = getDiskY(pegs[startPegIndex].length); // 注意：这里因为已经pop了，所以是当前长度（即原顶部位置） const endY = getDiskY(pegs[endPegIndex].length); // 目标位置高度 const peakY = 150; // 抬起高度 let startTime: number | null = null; const loop = (now: number) => { if (!startTime) startTime = now; const elapsed = now - startTime; const progress = Math.min(elapsed / duration, 1); const eased = easeInOutCubic(progress); // 轨迹插值：上 -> 平移 -> 下 let curX, curY; // 分三段：0-0.3 (上), 0.3-0.7 (平移), 0.7-1.0 (下) if (progress < 0.3) { // 抬起阶段 const p = progress / 0.3; curX = startX; curY = startY + (peakY - startY) * easeInOutCubic(p); } else if (progress < 0.7) { // 平移阶段 const p = (progress - 0.3) / 0.4; curX = startX + (endX - startX) * easeInOutCubic(p); curY = peakY; } else { // 下落阶段 const p = (progress - 0.7) / 0.3; curX = endX; curY = peakY + (endY - peakY) * easeInOutCubic(p); } setMovingDisk({ val: disk, x: curX, y: curY }); if (progress < 1) { requestAnimationFrame(loop); } else { // 动画完成，放入目标柱子 setMovingDisk(null); setPegs(prev => { const newPegs = [...prev]; newPegs[endPegIndex] = [...newPegs[endPegIndex], disk]; return newPegs; }); setCurrentStep(s => s + 1); } }; requestAnimationFrame(loop); }; // ========================================== // 辅助计算 // ========================================== const PEG_BASE_Y = 450; const DISK_HEIGHT = 20; const getPegX = (index: number) => 250 + index * 250; const getDiskY = (stackIndex: number) => PEG_BASE_Y - stackIndex * DISK_HEIGHT - (DISK_HEIGHT / 2); // ========================================== // 渲染组件 // ========================================== return (

); }; // ========================================== // 子组件 // ========================================== const Disk = ({ x, y, width, val, isMoving = false }: { x: number, y: number, width: number, val: number, isMoving?: boolean }) => ( {val} ); const CodeLine = ({ y, children, active, indent = 0, color = "#fff" }: any) => ( {active && } {children} ); const GridBackground = () => ( {Array.from({ length: 20 }).map((_, i) => ( ))} {Array.from({ length: 30 }).map((_, i) => ( ))} ); export default HanoiRecursionView;