16.华为OD机试满分题解：对称美学（Java 2024 E卷）| 递归与迭代双解

16.华为OD机试满分题解：对称美学（Java 2024 E卷）| 递归与迭代双解

🔥VIP专属：本文深度解析华为OD机试高频考点，提供两种优化解法，附详细注释和解题思路。掌握此技巧，轻松应对字符串递归类题型！

📋 题目概述

问题描述

给定对称字符串的生成规则：

• 第1个字符串为 “R”
• 第i个字符串 = 第i-1号字符串取反 + 第i-1号字符串
• 取反规则：R → B，B → R

求第n个字符串的第k个字符（k从0开始），输出"red"表示R，"blue"表示B。

输入输出示例

输入：
2
3 2
4 5

输出：
blue
red

💡 核心解题思路

关键观察

1. 递归结构：每个字符串都是对称的
2. 长度规律：第n个字符串的长度为 2^(n-1)
3. 分治思想：问题可以不断分解为更小的子问题

递归公式推导

设 f(n, k) 表示第n个字符串的第k个字符是否为R：

• n=1时，f(1, k)=true ®
• 设 len = 2^(n-1)，mid = len/2
  • 若 k < mid：f(n, k) = f(n-1, k)
  • 若 k ≥ mid：f(n, k) = !f(n-1, k-mid)

📝 代码实现详解

解法一：递归版本（直观但可能栈溢出）

importjava.util.Scanner;publicclassSymmetricAesthetics{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intT=scanner.nextInt();for(inti=0;i<T;i++){intn=scanner.nextInt();