每日算法 — 使用java实现跳绳：节奏模式识别与动态规划最优跳跃序列

引言

跳绳是一项对节奏感要求极高的运动，选手需要在绳子通过脚下的瞬间精确起跳。本文将跳绳抽象为序列匹配问题，用Java实现节奏模式识别系统，核心算法包括自相关函数计算摇绳周期、动态规划求解最优跳跃序列，以及基于滑动窗口的反应时间统计。

核心算法原理

1. 节奏周期检测：自相关函数

自相关函数（ACF）可以检测信号的周期性。对于离散信号 ( x[n] )：

[ R_{xx}[k] = \sum_{n=0}^{N-k-1} x[n] \cdot x[n+k] ]

当延迟 ( k ) 等于周期时，( R_{xx}[k] ) 出现峰值。

2. 最优跳跃序列：动态规划

给定绳子通过脚底的时间窗口序列，寻找最大不重叠跳跃子序列。每个跳跃有准备时间和持续时间，要求相邻跳跃不冲突。

[ dp[i] = \max(dp[i-1], dp[p(i)] + 1) ]

其中 ( p(i) ) 是第 ( i ) 个窗口之前最后一个兼容窗口的索引。

3. 反应时间统计与判定

通过滑动窗口统计历史反应时间，判断当前状态是否适合起跳。

Java完整实现

import java.util.*;

/**
 * 跳绳节奏识别与动态规划最优跳跃序列
 * 核心算法：自相关函数周期检测 + 动态规划最长兼容子序列 + 滑动窗口统计
 */
public class JumpRopeOptimizer {

    /**
     * 模拟摇绳通过脚底的信号（1表示通过，0表示未通过）
     * 生成周期性信号加噪声
     */
    public static List<Integer> generateRopeSignal(int totalSamples, double period, double noiseLevel) {
        List<Integer> signal = new ArrayList<>();
        Random rand = new Random(42);
        for (int i = 0; i < totalSamples; i++) {
            double phase = (i % period) / period;
            // 每个周期内有一个短暂的"通过"窗口
            double value = Math.exp(-Math.pow((phase - 0.5) * 8, 2));
            value += rand.nextGaussian() * noiseLevel;
            signal.add(value > 0.5 ? 1 : 0);
        }
        return signal;
    }

    /**
     * 自相关函数计算周期
     * @param signal 输入信号
     * @param maxLag 最大延迟
     * @return 估计周期
     */
    public int estimatePeriodByACF(List<Integer> signal, int maxLag) {
        int N = signal.size();
        double[] acf = new double[maxLag + 1];

        // 计算均值
        double mean = 0;
        for (int v : signal) mean += v;
        mean /= N;

        for (int lag = 0; lag <= maxLag; lag++) {
            double sum = 0;
            for (int i = 0; i < N - lag; i++) {
                sum += (signal.get(i) - mean) * (signal.get(i + lag) - mean);
            }
            acf[lag] = sum;
        }

        // 归一化
        if (acf[0] != 0) {
            for (int i = 0; i < acf.length; i++) acf[i] /= acf[0];
        }

        // 寻找第一个显著峰值（排除lag=0）
        double peakValue = -1;
        int peakLag = 1;
        for (int lag = 2; lag <= maxLag; lag++) {
            if (acf[lag] > acf[lag - 1] && acf[lag] > acf[lag + 1 < acf.length ? lag + 1 : lag] && acf[lag] > 0.3) {
                if (acf[lag] > peakValue) {
                    peakValue = acf[lag];
                    peakLag = lag;
                }
            }
        }

        return peakLag;
    }

    /**
     * 从信号中提取所有可用的跳跃窗口
     * 每个窗口表示绳子通过脚底的时间区间
     */
    public List<JumpWindow> extractJumpWindows(List<Integer> signal) {
        List<JumpWindow> windows = new ArrayList<>();
        int start = -1;

        for (int i = 0; i < signal.size(); i++) {
            if (signal.get(i) == 1 && start == -1) {
                start = i;
            } else if (signal.get(i) == 0 && start != -1) {
                windows.add(new JumpWindow(start, i - 1));
                start = -1;
            }
        }
        if (start != -1) windows.add(new JumpWindow(start, signal.size() - 1));

        return windows;
    }

    static class JumpWindow {
        int start, end;
        JumpWindow(int s, int e) { start = s; end = e; }
        int duration() { return end - start + 1; }
        int center() { return (start + end) / 2; }
        @Override
        public String toString() { return String.format("[%d, %d]", start, end); }
    }

    /**
     * 动态规划求解最大兼容跳跃序列
     * 约束：相邻跳跃之间需要准备时间（prepTime）
     * @param windows 跳跃窗口列表
     * @param prepTime 准备时间（样本数）
     * @return 最优跳跃序列索引
     */
    public List<Integer> findOptimalJumpSequence(List<JumpWindow> windows, int prepTime) {
        int n = windows.size();
        if (n == 0) return new ArrayList<>();

        // dp[i] = 使用前i个窗口能获得的最大跳跃数
        int[] dp = new int[n];
        int[] prev = new int[n]; // 记录前驱
        Arrays.fill(prev, -1);

        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 只选当前窗口
            // 寻找最大的兼容前驱
            for (int j = 0; j < i; j++) {
                if (windows.get(j).end + prepTime <= windows.get(i).start) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        prev[i] = j;
                    }
                }
            }
        }

        // 找到最大值
        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i] > dp[maxIdx]) maxIdx = i;
        }

        // 回溯重建序列
        List<Integer> sequence = new ArrayList<>();
        int cur = maxIdx;
        while (cur != -1) {
            sequence.add(cur);
            cur = prev[cur];
        }
        Collections.reverse(sequence);
        return sequence;
    }

    /**
     * 滑动窗口反应时间统计
     * 统计最近N次跳跃的反应时间，判断当前状态
     */
    public static class ReactionTimeStats {
        private final Queue<Long> reactionTimes;
        private final int windowSize;

        public ReactionTimeStats(int windowSize) {
            this.windowSize = windowSize;
            this.reactionTimes = new LinkedList<>();
        }

        public void addReactionTime(long ms) {
            reactionTimes.offer(ms);
            if (reactionTimes.size() > windowSize) reactionTimes.poll();
        }

        public double getMean() {
            if (reactionTimes.isEmpty()) return 0;
            long sum = 0;
            for (long t : reactionTimes) sum += t;
            return (double) sum / reactionTimes.size();
        }

        public double getStdDev() {
            if (reactionTimes.size() < 2) return 0;
            double mean = getMean();
            double sumSq = 0;
            for (long t : reactionTimes) sumSq += Math.pow(t - mean, 2);
            return Math.sqrt(sumSq / reactionTimes.size());
        }

        /**
         * 判断当前是否适合起跳
         * 标准：反应时间稳定且均值在合理范围内
         */
        public boolean isReadyToJump() {
            if (reactionTimes.size() < 3) return false;
            double mean = getMean();
            double std = getStdDev();
            return mean >= 100 && mean <= 400 && std < mean * 0.3;
        }
    }

    /**
     * 实时跳跃决策模拟
     */
    public void simulateRealTimeJumping(List<Integer> signal, int period, int prepTime) {
        List<JumpWindow> windows = extractJumpWindows(signal);
        List<Integer> optimalSequence = findOptimalJumpSequence(windows, prepTime);
        ReactionTimeStats stats = new ReactionTimeStats(10);

        System.out.println("=== 跳绳节奏识别与最优跳跃序列 ===\n");
        System.out.printf("检测到跳跃窗口数: %d%n", windows.size());
        System.out.printf("估计摇绳周期: %d 样本%n", period);
        System.out.printf("最优跳跃序列长度: %d%n%n", optimalSequence.size());

        // 模拟实时跳跃
        int jumpCount = 0;
        for (int idx : optimalSequence) {
            JumpWindow w = windows.get(idx);
            // 模拟反应时间（基于窗口中心偏移）
            long reactionTime = 200 + (long)(Math.random() * 100 - 50);
            stats.addReactionTime(reactionTime);
            jumpCount++;

            if (jumpCount % 5 == 0) {
                System.out.printf("第 %d 次跳跃 | 窗口: %s | 反应时间: %d ms | 均值: %.1f ms | 状态: %s%n",
                    jumpCount, w, reactionTime, stats.getMean(),
                    stats.isReadyToJump() ? "节奏稳定" : "需要调整");
            }
        }

        System.out.printf("\n总跳跃次数: %d%n", jumpCount);
        System.out.printf("平均反应时间: %.2f ms%n", stats.getMean());
        System.out.printf("反应时间标准差: %.2f ms%n", stats.getStdDev());
    }

    public static void main(String[] args) {
        JumpRopeOptimizer optimizer = new JumpRopeOptimizer();

        // 生成模拟信号：1000个样本，周期约50样本，带噪声
        List<Integer> signal = generateRopeSignal(1000, 50, 0.15);

        // 周期检测
        int period = optimizer.estimatePeriodByACF(signal, 200);
        int prepTime = Math.max(5, period / 5); // 准备时间为周期的1/5

        // 实时模拟
        optimizer.simulateRealTimeJumping(signal, period, prepTime);
    }
}

复杂度分析

总结

本文将跳绳运动抽象为序列分析问题，实现了三大核心算法：
1. 自相关周期检测：利用ACF从含噪信号中准确提取摇绳周期
2. 动态规划最优序列：在满足准备时间约束下最大化跳跃次数
3. 滑动窗口统计：实时监控反应时间稳定性，辅助状态判定

该系统可扩展应用于节拍检测、动作识别等更广泛的时间序列分析场景。