• ベストアンサー

このアルゴリズムは分かりますか?

sgwjnの回答

  • sgwjn
  • ベストアンサー率70% (47/67)
回答No.5

以前、私が同じようなプログラムを作った際に考えたアルゴリズムをこの問題に適用すると、 ※初めの4点を置くまで (1)原点を置く (2)取りうる座標の候補リスト(リスト1)を作成(原点周りの4点) (3)リスト1からランダムに1つ選択し、点を置く (4)リスト1を破棄し、次に取りうる座標の候補リスト(リスト2)を作成(原点と(3)でおいた点の周辺4点) (5)リスト2からランダムに1つ選択し、点を置く (6)リスト2を破棄し、次点を置く((5)をおいた時点で一意に決まるはず) ※以降の点を置く (7)取りうる座標の候補リスト(リスト3)を作成(周りの8点) (8)リスト3からランダムに1つ選択し、点を置く (9)リスト3からおいた点の座標を削除 (10)リスト3の候補が無くなるまで(8)、(9)を繰り返す (11)リスト3を破棄 (12)取りうる座標の候補リスト(リスト4)を作成(周りの4点) …以降同様の手順を繰り返す 取りうる座標の候補は、その時点の点の置き方で判るはずです。 データ構造は、X座標、Y座標を別の1次元配列で保持し、インデックスをランダムに選択すれば良いかと思います。 x = [0, 0, 1, 1] y = [0, 1, 0, 1]    ↑ ↑ ↑ ↑ インデックスをランダムに選択 学生の頃に考えたアルゴリズムですので、効率はあまり考慮していません。よろしければ参考まで。

takagoo100
質問者

お礼

ご返答ありがとうございます。 あまり理解できないのですが、 >取りうる座標の候補リスト(リスト3)を作成(周りの8点) とあるのですが、具体的にプログラムではどのように書けば良いのでしょうか? 始めの8点ぐらいまでなら頭の中で考えてリストを用意すればいいのでしょうが、、、増えてきますし、、 つまり仰っているのは決まった形のプログラムだと思いますが、それが分からないです。

関連するQ&A

  • コイン投げによる座標移動による確率

    座標平面上で原点から出発する点Pが次の規則に従って動きます。 コインを投げて表だったら点Pは右へ1、上へ1移動。 コインを投げて裏だったら点Pは右へ1、下へ1移動。 このとき、7回投げたとき、点Pが(3,1)を通らないで(7,3)へ移動する確率は?また、7回投げたとき、y座標が7回とも正となる確率を知りたいのです。 座標軸に手で何回も線を引いて数えることで求めることは出来たのですが、もっと数学的に求める方法が思いつきません。よろしくお願いします。

  • 2つの円が衝突しない距離 の早い求め方

    平面状の2つの円 点1[座標x1, y1 半径r1]   と  点2[座標x2, y2 半径r2] が接触しているかを (r1+r2)*(r1+r2) 左が右 (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) より大きいか否かで、衝突を判定できると学びました。 そして接触時に『2つの円が衝突しない距離(点2を動かす距離)』 を求めたいのですが、 今は角度を求める為にルートとアークコサインを使い(電卓) r1とr2の和を斜辺にして三角関数で求めていて時間がかかります。 これを何かもっと簡単に求める方法は無いものでしょうか・・?

  • 確率は座標系に依存?

    「xy座標系で x^2+y^2 = 4の円の中にランダムに点を配置する。このとき点が、単位円x^2+y^2 = 1の中にある確率を求めよ。」という問題があったとします。 単純に考えれば二つの円の面積比をとってP=1/4となるのが自然だと思うのですが、(x,y)=(rcosθ,rsinθ)としてrθ座標系に直してみると面積の比はP=(1*2π)/(2*2π)=1/2となりますよね。 座標系を変換しているのだから面積が変わるのは当然だとも思うのですが、(x,y)と(r,θ)は一対一に対応しているのに確率まで変わってしまうのがどうにも腑に落ちません。確率を計算する際にどうしてrθ座標系に変換すると間違いになるのか、どなたか教えてください。 ちなみにルイスキャロルの枕頭問題集に出ている「平面上にランダムにとった異なる三点が鈍角三角形を作る確率を計算せよ。」という問題を考えているときに、これと似たような問題にぶち当たったので質問させていただきました。

  • 数学IIIの問題

    2次曲線に関する問題です 解説もお願いします 1. 次の双曲線の焦点の座標と漸近線の方程式、とその概形を教えてください (1) (x^2/4) - (y^2/9) =1   (2) (x^2/4) - (y^2/9) = -1 2. 円 x^2 + y^2 =9 を媒介変数θを用いて表したもの 3. 楕円 (x^2/9) + (y^2/16) =1 を媒介変数θを用いて表したもの 4. 次の極座標で表される点の直交座標 (1) (2, Π/3)   (2) (1, -5Π/4) 5. 直交座標が次のような点の極座標 r>0 , 0≦θ<2Π (1) (√3, 1)    (2) (-2, 2)

  • 分かりません

    座標平面上の点であって、x座標,y座標とも整数であるものを格子点と呼ぶ。0以上の整数nに対して|x|+|y|≦nを満たす格子点(x,y )の個数をAnと置く。更にBn=ΣAk(Σの上にn、下にk=0って書いてある)と置く。次を求めよ。 問1、An 問2、Bn 問3、lim n →∞ nの3乗分のBn よろしくお願いします。 

  • 高校数学II 三角関数のすごく初歩的な質問です

    先週ころから数2で三角関数に入ったのですが、いきなり躓いてしまいました。元々文系で数学が とても苦手で問題もじっくり考えてやっとわかるくらいなんですが、今回のは全然わかりません。 これさえわかればあとは教科書なり問題集なりに解法がくわしく記載されてるのでなんとかなると思います。僕が躓いているところは基本中の基本で詳しく書く必要がないのか、何も書かれていません。とても恥ずかしいのですが、わからないところがあるので教えてください。お願いします。 前置き長くなってすいません 例3 3分の4πの正弦、余弦、正接 右の図で(図は省略)、円の半径がr=2のとき、点P(角θの動径と原点を中心とする半径r の円との交点Pの座標をx、yとする)の座標は(-1、-√3)である・・・以後省略 ※点pのあとの()は問題にはありませんが補足です。わかりにくかったらすいません ここの 「円の半径がr=2のとき、点Pの座標は(-1、-√3)」の部分がわかりません。 どうやって座標を出すのでしょうか?教えてください。お願いします。

  • 三角関数の計算について教えて下さい

    PLCのプログラムを作っているのですが、三角関数(?)の部分で 完全に躓いてしまいました。どうか教えて頂けないでしょうか? 点A(0.0)と点B(任意点X.Y)を直線で結びんで、その直径で円を描いて (点AとBを直径とする円です)直線の中間点より垂直に円と交差する場所まで 線を一本(座標は正数エリアのみ)描いた時、円と交差する垂直線の点の座標を 求める式を考えています。 (情報がなにか足りない場合は仰って頂けると有難いです。) 三角関数が自分ではサッパリ分からない為、どなたかご教授頂けると幸いです。 よろしくお願いします。

  • 数学でわからない問題があります

    数学でわからない問題があります 関数y=2分の1Xの二乗が1次関数y=2分の1X+3と点A,Bの 2点で交わっている。この時次の問題に答えなさい (1) 点A,Bの座標を求めなさい (2)三角OABの面積を求めなさい という問題です わかりやすくお願いします 中学レベルでお願いします

  • 一次関数の応用問題の解き方がわかりません…

    弟の数学の宿題を手伝っているのですが、どうやって答えを導いたらよいか非常に苦戦しています。ちなみに「一次関数」の応用問題です。答えの導き方がわかる方、どうか助けてください! お願いします!! 上図のように、x座標とy座標がともに整数である25個の点に、黒と白のしるしをつけ、これらの点をそれぞれ黒点、白点とよぶことにする。いま黒点P(a,b)からbだけ右に進み、aだけ下に進んだ点をQとし、2点P、Qを通る直線PQをひくものとする。次の問いに答えなさい。 (問)ある黒点Pをもとにしてひいた直線PQ上に、白点(1,5)がある。この黒点Pの座標を求めよ。 答えはP(3,2)だそうです。 どうやって答えを導いたらよいか教えていただけたら嬉しいです。

  • 一次関数の応用問題の解き方がわかりません…

    弟の数学の宿題を手伝っているのですが、どうやって答えを導いたらよいか非常に苦戦しています。ちなみに「一次関数」の応用問題です。答えの導き方がわかる方、どうか助けてください! お願いします!! 上図のように、x座標とy座標がともに整数である25個の点に、黒と白のしるしをつけ、これらの点をそれぞれ黒点、白点とよぶことにする。いま黒点P(a,b)からbだけ右に進み、aだけ下に進んだ点をQとし、2点P、Qを通る直線PQをひくものとする。次の問いに答えなさい。 (問)ある黒点Pをもとにしてひいた直線PQ上に、白点(1,5)がある。この黒点Pの座標を求めよ。 答えはP(3,2)だそうです。 どうやって答えを導いたらよいか教えていただけたら嬉しいです。