いつもお世話になっています。

現在他人のプログラムを読解する力をつけようと
訓練しています。

以下の文はとあるアルゴリズム本の2分探索の個所を
抜粋したものです。

int bs(*array, size, mokuteki)
{
  ue=size-1, sita=0;

  while(1){
    naka=(sita+ue) / 2;
    if(array[naka] == mokuteki)
      return ARU;
    else if(sita > ue) //・・・・・・★
      return NAI;
    else {
      if(array[naka] < mokuteki)
        sita = naka+1;
      else
        ue = naka-1;
    }
  }
}


ここで★部分の終了条件なのですが、なぜ
  sita >= ue
でいけないのか自分では理解できません。

要はsitaとueが同じ値になり、目的値が見つからなかった
のに再度ループする必要があるのか?、ということです。

特に明確な答えはいりませんがぜひ
ご意見を聞かせてください。

ちなみに作者は
「ue==sitaの状態ならば、幅1の範囲がありますから
 ループをもう一回実行する必要があります。」
と書いています。私には理解できません。


ちなみにこの本は「Javaで学ぶアルゴリズムとデータ構造」
という本です。だいたい一通り読みましたが読んでて
楽しいしわかりやすいし良書だと思います。高価ですが・・・。

このQ&Aに関連する最新のQ&A

A 回答 (5件)

再度ループさせる必要な無いしょう。


size が 0 であるリストを探索することもありますから、どちらにしても、先にarray[naka]を判定をするのは良くないです。

少し飛躍しますが、見つからなかった時にリストに追加しなければならない場合がありますよね?
soakunさんの例だと、ループを抜けた後に、l がそのまま挿入インデックスになるので都合がいいです。

個人的な趣味だと、break しているところは、return が好きなんですけど。
    • good
    • 0
この回答へのお礼

待ちに待った「自身あり」の肯定意見をありがとうございます。

さらにアルゴリズムの間違いまで指摘してくれてとても助かりました。

>size が 0 であるリストを探索することもありますから、

ごもっともです。もしそんなことしてたら
割り当てられてない記憶領域へアクセスさせて
クラッシュしてしまう所でした。

すばらしすぎます。どうやったらそこまで
見抜く力が付くのでしょうか?

お礼日時:2001/10/28 07:35

あう、そのとおりです(たはは~(汗


ご指摘どおり、不等号が逆転してますです;
    • good
    • 0
この回答へのお礼

自身満々で書いた場所の誤りは非常に見つけづらいと思います。
そんなsoakunさんのこれからの活躍を祈ってにポイントを
差し上げたいと思います。
えっ、えらそうですって。ごめんなさいです。

私のこんなひねくれた質問を読んで考えてくださった
方々全員に感謝いたします。

お礼日時:2001/10/28 07:34

>ところでsoakunさんのプログラムに誤りらしきものが・・(^^;



あぅ、どこが間違いなのでしょう?(^^;
# もしかしたらここを見る人のためにも修正したいので補足よろしゅー

この回答への補足

はい。入力ミスっぽいのとうっかりミスっぽいのがありました。

(1)while(l > h)
   これの符号は逆ですよね。

(2)while(・・){
    if(array[t] == mokuteki)
      break;
   }
   return (l > h) ? t : (-1);

   目的値が見つかっても負を返しちゃいますよね。   

間違ってたらごめんなさいです。(~~)/~

補足日時:2001/10/27 19:49
    • good
    • 0

二分木探索について手元にあるアルゴリズム書から


Cに書きおこしたものを書いてみます。
# この段階で上のプログラムと若干異なっているのですが(^^;

int
bs(array, size, mokuteki)
int *array;
int size;
int mokuteki;
{
int l = 0;
int h = size - 1;
int t;

while(l > h) {
t = (l + h) / 2;
if(array[t] == mokuteki)
break;
else if(array[t] < mokuteki)
l = t + 1;
else /* if(array[t] > mokuteki) */
h = t - 1;
}
return (l > h) ? t : (-1);
}
ここで、配列の値を、

int array[] = { 2, 4, 6, 9, 10, 15, 17, 18, 20 };

とし、
int mokuteki = 29;

でプログラムを実行させてみてください。
上記の関数は目的とする配列の添字が見つからなければ、
負の数を返します。
/* おまけ(Javaで書いた場合) */
class BinarySearchTest {
public static int search(Object ref, int mokuteki) {
int[] array = (int[])ref;
int l = 0;
int h = array.length - 1;
int t = -1; /* dummy */

while(l > h) {
t = (l + h) / 2;
if(array[t] == mokuteki)
break;
else if(array[t] < mokuteki)
l = t + 1;
else /* if(array[t] > mokuteki) */
h = t - 1;
}
return (l > h) ? t : (-1);
}

public static void main(String[] args) {
int array[] = new int[] { 2, 4, 6, 9, 10, 15, 17, 18, 20 };
int mokuteki = 29;

System.out.println("index:");
System.out.println(search(array,mokuteki));
System.out.println("\n");
}
}
    • good
    • 0
この回答へのお礼

プログラムまで書いていただきまことにありがとうございます。

う~ん。やはり目的値が見つからなかった場合の
終了判定はwhileループの外でした方が明確になりますね。

ところでsoakunさんのプログラムに誤りらしきものが・・(^^;

もうそろそろ私も
「作者がまちがいだ!」という風に妥協し始めてます。

「うん、そうだね。」とうなずいていただけると嬉しいのですが・・・

お礼日時:2001/10/27 07:48

sitaとueが同じ値になり、目的値が見つからなかったのに再度ループする必要はないと思いますが、


以前に、同じようなプログラムを書いたとき、sita >= ue では正しく動かなかったような記憶があります。

この回答への補足

ご意見たいへんありがとうございます。

動作を確認できそうなプログラムを作成してみました。
Cですみません。

★の部分を
  sita >= ue
に変更してもうまくいってしまいます。
どなたか失敗する例を知らないでしょうか?

#include <stdio.h>

enum{ NAI, ARU };
int bs(int array[], int size, int mokuteki);


int main(void)
{
  int array[]={1,3,6,13,14,19,19,22,30};
  int i,size;
  size=sizeof(array) / sizeof(array[0]) ;

  for(i=0; i<30; i++){
    int ret;
    ret=bs(array, size, i);

    if(ret == ARU)
      printf("%d:ある",i);
    else
      printf("%d:ない",i);

    ((i+1) % 5)? putchar(' ') : putchar('\n');
  }

  return 0;
}


int bs(int array[], int size, int mokuteki)
{
  int ue=size-1, sita=0, naka;

  while(1){
    naka=(sita+ue)/2;
    if(array[naka] == mokuteki)
      return ARU;
    else if(sita > ue) //・・・・・・・★
      return NAI;
    else {
      if(array[naka] < mokuteki)
        sita=naka+1;
      else
        ue=naka-1;
    }
  }
}


========================================================
コピペ用 ↓

========================================================
#include <stdio.h>

enum{ NAI, ARU};
int bs(int array[], int size, int mokuteki);


int main(void)
{
int array[]={1,3,6,13,14,19,19,22,30};
int i,size;
size=sizeof(array) / sizeof(array[0]) ;

for(i=0; i<30; i++){
int ret;
ret=bs(array, size, i);

if(ret == ARU)
printf("%d:ある",i);
else
printf("%d:ない",i);

((i+1) % 5)? putchar(' ') : putchar('\n');
}

return 0;
}


int bs(int array[], int size, int mokuteki)
{
int ue=size-1, sita=0, naka;

while(1){
naka=(sita+ue)/2;
if(array[naka] == mokuteki)
return ARU;
else if(sita > ue) //・・・・・・・★
return NAI;
else {
if(array[naka] < mokuteki)
sita=naka+1;
else
ue=naka-1;
}
}
}

補足日時:2001/10/25 01:58
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q${parameter:-word} と ${parameter:=word} の違い

bashのパラメータ展開で

${parameter:-word} と ${parameter:=word}

の違いが何なのかよく分らないのですが、何が違うのでしょうか?

http://www.linux.or.jp/JM/html/GNU_bash/man1/bash.1.html

Aベストアンサー

 :-の方は、parameterの値が変わりません。:=は変わります。どちらもparameterに既に値が入っている場合は何も起こりません。
 別の言い方をすると、:=の方はこの後bashが(子プロセスとして)起動するプロセスの環境変数にも$parameterがwordになりますし、:-はなりません。:=は何らかのプログラムを起動するスクリプト内で空っぽならデフォルト値を設定するというような用途に使用します。
 以下、bashですけど$が出てきまくると紛らわしいのでプロンプトを%とします。

% echo ${SAMURAI:=LAST}
LAST
% echo ${DORA:-YAKI}
YAKI
% echo $SAMURAI
LAST ←さっきのでSAMURAIにLASTが代入された
% echo $DORA
   ←さっきのでDORAにYAKIが代入されていない
%

Qオートマトン L = {ww^R: w ∈ {a, b}+}の中心の見つけ方

下記のようなオートマトンがあります。

L = {ww^R: w ∈ {a, b}+}
M = (Q, Σ, Γ, δ, q0, z, F)
Q = (q0, q1, q2),
Σ = {a, b},
Γ = {a, b, z},
F = {q2}.

(1)wをスタックに載せるために:
δ(q0, a, a) = {(q0, aa)}
δ(q0, b, a) = {(q0, ba)}
δ(q0, a, b) = {(q0, ab)}
δ(q0, b, b) = {(q0, bb)}
δ(q0, a, z) = {(q0, az)}
δ(q0, b, z) = {(q0, bz)}

(2)どこが文の中心か見つけるために(状態がq0からq1に変わる):
δ(q0, λ, a) = {(q1, a)}
δ(q0, λ, b) = {(q1, b)}

(3)w^Rと一致させるために:
δ(q1, a, a) = {(q1, λ)}
δ(q1, b, b) = {(q1, λ)}

(4)最後に:
δ(q1, λ, z) = {(q2, z)}

とあります。
問題の中にこれを元にしてL = {wcw^R: w ∈ {a, b}*}のnpdaをつくりなさい、
というのがありますが、それは(2)を
δ(q0, c, a) = {(q1, a)} ←cが入力されたらそこが中心
δ(q0, c, b) = {(q1, b)}
に変えて
δ(q0, λ, z) = {(q2, λ)} ←何も入力されなかったら文字を受け付ける(* → +なので)
を付け加えればよいですか? (多分、そうですよね?)

それと、上の(2)がどうやって中心を見つけているのか分かりません。
入力中は何文字入力されるかなんて分かりませんよね。
例えばbaabbaabという文があったとすると最初の四文字でbaabで
「さては中心はbaとabの間だな!」とか勘違いとかしないんですか?
入力がλということは毎回毎回入力がある度にチェックしているということでしょうか?
混乱している私に分かりやすい説明ができる方、どうかお願いします。

下記のようなオートマトンがあります。

L = {ww^R: w ∈ {a, b}+}
M = (Q, Σ, Γ, δ, q0, z, F)
Q = (q0, q1, q2),
Σ = {a, b},
Γ = {a, b, z},
F = {q2}.

(1)wをスタックに載せるために:
δ(q0, a, a) = {(q0, aa)}
δ(q0, b, a) = {(q0, ba)}
δ(q0, a, b) = {(q0, ab)}
δ(q0, b, b) = {(q0, bb)}
δ(q0, a, z) = {(q0, az)}
δ(q0, b, z) = {(q0, bz)}

(2)どこが文の中心か見つけるために(状態がq0からq1に変わる):
δ(q0, λ, a) = {(q1, a)}
δ(q0, λ, b) = {(q1, b)}

(3)w^Rと一致させるため...続きを読む

Aベストアンサー

先の2つの御質問からすると、non-deterministic(非決定的)なPDAを考えているわけですよね。

非決定的なオートマトンでは、「1つの入力系列に対して複数の遷移経路が考えられるが、そのうち1つでも受理状態で遷移が終了する経路が存在すれば、オートマトンはその入力を受理する」と考えます。

baabbaabの例であれば、"b"しか入力されていない状態、"ba"まで入力された状態、...、"baabbaab"まで入力されてしまった状態、のどこで(2)の遷移をやってもいいんです。
そのうち"baab"の状態で(2)の遷移をすれば受理状態で遷移が終了するので、このオートマトンは"baabbaab"を受理するといえるわけです。

> それは(2)を
> ....
> を付け加えればよいですか? (多分、そうですよね?)
そこはそれで合っていると思いますよ。

Qfmlのconfig.phで使う、q{~};やq#~#;q%~%;は全て同じ意味?

メーリングリストのカスタマイズをしていて、ネット上で情報を集めているのですがどうしても分からないところがあります。 fml 4.0
$SMTP_OPEN_HOOKなどのHOOKを行うときに、q{~};やq#~#;q%~%を同じサイトであっても使い分けているようで、SMTP_OPEN_HOOKの時には =q{~}; を、START_HOOKでは =q#~#; のようになっています。
プログラムというもの自体触ったことはないのですが、一応記号が変わっているだけで中身は同じなのかなと思っています。
実際のところ別物でしょうか?

fmlとqで検索をかけても情報が引っかかりませんし、fmlとq#などとしてもfmlでしか検索できないみたいで八方ふさがりです。
よろしくお願いします。

Aベストアンサー

fmlはPerlという言語で書かれています。これはPerlの記法の問題です。
どれも意味は同じです。違うのは、
・囲まれた内部で使われて無い記号を使って囲むため
・書いた人が違う
・気分によって使い分け?

Q【緊急】{ww: w∈{a, b}*}はRegular language?

{ww: w∈{a, b}*}はRegular languageですよね?
{ww^R: w∈{a, b}*}はNon-regular languageというのは知っています。

さっき試験が終わったばっかりで気になって仕方がありません。

Aベストアンサー

> という場合がありえますが
----------** 最後のa..ab、
を忘れていました。どっちにしても結論はかわりませんが、訂正します。

あと、ついでなので1つアドバイス的なことを。
正規表現の能力の限界は、直観的には、DFAが有限の状態しか持たないということに起因します。
例えば、(^i )^i(=同じ数の対応する括弧)が正規表現で表せないことはご存知ですよね。
これは、「(^i が入力された時点で、今までに何個の( が入力されたかを覚えておく必要があるが、それは有限の状態では不可能だから」と理解することができます。

こう理解しておくと、証明するまでもなく、{ww: w∈{a, b}*} は正規言語ではないということが予想できるかと思います。

QPowerShellの{get;}の意味

PowerShellで「Get-Date | Get-Member」と入力すると下記のようにでます。


Name MemberType Definition
---- ---------- ----------
(省略)
Date Property System.DateTime Date {get;} ←これ
Day Property System.Int32 Day {get;} ←これ
DayOfWeek Property System.DayOfWeek DayOfWeek {get;} ←これ
DayOfYear Property System.Int32 DayOfYear {get;} ←これ
(省略)

Definitionの部分の「 {get;}」の意味が分かりません。
よろしくお願いします。

PowerShellで「Get-Date | Get-Member」と入力すると下記のようにでます。


Name MemberType Definition
---- ---------- ----------
(省略)
Date Property System.DateTime Date {get;} ←これ
Day Property System.Int32 Day {get;} ←これ
DayOfWeek Property System.DayOfWeek DayOfWeek {get;} ←これ
DayOfYea...続きを読む

Aベストアンサー

Property だから "読み取り専用" ってことでしょ。
Get-Date で得られる DateTime 型のオブジェクトの Day プロパティは int 型で、読み取り専用。


人気Q&Aランキング

おすすめ情報