什么是字典序2定居_具體的算法
什么是字典序2定居_具體的算法
字典序不同排列的先后關(guān)系是從左到右逐個(gè)比較對(duì)應(yīng)的數(shù)字的先后來(lái)決定的。那么你對(duì)字典序了解多少呢?以下是由學(xué)習(xí)啦小編整理關(guān)于什么是字典序的內(nèi)容，希望大家喜歡!
字典序的概述
數(shù)字也可以作為特別的字符串...這種情況下...如果我們用字典序進(jìn)行比較...就有可能會(huì)出現(xiàn)下面這種情況...
"100"<"1000"..(加引號(hào)的目的是為了區(qū)別數(shù)字..與數(shù)字串..)
事實(shí)上呢.在計(jì)算機(jī)里...我們會(huì)這么看..和之前一樣...我們會(huì)首先比較第一個(gè)字符...
這里"1"='1'..(已經(jīng)可以看到區(qū)別了..在數(shù)中..數(shù)字因?yàn)槲恢玫牟煌瑫?huì)有不同的意義..而這里.這種分別變的不一樣了...)
..一步比較...還沒(méi)有辦法分辨出它們的大小...只好再比較之后的數(shù)...
這種情況回直到最后一次嘗試...第一個(gè)字符串已經(jīng)空掉之前...
如果硬要比較的話...
空格的ascii碼值是32.(Ascii碼還是用兩位十六進(jìn)制表示比較合適)
‘0’的ASCII碼值是48 所以‘100’<'1000'
例子：依次比字母, 如boat < boot <
cap < card < cat < to < too< two < up
字典序如下：
設(shè)P是1～n的一個(gè)全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1)從排列的右端開(kāi)始，找出第一個(gè)比右邊數(shù)字小的數(shù)字的序號(hào)j(j從左端開(kāi)始計(jì)算)，即 j=max{i|pi<pi+1}
2)在pj的右邊的數(shù)字中，找出所有比pj大的數(shù)中最小的數(shù)字pk，即 k=max{i|pi>pj}(右邊的數(shù)從右至左是遞增的，因此k是所有大于pj的數(shù)字中序號(hào)最大者)
3)對(duì)換pj，pk
4)再將pj+1......pk-1pkpk+1......pn倒轉(zhuǎn)得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，這就是排列p的下一個(gè)排列。
字典序的算法
設(shè)置了中介數(shù)的字典序全排列生成算法，與遞歸直接模擬法和循環(huán)直接模擬法的最大不同是，不需要模擬有序全排列的生成過(guò)程，也就不需要逐一地生成各個(gè)全排列，只要知道初始全排列，就能根據(jù)序號(hào)(m-1)，直接得到第m個(gè)全排列，因此速度非?？?。
它的缺點(diǎn)是在生成序號(hào)(m-1)的遞增進(jìn)進(jìn)制數(shù)時(shí)，需要事先創(chuàng)建一個(gè)用來(lái)存儲(chǔ)n的階乘數(shù)n! 的數(shù)組p[]，所以n的值不能太大，否則就會(huì)溢出，根據(jù)我的測(cè)試結(jié)果，當(dāng)1<=n<=20時(shí)不會(huì)溢出，當(dāng)21<=n時(shí)會(huì)溢出。
設(shè)置了中介數(shù)的字典序全排列生成算法需要設(shè)置中介數(shù)，在實(shí)際應(yīng)用中比較繁瑣，不如由前一個(gè)排列直接推得下一個(gè)排列方。
看過(guò)“字典序的算法”的人還看了：
1.人教版小學(xué)三年級(jí)語(yǔ)文上冊(cè)教學(xué)計(jì)劃范文3篇
2.計(jì)算機(jī)公共基礎(chǔ)知識(shí)題庫(kù)