×
通過社交網站直接登錄
×
條@我的評論,查看@我
條新私信,查看私信
條新評論,查看評論
位新粉絲 查看粉絲
數學天地 趣味數學 開放題 計算 解決
感謝 匿名網友 於 2020-03-20 14:50:20 提供 來源:33IQ網
(3)
現定義三類問題
P類問題:所有可以在多項式時間內求解的判定問題構成P類問題。判定問題:判斷是否有一種能夠解決某一類問題的能行演算法的研究課題。
NP類問題:所有的非確定性多項式時間可解的判定問題構成NP類問題。非確定性演算法:非確定性演算法將問題分解成猜測和驗證兩個階段。演算法的猜測階段是非確定性的,演算法的驗證階段是確定性的,它驗證猜測階段給出解的正確性。設演算法A是解一個判定問題Q的非確定性演算法,如果A的驗證階段能在多項式時間內完成,則稱A是一個多項式時間非確定性演算法。有些計算問題是確定性的,例如加減乘除,只要按照公式推導,按部就班一步步來,就可以得到結果。但是,有些問題是無法按部就班直接地計算出來。比如,找大質數的問題。有沒有一個公式能推出下一個質數是多少呢?這種問題的答案,是無法直接計算得到的,只能通過間接的「猜算」來得到結果。這也就是非確定性問題。而這些問題的通常有個演算法,它不能直接告訴你答案是什麼,但可以告訴你,某個可能的結果是正確的答案還是錯誤的。這個可以告訴你「猜算」的答案正確與否的演算法,假如可以在多項式(polynomial)時間內算出來,就叫做多項式非確定性問題。
NPC問題:NP中的某些問題的複雜性與整個類的複雜性相關聯.這些問題中任何一個如果存在多項式時間的演算法,那麼所有NP問題都是多項式時間可解的.這些問題被稱為NP-完全問題(NPC問題)。
試問:
那麼P問題與NP問題能相互轉換嗎?

標籤: 之和 數字 日期
著作權歸作者所有,轉載請聯繫作者獲得授權
答案:
解析:
5
收藏
數學天地 趣味數學 選擇題 計算 原創
於 2019-12-18 11:30提供
(16)

小D每天上下班需要乘坐公交車和地鐵,已知乘坐公交車的價格為1元/次,乘坐地鐵價格為5元/次,小D每天上班先乘坐公交車到地鐵站,再乘坐地鐵到公司,下班是先乘坐地鐵,再乘坐公交車,當你換乘時,可以享受換乘優惠1元,現在小D參加了「今日刷,明日返」的優惠活動,最高每天返3元,即當天交通卡刷卡消費超過3元,明天就返3元到你的交通卡里,活動持續10天,即最高返30元,又當你的交通卡在當月消費滿70元,後面乘坐地鐵的消費金額享受9折優惠,而小D周末不用公交卡,假如現在是2019年12月1日,小D不想在本月充值公交卡,那麼他至少要在公交卡里預留多少錢?(精確到整數)

標籤: 地鐵 公交車
著作權歸作者所有,轉載請註明出處
答案:
解析:
17
收藏
數學天地 趣味數學 選擇題 計算 原創
於 2019-11-15 12:16提供 來源:33IQ網
(21)

假如現在國家要進行一項工程,需要將圖中9個城市用某種特殊纜線連接(只要任意兩個城市之間都有至少一條通路即可,例如「北京」和「貴陽」,可以通過「北京」——「鄭州」——「株洲」——「貴陽」連接起來)。

圖中顯示的是所有允許用纜線連接的城市以及連接的成本如圖所示。
現在我們來討論解決類似問題的方法
①首先連接整幅圖中成本最小的連接線,也就是「鄭州」——「徐州」。之後把「鄭州」和「徐州」看為一個整體,尋找其他城市中與他們之一相連成本最小的城市,也就是「徐州」——「上海」。然後將三個連接過的城市看為一個整體,找出其他城市與這三個城市之一連接成本最小的城市,也就是「北京」——「鄭州」。就像這樣,直到所有城市都連為一體。

②從每個城市出發,都有若干個允許連接的城市。首先對所有城市,連接它們與從它們出發允許連接的城市中連接成本最小的。例如從「鄭州」出發,要連接「鄭州」——「徐州」;從「貴陽」出發,要連接「貴陽」——「柳州」;從「柳州」出發,也要連接「貴陽」,但是已經連接過,就不用再連接。從「昆明」出發,應該與「貴陽」相連,雖然「貴陽」已經與「柳州」相連,但是仍然需要「昆明」與貴陽相連。如此一來,圖中出現了若干個連為一體的城市集(例如「上海」「徐州」「鄭州」「北京」四個城市被連為一體),然後對於每一個城市集,找出它們與其他城市集之間連接的成本最小線路。例如「上海」「徐州」「鄭州」「北京」四個城市形成的城市集,與圖中剩餘5個城市形成的城市集之間,存在「鄭州」——「成都」,「鄭州」——「株洲」,「上海」——「株洲」。而我們要選擇的是成本最小的「鄭州」——「株洲」。就這樣,直到所有城市連為一體。

上面說的方法①和方法②,都成功找出了圖中的最優解。可是,這兩種方法是否具有普適性,解決任意類似問題呢?

(答案提示中,是一個結論,這個結論是本題的關鍵)

標籤: 工程 最優解
著作權歸作者所有,轉載請聯繫作者獲得授權
答案:
解析:
16
收藏
數學天地 趣味數學 選擇題 計算 原創
於 2015-08-31 16:00提供
(101)

某網舉辦每日簽到抽獎贏好禮活動,大獎是中獎幾率僅1%、價值3319元的寫真集(什麼人的寫真集值3319?漏了小數點吧?。。。呃,反正這不是重點)。用戶每天簽到后,在抽獎之前可以在下面兩個選項里任選其一,提高中獎概率:

1、前一天的中獎率提高20%(如第一天是1%,第二天就是1.2%,第三天就是1.44%,以此類推)

2、前一天的中獎率加4%(如第一天是1%,第二天就是5%,第三天就是9%,以此類推)

當中獎幾率超過100%后,就一定會中獎,請問運氣最差的情況下,最少需要多少天才能抽中寫真集?(第一天從中獎率1%開始算起)

該題最近被收錄於題集 等待學識解鎖解析
最後修改於 2022-11-24 16:35:29
著作權歸作者所有,轉載請聯繫作者獲得授權
答案:
解析:
78
收藏
數學天地 趣味數學 開放題 計算 原創
感謝 匿名網友 於 2016-01-16 21:42:11 提供
(11)

   在一個陰暗的角落裡,有幾個人交流。已知其中有2個傻子,2個瘋子,1個普通人,1個高智商的人,2個幸運兒(只有這幾類人)。

   他們正在做一套題,這套題包含10個選擇題,2分一個;10個判斷題,2分一個;10個填空題,2分1個;10個簡答題,4分一個,總分為100分。

   其中,我們知道,傻子選擇題的正確可能性是20%,填空題不可能正確,判斷題的正確可能性是50%,簡答題不可能正確;瘋子簡答題不可能正確,其餘所有題的正確可能性都是10%;普通人簡答題的正確可能性是75%,其餘題做對的可能性是50%;高智商簡答題一定做對,其餘所有題的正確可能性都是80%;幸運兒選擇題和判斷題一定能作對,其餘題做對的可能性是%30。

   問,有幾種情況?並列出及格率(精確至xx%) 的幾種可能 。

標籤: 正確 可能性
最後修改於 2021-11-10 09:34:10
著作權歸作者所有,轉載請聯繫作者獲得授權
答案:
解析:
6
收藏

原創趣味數學題庫提供各類與趣味數學相關的數學題解答以及各類小學趣味數學、趣味數學故事等。

如果你有其他有關趣味數學的好題目,歡迎與我們分享 請發布趣味數學的智力題