算法合集之數(shù)位計數(shù)問題解法研究-文庫吧在線文庫
【正文】 120小于 4，因為 120的數(shù)字之和為 3，而 4的數(shù)字之和為 4。 例題 2：算法分析 ?首先固定數(shù)字和，問題轉(zhuǎn)化為在區(qū)間 [A,B]內(nèi)所有數(shù)字和為 S的數(shù)當中，有多少個小于 K。 ? 區(qū)間劃分的目的是簡化問題，因此劃分方式也要因題而異，具體問題具體分析。 ? 這樣，在數(shù)字和相同的情況下，只需考慮字典序，我們成功的簡化了問題。 ? 我們可以將求 K在 1~N的位置換一種方式提出，即求 [1,N]中有多少個數(shù)比 K小，這個問題可以通過區(qū)間劃分的方法轉(zhuǎn)化為更小的問題并加以解決。 ?因為加減符號的改變與數(shù)字個數(shù)相關(guān)，因此為了讓規(guī)律更加明顯，我們盡量將1~N劃分為若干段區(qū)間，使得每個區(qū)間內(nèi)的數(shù)的數(shù)字個數(shù)相同。 例題 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)化為一個新問題：詢問[A,B]的結(jié)果，其中 A和 B包含相同的數(shù)字個數(shù)。 例題 2：算法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1