[表示 : 全て 最新50 1-99 101- 201- 301- 401- 2chのread.cgiへ]
Update time : 09/09 21:41 / Filesize : 141 KB / Number-of Response : 461
[このスレッドの書き込みを削除する]
[+板 最近立ったスレ&熱いスレ一覧 : +板 最近立ったスレ/記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

面白い問題教えて 第2版



376 名前:132人目の素数さん mailto:sage [02/02/11 20:14]
んじゃいきます

>>289>>294の問題、そろそろトドメ刺します。
自分でも確かめましたけど、間違いあるかもしれないのであったら指摘して下さい。
ちなみに部分列でも同じように命題が成り立つ、ってのは証明無しに使ってます。
後記号使いまくりなので分かりにく過ぎなのは勘弁して

(1)
まずn番目の単語をAnと表す。
次にA1以降の単語についてAnがA0の最初のx文字を含む最大のxをf(An)とする。
この時、A0の文字数をpとすると、f(An)<p
よってあるqに対してf(An)=qとなるnが無限に存在する。
このようなnをn_0,n_1,n_2,…と順に求めておくと
Bm=An_mとなるような単語列Bmでもこの命題は成り立つ。
(言い換えると単語A0の最初のq文字だけ含んでるような
  Anの無限部分列をBnとする、ということ。)

(2)
Bnに対して次のような操作をして新たな単語列Cnを作る。
Bnの中にA0の最初のq文字が含まれているが、その文字ごとでBnを分ける
例.(五文字のアルファベットの単語の場合)
A0=acccbaadecedbでBn=bcaecddcaccdbbeadabcddeaceccdの時、(この時q=12)
Bnをbca ec ddc ac cdb bea da bcd de ac e ccdって感じで分ける。
そして分けられたそれぞれの組に対してその組の中の一番後ろの文字を
使えるアルファベットの中で一番最後ので表して(以後これをeで表す)
それ以外の文字を残りのアルファベットで表す。
例.
Bn=bca ec ddc ac cdb bea da bcd de ac e ccdなら
Cn=abe de cce ae bce ade ce bce de ae e cceと変換する。






[ 続きを読む ] / [ 携帯版 ]

全部読む 前100 次100 最新50 [ このスレをブックマーク! 携帯に送る ] 2chのread.cgiへ
[+板 最近立ったスレ&熱いスレ一覧 : +板 最近立ったスレ/記者別一覧]( ´∀`)<141KB

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef