アルゴリズムの問題がわからん [転載禁止]©2ch.net

**１３２人目の素数さん** · 2015/06/23(火) 16:43:06.63

教えてちょ

http://www.pso2-uploader.info/uploda/src/up160546.png

**１３２人目の素数さん** · 2015/06/23(火) 16:49:51.91

こんなところより、VIPやなんJできいた方が良いと思うよ

**１３２人目の素数さん** · 2015/06/24(水) 07:05:45.80

この問題に限って言えば定数2を返す関数で間違ってはいないな。

**１３２人目の素数さん** · 2015/07/01(水) 23:12:39.39

http://anago.2ch.net/test/read.cgi/slotk/1434928540/342-346

**１３２人目の素数さん** · 2015/07/02(木) 21:57:58.99

数学ど素人だけどITの資格を取るのが趣味で基本情報技術者を持ってる
（本当はその二段階上のレベルの資格を3つ持ってる）
自分ならこのスレなら活躍できるかも知れないぞｗ

>>3
あー、これだから素人はｗ

目的文字列配列は、
「B」「C」「A」「NULL」
だよ

文字列配列の2文字目から4文字目は「B」「C」「A」だけど、
文字列配列の5文字目は「B」であって「NULL」ではない
だから、文字列配列の2文字目から5文字目は目的文字列配列と一致しない

「NULL」は文字列の最後を表す記号
したがって、文字列配列に「NULL」は一つしかない
なおかつ、「NULL」は文字列配列の最後にしかない

そのため、
文字列配列の最後から2文字目が「Ａ」か調べ、もし「Ａ」であれば、
文字列配列の最後から3文字目が「C」か調べ、もし「C」であれば、
文字列配列の最後から4文字目が「B」か調べ、もし「B」であれば、
目的文字列配列が発見できた、とするアルゴリズムを作ればよい

5 · 2015/07/02(木) 22:09:27.07

ちょっと訂正

＞文字列配列に「NULL」は一つしかない　→　文字列配列に「NULL」は最大で一つしかない
＞「NULL」は文字列配列の最後にしかない　→もし文字列配列「NULL」があるとしたら「NULL」は文字列配列の最後にしかない

NULLは文字列の最後を表す記号であるが、
文字列配列にNULLを含める事が必須であるとの記述は無い

問題文ではNULLの意味が記述されているだけであって、
文字列配列の最後にNULLを付加する事がルールとして示されているのではない

文字列配列の末尾にNULLを付加する事が必須ではないなら、
>5の探索方法だと、文字列配列の末尾の4文字が例えば「B」「C」「A」「Z」でも、
目的文字列を発見したと判定してしまう
そこで、次の様に訂正するべきだ

文字列配列の最後から1文字目が「NULL」か調べ、もし「NULL」であれば、
文字列配列の最後から2文字目が「Ａ」か調べ、もし「Ａ」であれば、
文字列配列の最後から3文字目が「C」か調べ、もし「C」であれば、
文字列配列の最後から4文字目が「B」か調べ、もし「B」であれば、
目的文字列配列が発見できた、とするアルゴリズムを作ればよい

**１３２人目の素数さん** · 2015/07/02(木) 22:16:43.93

よくわからないんですけど、Nullは文字列の最後に必ずつくわけで、なにかしらの文字列を探したいとなった時に文字列の「配列」を指定すれば最後にNullがあるのは当然なのではないですか？
これは単にBCAを探す問題ではないのですか？
もしNullも条件に入っているのならば、NullなしのBCAを探す問題はどのように書かれるのですか？

5 · 2015/07/02(木) 22:45:41.68

>>7
＞Nullは文字列の最後に必ずつくわけで
いいえ
「NULL」は文字列の最後を表す記号である事が説明されていますが、
文字列の最後に「NULL」を付加する事が必須であるとのルールは示されていません

仮に、文字列配列にも目的文字列配列にも末尾に「NULL」を付加する事が必須であれば、
まさしく>6の回答が正しい事になります

また、上記のNULLの意味を踏まえて、
目的文字列を「B」「C」「A」とすれば（NULLを付加しなければ）、
目的文字列は「B」「C」「A」「*」（ただし「*」は「NULL」を含む任意の文字列）
と等価になると思います（これは余談、かつ高度な考察ですからスルーしてくださいｗ）

さて、
＞NullなしのBCAを探す問題はどのように書かれるのですか？
ですが、
本来、>1の問題の作者はその様な趣旨の問題を作りたかったのだと思います
作者が文字列配列に「NULL」を付加した理由は、探索の終了の条件を明示するためと考えられます
そして、作者が目的文字列配列に「NULL」を付加した理由は、文字列に「NULL」を付加する事が必須であると錯覚したからだと思います
では、
＞NullなしのBCAを探す問題
については次からのレスで回答します

5 · 2015/07/02(木) 23:29:24.70

>7の＞NullなしのBCAを探す問題
について考えます
（文字列配列の末尾には必ず「NULL」が付加されているとします）

まず、文字列配列の添え字（各文字の上に示された[0]から始まる数字）を確認しましょう
文字列配列の、
1文字目の「A」の添え字は[0]です、
10文字目の「B」の添え字は[9]です
文字列配列[X]（[X]は任意の値の添え字）は、
文字列配列の「X+1」文字目を表します
添え字の表記の確認は以上です

アルゴリズムは次のようになります

Xの初期値を0にする
ループ開始点
もし、文字列配列[X+2]が「NULL」なら、探索を終了する
もし、文字列配列[X]が「B」かつ、文字列配列[X+1]が「C」かつ、文字列配列[X+2]が「A」なら、目的文字列を発見したとする
Xの値を1増やす
ループ終了（ループ開始点へ）

以上

このアルゴリズムに従えば、Xの値が2の時に、
文字列配列[X]が「B」かつ、文字列配列[X+1]が「C」かつ、文字列配列[X+2]が「A」
という条件に合致します

「Xの値を0から1ずつ増やしながらループする」、というのがポイントとなります、それが線形探索ですね
それによって、文字列配列の左端から順番に、1文字ずつずらしながら、目的文字列と合致するか調べる事ができるのです
（あと、＞もし、文字列配列[X+2]が「NULL」なら、探索を終了する　について、次のレスで少し細かい説明をします）

5 · 2015/07/02(木) 23:40:55.29

>9の続きで、
＞もし、文字列配列[X+2]が「NULL」なら、探索を終了する
につてい補足します

1の問題で示された文字列配列を例にすれば、
Xの値が8になった時に、文字列配列[X+2」が「NULL」となり、探索が終了します

しかし、この終了の条件では、文字列配列の内容次第では、問題が生じるのです
（ただし、文字列配列に「NULL」が付加されない場合は考えないとします）
それは、文字列配列の長さが3文字未満の場合です

文字列配列の長さが1文字や2文字の場合でも（さすがに0文字以下は無いとして）正しく探索を終了するためには、
もし、文字列配列[X]が「NULL」なら、探索を終了する
もし、文字列配列[X+1]が「NULL」なら、探索を終了する
という、終了の条件を付け加える必要があります

5 · 2015/07/03(金) 00:17:19.35

ついでに、アルゴリズムにおける「配列」について説明しておきます

そもそも、アルゴリズム初心者の方は配列になじみが無いでしょうからね
この配列は、アルゴリズムのもっとも本質的な要素の一つです
もう一つの重要な要素はループです
アルゴリズムは配列とループの組み合わせで、
無限大の（この「無限大」については数学的に厳密な意味を追究しないでください）可能性を持つのです

配列とは、特定の物を収める任意の数の並んだ箱の様な物です
配列を利用するためには、まず配列を定義します
配列の定義とは、配列の名前を決めて、箱に入れる物の種類を1つ決めて、箱の数を決めます
>1の問題の文字列配列では、配列の名前は文字列配列で、
箱に入れる物の種類は文字列で、箱の数は11です（ただし、11個目以降の表記されていない箱もある可能性はあります）

では、例として配列を定義してみましょう

配列の名前・・・数値配列
箱に入れる物・・・整数
箱の数・・・5

上記の定義によって、数値配列[0]、数値配列[1]、・・・、数値配列[4]、と、
整数を収めるための並んだ箱が5個用意されるのです
ここで、数値配列[X]の[X]は添え字と言って、5個の個別の箱を示す番号となります
添え字は通常、0から始まる連番です（箱の数が5個なら添え字は0~4です）

次に、配列の利用の例を示します
上記の数値配列を利用して、5日間に食べたパンの枚数を記録するとします
1日目から順に、3,2,5,3,7枚のパンを食べたとします、これを順に数値配列に収めると、
数値配列[0]=3　数値配列[1]=2　数値配列[2]=5　数値配列[3]=3　数値配列[4]=7
となります
（続く）

5 · 2015/07/03(金) 00:43:15.80

(11の続き)
さて、ここで、配列の話をひとまず置いておいて、アルゴリズムにおけるループについて説明します
先ほど、アルゴリズムは配列とループの組み合わせで無限大の可能性を持つと書いた通り、
配列について説明するなら同時にループについても説明しなければ効果的ではありません

そのためには、まず、アルゴリズムにおける表記が多くの数学者たちの直観に反する事から説明する必要があります
みなさんは次の表記をどうとらえるでしょうか
A=1
数学ど素人の自分は数学的な「=」の意味を厳密に知りません、しかし、アルゴリズムにおける
A=1の意味をここで説明する事はできます
アルゴリズムでA=1ときたら、Aに1を代入する、という事なのです
そもそもAが変数である事から説明しないといけないのですが
変数とは特定の種類の値を収める箱の様な物です（おっと、配列の説明と似ていますね、配列はその箱が並んだ物でした）

変数Aが整数を収める箱だとすると、
A=1とすると、変数Aの値は1になります
次にA=2とすると、変数Aの値は2になります
変数は計算にも利用できます
整数を収める変数Bもあるとして、B=3とします
そして、A+Bを計算すると答えは5になります
変数には計算結果も代入できます、A=B+1とした場合、
変数Aの値は4になります

では、A=0として、A=A+1とするとどうなるでしょうか？
数学者はA=A+1を方程式として考える事でしょうが、アルゴリズムの表記が数学者の直観に反する事は前述の通りです
アルゴリズムでA=A+1ときたら、変数AにA+1の計算結果を代入する、という事なのです
そして、A=0としていますから、A=A+1は、変数Aに0+1の計算結果を代入する、という事なのです
その結果、変数Aの値は1になります
では、さらにA=A+1を繰り返すとどうなるでしょうか、今変数Aの値は1ですが、もう一度A=A+1とすると、A=1+1で、
変数Aには計算結果の2が代入されます（続く）

**１３２人目の素数さん** · 2015/07/03(金) 00:46:18.08

>>8
すみません、>>6よく読んでませんでした
結局屁理屈ってことですね
ありがとうございました
配列とは何かはわかっているつもりです
非負整数に添え字づけられた族のことですよね