分形(找规律)

例题：循环比赛日程表

  1. 8位选手的循环比赛表可以由四名选手的循环比赛表根据对称性“生成出来”
  2. 分治思想：不断的把一个规模为n的问题分成4个规模为n/2的子问题
  4. //左上角(a1,b1)，右下角(a2,b2)，[begin, end]的数字组成
  5. void makelist(int a1, int b1, int a2, int b2, int begin, int end)
  6. {
  7.     //问题的边界
  8.     if (begin == end){
  9.         a[a1][b1] = begin;
  10.         return ;
  11.     }
  13.     //求解子问题
  14.     //分成四个区域，左上角区域的右下角坐标是(a3, b3)
  15.     int a3 = (a1 + a2) / 2, b3 = (b1 + b2) / 2; 
  16.     int mid = (begin + end) / 2;
  17.     makelist(a1, b1, a3, b3, begin, mid);  //左上角区域
  18.     makelist(a1, b3+1, a3, b2, mid+1, end); //右上角区域
  19.     makelist(a3+1, b1, a2, b3, mid+1, end); //左下角区域
  20.     makelist(a3+1, b3+1, a2, b2, begin, mid); //右下角区域
  21. }
  23. //函数调用
  24. makelist(1, 1, n, n, 1, n); //左上角(1,1)，右下角(n,n)，由1~n数字组成
  27. // 这道题目也可以用从小大到递推出来整个地图

例题：Fractal Streets

  1. //分形，著名的通过一定规律无限包含自身的“分形”图。