條件：1K內(nèi)存，1MHzCPU，每秒可以改變2^20次狀態(tài)。問：一個程序最長的運行時間是多少？

答：首先程序是確定性的，就說明內(nèi)存的狀態(tài)不會重復(fù)，否則就永遠結(jié)束不了。從這一點出發(fā)，可以知道內(nèi)存的狀態(tài)共有 2^8k , 然后CPU每秒改變 2^20 個狀態(tài)，所以這臺計算機最長出現(xiàn)不重復(fù)的狀態(tài) 2^(8k-20）秒。

posted on 2009-10-15 10:57 尹東斐閱讀(3675) 評論(12) 編輯收藏引用

FeedBack:

# re: 最長運行時間（百度筆試題）

2009-10-15 11:06 | wulin

汗，我當時就想寫這個答案的，但是又不確定，不知道這么分析，早知道寫上了。
這個題似乎也挺簡單，不過是不是需要留出存儲程序的內(nèi)存空間呢？回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-15 11:12 | 尹東斐

@wulin

不需要考慮存儲程序的空間，因為數(shù)據(jù)和程序在內(nèi)存中完全沒有區(qū)別。所以從某種角度來看，程序也是數(shù)據(jù)的一種。回復(fù) 更多評論

# re: 最長運行時間（百度筆試題） [未登錄]

2009-10-15 12:33 | lee

內(nèi)存狀態(tài)不會重復(fù)？？內(nèi)存里不就是0，1么，重復(fù)指的是什么意思？回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-15 16:52 | yindf

@lee

重復(fù)指：比如說內(nèi)存原來是 10101010101010 如果你的程序運行了一會，內(nèi)存又成為 10101010101010 的話，那么你的程序肯定不會正常結(jié)束的。

這并不是指普通的死循環(huán)，死遞歸等等，而是指計算機的狀態(tài)又回到原點了。回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-15 18:09 | Vincent

能說下其他幾道筆試題嗎?^_^ 回復(fù) 更多評論

# re: 最長運行時間（百度筆試題） [未登錄]

2009-10-17 22:57 | steven

這個題目真是不知所云，答案也是一樣，莫非是我太out了？回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-18 08:00 | Chika

這是什么部門的筆試題啊？回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-24 08:57 | 淡月清風

這問題，真是不之所云。回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-24 10:14 | yindf

@Vincent

這題目也是別人告訴我的，其他題目據(jù)說不是很難。回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2009-10-24 10:15 | yindf

@steven

這種開放性的題目是比較難找到切入點，不過仔細想想還是有辦法的。回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2010-03-13 08:18 | zhjx

那么詢問如果運行一段時間時是10101010101010，但是再過了一段時間之后是10101010101010這種情況為何不可以? 回復(fù) 更多評論

# re: 最長運行時間（百度筆試題）

2010-03-14 11:24 | yindf

@zhjx

那就是說你的程序存在從狀態(tài)10101010101010 到狀態(tài)10101010101010的一個回路，那么你的程序就永遠不會結(jié)束了。（要考慮狀態(tài)不僅包括數(shù)據(jù)，連內(nèi)存中的指令也一樣了）。回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2010年3月

日

一

二

三

四

五

六

常用鏈接

留言簿(4)

隨筆檔案

文章分類

深入探索 boost::lambda 系列(3)

文章檔案

2009年2月 (3)

相冊

好友博客

CUCmehp
λ-calculus
編譯器狂人

常用鏈接

留言簿(4)

隨筆檔案

文章分類

文章檔案

相冊

好友博客

搜索

最新評論

閱讀排行榜

評論排行榜