teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

5

別解3を追加

2017/02/04 13:06

投稿

raccy
raccy

スコア21768

answer CHANGED
@@ -103,3 +103,17 @@
103
103
  ```JavaScript
104
104
  let val = (n => y => (x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2))(Math.floor(2 * n * y)))(3)(Math.random());
105
105
  ```
106
+
107
+ ---
108
+ 【別解3】
109
+ -1は奇数乗か偶数乗かだけで切り替わることに気付いた。
110
+
111
+ ```JavaScript
112
+ let val = (x => ((-1)**x * ((x - x % 2) / 2 + 1)))(Math.floor(6 * Math.random()));
113
+ ```
114
+
115
+ IE等の古いブラウザ用に書き直すと
116
+
117
+ ```JavaScript
118
+ var val = function (x) {return Math.pow(-1, x) * ((x - x % 2) / 2 + 1);}(Math.floor(6 * Math.random()));
119
+ ```

4

説明がちょっとおかしかったのを修正

2017/02/04 13:06

投稿

raccy
raccy

スコア21768

answer CHANGED
@@ -94,7 +94,7 @@
94
94
  // 固定の所は評価をしてしまって。qもなくす。
95
95
  const f = x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2);
96
96
  ```
97
- これに最初の2nを掛けて床関数をとって2足すをMath.random()にしたものを与えるようる。
97
+ これに最初の2nを掛けて床関数で整数化したものを与えると[0,1)を均等配分できる。
98
98
  ```JavaScript
99
99
  const f_ = n => y => (x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2))(Math.floor(2 * n * y));
100
100
  ```

3

別解2が整数の最大値を超える場合がるため、修正。

2017/02/04 12:52

投稿

raccy
raccy

スコア21768

answer CHANGED
@@ -1,6 +1,6 @@
1
1
  【条件】
2
2
  1. 乱数生成は1度のみ行う。
3
- 2. 任意の整数`n`に対して、`-n`, `-n+1`, ... `-2`, `-1`, `1`, `2`, ... `n-1`, `n`の計n*2個の整数の内一つを返す。ランダム性は1.で生成した乱数を用いること。ただし、`n`は`1`以上`2**52-1`以下とする。(`2**52`以上の場合は`2*n`が`Number.MAX_SEFE_INTEGER`を越えるため)
3
+ 2. 任意の整数`n`に対して、`-n`, `-n+1`, ... `-2`, `-1`, `1`, `2`, ... `n-1`, `n`の計n*2個の整数の内一つを返す。ランダム性は1.で生成した乱数を用いること。ただし、`n`は`1`以上`2**52-1`以下とする。(`2**52`以上の場合は`2*n`が`Number.MAX_SAFE_INTEGER`を越えるため)
4
4
 
5
5
  【考察】
6
6
  `Math.random()` [0,1)の乱数
@@ -58,22 +58,24 @@
58
58
 
59
59
  ---
60
60
  【別解2】
61
+ ※ 途中の演算で`Math.MAX_SAFE_INTEGER`を越える場合があるため修正。
62
+
61
63
  Math.floorを一回だけにする方法を考える。他にも演算はなるべく1回とする。
62
64
 
63
- 2n倍したものにfloorをとり、2を足せば2, 3, ... 2n, 2n+1になる。
65
+ 2n倍したものにfloorをとると0, 1, ... 2n-2, 2n-1になる。
64
66
  これを2を除数とした商と剰余を考えると、下記になる。
65
- 商: 1, 1, 2, 2, ... 2n-1, 2n-1, 2n, 2n
67
+ 商: 0, 0, 1, 1, ... 2n-2, 2n-2, 2n-1, 2n-1
66
68
  剰余: 0, 1, 0, 1, ... 0, 1, 0, 1
67
69
  つまり、剰余部分は-1を底にしてその値を冪指数にした冪を求めれば
68
70
  剰余: 0, 1, 0, 1, ... 0, 1, 0, 1 => 1, -1, 1, -1 ... 1, -1, 1, -1
69
- が得られるため、後は商と掛ければ、
71
+ が得られるため、後は商に1足した物と掛ければ、
70
72
  1, -1, 2, -2, ... 2n-1, -2n+1, 2n, -2n
71
73
  が得られる。
72
74
 
73
75
  JavaScriptにすると次のような関数になる。
74
76
  ```JavaScript
75
77
  // q 商、r 剰余
76
- const g = r => q => (-1)**r * q;
78
+ const g = r => q => (-1)**r * (q + 1);
77
79
  ```
78
80
  JavaScriptには商を直接求める演算子や関数がないため剰余から求める関数を考える。
79
81
  ```JavaScript
@@ -86,18 +88,18 @@
86
88
  // `x % 2`は冗長のためさらに書き替える。
87
89
  const f = x => (r => g(r)(h(x)(2)(r)))(x % 2);
88
90
  // 関数を展開する。
89
- const f = x => (r_ => (r => q => (-1)**r * q)(r)((d => m => r => (d - r) / m)(x)(2)(r_)))(x % 2);
91
+ const f = x => (r_ => (r => q => (-1)**r * (q + 1))(r)((d => m => r => (d - r) / m)(x)(2)(r_)))(x % 2);
90
92
  // rはr_と同じ、xとdは同じであり、mは2固定で冗長のためまとめる。
91
- const f = x => (r => (q => (-1)**r * q)((m => (x - r) / 2)()))(x % 2);
93
+ const f = x => (r => (q => (-1)**r * (q + 1))((m => (x - r) / 2)()))(x % 2);
92
94
  // 固定の所は評価をしてしまって。qもなくす。
93
- const f = x => (r => (x - r) / 2 * (-1)**r)(x % 2);
95
+ const f = x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2);
94
96
  ```
95
97
  これに最初の2nを掛けて床関数をとって2足すをMath.random()にしたものを与えるようにする。
96
98
  ```JavaScript
97
- const f_ = n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2);
99
+ const f_ = n => y => (x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2))(Math.floor(2 * n * y));
98
100
  ```
99
101
 
100
102
  n=3のときのため、最終的に次のようになる。
101
103
  ```JavaScript
102
- let val = (n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2))(3)(Math.random());
104
+ let val = (n => y => (x => (r => ((-1)**r * ((x - r) / 2 + 1)))(x % 2))(Math.floor(2 * n * y)))(3)(Math.random());
103
105
  ```

2

別解2を追加

2017/02/04 04:37

投稿

raccy
raccy

スコア21768

answer CHANGED
@@ -54,4 +54,50 @@
54
54
  ```JavaScript
55
55
  let v = (n => x => (-1)**Math.floor(2 * x) * (Math.floor(2 * n * x) % n + 1))(3)(Math.random());
56
56
  ```
57
- となる。
57
+ となる。
58
+
59
+ ---
60
+ 【別解2】
61
+ Math.floorを一回だけにする方法を考える。他にも演算はなるべく1回とする。
62
+
63
+ 2n倍したものにfloorをとり、2を足せば2, 3, ... 2n, 2n+1になる。
64
+ これを2を除数とした商と剰余を考えると、下記になる。
65
+ 商: 1, 1, 2, 2, ... 2n-1, 2n-1, 2n, 2n
66
+ 剰余: 0, 1, 0, 1, ... 0, 1, 0, 1
67
+ つまり、剰余部分は-1を底にしてその値を冪指数にした冪を求めれば
68
+ 剰余: 0, 1, 0, 1, ... 0, 1, 0, 1 => 1, -1, 1, -1 ... 1, -1, 1, -1
69
+ が得られるため、後は商と掛ければ、
70
+ 1, -1, 2, -2, ... 2n-1, -2n+1, 2n, -2n
71
+ が得られる。
72
+
73
+ JavaScriptにすると次のような関数になる。
74
+ ```JavaScript
75
+ // q 商、r 剰余
76
+ const g = r => q => (-1)**r * q;
77
+ ```
78
+ JavaScriptには商を直接求める演算子や関数がないため剰余から求める関数を考える。
79
+ ```JavaScript
80
+ // d 被除数、m 除数
81
+ const h = d => m => r => (d - r) / m;
82
+ ```
83
+ 除数は2で固定であるため、これを用いると次のようになり、展開しながら変形していく。
84
+ ```JavaScript
85
+ const f = x => g(x % 2)(h(x)(2)(x % 2));
86
+ // `x % 2`は冗長のためさらに書き替える。
87
+ const f = x => (r => g(r)(h(x)(2)(r)))(x % 2);
88
+ // 関数を展開する。
89
+ const f = x => (r_ => (r => q => (-1)**r * q)(r)((d => m => r => (d - r) / m)(x)(2)(r_)))(x % 2);
90
+ // rはr_と同じ、xとdは同じであり、mは2固定で冗長のためまとめる。
91
+ const f = x => (r => (q => (-1)**r * q)((m => (x - r) / 2)()))(x % 2);
92
+ // 固定の所は評価をしてしまって。qもなくす。
93
+ const f = x => (r => (x - r) / 2 * (-1)**r)(x % 2);
94
+ ```
95
+ これに最初の2nを掛けて床関数をとって2足すをMath.random()にしたものを与えるようにする。
96
+ ```JavaScript
97
+ const f_ = n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2);
98
+ ```
99
+
100
+ n=3のときのため、最終的に次のようになる。
101
+ ```JavaScript
102
+ let val = (n => y => (x => (r => (x - r) / 2 * (-1)**r)(x % 2))(Math.floor(2 * n * y) + 2))(3)(Math.random());
103
+ ```

1

別解を追加

2017/02/04 00:01

投稿

raccy
raccy

スコア21768

answer CHANGED
@@ -27,4 +27,31 @@
27
27
  let v = (x => Math.floor(6 * x) + 1 - 7 * Math.floor(2 * x))(Math.random());
28
28
  ```
29
29
 
30
- 数学っぽく考えたつもりですが、`Math.random()`がまったく数学っぽくない時点でなんとも言えないです。
30
+ 数学っぽく考えたつもりですが、`Math.random()`に副作用あるのでまったく数学っぽくない時点でなんとも言えないです。
31
+
32
+ ---
33
+
34
+ 【別解】
35
+ [0,1) => -n, -n+1, ... -2, -1, 1, 2, ... n-1, n
36
+ となる写像関数を直接考える。
37
+
38
+ 1. 2倍すれば[0,2)となるため、[0,1), [1,2)に分離でき、floorをとれば0, 1になる。
39
+ 2. -1を底、1.の値を冪指数とする冪を求めると、1, -1になる。
40
+ 3. 2n倍すれば[0,2n)となるため、[0,1), [1,2), ... [n-1, n), [n, n+1), ... [2n-2,2n-1), [2n-1,2n)に分離でき、floorをとれば0, 1, ... n-1, n, ... 2n-2, 2n-1となる。
41
+ このうちの前半は1.の0(2.の1)に、後半は1.の1(2.の-1)に相当する。
42
+ 4. さらにnでの余りを求めると0, 1, ... n-1, 0, ... n-2, n-1と前半と後半が同じである。
43
+ 5. さらに1足せば1, 2, ... n, 1, ... n-1, nとなる。
44
+ 6. 2.と5.を組み合わせれば、目的の写像が得られる。
45
+ f(n)(x) = (-1)^[2x]*([2nx]%n+1)
46
+ ※ fはカリー化されている。^ ... 冪乗。[z] ... ガウス記号、床関数。% ... 剰余。
47
+
48
+ これをJavaScriptで表すと下記になる。
49
+ ```JavaScript
50
+ const f = n => x => (-1)**Math.floor(2 * x) * (Math.floor(2 * n * x) % n + 1)
51
+ ```
52
+
53
+ 写像関数が得られたので、n=3の時にxが[0,1)分布の乱数を与えることで答えは
54
+ ```JavaScript
55
+ let v = (n => x => (-1)**Math.floor(2 * x) * (Math.floor(2 * n * x) % n + 1))(3)(Math.random());
56
+ ```
57
+ となる。