算法合集之數(shù)位計數(shù)問題解法研究-在線瀏覽
2024-12-05 18:36本頁面
【正文】 從小到大順序從左到右依次寫下，然后在每一數(shù)位之前依次插入加號和減號 (循環(huán) )，求結果。 ?因為加減符號的改變與數(shù)字個數(shù)相關，因此為了讓規(guī)律更加明顯，我們盡量將1~N劃分為若干段區(qū)間，使得每個區(qū)間內(nèi)的數(shù)的數(shù)字個數(shù)相同。 ?根據(jù)數(shù)字個數(shù)的奇偶性，這里分為兩種情況討論。 ? 例如 120小于 4，因為 120的數(shù)字之和為 3，而 4的數(shù)字之和為 4。 20小于 200，因為在字典序意義下” 20””200” 例題 2： Graduated Lexicographical Ordering（ ZOJ 2599） ?求 1~N中第 K大的數(shù)； K在 1~N中的位置 ?范圍： 1=K=N=1015 例題 2：算法分析 ? 原問題內(nèi)有兩問，事實上兩問之間可以互相轉(zhuǎn)化，因此首先考慮解決較為容易的一問。 ? 我們可以將求 K在 1~N的位置換一種方式提出，即求 [1,N]中有多少個數(shù)比 K小，這個問題可以通過區(qū)間劃分的方法轉(zhuǎn)化為更小的問題并加以解決。 ? 原因在于，對于比較兩數(shù)的首要元素 ——數(shù)字和，在任何連續(xù)區(qū)間內(nèi)，都沒有很好的規(guī)律，可以直接利用。 例題 2：算法分析 ?首先固定數(shù)字和，
教學課件相關推薦
鄂ICP備17016276號-1