確保循環結束的機制

Question

當我在大學時，我們有來自David Parnas的客座講座。在這篇文章中，他提到了一個用於保證循環（while循環，for循環等）在某個時刻安全退出的機制。他嘲笑沒有人知道這是什麼......可悲的是，多年後我也不知道。有誰知道這個機制被稱爲什麼？

Answer 1

根據他的專業領域（包括正確性的正式證明）來判斷，我認爲他的意思是loop variant，這是一種用於證明環路終止的通用技術。

Answer 2

這個問題似乎不合邏輯。

沒有一個gaurantee可以確保循環退出，而不是創建一個你知道會被命中的後置條件，即增加一個計數器，不要觸摸循環內部的計數器並使其達到最大值。

您也可以創建一個計時器或其他結構來檢查循環是否花費太長時間。

帕納斯在這裏暗示的是什麼？任何循環的普遍退出不會干擾邏輯或簡單地設計適當的後置條件？

Answer 3

有很多方法，以保證循環退出安全：

1. 不要寫是無限
2. ，其他的被留下作爲一個鍛鍊; Tibial

嚴重的是，最好的方法是保持簡單，並有一個穩定和完全測試的終止條件（即檢查是否應該運行另一次迭代或退出的代碼）。

你所描述的很可能會被翻譯成halting problem，這是一個衆所周知的問題，沒有解決方案。

此外，谷歌搜索顯示David Parnas在利默里克大學工作，你可以打電話給他並要求與他交談。我敢肯定，他會很高興你還在試圖:)

Answer 4

你的客座講師可能已經提到Cycle Detection，檢測無限循環的方法來從他教你回去再學。

This blog post描述了檢測鏈表中的無限循環。有趣的是，它使用與維基百科文章相同的術語。