- 締切済み
アルゴリズムでわからない問題があります。（C言語）
問題１：探索アルゴリズムであるハッシュ法について正しいものを選べ。 (1)ハッシュ関数の出力によりデータを格納した配列の先頭から順番に調べる． (2) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめ木構造に格納しておく． (4) 入力データを格納した配列を繰り返し２つに分割し，それぞれを順番に調べていく． (3) 入力データから格納場所の位置に変換する関数（ハッシュ関数）の出力により，データの探索場所を決定する。 (5) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめヒープに格納しておく 問題２：探索アルゴリズムであるハッシュ法について正しくないものを選べ。 (1)入力データはハッシュ値で決められる場所に格納される． (2) ハッシュ関数には，異なる入力の値に対し異なる値を出力することが求められる． (3) ハッシュ関数の時間計算量は，入力データのサイズに比例する． (4) データの格納場所が大きい方が効率がよい． (5) 一般に２分探索法より高速に動作する． どなたかアルゴリズムに詳しい方回答お願いします
- choko_tan
- お礼率3% (1/29)
- C・C++・C#
- 回答数3
- ありがとう数0
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- utun01
- ベストアンサー率40% (110/270)
No.2さんと若干見解の異なる部分についてのみ記載します。 ・問題２ (2)について ハッシュ関数の理念としては正しい気がします。 現実的には不可能なので、完全にこのように作られるハッシュ関数はありませんが・・・。 出題者の意図次第な感じですね。 ・問題２ (4)について ここで言うハッシュ法が、ハッシュテーブルを使うものなのか、 実アドレスを使うものなのかによって違います。 前者であれば間違いですが、後者であれば正解です。 ちなみに、後者のアルゴリズムはあまり一般的DBでは使用されていません。 以下、蛇足です。 とにかく問題の作り方が良くありません。 問題１についても、恐らく答えは(3)ですが、 (3)の場合は、ハッシュテーブルを用いる一般的な方法とは一線を画します。 （上で言っている後者の方法） 勉強中のようですので、ついでにこの辺も調べてみてはいかがでしょうか。
関連するQ&A
- アルゴリズムに関する問題
こんばんわ、いくつかの問題につまってしまったので解答と簡単な解説をお願いします； 【問1】 4桁の数字( a1a2a3a4 )をハッシュ法を用いて配列に格納したい。 ハッシュ関数をmod（ a1 +a2 +a3 +a4 ,5 ）とし、求めたハッシュ関数値に対応する位置の配列要素に格納する場合、９５７６は（ア）～（オ）のどこに入るか。 ここでmod（x，5）の値は、xを5で割った余りとする。 位置 配列 ０ （ア） １ （イ） ２ （ウ） ３ （エ） ４ （オ） 【問２】 相違なるｎ個のデータが昇順に整列された表がある。この表を１ブロックｍ個に分割し、各ブロックの最後尾のデータだけ線形検索することによって、目的のデータを探し出す。 次に当該ブロック内を線形検索して目的のデータを探し出す。 このときの平均探索（比較）回数は（ア）～（エ）のうちどれか。 ここでｍ＜ｎとし、目的のデータは必ず表の中に存在するものとする。 （ア） （イ） （ウ） （エ） ｎ ｎ ｎ ｍ ｎ ─ ─ ｍ ＋ ─ ─＋─ ｍ ２ｍ ｍ ２ ２ｍ 【問3】 次の手順はシェルソートによる整列を示している。 データ列”7，2，8，3，1，9，4，5，6”を手順（１）～（４）に従って整列すると手順（３）を何回繰り返して完了するか。 ここで、〔〕は小数点以下を切り捨てる。 ＜手順＞ （1）〔データ数÷3〕→Ｈとする。 （2）データ列を互いにＨ要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を挿入方を用いて整列する。 （3）〔Ｈ÷3〕→Ｈとする （4）Ｈが0であればデータ列の整列は完了し、0でなければ（2）に戻る。 以上になります。
- ベストアンサー
- その他([技術者向] コンピューター)
- 探索・整列アルゴリズムのメリット・デメリットについ
「コンピューターはなぜ動くのか？」の第５章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1 主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)～(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。
- 締切済み
- その他([技術者向] コンピューター)
- 定番アルゴリズムのメリット・デメリットについて
定番アルゴリズムとして以下のアルゴリズムが挙げられますが、 (1)ユークリッドの互徐法 (2)エラトステネスのふるい (3)線型探索 (4)二分探索 (5)ハッシュ探索 (6)バブル・ソート (7)クイック・ソート ↑これらの各々のアルゴリズムのメリット・デメリットについてをそれぞれ教えてください。 よろしくお願いします。
- 締切済み
- その他([技術者向] コンピューター)
- C言語についての質問です＞＜
0から100までの乱数を発生させ要素20個の整数配列aに乱数を格納し、 その配列を大きい順番に並び替える。 その際もともと格納されていた配列の場所もあわせて 表示するプログラムを示せ。 乱数発生にはsrand関数とrand 関数を使います。 二次元配列を使うこと． プログラムリソースとプログラム解説をつけてほしいです＞＜ 例 number place a[0]=98 3 a[1]=94 19 a[2]=90 1 のようになるようにお願いしますm(_ _)m
- 締切済み
- C・C++・C#
- C言語の問題
配列の問題 １．キーボードから入力したアルファベットの大文字（A～Z)の入力回数をそれぞれ数え、結果を画面出力するプログラムを作成せよ。但し、入力の終了はEOFとし、入力回数のカウントには、配列を用いるものとする。（文字ごとに回数を格納する配列を用意する） ２．キーボードから番号（数字）を入力し、その番号に該当する文字列中の文字を画面表示するプログラムを作成せよ。なお、数字以外の文字が入力した場合と、文字列の範囲外の数字が入力された場合は、任意のメッセージを出力し、再入力するようにする。また文字列はキーボードから入力するものとする。 この問題が解けなくて困ってます。どうか知恵をかしてください。
- ベストアンサー
- C・C++・C#
- C言語 テキスト問題
なぞなぞの問題文が格納されているファイルにおける1行目の問題文と答えが格納されているファイルにおける1行目の答えを読み込む処理を実装せよ。また、読み込んだ問題文と答えをそれぞれ出力せよ。 以下に、問題文のファイルと答えのファイルに格納されている文字列を示す。 ・問題文(nazonazo_mondai): 自分の家をおんぶしている虫は何？ ケガをしたときにつける毒は何？ 銀色のチャックを大急ぎで集めている生き物は何？ スポーツで破りたいものといえば何？ 草が古くなったよ。どんな味がした？ ・答え(nazonazo_kotae): カタツムリ 消毒 イソギンチャク 記録 苦い味 入力される値 なし 期待される出力値 自分の家をおんぶしている虫は何？ カタツムリ 制約 ・問題文のファイル名、答えのファイル名は以下を用いること。 問題文：nazonazo_mondai 答え：nazonazo_kotae ・それぞれのファイルを読み込めなかった場合の処理として、以下を出力しプログラムを終了する。 問題ファイルの読み込みに失敗しました。プログラムを終了します。 回答ファイルの読み込みに失敗しました。プログラムを終了します。 ・問題文と答えを読み込む配列は以下を用いること。 char question[256]; char answer[32]; ・fgets関数を使ってファイル内の文を読み込む際に、配列の大きさを引数として渡す必要がある。 その際にsizeof関数を用いること。 ポイント ・fgets関数、sizeof関数の使い方は以下のサイトを参考にすると良い サンプルケース1 入力値 なし 期待される出力値 自分の家をおんぶしている虫は何？ カタツムリ
- ベストアンサー
- C・C++・C#
- ハッシュ（オープンアドレス法） C言語の課題
努力はしてみたのですが、C言語の課題ができません。教えていただけないでしょうか。 問：名前と年齢を入力し、名前をキーとしてハッシュ（オープンアドレス法）に登録する。'-'が入力されると登録を終了し、次に入力された名前をハッシュ法で検索し、あればその人のデータをハッシュから削除する、その後、ハッシュ表の内容を出力するプログラムを作成せよ。ただしハッシュ表の大きさは５とする。 例 koizumi 入力 1 入力 fukuda 入力 2 入力 aso 入力 3 入力 - 入力 koizumi 入力 fukuda(2) 出力 aso(3) 出力 ハッシュ関数は int hash(char *name) { int ret=0; while (*name)ret += *name++; return ret%5; } 再ハッシュ関数は int rehash(int h) { return (h+1)%5; } を使おうと考えています。 内容を理解できないと困るので簡単なプログラムをお願いします。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- C言語
以下のC言語のプログラムを教えてください。 お願いします。 (1)標準入力から文字列（2 文字以上）を入力し，文字数を計上すると共に，入力された文字列の逆順に入れ替える処理を実現してください．なお，以下の要件を満たしたプログラムを作成してください． ・ 入力された文字列は，char 型の配列（要素数50）で受け取ること ・ 文字数を計上するcount 関数（引数：配列のアドレス，戻り値：文字数）を定義 し，main 関数より呼び出すこと ・ 文字列を逆順に入れ替えるreverse 関数（引数：配列のアドレス，戻り値：無し） を定義し，main 関数より呼び出すこと ・ 標準出力の処理は，main 関数で記述すること 【プロトタイプ宣言】 int count(char *str); void reverse(char *str); 【実行結果】 文字列を入力してください（2 文字以上） apple 文字数 = 5 入れ換え前 apple 入れ換え後 elppa (2)char 型の配列（要素数50）を2 つ宣言し，標準入力から2 つの文字列を入力してください．そして，格納した字列を入れ替える関数（swapstr 関数）を作成し，入れ替え前と入れ替え後の配列内の値（文字列）を配列名とともに標準出力するプログラムを作成してください． 【プロトタイプ宣言】 void swapstr(char *str1, char *str2); 【実行結果】 2 つの文字列を入力してください apple strawberry 入れ換え前 配列str1 = apple 配列str2 = strawberry 入れ換え後 配列str1 = strawberry 配列str2 = apple
- 締切済み
- 情報工学
- C言語 テキスト問題
問題文の表示、回答の入力、答えの表示が行えるようにせよ。 以下に、問題文のファイルと答えのファイルに格納されている文字列を示す。 ・問題文(nazonazo_mondai): 自分の家をおんぶしている虫は何？ ケガをしたときにつける毒は何？ 銀色のチャックを大急ぎで集めている生き物は何？ スポーツで破りたいものといえば何？ 草が古くなったよ。どんな味がした？ ・答え(nazonazo_kotae): カタツムリ 消毒 イソギンチャク 記録 苦い味 入力される値 カタツムリ 消毒 イソギンチャク 記録 苦い味 期待される出力値 第01問 ===================== 自分の家をおんぶしている虫は何？ 第01問の答え: カタツムリ 第02問 ===================== ケガをしたときにつける毒は何？ 第02問の答え: 消毒 第03問 ===================== 銀色のチャックを大急ぎで集めている生き物は何？ 第03問の答え: イソギンチャク 第04問 ===================== スポーツで破りたいものといえば何？ 第04問の答え: 記録 第05問 ===================== 草が古くなったよ。どんな味がした？ 第05問の答え: 苦い味 制約 ・問題文のファイル名、答えのファイル名は以下を用いること。 問題文：nazonazo_mondai 答え：nazonazo_kotae ・それぞれのファイルを読み込めなかった場合の処理として、以下を出力しプログラムを終了する。 問題ファイルの読み込みに失敗しました。プログラムを終了します。 回答ファイルの読み込みに失敗しました。プログラムを終了します。 ・以下の構造体を用いてなぞなぞの問題と答えを読み込むこと。 構造体「MONDAI」を定義して、 「MONDAI」の構造体の中には以下のメンバを定義してください。 ただし、typedefを用いること。 【メンバ名】 【データ型】 【説明】 question 文字配列[要素数:256] 問題文を格納する変数 answer 文字配列[要素数:50] 答えを格納する変数 kaitou 文字配列[要素数:50] 入力した回答を格納する変数 ・fgets関数を使ってファイル内の文を読み込む際に、配列の大きさを引数として渡す必要がある。 その際にsizeof関数を用いること。 ・問題文の出力と答えの出力にはそれぞれ以下を使用すること 第%02d問 ===================== 第%02d問の答え: ポイント ・構造体のメンバ変数にkaitouを追加しています。ここに入力内容を格納すること。 ・問題文の表示、回答の入力、答えの表示を5回繰り返すようにする。 ・答えで表示する文字列は、nazonazo_kotaeのファイルから読み込んだ文字列を出力すること。 ※ kaitouに格納された文字列ではないことに注意してください。 サンプルケース1 入力値 カタツムリ 消毒 イソギンチャク 記録 苦い味 期待される出力値 第01問 ===================== 自分の家をおんぶしている虫は何？ 第01問の答え:カタツムリ 第02問 ===================== ケガをしたときにつける毒は何？ 第02問の答え:消毒 第03問 ===================== 銀色のチャックを大急ぎで集めている生き物は何？ 第03問の答え:イソギンチャク 第04問 ===================== スポーツで破りたいものといえば何？ 第04問の答え:記録 第05問 ===================== 草が古くなったよ。どんな味がした？ 第05問の答え:苦い味
- 締切済み
- C・C++・C#
