番兵と検索関連の質問

[アスタリスク]

問題の意味すらわかりません援護射撃よろしくお願いします

0 から100 までの範囲で整数の乱数を1000 個発生させ、ターゲット整数を検索し、何番目の数
字でターゲット整数が見つかるか、番兵を使わない関数NonSentinel と、番兵を使う関数Sentinel の２つで求
める下のプログラムを完成させなさい。このプログラムをbanpai.c として実行ファイルをbanpei.exe とする場
合、
>banpei 50
> 番兵なし54, 番兵あり54
>banpei 200
> 番兵なし-1, 番兵あり1001
のように動作する。
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 1001 // データの長さ+ 番兵
#define MAX 101 // データの範囲
/*----------------------------------------------
関数プロトタイプ
-----------------------------------------------*/
void GenerateNumbers(int* m, int n);
int Sentinel(int target, int* m, int n);
int NoSentinel(int taget, int* m, int n);
/*----------------------------------------------
**
番兵をつかった線形検索問題
* m[/url] の中からtarget を探し、配列の中の行番号を求める。
*-----------------------------------------------*/
int main(int argc, char** argv)
{
int m[LENGTH]; // ランダムに発生させる数
int target; // 検索する数
GenerateNumbers(m, LENGTH-1); // ゼロから100 までの乱数を発生させてm に代入
target = strtol(argv[1], NULL, 0); // ターゲットは二番目の引数
printf("番兵なし%d, 番兵あり%d\n",
NoSentinel(target, m, LENGTH-1), // 番兵を使わずに検索
Sentinel(target, m, LENGTH) // 番兵を使って検索
);
}/
*----------------------------------------------
線形検索
input int target: 検索する数
int m[/url]; 検索対象の配列
int n; 配列の次数
戻り値: 何番目に見つかったか、もしなければ-1 を返す
33
-----------------------------------------------*/
int NoSentinel(int target, int* m, int n)
{}/
*----------------------------------------------
番兵を使った線形検索
input int target: 検索する数
int m[/url]; 検索対象の配列
int n; 配列の次数
戻り値: 何番目に見つかったか、もしなければ番兵を返す
-----------------------------------------------*/
int Sentinel(int target, int* m, int n)
{}/
*----------------------------------------------
**
Random number generator
* Generate n random numbers ranging from 0 to 100
* and stored in m[/url].
* 2008.9.12
* input/output int m[/url];
* input int n;
*-----------------------------------------------*/
void GenerateNumbers(int* m, int n)
{
int ii;
for (ii=0; ii<n; ii++){
m[ii] = rand()%MAX;
}
}

[conio]

では問題の意味から。

まず、要素が10の配列vがあるとします。
この中から、100という値が入っている場所を探すものとします。
-------------------
┃v[0] = 20
┃v[1] = 30
┃v[2] = 40
┃v[3] = 50
┃v[4] = 60
┃v[5] = 70
┃v[6] = 80
┃v[7] = 90
┃v[8] = 10
▼v[9] = 0
-------------------

この時の終了条件は、
-------------------------------
・添え字が0～9までの間で終了
・検索した値が100であれば終了
-------------------------------
上記の2つになります。
これが非番兵法です。


で、今度は一番最後に検索したい値を入れておくとします。
（要素が一つ分増えます。 v[10]　⇒　v[11]）
-------------------
┃v[0] = 20
┃v[1] = 30
┃v[2] = 40
┃v[3] = 50
┃v[4] = 60
┃v[5] = 70
┃v[6] = 80
┃v[7] = 90
┃v[8] = 10
┃v[9] = 0
▼v[10] = 100
-------------------

こうしておくと、必ず検索したい値が見つかることになります。
なので、終了条件は
--------------------------------
・検索した値が100であれば終了
（番兵v[10]であれば失敗、それ以外であれば成功と判断）
--------------------------------
の一つだけで良いことになります。

これが番兵法です。

[asd]

既にconio氏が番兵法については解説してありますが、
配列の一番最後に置かれた検索する値のことを番兵と呼びます。
配列にアクセスする際には配列の範囲外アクセスしないようにしながら検索をしなければなりませんが、
番兵を用意することで範囲外アクセスする前に番兵が止めてくれます。

番兵法が何かが分かってもどうやってプログラムを書けばよいのか分からない場合には
以下の点を教えてもらえると詳しい回答ができると思います。

・アスタリスクさんがどのくらいプログラムができるのか
　→配列の中から指定された値を探すプログラムが書ける、
　　配列の要素にアクセスできる
　　文字列比較ができる
　　などなど
・自分で作ってみたソースがあるならば＜pre＞＜/pre＞で囲んで貼り付けると
　よいでしょう(上では全角の＜＞で囲んでいますが実際に書き込むときには半角の不等号で囲んでください)

[asd]

折角ですので質問者さんが貼り付けたソースを整形しておきます。

#include <stdio.h>
#include <stdlib.h>
#define LENGTH 1001 // データの長さ+ 番兵
#define MAX 101 // データの範囲
/*----------------------------------------------
関数プロトタイプ
-----------------------------------------------*/
    void GenerateNumbers(int* m, int n);
    int Sentinel(int target, int* m, int n);
    int NoSentinel(int taget, int* m, int n);
/*----------------------------------------------
**
番兵をつかった線形検索問題
* m[/url] の中からtarget を探し、配列の中の行番号を求める。
*-----------------------------------------------*/
int main(int argc, char** argv)
{
    int m[LENGTH]; // ランダムに発生させる数
    int target; // 検索する数
    GenerateNumbers(m, LENGTH-1); // ゼロから100 までの乱数を発生させてm に代入
    target = strtol(argv[1], NULL, 0); // ターゲットは二番目の引数
    printf("番兵なし%d, 番兵あり%d\n",
        NoSentinel(target, m, LENGTH-1), // 番兵を使わずに検索
        Sentinel(target, m, LENGTH) // 番兵を使って検索
    );
    return 0;
}
/*----------------------------------------------
線形検索
input int target: 検索する数
int m[/url]; 検索対象の配列
int n; 配列の次数
戻り値: 何番目に見つかったか、もしなければ-1 を返す
-----------------------------------------------*/
int NoSentinel(int target, int* m, int n)
{
    /*n個の要素を持つ配列mからtargetを検索します*/
}

/*----------------------------------------------
番兵を使った線形検索
input int target: 検索する数
int m[/url]; 検索対象の配列
int n; 配列の次数
戻り値: 何番目に見つかったか、もしなければ番兵を返す
-----------------------------------------------*/
int Sentinel(int target, int* m, int n)
{
    /*n個の要素を持つ配列mからtargetを検索します*/
}
/*----------------------------------------------
**
Random number generator
* Generate n random numbers ranging from 0 to 100
* and stored in m[/url].
* 2008.9.12
* input/output int m[/url];
* input int n;
*-----------------------------------------------*/
void GenerateNumbers(int* m, int n)
{
    int ii;
    for (ii=0; ii<n; ii++){
        m[ii] = rand()%MAX;
    }
}

[アスタリスク]

conio様asd様ありがとうございます。番兵の意味もおぼろげながらわかってきました。
ところでasdさんが最後に書いてくださったソースプログラムをemacsに貼り付け
ターミナルで実行するとbus errorとか表示されます。何がいけないのでしょうか？
このプログラムでは「秒」が二つ（番兵有りと無し）出力されるんですよね？

[ドラ]

>target = strtol(argv[1], NULL, 0);
コマンドライン引数で探索する数値を渡さないとここでバグりそうですね。

>このプログラムでは「秒」が二つ（番兵有りと無し）出力されるんですよね？
なぜ「秒」なのでしょうか？
コメントに嘘が書かれている可能性もありますが
とりあえず、↓のようにコメントされています。

>/*----------------------------------------------
>**
>番兵をつかった線形検索問題
>* m[/url] の中からtarget を探し、配列の中の行番号を求める。
>*-----------------------------------------------*/

[box]

> ところでasdさんが最後に書いてくださったソースプログラム

これって、質問者さんが最初に投稿されたソースを整形しただけですよね。
検索する関数の中身が何もないですから、正しく動かないのは当然かと。

[アスタリスク]

int NoSentinel(int target, int* m, int n)
{ int i=-1;while(n) if(m[(n--)-1]==target) i=n; return i; }

int Sentinel(int target, int* m, int n)
{ for(m[n]=target,n=0;m[n]!=target;n++); return n; }

なかみというのはこれでいいでしょうか？
　　
　　あ秒じゃなくて「番目」で出力されるだけですね　すみませんでした

[non]

> NoSentinel(target, m, LENGTH-1), // 番兵を使わずに検索
> Sentinel(target, m, LENGTH) // 番兵を使って検索
最後の引数が、両方とも配列の次数と書いてあるのに、違うのはわかりにくいのではないか。

NoSentinelの関数では、後ろから探索しているため、探索回数がｎ回になる。見つかったら
探索をやめた方が探索回数が少なくてすむので、前から探索すべきではないのか。

[ドラ]

Sentinel関数のfor文の最初の「 m[n]=target 」の部分で
配列の領域外に書き込んでいます。

[アスタリスク]

B評価きましたc狙いだったのでとても満足しています
・[41082] conio
・[41084] asd
・[41105] ドラ
・[41106] box
・[41115] non
様ありがとうございました