算法合集之?dāng)?shù)位計(jì)數(shù)問題解法研究-wenkub
2022-11-02 18:36:24 本頁面
【正文】 上為解決此類問題的總原則，接下來我們通過兩道例題說明如何利用上述原則解決具體問題。 例題 1： The Sum ?按照上述原則將 [1,N]劃分為若干子區(qū)間：（這里以 N=123456為例） ? [1,9]U[10,99]U[100,999]U[1000,9999]U[10000,99999]U[100000,123456] 例題 1： The Sum ?那么，原問題轉(zhuǎn)化為一個(gè)新問題：詢問[A,B]的結(jié)果，其中 A和 B包含相同的數(shù)字個(gè)數(shù)。 555小于 78，因?yàn)樵谧值湫蛞饬x下” 555””78”。 例題 2：算法分析 ? 嘗試分解區(qū)間，我們發(fā)現(xiàn)，似乎怎樣將區(qū)間拆分都不能將問題簡化。 ?顯然，當(dāng) K的數(shù)字和大于 S時(shí)，答案等于[A,B]區(qū)間內(nèi)所有數(shù)字和為 S的數(shù)的總數(shù)，當(dāng) K的數(shù)字和小于 S時(shí)，答案等于 0。 例題 2：算法分析 ? 那么，下一步的區(qū)間劃分主要考慮字典序的因素，因此按照首位的不同數(shù)字進(jìn)行劃分。 。 ? 若問題不滿足上述條件，可以考慮對(duì)原問題加以轉(zhuǎn)化使其能夠滿足以上條件。 例題 2：算法分析 ? 新問題：當(dāng) K的數(shù)字和為 S時(shí)，在 [A,B]中所有
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1