acm新生培訓(xùn)講座ppt課件(編輯修改稿)
2024-11-15 04:27 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 n ? 1 3 5 7 … 2n 3 2n1 ? J(2n)=2*J(n)1. 約瑟夫環(huán)問(wèn)題一 ? 當(dāng)有奇數(shù)個(gè)人的時(shí)候，我們假設(shè)為 2n+1個(gè)人，經(jīng)過(guò)第一圈之后還剩下 n+1個(gè)人。去掉 2n之后，下一個(gè)要去掉的就是 1，最后還是剩下 n個(gè)人。 約瑟夫環(huán)問(wèn)題一 ? 剩下的 n個(gè)人還是一個(gè)新的約瑟夫環(huán)問(wèn)題。 ? 1 2 3 4 … n 1 n ? 3 5 7 9 … 2n 1 2n+1 ? J(2n+1)=2*J(n)1 約瑟夫環(huán)問(wèn)題一 ? 綜上，我們可以得到如下遞推公式： ? 該問(wèn)題可以在 O(n)的復(fù)雜度解決。 約瑟夫環(huán)問(wèn)題一 ? 約瑟夫環(huán)問(wèn)題一 ? 由上圖可以看出如果 n為 2的冪次方的時(shí)候，J(n)=1，這是顯然
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1