- ベストアンサー
アルゴリズムに関する問題が解けません
現在幾何アルゴリズムの勉強をしているのですが、ある問題が解けなくて困っています。だれか分かる人がいたら教えてください。 直交多角形を監視するのに[n/4]人の警備員が必要である例を一つ挙げよ。
- rict-mict
- お礼率86% (123/143)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数5
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
まずはこの論文を読んでみてはいかがでしょうか？ http://repository.lib.gifu-u.ac.jp/bitstream/123456789/1832/1/510111.pdf あと「アートギャラリ監視問題」でググってみるのもおすすめします。
その他の回答 (1)
関連するQ&A
- アルゴリズム
アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。 (1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。 解) n=100*2 =200 (2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。 解) 求める問題の大きさをxとおくと n=(100^2)*100 =10000*100 =1000000 (3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。 解) 2^40=(2^20)*(2^20) =1*(2^20) =2^20[時間]
- ベストアンサー
- その他（プログラミング・開発）
- アルゴリズム系の問題知りませんか？
再来週大学院試験を控えている者です。 入試の項目に「プログラミング(アルゴリズム)」と書いてあり、ある程度複雑なアルゴリズムを考えるような問題が出る事が予想されます。 きっと二分探索木やクイックソートのような問題が出るように思います。 アルゴリズムを考えるような問題としていい問題ご存じないでしょうか？ アルゴリズムを考えるような問題としてはハノイの塔とかよいように思いますが ちょっと入試の問題としては出ないような気がします。 自分では他に線形リストやスタックなども勉強したんですが、 C,JAVA,Pascal,フォートランなどどの言語で回答してもよい事になっているので言語に限定した問題は出ないように思います。 90分で解く３問あるうちのプログラムは１つですから30分以内に解けるような問題のはずです。 (出題される可能性も考えていただければ幸いです)よい問題をご存知でしたら教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- C++でのアルゴリズム
次の条件を満たすアルゴリズムをC++のコードで教えてください！ 大きさ2×1の長方形n個を 縦2 横n の長方形になるように並べるときの並べ方の総数を求めるアルゴリズム 入力nは、１以上の整数が入力される前提でよい。 例として、 n=1 1通り n=2 2通り n=3 3通り n=5 8通り n=7 21通り となります お願いします。
- ベストアンサー
- C・C++・C#
- 組み合わせ問題のアルゴリズム
あらかじめ用意された整数を足して、その合計がある指定された整数と等しくなる組み合わせの数を調べるプログラムを書こうとしているのですが、苦労しています。 具体例がないと伝わりにくいかもしれないので例をあげると、 例えばあらかじめ用意された整数というのが 1・1・2・2・5・8 の4つで、 指定された整数が10である場合は、 8と2 8と1と1 5と2と2と1 という3通りの組み合わせがあるので、3を出力したいというわけです。 今まではもっと単純なアルゴリズムしか考えてこなかったので、こういった組み合わせのような問題が難しく感じられます。 こういう場合、アルゴリズムはどのようなものが考えられるでしょうか。 よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- Nクイーン問題のアルゴリズムについて
Nクイーン問題のアルゴリズムについて http://www.itmedia.co.jp/news/articles/0410/06/news079.html ↑このニュースにあるようなNクイーン問題の総数を求めるアルゴリズムは、どんな手法を使っているんでしょうか。 調べたところ、組み合わせ問題には「バックトラック法」が有効と出てきたのですが、世界記録を樹立したプログラムもそれを用いているんでしょうか。 ちなみにプログラムは以下のサイトからゲット出来ます。 http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm 私にはさっぱりなので、どなたかわかる方ご教授ください。
- ベストアンサー
- その他（プログラミング・開発）
- アルゴリズム フェルナンデスとは？
こんにちは。 Nクイーン問題探索アルゴリズムは、 チェスのような基盤にクイーンを取られないように 何個配置できるかという問題だと思います。 同じようなものだと思うのですが、 アルゴリズム フェルナンデス、Fernandes問題 もしくはフェルナンデスの法則や定理を聞いたことがありますか？ 知っていたら教えてください。 よろしくお願いします。 以上
- ベストアンサー
- その他（プログラミング・開発）
- ソフトウェア開発技術者試験のアルゴリズム問題
ソフトウェア開発技術者試験のアルゴリズム問題は どうしたらできるようになりますか。 いろいろと検索していると、対策としては過去問題を 解くこととありますが、それ以外はありますか？ 現在アルゴリズム勉強用の本を購入して、 勉強はしていますが、まったくできるようになっている 気がしません。 これは費やす時間が足りないからでしょうか。 ある一定量をこなせば、自然とできるものなのでしょうか。
- ベストアンサー
- 情報処理技術者
- アルゴリズムを勉強していたのですが、線形探索をする
アルゴリズムを勉強していたのですが、線形探索をする時にデータ件数がNの時平均比較回数が(N+1)÷2回となっていたのですが、なぜ+1をしているのでしょうか？普通にN÷2ではダメなんでしょうか 解説お願いします
- 締切済み
- C・C++・C#
お礼
有難うございました。非常によく分かりました。