X
トップページ⇒数学
64コメント26KB
アルゴリズムの問題がわからん [転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
0002１３２人目の素数さん
垢版 |
2015/06/23(火) 16:49:51.91ID:PAT/c+dF
こんなところより、VIPやなんJできいた方が良いと思うよ
0005１３２人目の素数さん
垢版 |
2015/07/02(木) 21:57:58.99ID:yxb4cVte
数学ど素人だけど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」であれば、
目的文字列配列が発見できた、とするアルゴリズムを作ればよい
00065
垢版 |
2015/07/02(木) 22:09:27.07ID:yxb4cVte
ちょっと訂正

＞文字列配列に「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」であれば、
目的文字列配列が発見できた、とするアルゴリズムを作ればよい
0007１３２人目の素数さん
垢版 |
2015/07/02(木) 22:16:43.93ID:iYKWRpCP
よくわからないんですけど、Nullは文字列の最後に必ずつくわけで、なにかしらの文字列を探したいとなった時に文字列の「配列」を指定すれば最後にNullがあるのは当然なのではないですか？
これは単にBCAを探す問題ではないのですか？
もしNullも条件に入っているのならば、NullなしのBCAを探す問題はどのように書かれるのですか？
00085
垢版 |
2015/07/02(木) 22:45:41.68ID:yxb4cVte
>>7
＞Nullは文字列の最後に必ずつくわけで
いいえ
「NULL」は文字列の最後を表す記号である事が説明されていますが、
文字列の最後に「NULL」を付加する事が必須であるとのルールは示されていません

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

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

さて、
＞NullなしのBCAを探す問題はどのように書かれるのですか？
ですが、
本来、>1の問題の作者はその様な趣旨の問題を作りたかったのだと思います
作者が文字列配列に「NULL」を付加した理由は、探索の終了の条件を明示するためと考えられます
そして、作者が目的文字列配列に「NULL」を付加した理由は、文字列に「NULL」を付加する事が必須であると錯覚したからだと思います
では、
＞NullなしのBCAを探す問題
については次からのレスで回答します
00095
垢版 |
2015/07/02(木) 23:29:24.70ID:yxb4cVte
>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」なら、探索を終了する　について、次のレスで少し細かい説明をします）
00105
垢版 |
2015/07/02(木) 23:40:55.29ID:yxb4cVte
>9の続きで、
＞もし、文字列配列[X+2]が「NULL」なら、探索を終了する
につてい補足します

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

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

文字列配列の長さが1文字や2文字の場合でも（さすがに0文字以下は無いとして）正しく探索を終了するためには、
もし、文字列配列[X]が「NULL」なら、探索を終了する
もし、文字列配列[X+1]が「NULL」なら、探索を終了する
という、終了の条件を付け加える必要があります
00115
垢版 |
2015/07/03(金) 00:17:19.35ID:anc5Zim7
ついでに、アルゴリズムにおける「配列」について説明しておきます

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

配列とは、特定の物を収める任意の数の並んだ箱の様な物です
配列を利用するためには、まず配列を定義します
配列の定義とは、配列の名前を決めて、箱に入れる物の種類を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
となります
（続く）
00125
垢版 |
2015/07/03(金) 00:43:15.80ID:anc5Zim7
(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が代入されます（続く）
0013１３２人目の素数さん
垢版 |
2015/07/03(金) 00:46:18.08ID:HoTH5wsh
>>8
すみません、>>6よく読んでませんでした
結局屁理屈ってことですね
ありがとうございました
配列とは何かはわかっているつもりです
非負整数に添え字づけられた族のことですよね
00145
垢版 |
2015/07/03(金) 01:16:36.05ID:anc5Zim7
(12の続き)
変数Aに2が代入されたところで、さらにA=A+1とすると、変数Aには2+1の計算結果が代入されて、変数Aには3が代入されます
つまり、A=A+1とするたびに、Aの値が1ずつ増加していくというのが、アルゴリズムの性質なのです

では、少し話を戻します、A=A+1の代入式の説明は、アルゴリズムにおけるループの説明のために必要だったのです
そして、ループの説明は配列とループの組み合わせの説明のために必要だったのです

>11で用意した数値配列、
数値配列[0]=3　数値配列[1]=2　数値配列[2]=5　数値配列[3]=3　数値配列[4]=7
を例にした説明に戻りたいと思います
この場合の　数値配列[0]=3　も、アルゴリズムとしての意味は、数値配列[0]に3を代入する、という事です
配列とは変数（先ほどまで箱と呼んできました）が並んだ物であり、変数の説明は>12の通りです
数値配列[0]や数値配列[1]もそれぞれが1つの変数で、変数として値が代入されるのです

再び変数Aを登場させます
変数Aには0~4の値を代入するとします
数値配列[A]とした場合、Aの値によって、数値配列[0~4]を表す事が出来るのです
変数Aの値が2なら、数値配列[A]は数値配列[2]を表し、数値配列[2」の値は5です
これを利用すれば、X日目に食べたパンの枚数を知りたければ、1日目に食べたパンの枚数は数値配列[0]に代入されているので、
A=X-1として、数値配列[A]の値を参照すれば良いのです、
例えば、4日目に食べたパンの枚数なら、A=4-1でA=3、数値配列[A]の値は3で、3枚だった事が分かります
これは変数Aと数値配列を組み合わせて任意の日にちに食べたパンの枚数を調べる方法です
数値配列[1]の[1]を添え字というと説明しましたが、添え字の値は変数（この例では変数A）でも指定できるのです

次に、本題であるループと配列の組み合わせを示します
00155
垢版 |
2015/07/03(金) 02:00:22.92ID:anc5Zim7
(14の続き)
>11からの配列とループの説明を総合すると、次の様なアルゴリズムも理解できると思います
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
数値配列[0~4]に次の値を代入する
数値配列[0]=3　数値配列[1]=2　数値配列[2]=5　数値配列[3]=3　数値配列[4]=7
変数A=0
変数B=0
変数C=0

ループの開始点
B=B+数値配列[A]
A=A+1
ループの開始点へ、ただし、A=5ならループを終了する

C=B/5
Bの値を表示する
Cの値を表示する
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
BとCの値としてそれぞれ幾らが表示されるでしょうか？
このアルゴリズムの肝は、＞B=B+数値配列[A]　と、＞A=A+1　の部分です、これこそ、「配列とループの組み合わせ」なのです
B=B+数値配列[A]　の処理では、Bの初期値を0として、Bに数値配列[A]を加算した値をBに代入しています
A=A+1　の処理によって、ループを繰り返すたびにAの値は0から1ずつ増加しています
その結果、1回目のループではBに数値配列[0]が加算され、2回目のループではBに数値配列[1]が加算されます
結論を言いますと、上記のアルゴリズムを実行すると、表示されるBの値は20になり、Cの値は4になるのですが
このアルゴリズムは、5日間に食べたパンの枚数の合計値と、1日に食べたパンの枚数の平均値を求めるものなのです
このアルゴリズムに少し手を加えれば、1日に食べたパンの枚数の最大値や最小値などを求める事もできます
その汎用性こそ配列とループの組み合わせが無限の可能性を持つと言える根拠です

>>13いえいえ、問題を作った人が悪いのです
配列は重要なので、解説しようと思いましたが、難しかったですｗ
一度レスは休みますが、また良い説明が思いついたら書きにきます
0017１３２人目の素数さん
垢版 |
2015/07/03(金) 16:58:40.95ID:f+HQExFc
5さん根本的にミスしてるぞ。

何故、目的文字列配列にNULLが挿入されているのか考えてみろ。
普通は、目的文字列を探索するのに「B」「C」「「A」とかではなく、
目的文字列の頭から見つけていって、NULLがでてくるまでを
合致条件とみなすというのを繰り返すアルゴリズムを作成する。
0019１３２人目の素数さん
垢版 |
2015/07/03(金) 19:48:24.29ID:HoTH5wsh
だから屁理屈なのです
BCAではなく、BCANullを探していると主張しているのです
0020１３２人目の素数さん
垢版 |
2015/07/03(金) 20:00:06.43ID:f+HQExFc
屁理屈でもいいけど、
「下記の文字列データ配列の中から」と書いてあって、図にはしっかりと
NULLが記載されている。
とするならば、５の主張する「文字列配列の最後にNULLを付加する事がルールとして
示されているのではない 」が明らかに間違い。
0021１３２人目の素数さん
垢版 |
2015/07/03(金) 20:07:28.76ID:HZrF1ZVf
nullを深読みしても意味が無い
0022１３２人目の素数さん
垢版 |
2015/07/03(金) 20:08:35.73ID:HoTH5wsh
間違いとはいえませんが、常識的に考えておかしいから「屁理屈」なのです
図に書いてあったとしても、そのNullが、強制されたものか、任意に付け加えられたものであるかは判断することはできません
0024１３２人目の素数さん
垢版 |
2015/07/03(金) 20:13:43.20ID:HoTH5wsh
なぜ判断できるのですか？
0027１３２人目の素数さん
垢版 |
2015/07/03(金) 20:22:37.49ID:HoTH5wsh
その自明なことを問われているとは考えないのですか？
0028１３２人目の素数さん
垢版 |
2015/07/03(金) 20:26:00.06ID:f+HQExFc
意味が分からないのだが？

では、目的文字列配列を何故「B」「C」「A」「*」（ただし「*」は「NULL」を含む任意の文字列）
と表現できるのか？
「*」「*」「*」「*」（ただし「*」は「NULL」を含む任意の文字列） と表現するのが筋では
0029１３２人目の素数さん
垢版 |
2015/07/03(金) 20:29:17.77ID:HoTH5wsh
なんか最初の私と同じ勘違いしてるんですかね？
>>5の言ってるのは、7文字目〜10文字目がBCANullであるのをしらべるだけでよいということです
Nullをワイルドカード扱いにはしていませんよ
0031１３２人目の素数さん
垢版 |
2015/07/03(金) 20:34:31.11ID:HoTH5wsh
>>8
＞仮に、文字列配列にも目的文字列配列にも末尾に「NULL」を付加する事が必須であれば、
＞まさしく>6の回答が正しい事になります
＞また、上記のNULLの意味を踏まえて、

これは私達の「勘違い」に付き合っているだけです
0032１３２人目の素数さん
垢版 |
2015/07/03(金) 20:35:23.33ID:f+HQExFc
7文字目〜10文字目がBCANullであるのをしらべるだけでよいということです

str[4]=NULL　という場合は考えられないのか？
0034１３２人目の素数さん
垢版 |
2015/07/03(金) 20:47:00.89ID:HoTH5wsh
>>32
はい、なぜならば、あなたの言う通り、図には、10文字目にNullがあり、5文字目はNullではないからです
0036１３２人目の素数さん
垢版 |
2015/07/03(金) 20:50:22.51ID:HoTH5wsh
どういう意味ですか？
0037１３２人目の素数さん
垢版 |
2015/07/04(土) 05:50:49.34ID:t+w4ffB5
☆ 総務省の『憲法改正国民投票法』のURLですわ。☆
http://www.soumu.go.jp/senkyo/kokumin_touhyou/
☆ 日本国民の皆様方、2016年7月の『第24回 参議院選挙』で、日本人の悲願である
改憲の成就が決まります。皆様方、必ず投票に自ら足を運んでください。お願いします。☆
0038１３２人目の素数さん
垢版 |
2015/07/08(水) 07:07:11.78ID:W6qMGOWm
面白そうなスレ見つけたと思ったら変な奴がドヤ顔で屁理屈並べてるだけでワロエナイ
0040１３２人目の素数さん
垢版 |
2015/07/08(水) 15:34:23.89ID:acNgIw6V
仕様に解釈に迷う所があったら確認するのがプロの仕事で
俺理論で突っ走るのはド素人だよな
0042１３２人目の素数さん
垢版 |
2016/12/18(日) 17:08:00.80ID:9aVtBTUZ
良スレ
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況