2013年4月29日 星期一

Πυθαγόρας

陳力!!!!!!!!!!!!!!!!!可以來看一下XD
之前那個神祕的東東的證明~

a^2 + b^2 = c^2 (a, b, c 是整數)

=> (a/c)^2 + (b/c)^2 = 1
---------------------------------
Let: x = a/c,y = b/c (x, y 是有理數)

=> x^2 + y^2 = 1

=> y * y = (1+x)(1-x)

=> y / (1+x) = (1-x) / y
---------------------------------
Let: t = y / (1+x) = (1-x) / y (t 是有理數)

x = 1 - yt,y = t + xt

=> x = (1-t^2) / (1+t^2), y = (2t) / (1+t^2)
---------------------------------
Let:t = u / v (u, v 是整數)

x = (v^2 - u^2) / (v^2 + u^2)
y = ( 2 * u * v ) / (v^2 + u^2)
---------------------------------
因為是比例,所以乘一個 r

a = (v^2 - u^2) * r
b = (2 * u * v) * r
c = (v^2 + u^2) * r
---------------------------------
放進任意正整數的 v, u, r 便可以得到所有的triple。(v > u)

但如果要找的是素勾股數(gcd(a, b, c) = 1):

不需要 r 這個數字,v 和 u 也要互質且必定一奇一偶
(這部份很容易證明,若符合任一條件則不是素勾股數)
---------------------------------
但要保證,剩下的全部都是素勾股數就比較困難

a = (v^2 - u^2) 奇
b = (2 * u * v) 偶
c = (v^2 + u^2) 奇

gcd(b, c)
= gcd(b, b + c) // b=gx, c=gy, x互質於y, 則x互質於x+y(cont.)
= gcd(2 * u * v, (v + u) ^ 2) // 用反證法證明上述論點
= gcd(u * v, (u + v) ^ 2) // 可以知道b + c是奇數

引理:A互質於C 且 B互質於C => A * B互質於C
Pf: 用反證,A=pa, B=qb, C=gc, p*q = g, 矛盾

u互質於v => u互質於u+v => u互質於(u+v)^2
同理可以得證  =========> v互質於(u+v)^2

因此 gcd(u * v, (u + v) ^ 2) = gcd(b, c) = 1
因此 gcd(a, gcd(b, c)) = gcd(a, b, c) = 1
---------------------------------
最後順便證「對於不同的(u, v)不可能會有相同的(a, b, c)」

先觀察一下
a = (v^2 - u^2)
b = (2 * u * v)
c = (v^2 + u^2)
可以知道c > a 且 c > b,但不保證b > a

因為我們希望的是a, b, c由小排到大,所以要證的如下:
若 (u, v) != (u', v'),則 (a, b, c) != (a', b', c') 且 (a, b, c) != (b', a', c')

這邊很簡單,亂搞一下就出來了~XD
話說,證岀來還滿爽的XDDDDDDDD

2013年4月13日 星期六

有趣的題目

自己亂創的題目:

       給你N堆石頭,a1, a2, a3, a4, a5, a6...,你可以選一群大小相同的石堆集合,一起拿掉1顆石頭,如: 1,3,5,5,5 -> 1,3,4,4,5 或 1,3,5,5,5 -> 1,3,4,5,5。兩個人在玩這個遊戲,問先手勝利還是後手。

2013年4月1日 星期一

最小圓覆蓋

好久沒有學習新東西了,今天因為剛好要用到 (poi的plot)

所以就順便學一下了,如果有敘述不清,歡迎糾正>_____<

=====================================


Lv 1. Naiwny Algorytm(樸素算法) O(n^4)


枚舉三個點,做出一個圓圈圈,看有沒有覆蓋所有的點點點點


Lv 2. Zhang Jiao(張角法) O(n^3)



       想法其實也很簡單,就是枚舉兩個點(如圖中的A, B)當圓周上的點,接下來,因為離這個圓越遠的角一定越小,所以找出在AB線段上面跟下面兩種的最小角點(也就是像圖中的C與D),如果這兩個角alpha + beta >= pi 的話,你就得到一個包含圓了(太小就變成一個怪怪的橢圓了),雖然要特別判一下,就是如果max(alpha, beta) >= pi,就可以把AB當成直徑,如果 < pi,就拿這三個點做圓(必定唯一)。

接下來就要進行大進化!

Lv 9999999. Venusaur(廟哇花) O(n)

       其實叫隨機增量法 A___A ,利用一個神定理和Random的特性,以最樸素作法少三個冪次的超神演算法。(雖然常數頗大)

神定理:假設{p1, p2 ... pi-1},形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 產生一個最小包含圓:
加入 pi 之後(不是M_PI,只是p的第i項XDDD)
--------------------------------------------------------------------
1. pi 在圓內or圓上:爽!什麼毛都不用做
2. pi 在圓外:對於{p1 ~ pi}的最小包含圓,pi一定在圓上(依據神定理)

=====================================

至於他發生2.的這件事的機率是多少呢!因為1~i ,普通情況只會有三個點在圓上,所以機率是 3 / i !!!!!!!!!!! 接下來你輕鬆亂推廣神定理。

亂推神定理:假設{p1, p2 ... pi-1},且點 x 在圓周上,形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}且點 x 在圓周上,所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 且圓周上有點x,產生一個最小包含圓:
加入 pi 之後
--------------------------------------------------------------------
1. pi 在圓內or圓上:爽!什麼毛都不用做
2. pi 在圓外:對於{p1 ~ pi}且x在圓周上的最小包含圓,pi一定在圓上(依據亂推神定理)


=====================================


相同的,發生2.的機率還是3 / i 或更低。這時你已經確定有兩個點在圓周上了。
接下來,反正就再做一次亂推神定理,就有三個確定的點啦~~~~~~~~~

三個點形成一個圓~所以就結束了。

至於為什麼是O(n),請自行做點小小的計算吧。