註冊 登入



打印

[程式編寫] discrepancy problem

[隱藏]
引用:
原帖由 darigold 於 2018-9-18 12:02 AM 發表



哦…那你慢慢玩。

有斷估冇痛苦,我估下你最終會玩成點。
我們已經知道sequence到1000左右收皮,假設 number of sequence會一路爆上之500再一路爆落。
再假設到500左右 1% sequence會活下來。
你的 storage 係2^500 x 1% x 500 bits / 8 bit per byte / 1024 kb per byte / 10 ...


兩樣野:一,人會變通,二,實際情況可能比起斷估情況更理想。

先講一,其實我只係想知道每個長度有幾多可能性。具體每個可能性是甚麼,我真是無乜特別興趣要知。例如望住個77.txt,入面六億幾條路徑,我暫時諗唔到可以點用。所以,往後,如果發現儲存空間不足,我會修改程式,只保留最近兩步,作為預備windows update/hang機/斷電之後個程式由上一步繼續之用,兩步之前啲file全部delete。

再講二,實際長度去到幾多,分支可能性才達到maximum,呢個係我有興趣知道的問題。未必是500附近。我唔知係幾多。長度78計到出來了,可能性少過長度77。



熄燈,鎖門,爆大鑊
精選樓盤
引用:
原帖由 煙民母親生賤種 於 2018-9-18 03:46 AM 發表

雖然我唔識呢個 topic, 但唔同意你話無實際用途。呢個世界能夠發生到既野,都有佢用途,而只係你,我,他,他們未發現到佢既用途。
都係。數學理論最初可能出於好奇心而被建立,後來才喺其他領域被發現有用途。complex number就係一個好例子。



熄燈,鎖門,爆大鑊

回覆 引用 TOP

引用:
for all i, j

to check if they are "alive", we only need to consider all the "j"s such that 2^n*k is divisible by j (otherwise, the newly added last step would not be performed)

let j=2^x*k^y, where 0≦x≦n, 0≦y≦1

the resultant length of (a[j], a[2*j], …, a[2^n*k]) would be of the form 2^n*k/j=2^(n-x)*k^(1-y)

there are 3 possibilities:

case 1: 2^(n-x)*k^(1-y)=1 (when x=n, y=1)

case 2: 2^(n-x)*k^(1-y)=k (when x=n, y=0)

case 3: 2^(n-x)*k^(1-y) is an even number (when x<n)
終於有時間看看,看到中間有個問題:

1. for all i, j             --->即 j 是任何正整數
2. 0 < k < D           ---->即 k 是 少於 D的任何正整數
3. j divides 2^n*k     --->即 j | 2^n*k

所以,  只要 j | k, 則 j | 2^n*k
咁, j 未必是 j=2^x*k^y 這個形式,

例如: k = 9,  L = 2^x * 9, j 可以是 2^x * 3,
這 L/j = (2^x * 9) / (2^x * 3) = 3
咁 2^n*k/j 其實可以是單數,是不是?

如果按你的邏輯,k 需要是質數。



引用:
原帖由 assembly.jc 於 2018-9-19 01:33 AM 發表



終於有時間看看,看到中間有個問題:

1. for all i, j             --->即 j 是任何正整數
2. 0 < k < D           ---->即 k 是 少於 D的任何正整數
3. j divides 2^n*k     --->即 j | 2^n*k

所以,  只要 j | k, 則 j | 2^n*k
咁, j 未必是 j=2^x*k^y 這個形式,

例如: k = 9,  L = 2^x * 9, j 可以是 2^x * 3,
這 L/j = (2^x * 9) / (2^x * 3) = 3
咁 2^n*k/j 其實可以是單數,是不是?

如果按你的邏輯,k 需要是質數。
「例如:k=9,L=2^x*9,j可以是2^x*3」呢句錯了。如果k係9,如果我代入x=1,L就係18,j就係6,j除唔盡k。

你觀察返discrepany<5、7、9、11的情形,k唔一定要係質數。



附件

x.jpg (246.08 KB)

2018-9-19 12:37 PM

x.jpg

熄燈,鎖門,爆大鑊
[隱藏]
我再消化返我嗰個證明,諗到更簡單/更符合直觀的表達。

「單雙性」。

任意兩個(不同的)單數,距離至少是2。

任意兩個(不同的)雙數,距離至少是2。

即:任意兩個「單雙性相同」的數字,距離至少是2。

一個序列,長度L,k除得盡L,子序列長度L/k,前一步的子序列長度L/k-1,如果L/k-1與D單雙性相同,即是前一步的子序列終點最遠只可能觸及±(D-2)。

咁你再行多一步,都唔會觸及±D,最多觸及±(D-1)。即是discrepancy仍然<D。

所以,「可能性一開二」的充份而且必要條件是:L/k-1與D單雙性相同,亦即是,L/k與D單雙性不同。

問題係:咁有啲咩數,除極都係單數/雙數?

單數除極都係單數。你無可能單數俾一個(除得盡佢嘅)數除完之後會變雙數的。

雙數如果係呢個形式:2^n*k,除出來可能係1,或k,或雙數。

所以:

如果D係單數,L必須是2^n*k,n=0,1,2,...,k<D。呢類數,除極都一係細過D,一係出雙數。

如果D係雙數,仲簡單,只要L係單數就可以了。單數除極都係出單數。



熄燈,鎖門,爆大鑊
引用:
原帖由 肥矮太空灰 於 2018-9-19 12:37 PM 發表


「例如:k=9,L=2^x*9,j可以是2^x*3」呢句錯了。如果k係9,如果我代入x=1,L就係18,j就係6,j除唔盡k。

你觀察返discrepany
寫多了,中間二行可以不要,然而,j 是否能整除 k,不是重點,重點是 L/j 可以是單數。

改個過個變數就是了,修改如下:
1. for all t, j             --->即 t, j 是任何正整數
2. 0 < k < D           ---->即 k 是 少於 D的任何正整數
3. j divides 2^n*k     --->即 j | 2^n*k

所以,  只要 t | k, 則 t | 2^n*k      
咁, j 未必是 j=2^x*k^y 這個形式,可以是 2^x * t,t < k

設,t = 3, k = 9,  L = 2^x * 9, j 可以是 2^x * 3,
這 L/j = (2^x * 9) / (2^x * 3) = 3
咁 2^n*k/j 其實可以是單數。



引用:
原帖由 肥矮太空灰 於 2018-9-19 01:50 PM 發表

我再消化返我嗰個證明,諗到更簡單/更符合直觀的表達。

「單雙性」。

任意兩個(不同的)單數,距離至少是2。

任意兩個(不同的)雙數,距離至少是2。

即:任意兩個「單雙性相同」的數字,距離至少是2。

一個序列,長度L,k除得盡L,子序列長度L/k,前一步的子序列長度L/k-1,如果L/k-1與D單雙性相同,即是前一步的子序列終點最遠只可能觸及±(D-2)。

咁你再 ...
Thanks, 稍後再看



回覆 引用 TOP

引用:
原帖由 assembly.jc 於 2018-9-19 02:59 PM 發表


寫多了,中間二行可以不要,然而,j 是否能整除 k,不是重點,重點是 L/j 可以是單數。

改個過個變數就是了,修改如下:
1. for all t, j             --->即 t, j 是任何正整數
2. 0 < k < D           ---->即 k 是 少於 D的任何正整數
3. j divides 2^n*k     --->即 j | 2^n*k

所以,  只要 t | k, 則 t | 2^n*k      
咁, j 未必是 j=2^x*k^y 這個形式,可以是 2^x * t,t < k

設,t = 3, k = 9,  L = 2^x * 9, j 可以是 2^x * 3,
這 L/j = (2^x * 9) / (2^x * 3) = 3
咁 2^n*k/j 其實可以是單數。
呀我明你意思。我個證明有漏洞。如果k係合成數,2^n*k的因子,j,未必係2^x*k^y。

假設k=Π(p[t]^q[t]),j應該係2^x*Π(p[t]^y[t])咁樣形式,當中0≦x≦n,0≦y[t]≦q[t]。

結果一樣,只係要case 2諗多少少:如果除完出來,又唔係1,又唔係2^(某個正數)*(另一個正數),即是剩番Π(p[t]^(q[t]-y[t])),即是,a factor of k。

k本身小於D。k的因子必然不大於k。所以k的因子必然小於D。結果一樣,最後一步是「任行」,可能性是前一步乘2。

謝謝指正。

[ 本帖最後由 肥矮太空灰 於 2018-9-19 03:54 PM 編輯 ]



熄燈,鎖門,爆大鑊

回覆 引用 TOP

引用:
原帖由 肥矮太空灰 於 2018-9-18 09:34 AM 發表




兩樣野:一,人會變通,二,實際情況可能比起斷估情況更理想。

先講一,其實我只係想知道每個長度有幾多可能性。具體每個可能性是甚麼,我真是無乜特別興趣要知。例如望住個77.txt,入面六億幾條路徑,我暫時諗唔到可以點用。所以,往後,如果發現儲存空間不足,我會修改程式,只保留最近兩步,作為預備windows update/hang機/斷電之後個程式由上一步繼續之用, ...
BFS 真的不是辦法 … 就算 darigold 估錯一億倍,你都係冇機會…



[隱藏]
引用:
原帖由 tom.care 於 2018-9-20 09:09 AM 發表



BFS 真的不是辦法 … 就算 darigold 估錯一億倍,你都係冇機會…
咁我run到佢run唔到為止。盡做。



熄燈,鎖門,爆大鑊

回覆 引用 TOP

引用:
原帖由 肥矮太空灰 於 2018-9-19 01:50 PM 發表

一個序列,長度L,k除得盡L,子序列長度L/k,前一步的子序列長度L/k-1,如果L/k-1與D單雙性相同,即是前一步的子序列終點最遠只可能觸及±(D-2)。
這一段想表達什麼?

例如: L=99, k=3, D=5
L/k = 99/3 = 33
L/k-1 = 99/2 = 49

子序列終點是什麼?



引用:
原帖由 assembly.jc 於 2018-9-21 07:20 PM 發表



這一段想表達什麼?

例如: L=99, k=3, D=5
L/k = 99/3 = 33
L/k-1 = 99/2 = 49

子序列終點是什麼?
先乘除後加減,L/k-1=99/3-1=33-1=32。

discrepancy的圖形意義是:試盡所有k,序列最遠可以走到離開原點有幾遠。discrepancy<D的話,即是無論你選甚麼k,在整個過程中,你離開原點最遠的時候,距離都小於D。

長度=L的序列由長度=L-1的序列建構出來。

對應於每一個k,都有一個特定的子序列。如果k除不盡L,即是新增的第L步是不會被執行,子序列與之前L-1時的情況相同,discrepancy也相同,不用再計。

所以只需考慮k除得盡L的情形。



熄燈,鎖門,爆大鑊
引用:
原帖由 肥矮太空灰 於 2018-9-21 11:09 PM 發表


先乘除後加減,L/k-1=99/3-1=33-1=32。

discrepancy的圖形意義是:試盡所有k,序列最遠可以走到離開原點有幾遠。discrepancy
既然是數學證明,師兄試下用簡單通用的數學符號去表現關鍵的概念,然後一步步推演出結論,咁大家可能容易理解些。



回覆 引用 TOP

例如
證明: 任何整數 n, d. 如果 n 是單數,則 n/d 也是單數。
反證法:
設 s, k 是整數,(2*k-1) / d 是雙數
則,(2*k-1) / d = 2s
=> 2*k-1 = 2sd
單數唔可能等於雙數,故得證。



回覆 引用 TOP

 59 1234
 提示:支持鍵盤翻頁 ←左 右→
[按此隱藏 Google 建議的相符內容]






重要聲明:本討論區是以即時上載留言的方式運作,香港討論區對所有留言的真實性、完整性及立場等,不負任何法律責任。而一切留言之言論只代表留言者個人意 見,並非本網站之立場,讀者及用戶不應信賴內容,並應自行判斷內容之真實性。於有關情形下,讀者及用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。 由於本討論區受到「即時上載留言」運作方式所規限,故不能完全監察所有留言,若讀者及用戶發現有留言出現問題,請聯絡我們。香港討論區有權刪除任何留言及拒絕任何人士上載留言 (刪除前或不會作事先警告及通知 ), 同時亦有不刪除留言的權利,如有任何爭議,管理員擁有最終的詮釋權 。用戶切勿撰寫粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論,敬請自律。本網站保留一切法律權利。


Copyright©2003- Discuss.com.hk Limited. All Right Reserved.
版權所有,不得轉載。