この問題は対称性を利用することによってかなり簡単にできます。 まず第一に、y 軸を全く無視できることは少し考えれば明白です。 任意の x 成分を選んでマッチ棒の一端とし、任意の方向 @c{$\theta$} θを選んで、そして x と @c{$x + \cos \theta$} x + cos(θ) (これはマッチ棒のもう一方の端の x 座標です) が縦線をまたぐかどうかを調べれば良いのです。 各縦線は整数の座標値を取るので、 この2つの値が整数を囲むとき「交差」は起こります。
マッチ棒の両端は同等なので、左側を x としてもかまいません。 この場合 θ は右側を指す角度であって、-90 から 90 の範囲です。 (ラジアンを使うこともできましたが、 @c{$\pi$} pi を推定するときに @c{$\pi/2$} pi/2 ラジアンを参照したら、カンニングしたような気がするでしょう!)
縦線の平面は無限に広いので、マッチ棒の左端の両側の縦線に座標 0 と 1 を 選ぶことができます。 マッチ棒が縦線と交差しなければ右端は 0 と 1 の間にあり、 交差していれば 1 と 2 の間にあります。 従って、任意の x と @c{$\theta$} θ を選び、@c{$x + \cos \theta$} x + cos(θ) を計算して、 結果のいくつが 1 を越えるか数えれば良いのです。簡単でしょ!
v . と t . コマンドを使うと、ちょっと速く実行できます。
1: [0.52, 0.71, ..., 0.72] 2: [0.52, 0.71, ..., 0.72]
. 1: [78.4, 64.5, ..., -42.9]
.
v . t . 1. v b 100 RET V M k r 180. v b 100 RET V M k r 90 -
(次の段階は、コンピューターのスピードによっては少し遅いかもしれません。)
2: [0.52, 0.71, ..., 0.72] 1: [0.72, 1.14, ..., 1.45]
1: [0.20, 0.43, ..., 0.73] .
.
m d V M C +
1: [0, 1, ..., 1] 1: 0.64 1: 3.125
. . .
1 V M a > V R + 100 / 2 TAB /
第3の方法も試してみましょう。100万までの乱数整数を使います。 k r コマンドに整数引数をつけると乱数整数をひとつ発生します。
2: [1000000, 1000000, ..., 1000000] 2: [78489, 527587, ..., 814975]
1: [1000000, 1000000, ..., 1000000] 1: [324014, 358783, ..., 955450]
. .
1000000 v b 100 RET RET V M k r TAB V M k r
1: [1, 1, ..., 25] 1: [1, 1, ..., 0] 1: 0.56
. . .
V M k g 1 V M a = V R + 100 /
1: 10.714 1: 3.273
. .
6 TAB / Q
GCD 関数のこの性質の証明は、Knuth のArt of Computer Programming, 第2巻, 4.5.2節の練習問題 10 を参照してください。
先ほど v . や t . をタイプしたのなら、 もう一度それらをタイプしてフルサイズ表示に戻してください。
Go to the first, previous, next, last section, table of contents.
利用度数