公選課期末考察

2022-11-24 00:42:11 字數 1208 閱讀 9839

學生姓名: 何家晟學號:10064038

學院: 電腦科學學院

專業: 自動化年級: 10級

任課教師: 邢光林

2011年10月31日

趣味謎題之吃醋丈夫謎題演算法解析

摘要:吃醋的丈夫謎題的演算法分析,通過轉治法來進行分析處理。將問題轉化為圖的形式進行更加有效的分析。

通過列舉若干次來探索發現規律來解決本謎題。通過繪圖來觀察所需擺渡的次數,並發現其規律,進行合理的假設,再通過進一步的驗證來證實假設的正確性。

關鍵詞:

吃醋丈夫;轉治法;圖;假設;驗證

正文:吃醋丈夫謎題:假設有n對夫婦要度過一條河,有一隻船最多隻能載2個人過河。

若丈夫與妻子不在河的一岸,而在妻子的那岸有另一男士在場,即使有其他人在場,丈夫也會吃醋。問題是這n(n≥2)對夫婦能否順利過岸,若能過河,那麼需要渡幾次河?

要討論本問題的演算法解析,所應用的方法為轉治法。現在我們將本問題轉治為圖形式的問題來看,首先假設n=2時的情況,則有h1,h2,w1,w2,2對夫婦。

←①2對夫婦渡河圖

由圖①可知若n=2時則需要通過5次擺渡可以過河。則表明這個謎題是有解的,現在在具體分析在n對夫婦的情況下需要多少次擺渡。不妨再假設3對夫婦的渡河情況,即n=3,則有h1,h2,h3,w1,w2,w3三對夫婦。

↓↓②3對夫婦渡河圖

由圖②看出在3對夫婦渡河的時間複雜度顯然比2對夫婦渡河是要大的多,並且總計需要11次擺渡才能夠渡河成功,再次結合圖①來看,2對夫婦是需要5次擺渡能夠實現在符合題意的約束下渡河成功,3對夫婦則需要11次擺渡才能夠渡河成功。因此我們大膽假設在n=4的時候需要17次擺渡,n=5時需要23次擺渡。經過“圖”的方法進行確認,發現該假設是成立的,由於過於複雜筆者就不在此一一列舉。

因此當有n對夫婦渡河時,則需要5+(n-2)即6n-7次擺渡能夠成功渡河。那麼此謎題就解決了。

筆者認為謎題的方法只要正確便能找到解決為題的方法,方法的優劣能夠有效的減小時間複雜度。因此在解決問題前,人們常常通過計劃來探尋解決問題最為有效的方法來更為簡便的解決實際問題。將實際問題進行轉治,能夠有效的解決問題,當然轉治法並不使用於所有的問題,通過實際問題的轉化來解決問題。

在進行轉治分析處理的同時,還需要能夠冷靜的分析和探索事物的規律。這樣就能夠正確有效的解決實際問題。

參考文獻:

[1]百度百科

[2]謎題集

[3]演算法求解

[4]探索自然規律

[5]

網路安全基礎期末考察標準

網路安全基礎考察內容 適用班級 應用12301 樓宇12302考查形式 實踐性 可選題目 1 網路安全規劃與方案制定,網路規模自定,需完整合理的描述自己的網路安全構建,對於客戶機 伺服器 路由器 防火牆 入侵檢測系統 交換裝置等安全相關裝置有較完備的安排與規劃。2 對於網路安全形式的分析 分析現有網...

大學物理實驗期末考察報告

1 什麼是誤差 絕對誤差和相對誤差?絕對誤差和相對誤差各描述什麼樣的物理意義?答 測量值與真值之差異稱為誤差 測量誤差與被測量真值之比稱為相對誤差 測量值與真實值之差的絕對值稱為絕對誤差。絕對誤差反映測量值偏離真值的大小,它可以表示一個測量結果的可靠程度 相對誤差是絕對誤差與測量值或多次測量的平均值...

相關推薦