PHPチームの試合問題
13750 ワード
nチームの試合は、それぞれ0、1、2...n−1は、それらの間の実力対比関係が知られており、1つの2次元配列w[n][n]に格納され、w[i][j]の値はi、jと番号付けされたチームの中でより強い1本を表す.したがってw[i][j]=iまたはjは、それらの出場順序を与え、order[n]={4,3,5,8,1......}のような配列order[n]に格納される.では、1回戦は4対3、5対8です.......勝者が昇格し、敗者が淘汰され、同じラウンドで淘汰されたすべてのチームの順位は細分化されなくなり、すなわち勝手に並ぶことができ、次のラウンドは前のラウンドの勝者が順番に、さらに2対5の順に、例えば1位のプログラミングが実現するまで、2次元配列w、1次元配列orderと試合順位を出力するための配列result[n]を与え、resultを求める.
1 <?php
2 # ， w[n][n] order[n]
3 # r[n]
4
5 #
6 function swap(&$a, $i, $j) {
7 $temp = $a[$i];
8 $a[$i] = $a[$j];
9 $a[$j] = $temp;
10 }
11
12 function result($w, $order) {
13 $result = array();
14 while (count($order) > 1) {
15 $len = count($order);
16 $next_order = array();
17 for ($i = 0; $i < $len; $i += 2) {
18 #
19 if ($i == $len - 1) {
20 $next_order[] = $order[$i];
21 break;
22 }
23
24 # ，
25 $next_order[] = $w[$order[$i]][$order[$i + 1]];
26 $result[] = $w[$order[$i]][$order[$i + 1]] == $order[$i] ? $order[$i + 1] : $order[$i];
27 }
28
29 #
30 $order = $next_order;
31 }
32
33 $result[] = $order[0];
34 return $result;
35 }
36
37 # ， O(1)
38 function result2($w, $order) {
39 $limit = count($order);
40
41 # n - 1
42 while ($limit > 1) {
43 #
44 for ($i = 0, $j = 0; $i < $limit; $i += 2) {
45 $win_inx = ($i == $limit - 1) ? $i : ($w[$order[$i]][$order[$i + 1]] == $order[$i] ? $i : $i + 1); #
46 swap($order, $win_inx, $j); #
47 $j++;
48 }
49 $limit = $j;
50 }
51
52 return $order;
53 }
54
55 #
56 for ($i = 0; $i < 11; $i++) {
57 $order[] = $i;
58 for ($j = 0; $j < 11; $j++) {
59 $rand = rand(2, 11) % 2;
60 $w[$i][$j] = $rand ? $i : $j;
61 }
62 }
63
64 shuffle($order);
65
66 $result= result($w, $order);
67 print_r($w);
68 echo "<br>";
69 echo "<br>";
70 print_r($order);
71 echo "<br>";
72 echo "<br>";
73 print_r($result);
74 echo "<br>";
75 echo "<br>";
76 print_r(result2($w, $order));
77 echo "<br>";
78 echo "<br>";
79 ?>