ウォーターサーバーとコーヒーマシンが一体化した画期的マシン >>

今、ダイクストラ法を用いて最短経路問題についてのプログラムを作成して完成したところです.

このダイクストラ法をフィボナッチヒープを用いて高速化できると聞きました.

ウィキペディァで見てもよくわかりません。。。。

どなたか、このフィボナッチヒープの仕組みなど解説しているサイトを教えて下さい.

できたら、この場での解説もお願いします.

A 回答 (1件)

正直なところ, フィボナッチヒープを使うのはお勧めしません.


理論上は速くなるんですが, 実際にプログラムにすると個々の処理に時間がかかるためむしろ遅くなると思います.
まあ, 有名なデータ構造ではありますのでちょっと大きめの本を見れば書いてあるかと思いますが....
    • good
    • 1

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

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

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

Q変数の型でlong longとunsigned long longと言うのは何ですか?

教えていただきたいのですが、変数の型にlong longやunsigned long long
なるものがあると聞いたのですが、どのようなものでしょうか?
また、どのように宣言するのでしょうか?通常のlongなどと同じ要領で宣言し
てやれば良いのでしょうか?
もし、この型がある場合に、制約はあるのでしょうか?Unixでしか使えないとか
の制約等ありましたらぜひ教えてください。
お願いいたします。

Aベストアンサー

long longはANSI-Cの新しい改訂版C99で正式に採用されました。
C99以前のANSI-C対応処理系では独自拡張(gccなど)です。
環境の指定が無いので独自拡張は無視してANS-C99について解答します。

long longまたはlong long int=64ビット符号付き整数
unsigned long longまたはunsigned long long int=64ビット符号無し整数

定数の場合はLL(=long long)またはLLU(=unsigned long long)を付加する。
LL,LLU小文字でもよい。
1LL,0LL,100000000000lluなど

long long系の整数使うライブラリ関数について
・printf/scanf系書式の追加
%lld(=long long) および%llu(=unsigned long long)
・その他ライブラリ関数
文字列整数化:strtollが用意される。

現状では日本語で読めるC99の包括的な資料は存在しません。
英語版で良ければC99のドラフトが参考URLで読むことができます。

参考URL:http://anubis.dkuug.dk/JTC1/SC22/WG14/

long longはANSI-Cの新しい改訂版C99で正式に採用されました。
C99以前のANSI-C対応処理系では独自拡張(gccなど)です。
環境の指定が無いので独自拡張は無視してANS-C99について解答します。

long longまたはlong long int=64ビット符号付き整数
unsigned long longまたはunsigned long long int=64ビット符号無し整数

定数の場合はLL(=long long)またはLLU(=unsigned long long)を付加する。
LL,LLU小文字でもよい。
1LL,0LL,100000000000lluなど

long long系の整数使うライブラリ関数について
・...続きを読む

Qint型からchar型への変換

タイトル通り、int型からchar型への変換の仕方がわかりません!><
どうしたらいいのでしょうか?

Aベストアンサー

#include <stdio.h>


char buf[5];
int no;

no = 10;
sprintf(buf, "%d", no);

QC言語における再帰呼び出しの限界?について

お世話になります、AEと申します。
次のような件に悩まされています。

○画像のラベリング処理において、再帰呼び出しによって塗りつぶし処理を行っているのですが、再帰の回数が多くなると途中でメモリリークによるものと思われるエラーが発生し処理が中断してしまいます。
#ただし、物理メモリを全部使い果たした様子はありません。

ソースコードやエラーメッセージを添付できず、漠然とした質問で大変心苦しいのですが、一般論として、

○Windows上で開発したプログラムにおいては、再帰の回数(あるいは再帰呼び出しのために確保されるメモリ量)は有限なのでしょうか?また有限であったとしてそれを拡張する設定があるのでしょうか?

ということについてご意見などいただければと思います。

****
無論、プログラム自体の不具合によってメモリリークを引き起こしているんじゃないの?とか、そもそもメモリが足りてないんじゃないの?というご意見もあるかと思いますが、それは取り敢えずおいておいて、一般的な意見として、「メモリの許す限り何回でもいけるぞ!」とか「同じような経験をしたぞ!」とかいう意見を伺えれば幸甚です。
合わせて解決策がもしあるものでしたらご意見ください。

一般的なUNIXではlimitでユーザが使えるメモリ量を設定できると思うのですが、そういう類の設定がWindowsにもあるぞ!というご意見などもお待ちしております。
勉強不足で申し訳なのですが、よろしくお願いいします。

お世話になります、AEと申します。
次のような件に悩まされています。

○画像のラベリング処理において、再帰呼び出しによって塗りつぶし処理を行っているのですが、再帰の回数が多くなると途中でメモリリークによるものと思われるエラーが発生し処理が中断してしまいます。
#ただし、物理メモリを全部使い果たした様子はありません。

ソースコードやエラーメッセージを添付できず、漠然とした質問で大変心苦しいのですが、一般論として、

○Windows上で開発したプログラムにおいては、再帰の回数(あ...続きを読む

Aベストアンサー

再帰の回数は有限です。というより、再帰のために使えるメモリの量が有限です。

数年前ためしたところでは、単純な級数の再帰で、
1万回程度の再帰呼び出しが限界でした。

この現象は、C言語のプログラムが使うメモリが、いくつかに
分かれていることに原因があります。
(メモリとしては同じなのですが、使われ方が違うのです。)
だいたい、4種類になります。

(1)コード領域(プログラムを記憶しておく)
(2)静的記憶領域(即値データを記憶しておく)
(3)スタック領域
(4)ヒープ領域

関数の再帰呼び出しのとき使うメモリは、(3)の「スタック領域」です。
一方、malloc()などで確保できるメモリは、(4)の「ヒープ領域」です。

一般的に、ヒープ領域の方がはるかに多くのメモリを確保できます。
スタック領域に使えるメモリは、それほど多くはありません。
そのかわり、関数呼び出しなどに使いやすい構造になっています。
スタックのメモリは、あくまでも「一時置き」と考えられています。
(これでもずいぶん多くなったのです。
MS-DOSの時代は、ちょっと深い再帰呼び出しをすると
すぐにスタックメモリが足りなくなりました)

スタックの量を増やすコンパイルオプションは、
コンパイラによって存在したと思いますが、
すみませんが覚えていません。
極端に増やすことはできないと思います。
どのみち限界があるので、
あまり深い再帰呼び出しはしない方がいいです。
(環境によって、どの程度なら大丈夫というのはありますが)

実用プログラムであれば、面倒でも、再帰を使わない構造に書き直す方がいいのではないでしょうか。

再帰の回数は有限です。というより、再帰のために使えるメモリの量が有限です。

数年前ためしたところでは、単純な級数の再帰で、
1万回程度の再帰呼び出しが限界でした。

この現象は、C言語のプログラムが使うメモリが、いくつかに
分かれていることに原因があります。
(メモリとしては同じなのですが、使われ方が違うのです。)
だいたい、4種類になります。

(1)コード領域(プログラムを記憶しておく)
(2)静的記憶領域(即値データを記憶しておく)
(3)スタック領域
(4)ヒープ領域

関数の再帰呼...続きを読む

Qマージソートの計算量について-O(n*logn)

マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が1になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト?が*nなのでしょうか。
またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。

Aベストアンサー

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、
たとえば、16の要素をマージソートする場合を例にあげると、

・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。

・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるので、比較回数は12回。

・要素数が4の部分列を要素数が8の部分列に統合する時の比較回数は7回です。要素数が8の部分列は全部で2個あるので、比較回数は14回。

・要素数が8の部分列を要素数が16の列に統合する時の比較回数は15回です。要素数が16の列は全部で1個あるので、比較回数は15回。

以上合計すると、比較回数8+12+14+15=49回で64要素のマージソートができるわけです。

この「比較回数」を「要素数n」の式で表現するわけですが、
個々の部分列の統合時の比較回数は、要素数n、分割数kとすると、n-k回になりますから、n=2^x (x = log n) とすると、
総比較回数=Σ(k=0~x-1) (n-2^k) = n x - n + 1 = n log n - n + 1
になります。

計算量(オーダー)の議論では、次数の低い項は無視しますから、
O(n log n - n + 1) = O(n log n) になります。

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合する...続きを読む

Q法(mod)の四則演算について

とても困ってます。
情報セキュリティの課題で

・整数は素数を法とする演算では、四則演算が実行できる。その例を示せ。
・整数は合成数を法とする演算では、四則演算の一部で、解が一意に定まる場合と定まらない場合がある。その例を示せ。

この2つの問題が分かりません。
答えを教えていただけませんか?お願いします。

Aベストアンサー

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) - (5 mod 7) = 1 mod 7 = 1 … (1)
また、(13 - 5) mod 7 = 8 mod 7 = 1 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) - (5 mod 7) = (13 - 5) mod 7

3. 乗算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) × (5 mod 7) = 30 mod 7 = 2 … (1)
また、(13 × 5) mod 7 = 65 mod 7 = 2 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) × (5 mod 7) = (13 × 5) mod 7

4. 除算
剰余の除算は整数や実数といった一般的な数値の除算と異なるので注意して下さい。
剰余での除算は「逆数を掛ける」ことで定義されます。「aをbで割る」はa×b^-1で表されます。

(3 mod 7) × (5 mod 7) = 1なので、(5 mod 7)^-1 = (3 mod 7)
また、3.乗算の結果から、(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1が言える。これを計算すると、
(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1 = (13 mod 7) × (3 mod 7) = 4


・法が合成数の場合
良い例かどうかは分かりませんが…。
法が8のときの除算を例に挙げてみます。

例えば、(5 mod 8) × (3 mod 8)^-1は(3 mod 8) × (3 mod 8) = 1だから、
(5 mod 8) × (3 mod 8)^-1 = (5 mod 8) × (3 mod 8) = 7のように計算できます。
しかし、(5 mod 8) × (4 mod 8)^-1は、4 mod 8の逆数を求めることができないため計算できません。

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7...続きを読む


人気Q&Aランキング