Geekly Articles each Day

サルず無限の仕事

タむプラむタヌに猿を眮いお、垞に誀っおキヌをたたくず、遅かれ早かれ、戊争ず平和、ピタゎラスの䜜品のコレクション、そしお今読んでいる蚘事を印刷するこずは誰もが知っおいたす。



驚くべき事実ですが、さらに興味深いのは、特定のテキストを入力するのにどれくらい時間がかかるかを理解しようずするこずです。 䜙分なパラメヌタヌ猿によるタむピングの速床を駆動させないために、質問に察する答えを探したす。キヌストロヌクは平均で䜕回かかりたすか。 文字列「abc」の方が「aaa」よりはるかに簡単に入力できるこずは明らかですか この投皿はこの問題を解決するこずに専念しおいたす。 途䞭で、関数のプレフィックスずそのプロパティに぀いお説明したす。


サルが特定のテキストの入力に費やす時間は、ランダム倉数であるこずが明らかです。 したがっお、圌女の数孊的な期埅に぀いお尋ねるこずは論理的です。


問題の正匏な声明


倧文字のラテン文字 "a"-"z"で構成される文字列sが䞎えられたす。 マットを芋぀ける必芁がありたす。 すべおの文字が平等に入力される堎合確率1/26 、文字列s党䜓が入力される前に、ランダムなキヌストロヌクの回数を埅機したす。


決定コヌド

これがなぜ機胜し、このPi関数が䜕であるかを理解するには、蚘事党䜓を読む必芁がありたす:(。


string s; //,    int n = s.length(); vector<int> p = Pi(s); vector<long double> pow(n+1); pow[0] = 1; int i; for (i = 1; i <= n; i++) { pow[i] = pow[i-1]*26; } long double ans = 0; for (i = n; i>0; i = p[i-1]) { ans += pow[i]; } cout << ans;

プレフィックス機胜


この機胜は、問題の解決に圹立ちたす。 関数プレフィックスは、文字列内の郚分文字列を芋぀ける有名なアルゎリズム KMPアルゎリズムのために、D。KnutずM. PrattおよびD. Morrisに類䌌によっお導入されたした。 文字列sのプレフィックス関数は、最長のネむティブ文字列プレフィックスの長さを返したす。これは、そのサフィックスでもありたす。


プレフィックスずサフィックス

末尟からいく぀かの文字を砎棄する堎合、プレフィックスは行の先頭にすぎたせん。 したがっお、行「aba」には4぀のプレフィックスがありたす。「」空行、「a」、「ab」、「aba」です。 接尟蟞は同じですが、文字は先頭から削陀されたす。 ただし、䞀郚の接尟蟞ず接頭蟞は䞀臎する堎合がありたす。 文字列「aba」には、「」、「a」、「aba」の3぀の接頭蟞接尟蟞がありたす4番目の接尟蟞「ba」は接頭蟞「ab」ず䞀臎したせん。 サフィックスたたはプレフィックスは、行党䜓より短い堎合に適切ず呌ばれたす 。


正匏に蚀えば \ pis= max \ {k \、| \、0 \ le klt; | s |、\、pref_ks= suf_ks\}


ここで、 pref k sは文字列sの長さkのプレフィックスであり、 suf k sは文字列sの長さkのサフィックスです。


ILCアルゎリズムず他のアプリケヌションの䞡方で、特定の文字列のすべおのプレフィックスに察しおプレフィックス機胜をすぐに怜蚎する方がはるかに䟿利です。 はい、恐ろしいですね-プレフィックスごずに、サフィックスのサフィックスず䞀臎する最倧のカスタムプレフィックスを芋぀ける必芁がありたす。 しかし実際には、すべおが簡単です。


\ pi_sk= \ pipref_ks、\、1 \ le k \ le | s |


このような拡匵プレフィックス関数は、単玔な蚈算よりも蚈算が簡単なため、䞻に圹立ちたす。 \ pis 。 以䞋の倀 \ pi_sk s = "ababac"の堎合。


  k1 2 3 4 5 6
    sアババク
 Pi0 0 1 2 3 0

蚈算関数のプレフィックス


蚈算コヌド
 vector<int> Pi(string s) { int n = s.length(); vector<int> p(n); p[0] = 0; for (int i = 1; i < n; i++) { int j = p[i-1]; while (j > 0 && s[i] != s[j]) { j = p[j]; } if (s[i] == s[j]) j++; p[i] = j; } return p; }

関数プレフィックスの簡単なON蚈算は、2぀の単玔な芳枬に基づいおいたす。


1䜍眮kの接頭蟞接尟蟞を取埗するには、䜍眮k-1のある皮の接頭蟞接尟蟞を取り、䜍眮kの蚘号の最埌に远加する必芁がありたす。


2長さnの文字列sのすべおの接尟蟞接頭蟞は、次のように取埗できたす。 \ pi_sn、\、\ pi_s\ pi_sn、\、\ pi_s\ pi_s\ pi_sn 次の倀が0になるたで続きたす。このプロパティは、「abacaba」行で確認できたす。 ここに \ pi_s7= 3、\、\ pi_s3= 1、\、\ pi_s1= 0 、これはすべおのプレフィックスずサフィックス「aba」、「a」、「」に察応したす。 これは、プレフィックスの最倧サフィックスの長さが \ pi_sn 。 次のプレフィックスサフィックスは短くなりたす。 ただし、最初のプレフィックスサフィックスは行sの先頭ず末尟の䞡方にあるため、次のプレフィックスサフィックスは最初のプレフィックスサフィックスの䞭で最も長いプレフィックスサフィックスになりたす。


したがっお、䜍眮iの関数接頭蟞を構築するには、前の䜍眮の関数接頭蟞の倀から、接尟蟞が新しい文字で続き、接頭蟞になるたで繰り返すだけで十分ですこのため、新しい文字を1぀だけチェックする必芁がありたす。 このようなアルゎリズムは線圢時間で実行されたす。これは、関数のプレフィックスの倀が毎回最倧1増加するため、 n回以䞊枛少するこずはできないため、ネストされたルヌプが合蚈n回以䞋で実行されるこずを意味したす。


KMPステヌトマシン


問題を解決するために必芁な次の数孊的オブゞェクトは、特定の文字列sで終わる行を受け入れる有限状態マシンです。 このオヌトマトンは、あたり知られおいない別のKnuth-Moriss-Prattアルゎリズムの修正で䜿甚されたす。 このバヌゞョンのアルゎリズムでは、特定の行テンプレヌトで終わるすべおの行を受け入れる状態マシンが構築されたす。 次に、テキスト文字列がマシンに送信されたす。 マシンが枡されたテキストを受け入れるたびに、テンプレヌトの次の出珟が怜出されたす。 タむプラむタヌの背埌にある猿の問題を解決するのに圹立぀のはこのマシンです。


有限状態マシンずは

ステヌトマシンは、ある皮の内郚状態を持぀ボックスずしお想像するのが最も簡単な数孊的オブゞェクトです。 最初は、ボックスは初期状態です。 ボックスには、䞀床に1文字ず぀行を入力できたす。 各シンボルの埌、珟圚の状態ず入力されたシンボルに応じお、ボックスの状態が倉わりたす。 たた、䞀郚の状態は良奜です数孊甚語は最終状態です 。 圌らは、この文字列を文字ごずに䞎えた埌、マシンが良奜な状態にある堎合、オヌトマトンは文字列を受け入れるず蚀いたす。


宇宙船を決定するには、初期状態、良奜な状態、および遷移関数を決定する必芁がありたす-状態ずシンボルごずに、オヌトマトンが入る新しい状態を指定する必芁がありたす。 オヌトマトンを完党な方向のグラフずしお描画するず䟿利です。この堎合、頂点は状態であり、各゚ッゞに1぀のシンボルのみが曞き蟌たれたす。 各頂点には、各シンボルに正確に1぀の゚ッゞが必芁です。 次に、行を凊理するには、この行の文字を゚ッゞに沿っお移動するだけです。 パスが最終状態で終了した堎合、マシンはそのような文字列を取埗したす。


このオヌトマトンを䜜成するには、すでに知っおいるプレフィックス関数を䜿甚したす。
マシンには0からnたでの番号が付けられたn + 1の状態がありたす。 状態kは、長さkのパタヌンのプレフィックスを持぀最埌に入力されたk文字の䞀臎に察応したす文字列「abac」を怜玢する堎合、最埌の珟圚のテキストに関心がありたす「abac」、「aba」、「ab」、「a」たたはwhatこれは、1文字を远加した埌に同じ結果を埗るのに十分です。 状態0は初期状態で、状態nは最終状態です。 混乱が生じる堎合がありたす。たずえば、「zzzabab」ずいう行に自動的にフィヌドされる「ababccc」ずいう甚語では、状態2ず4の䞡方を遞択できたす。ただし、入力したテキストに関する必芁な情報を倱わないように、垞に最高の状態を遞択したす。


KMPステヌトマシンの䟋

文字列「ababac」のマシンは次のずおりです。 たずえば、アルファベットは「a」〜「c」の文字のみで構成されたす。 明確にするために組み合わされた平行リブ。 実際、各゚ッゞに察応する文字は1぀だけです。 初期状態は0 、最終状態は6です。


状態0から状態6ぞのパスは、それがどれほど困難であっおも、文字列「ababac」で終わるこずを確認するのは簡単です。 逆に、このようなパスは必ず状態6で終了したす。


ステヌトマシン構築コヌド
 string s; // . int n = s.length(); vector< vector<int> > nxt(n+1, vector<int>(256)); //   nxt[][] ==   vector<int> p = Pi(s); //  . .   nxt[0][s[0]] = 1; //    0   0. for (int i = 1; i <= n; i++) { for (int c = 0; c < 256; c++) nxt[i][c] = nxt[p[i-1]][c]; //p[]   ,   -1 if (i < n) nxt[i][s[i]] = i+1; }

遷移の構築方法に泚意しおください。 状態iからの遷移を蚈算するには、2぀のオプションを怜蚎したす。 新しい文字がs [i]の堎合、遷移は状態i + 1になりたす。 ここではすべおが明らかです。i文字に䞀臎があった堎合、文字列sから次の文字を远加するず、䞀臎の長さが1増加したす。 シンボルが䞀臎しない堎合、状態から遷移を単にコピヌしたす \ pi_si 。 なんで この堎合の遷移は、番号≀iの状態に正確になりたす。 そのため、移行埌、入力したテキストに関する情報の䞀郚を忘れたす。 先に進む前にこれを行うこずができたす。 消去できる最䜎限は、実際には状態がiではないふりをするこずですが、 \ pi_si 。 䞊蚘の䟋のように、テキストが「abab」たたは「ab」で終わるず考えるこずができたす。 「abab」からの移行がない堎合は、「ab」からの移行を䜿甚できたす。


解決策


これでタスクを解決する準備ができたした。
stringのKMPオヌトマトンを構築したす。 すべおの文字はランダムに猿によっお入力されるため、シンボル自䜓は重芁ではなく、遷移グラフの゚ッゞのみが重芁です。 問題は次のように再定匏化できたす。マットを芋぀けたす。 状態0から状態nに到達するたでのランダムりォヌクで遷移の数を埅機したす。


この定匏化で倉数を導入するこずは論理的です E k 、0≀k≀n-状態nに達するたでの遷移の数の期埅。 E 0が元の問題の答えになりたす。 Zを有効な文字アルファベットのセットにしたす。 連立方皋匏を䜜成できたす。


E_n = 0


E_k = 1 + \ frac {1} {| Z |} \ sum_ {c \ in Z} {E_ {nxt [k] [c]}}、k = 0..n-1


方皋匏1は、状態nに到達するずランダムりォヌクが停止するこずを意味したす。
他の状態では、䜕らかの遷移が行われるため、匏2に甚語1が存圚したす。 2番目の項は、すべおの可胜なオプションの合蚈にこれらのオプションの確率を掛けたものです。 すべおの確率は同じです。したがっお、合蚈のサむンずしお取り出されたす。


On ^ 3には既に問題の解決策がありたす。構築された線圢方皋匏系は、ガりス法によっお解くこずができたす。 しかし、このシステムを少し芋お、関数の接頭蟞があるこずを芚えおいれば、぀たり、解決策ははるかに簡単で高速です。


有限状態マシンの構築を思い出しおください。 簡単にするために、 \ pi_s 私はちょうど䜿甚したす \ pi  状態kからの遷移は、状態からの遷移ずほが䞀臎したす \ pik 。 遷移の違いは、シンボルs [k-1]のみです。 したがっお、状態kおよび状態の方皋匏2の右蟺 \ pik 1぀の甚語のみが異なりたす。 の方皋匏で \ pik 䟡倀がある E_ {nxt [\ pik] [s [k-1]]} の代わりに E_ {nxt [k] [s [k-1]]} kの方皋匏で。 さらに、 nxt [k] [s [k-1]] = k + 1です。 この事実を䜿甚しお、方皋匏2を曞き換えるこずができたす。


E_k = E _ {\ pik} + \ frac {1} {| Z |}E_ {k + 1} -E_ {nxt [\ pik] [s [k-1]]}


次に、もう1぀芳察する必芁がありたす。 わかった


nxt [\ pik[s [k-1]] = \ pik + 1


぀たり 状態の関数接頭蟞を芋぀けるには、前の状態から関数接頭蟞を取埗し、そこから次の状態に぀ながる蚘号をたどる必芁がありたす。
確かに、状態を考慮するず \ pik 、それは文字s [k-1]で終わる行に察応したす。 そのため、このシンボルには遷移がありたす。 そのような遷移が存圚するが、番号<kを持぀最倧の状態を考えたす。 シンボルs [k-1]の埌に䜕らかのサフィックスが付いた堎合 pref_ks その埌、遷移前に接尟蟞でした pref_ {k-1}s 。 これは右端のそのような状態だったため、最倧プレフィックスサフィックスに察応したす。 pref_ {k-1}s 、぀たり数字があるこずを意味したす \ pik-1 。 だから、この驚くべき有甚な事実を埗た。


次に、3は次のように倉換されたす。


E_k = E _ {\ pik} + \ frac {1} {| Z |}E_ {k + 1} -E _ {\ pik + 1}


たたは別の方法で


| Z | E_k-E _ {\ pik}=E_ {k + 1} -E _ {\ pik + 1}


等号の䞡偎には負の数がありたす kが倚いほどE kが小さくなるこずが論理的です。 䞡偎に-1を掛けたす。


| Z | E _ {\ pik}-E_k= E _ {\ pik + 1}-E_ {k + 1}


ただし、4はk> 0に察しおのみ有効です。 k = 0の堎合、匏2を明瀺的に蚘述できたす。 遷移は状態1に぀ながり、残りはすべお状態0に戻りたす 。


E_0 = 1 + \ frac {1} {| Z |} E_1 + \ frac {| Z | -1} {| Z |} E_0


ここで、巊偎のすべおの倉数を収集し、方皋匏に| Z |を掛けたす。 そしお亀換 0 = \ pi1 1文字には空でないプレフィックスがないため、1文字のプレフィックス関数は垞に0です


E _ {\ pi1}-E_1 = | Z |


方皋匏1、4、および5を繰り返すこずができたす。これは、これらが方皋匏を解析するシステムを構成するためです。


E _ {\ pi1}-E_1 = | Z | \\ | Z | E _ {\ pik}-E_k= E _ {\ pik + 1}-E_ {k + 1}、\、k = 1..n-1 \\ E_n = 0


2番目の巊偎の最初の方皋匏をk = 1で眮き換え 、次にk = 2などで眮き換えたす 。 私達は埗る


E _ {\ pik}-E_k = | Z | ^ k、\、k = 1..n


これで、解決策はほが準備できたした。今、 k = nに぀いお6を怜蚎し、 E_n = 0 私達は埗る


E _ {\ pin} = | Z | ^ n


6のこの倀を k = \ pin -私達は埗る


E _ {\ pi\ pin} = | Z | ^ n + | Z | ^ {\ pin}


同様に、以䞋を取埗したす。


E _ {\ pi\ pi\ pin} = | Z | ^ n + | Z | ^ {\ pin} + | Z | ^ {\ pi\ pin}


したがっお、次の匏を取埗するたで続行できたす。 E_0 、぀いでに、問題に察する答えです。 瀺す \ pi ^ k 行にk回適甚される関数 \ pi その埌


E_0 = \ sum_ {k\ pi ^ kngt; 0} | Z | ^ k


したがっお、Onの問題の解決策を埗たした。文字列sの関数のプレフィックスを䜜成し、 0に達するたでnから繰り返し、同時に床| Z |を加算したす。 プレフィックスの珟圚の長さず等しい。 これは、蚘事の冒頭で瀺したたさにその解決策です。


*を芋るず、文字列「aaa」が「abc」よりも入力が難しい理由が明らかになりたす。「aaa」では3番目の反埩のみ \ pi れロであり、2行目には通垞、接尟蟞に等しい空でない接頭蟞はありたせん。 \ pi すぐにれロになりたす。


備考


プレフィックス関数ずILCマシンは、文字列を操䜜するための非垞に䟿利なツヌルです。 芪愛なる読者が興味を持っおいるなら、私は他の問題の解決策を芋぀けるこずができたす。 PMのタむプミスに぀いお教えおください、ありがずう。


曎新


たず、 Habréの数匏を含む蚘事を䜜成する玠晎らしいサヌビス https://habrahabr.ru/post/264709/ に感謝したす 。 圌がいなかったら、この蚘事はなかったでしょう。 すぐにそれに぀いお曞くのを忘れたのは残念です。


第二に、倚くのコメンテヌタヌは圌らの盎感に混乱しおいたす。 定理では、これはしばしば起こりたす。 はい、最初に同じ長さのテキストを入力する確率は同じです。 はい、同じ長さのテキストの出珟頻床は、無限のランダムテキストで同じです。 これはすべお真実ですが、これらの事実から、 最初の行が出珟する前の文字数の予想が同じになるずいうこずにはなりたせん。 逆もたた同様です。無限テキストの行「hh」が行「hk」よりも埌に衚瀺されるずいう事実から、カゞノは黒の埌に赀に眮かれるべきではありたせん。


2぀の行「hh」ず「hk」が衚瀺されるたで、指の期埅を数えたしょう。 期埅倀は、すべおのiの合蚈です。぀たり、 i文字の文字列を初めお入力する確率はiです。 倪字のフレヌズは、最初に入力した最埌の文字が怜玢に䞀臎するこずを意味しこの確率は䞡方の行で同じです、2番目に、怜玢文字列が最初のi-2文字間で発生したせん 。 この2番目の芁因は、回線ごずに異なりたす。 行が芋぀からない確率は、単にこの行が含たれおいないすべおのテキストの数を、この長さのすべおのテキストの数で割ったものです。


ここで重芁なのは、文字列「hk」を含たない長さkの行、合蚈k + 1 「k ... kh」、「k ... kch」、「k ... kchch」、「k ... kchchch」、...、「kch ... h」および「 h ... h。」 これは、シンボル「h」の埌には「h」しか存圚できないためです。


文字列「hh」を含たない長さkのドレむンは、はるかに倧きくなりたす。぀たり、F k + 1-数字k + 1の䞋のフィボナッチ数これらは、数字1、1、2、3、5、8、13、...です。前の2぀の合蚈。 たずえば、 k = 2の堎合、3行は「kk」、「kch」、「hk」になりたす。 これらの数倀は非垞に急速に成長するため、文字列「kk」の期埅倀のすべおの甚語は、確率が高くなるため、より倧きくなりたす。


数回のクリックで初めおテキストを印刷する確率は、テキストの最初ず途䞭で䞀床もテキストを印刷しない確率に䟝存するこずに泚意しおください。 この確率は、特定の行を含たない行の数に正比䟋したすが、テンプレヌトによっお異なりたす。


繰り返しになりたすが、これは私が思い぀いたものではなく、非垞に盎感的ではありたせんが、これはよく知られた事実です。 たずえば、この蚘事を芋おくださいアリスずボブに関するタスクを探しおください -4段萜 https : //habrahabr.ru/post/279337/



Source: https://habr.com/ru/post/J200834/

More articles:


All Articles