淘宝网站建设的策划书,建设银行网上银行网站进入不了,太原做网站页面的,山东城乡住房建设厅网站《算法分析与设计》循环赛日程表算法
CONDITION1. 输入2的K次方支队伍#xff0c;输出赛程表。
CONDITION2. 考虑队伍数量不是2的K次方情况下#xff0c;输出赛程表。
【本题涉及算法#xff1a;分治算法】 本文给出两个方法#xff0c;
方法1只处理2^k(k1)场景输出赛程表。
CONDITION2. 考虑队伍数量不是2的K次方情况下输出赛程表。
【本题涉及算法分治算法】 本文给出两个方法
方法1只处理2^k(k1)场景方法2处理全部k2场景。并给出参数选择是否随机排序
方法1tableDoublePrepare方法2tablePrepare为对外提供接口。
实际逻辑方法处理为tableDouble与table 先上实现效果 Preparing
SDK
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
测试主体 static int[] arr2 new int[50]; // 前缀表static int[][] arr0; // 结果数组static int[][] arr1; // 间接结果数组static int[][] arr1_; // 结果数组public static void main(String[] args) {arr2[0] 1;for (int i 1; i arr2.length; i) {arr2[i] arr2[i - 1] * 2;}Scanner sc new Scanner(System.in);int n1 sc.nextInt();int n2 sc.nextInt();tableDoublePrepare(n1, 1, n1);printArr(arr0);tablePrepare(n2, 1, n2, true); // 第二参数为是否随机排序printArr(arr1_);}/*** 打印二维数组不限制方阵* param arr 二维数组*/public static void printArr(int[][] arr) {for (int i 0; i arr.length; i) {for (int j 0; j arr[0].length; j) {System.out.printf(%4d, arr[i][j]);}System.out.println();}} CONDITION1
Code: /*** 预处理进入循环赛表获取只适应于2^k, k1* param n 人数* param start 首位 比如1* param end 尾位 比如8真实比赛人数*/public static void tableDoublePrepare(int n, int start, int end) {System.out.println(循环赛程表2^k场景);arr0 new int[n][n];for (int i 0; i n; i) {arr0[i][0] i; // 首列赋值}tableDouble(n, arr0, start, end, end / 2);}/*** 循环赛表获取只适应于2^k, k1* param n 真实比赛人数* param arr 循环赛表* param start 首位 比如1* param end 尾位 比如8真实比赛人数* param disHalf 位差*/private static void tableDouble(int n, int[][] arr, int start, int end, int disHalf) {if (start end - 1) {arr[0][start - 1] arr[1][end - 1] start;arr[0][end - 1] arr[1][start - 1] end;} else {tableDouble(n, arr, start, start disHalf - 1, disHalf / 2);tableDouble(n, arr, end - disHalf 1, end, disHalf / 2);for (int i 0; i disHalf; i) {// 对应第一个tablefor (int j start - 1; j start disHalf - 1; j) {arr[i disHalf][j disHalf] arr[i][j];}// 对应第二个tablefor (int j end - disHalf; j end; j) {arr[i disHalf][j - disHalf] arr[i][j];}}}} CONDITION2
Code: /*** 预处理进入循环赛表获取适合任意大于等于2的比赛人数* param n 真实比赛人数* param start 首位 比如1* param end 尾位 比如8真实比赛人数* param random_ 是否进行天数随机*/public static void tablePrepare(int n, int start, int end, boolean random_) {System.out.println(循环赛程表全场景);int l 0;int r arr2.length;while (l r) {int mid (l r) / 2;if (arr2[mid] end) {l mid 1;} else {r mid - 1;}}n arr2[l];arr1 new int[n][n];for (int i 0; i end; i) {arr1[i][0] i; // 首列赋值超过end的不赋值}table(n, arr1, start, arr2[l], arr2[l] / 2, end);if (random_) {HashSetArrayListInteger set new HashSet();for (int j 1; j n; j) {ArrayListInteger list new ArrayList();for (int i 0; i end; i) {list.add(arr1[i][j]);}set.add(list);}int j 1;for (ArrayListInteger list : set) {int i 0;for (Integer integer : list) {arr1[i][j] integer;}j;}}if (n l) {arr1_ arr1;} else {arr1_ new int[end][n];for (int i 0; i end; i) {arr1_[i] arr1[i];}}}/*** 循环赛表获取适合任意大于等于2的比赛人数* param n 总位差* param arr 循环赛表* param start 首位 比如1* param end 尾位 比如8* param disHalf 位差* param ending 比赛人数真实比赛人数*/private static void table(int n, int[][] arr, int start, int end, int disHalf, int ending) {if (start end - 1) {if (start ending) arr[0][start - 1] arr[1][end - 1] start;if (end ending) arr[0][end - 1] arr[1][start - 1] end;} else {table(n, arr, start, start disHalf - 1, disHalf / 2, ending);table(n, arr, end - disHalf 1, end, disHalf / 2, ending);for (int i 0; i disHalf i ending - disHalf; i) {// 对应第一个tablefor (int j start - 1; j start disHalf - 1; j) {arr[i disHalf][j disHalf] arr[i][j];}// 对应第二个tablefor (int j end - disHalf; j end; j) {arr[i disHalf][j - disHalf] arr[i][j];}}}}
}
