算法分析与设计——递归(2)比赛问题

2026-08-31 15:38:46 照明科技发展

NBA 季后赛中，我们总是安排较强的队伍对战较弱的队伍。例如，用排名第 1 的队伍和第 n 的队伍对决，这是一个可以让比赛更加有趣的好策略。现在，给你 n 支队伍，你需要以字符串格式输出它们的 最终 比赛配对。在每一轮的匹配过程中，你都需要遵循 将强队与弱队配对 的原则。比如输入4，输出((1,4),(2,3))每个括号表示一组对决

问题描述在 NBA 季后赛中，我们总是安排较强的队伍对战较弱的队伍。例如，用排名第 1 的队伍和第 n 的队伍对决，这是一个可以让比赛更加有趣的好策略。现在，给你 n 支队伍，你需要以字符串格式输出它们的 最终 比赛配对。在每一轮的匹配过程中，你都需要遵循 将强队与弱队配对 的原则。

输入格式输入一个正整数n（n>1)，代表n 支队伍按从 1 到 n 的正整数格式给出，分别代表它们的初始排名（排名 1 最强，排名 n 最弱）。

输入样例4

输出格式用括号和逗号来表示匹配对——括号表示匹配，逗号来用于分割。

输出样例((1,4),(2,3))

注： 在第一轮，我们将队伍1和4配对，2和3配对，以满足将强队和弱队搭配的效果。 得到(1,4),(2,3). 在第二轮，(1,4) 和 (2,3) 的赢家需要进行比赛以确定最终赢家， 因此需要再在外面加一层括号。 于是最终答案是((1,4),(2,3))。

解题思路也是个典型的递归问题，是个逐层递归的题，从1可以扩展到(1,2)。括号里的每一个数再各自扩展成(1,4),(2,3)，扩展的结果和当前扩展目标和当前数有关，比如从2层扩展到4层，与1相匹配的数就是(4+1)-1 ,与2相配的数就是(4+1)-2

解题步骤

逐层构建方法解决问题。

构建方法，如果当前数字为1，则返回1，此乃递归出口，表示在第一层只有1。否则递归，参数为当前数字的1/2的。

构建方法，参数是当前序列，扩展层数。

构建方法，当前数字，扩展层数，这一步负责将每个需要扩展的数变成扩展目标。

解题代码import java.util.Scanner;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

public class gameOrder {

public static void main(String[] args){

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

String res = new String();

System.out.print(order(n,res));

}

public static String order(int n , String str){

if (n==1){

return "1";

}

return enlarge(order(n/2,str),n);

}

public static String enlarge(String str, int num){

int n = num/2;

int i =n;

while (i!=0){

String pattern = "\\b"+i+"\\b";

Pattern r = Pattern.compile(pattern);

Matcher m = r.matcher(str);

str = m.replaceFirst(getlarge(i,num));

i--;

}

return str;

}

public static String getlarge(int num1, int n){

return "(" + num1 + "," + (n + 1 - num1) + ")";

}

}