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

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

以下の文はとあるアルゴリズム本の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と関連する良く見られている質問

Qaccess2003 クロス集計クエリに抽出条件を設定する

QNo.3495024にて、「取引先ごとの月次売上(部品別および合計)」をフォーム形式で表示する方法を質問した者です。
1)クロス集計クエリの抽出条件としてこのコンボを設定
2)フォームに置いたボタンでクロス集計クエリまたはそれをソースにした別フォームを開く
という方法を教えていただきました。

昨夜から自分なりに調べましたが、1)のクロス集計クエリに抽出条件を設定する方法がわかりません。 昨日の今日で再質問も気が引けますが、時間がないので質問させてください! ご存知の方、よろしくお願いいたします。

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住所録から2つ以上の条件で抽出する関数について

Windows Excel 2003で住所録から2つ以上の条件で抽出するにはどんな関数を使えばいいですか?

例えば住所録で『TELとFAXが異なっている番号の別々のセル』と『TELとFAXが同じ番号のセル(TELとFAXが同じなのでFAXのセルは空欄)』尚且つ『Eメールのある会社名』を抽出する関数はありますか?

Aベストアンサー

どういうレベルで要っているのかわかりませんが
>関数はありますか?
単独関数ではありません。2つ以上の関数を組み合わせたり、作業列を使ったりすれば出来るといえます。
単独の関数はあるとも無いとも言えるが、該当分行がつめたカタチでは単独の関数ではありません。
該当が飛び飛びで出てよいなら、IF関数で簡単に出来ます。これわかりますね。
A1 TELNO,B1 FAXNOとして
C1に =IF(A1<>B1,A1,"") D1に=IF(A1<>B1,B1,"")  でよいわけです。
 ここの質問に出るレベルは、ほとんど関数の組み合わせが必要です。
ーー
Googleで「imogasi方式」で照会してください。条件をかけて、抜き出す課題が相当数出てきます。
回答は
A.関数の組み合わせー作業列なし
B.関数の組み合わせー作業列を使うー>Imogasi方式など
などの回答が見られます。
もちろんフィルタやフィルタオプションの設定のお勧めの回答もあるでしょう。
私見では、A.の式が理解できたら、関数は9割5分は卒業です。
関数に拘らず、データ^フィルターフィルタオプションの設定
をお勧めします。(データーフィルタではないですよ)

どういうレベルで要っているのかわかりませんが
>関数はありますか?
単独関数ではありません。2つ以上の関数を組み合わせたり、作業列を使ったりすれば出来るといえます。
単独の関数はあるとも無いとも言えるが、該当分行がつめたカタチでは単独の関数ではありません。
該当が飛び飛びで出てよいなら、IF関数で簡単に出来ます。これわかりますね。
A1 TELNO,B1 FAXNOとして
C1に =IF(A1<>B1,A1,"") D1に=IF(A1<>B1,B1,"")  でよいわけです。
 ここの質問に出るレベルは、ほとんど関数の組み合わ...続きを読む

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

Q別シートに複数条件を選択すると抽出され合計値がでてくるような関数はありますか

毎日、以下のような作業内容が手元にくるのですが今までは手でノートに振り分け管理していたのですが、エクセルの関数で別シートに複数条件を選択すると抽出され合計値がでてくるような関数はありますか。
よろしくお願いします。

↓毎日くる作業内容です。
ex)これを日ごとにシートに入力して、別シートに項目の班替え選択→内訳選択→班長を選択→形を選択→該当する全日付から時間が抽出され合計時間がでてくる

Aベストアンサー

条件をかけるとして、条件該当の明細を必要としているのか、合計だけでよいのか、質問ではっきりしない。添付画像通常は小さくなり見にくい。
質問文に簡略化した1例(10行以内でよい)を挙げて質問すべきだ。要点を掴む能力と思考力が鍛えられる。
>ex)これを日ごとにシートに入力して、別シートに項目の班替え選択→内訳選択→班長を選択→形を選択→該当する全日付から時間が抽出され合計時間がでてくる、の部分。
4条件で加算の例か。
====
条件該当分の明細を出すなら
データーフィルタオプションの設定で出来るはず。
関数関数と言うが、エクセルは第1的には、操作の体系のソフトですよ。他シートにデータを出すのは、他シート側で操作を始めてください。
ーー
関数なら、自称「imogasi方式」で出来ると思います。
Googleで「imogasi方式」で照会すれば数百の例が出ると思います。
現データシート(Sheet1)条件該当分の行にだけ、上の行から順に連番をフリ(式の複写を使う)、他シート(Sheet2)で
Sheet2の行1に-->Sheet1の連番1の行をINDEX関数で持ってくる。
Sheet2の行2に-->Sheet1の連番2の行をINDEX関数で持ってくる。
・・以下同じ。
これを式の複写で自動で行える。
=====
合計だけで良いのなら、多分、条件が多数のものに対する合計をほしい、になり、条件値の組み合わせを手作業でセルにセットするのか、操作関数で出すのかも質問に書いてない。合計を出すより、この条件データを揃える方が、いつも言っているが、難しい。
>複数条件を選択すると抽出され合計値がでてくるような関数
これが文字通り合計計数だけでよいなら、毎日ここに質問が出る
SUMPRODUCT、SUMIFSのどちらかをつかえだけ。質問にエクセルバー順が書いてないのは、エクセルの勉強経験不足。
2007で便利な関数が出来たのは有名な話。

条件をかけるとして、条件該当の明細を必要としているのか、合計だけでよいのか、質問ではっきりしない。添付画像通常は小さくなり見にくい。
質問文に簡略化した1例(10行以内でよい)を挙げて質問すべきだ。要点を掴む能力と思考力が鍛えられる。
>ex)これを日ごとにシートに入力して、別シートに項目の班替え選択→内訳選択→班長を選択→形を選択→該当する全日付から時間が抽出され合計時間がでてくる、の部分。
4条件で加算の例か。
====
条件該当分の明細を出すなら
データーフィルタオプション...続きを読む

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エクセルにおいて複数の条件から抽出することができる関数(式)を教えてください。

皆さんどうか教えてください

エクセルにおいて複数の条件から抽出することができる関数(式)を教えてください。

400  70円  ad   6個
700  60円  da 7個  
100  30円 ad   9個
400  50円  ad   10個


などの表で、400で70円でadなものの数を求める
条件で数値を求めるにはどうすればいいのでしょうか

また条件にあったデータに6個などの数値をかけて合計した数値を求めるにはどうすればいいのでしょうか

関数でできる方法をお願いします。


あと”なおかつ”などの条件を行う関数も教えてください

どうかヨロシクお願いします。

Aベストアンサー

#4さんの回答で解決しませんか?

1行に複数のデータが入力されており、全ての列を満たす行数をカウントしたいということですか?
カウント対象が1万行あるとすると
=SUM((A1:A10000=A列の条件)*(B1:B10000=B列の条件)*(C1:C10000=C列の条件)*(D1:D10000=D列の条件)・・・)
と必要なだけ入力し、ctrlキーとshiftキーを押しながら
enterキーで式を確定して下さい。そうすると式が
{=SUM((A1:A10000=A列の条件)*(B1:B10000=B列の条件)*(C1:C10000=C列の条件)*(D1:D10000=D列の条件)・・・)}
という風な括弧で括られます。(配列数式になる)

列の条件は、数値ならそのまま、文字列なら""で囲います。
セルを指定しても構いません。
(1行目と同じ場合のみカウントという事であれば=A$1等となる)

もし、例の場合でいう400でadの場合の金額*個数を求めたいなら
(例では70円*6個+50円*10個で920円)
=SUM((A1:A10000=400)*(C1:C10000="ad")*(B1:B10000)*(D1:D10000))
をctrlキーとshiftキーを押しながらenterキーです。

後は応用です。

#4さんの回答で解決しませんか?

1行に複数のデータが入力されており、全ての列を満たす行数をカウントしたいということですか?
カウント対象が1万行あるとすると
=SUM((A1:A10000=A列の条件)*(B1:B10000=B列の条件)*(C1:C10000=C列の条件)*(D1:D10000=D列の条件)・・・)
と必要なだけ入力し、ctrlキーとshiftキーを押しながら
enterキーで式を確定して下さい。そうすると式が
{=SUM((A1:A10000=A列の条件)*(B1:B10000=B列の条件)*(C1:C10000=C列の条件)*(D1:D10000=D列の条件)・・・)}
という風な括弧...続きを読む

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}*} は正規言語ではないということが予想できるかと思います。

Q条件に合うデータを抽出する関数

EXCELで、条件に合うデータを抽出し個数を表示させたいと思っています。
ただしSUMPRODUCTなどの『複数条件の設定』ではなく、『特定の文字列を除く』
という形で設定したいのですが、そのような関数はありますか?

Aベストアンサー

=COUNTIF(範囲,"<>*文字列*")
で出来ませんか?
=SUMPRODUCT(ISERROR(FIND("文字列",範囲))*1)
でも同じに出来ますけど...

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ランキング