找一個數的所有因子的方法

這是我中一時遇到而解決不了的問題,解決不了不是因為我不懂寫電腦程式,也不是因為這問題本身很困難,而是自己的思想陷入了一個無窮遞歸的循環中跑不出來,因此令我對電腦最初設計者Newman提出的「停止問題(Halting problem)」印象深刻,人腦真的不同電腦。
我當時用的是Dbase作業系統,所以當學到有速算法可立刻分出哪一個數是某數的倍數時,立刻蠢蠢欲動,想寫一個可以分解一個數的所有因子的程式,我的思路是既然一個數最高的因子是它的平方根,因此只要由2開始逐個用速算法測試,直到它最接近它的平方根的整數為止,但是如此一來,數值大小便和要測試的時間成指數比例,8個位的數字是4個位的100部,如何縮短它的所需時間呢?
其中一個思路就是利用遞歸的慨念,在測試某一數字是否它的因子之前,先去測此因子是不是之前已測試的因子之部數,例如要測試101是否為4的部數,只要再測試一下4是不是之前曾測試過的因子2的部數,另外再用邏緝去推斷,既然101不可以被2整除,則它當然不可能被2的部數4來整除;倒過來說,如果它可以被2去整除,則一定要先測試才知道它可不可以被4去整除。

所以最初想的程式的大致結構如下:
輸入1N位的數字,用它的平方根來產生1陣列,以陣列的1來表達可被整除
由2開始到它的平方根(否則會進死迴圈不能停止),
{當陣列對應的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被整除,
如果可以的話把陣列對應的值改成1}

,好像是忘記了什麼?忘記了節省時間的因子再被之前的因子去測試的「偉大發現」!
再補充一下,但如何加上去呢?因為測試數字的次數是定值,而測試因子的次數卻跟因子值而變,我當時不懂如何用Dbase寫出來,因此問題被擱置了!

現在當然是想通了,
輸入1N位的數字,用它的平方根來產生1陣列,以陣列的1來表達可被整除
K由2開始到它的平方根(否則會進死迴圈不能停止),
{
N由2開始直到K的正整數平方根
(當陣列K的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被N整除,
如果可以的話,則:
假如陣列K的值是0,即之前已測試的因子不可以整除輸入的數字,改陣列N的值為0;
並把K加1)
當陣列K的值不是1時,
用存在資料庫的樣式來比較輸入之數字是不是可被整除,
如果可以的話把陣列對應的值改成1;}

不過我當時想的還有更深的一步,有沒有辦法去令電腦自己懂得尋找速算法而不見程式人員輸入呢?我當然懂2,3,4,5,6,9的速算法,但要是其他未知的呢?可不可以寫一個程式去讓電腦先去自己生產一個速算法,然後再利用自己生產的速算法來檢測因子呢?可不可以再推前幾步呢?

(以當時的技術是決沒有可能,但現在可以利用程式天演算法(evolutionary computing)來自己生產程式,所以是絕對可能,但是它可能到再前哪一步呢?相信再進步的電腦也不懂自己找問題來研究吧!)

~ 由 newnewhkcc1976 於 五月 1, 2009.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

 
%d 位部落客按了讚: