teratail
回答率
85.35%
teratail header banner
teratail header banner
質問するログイン新規登録
トップアルゴリズムに関する質問整数を対称行列のindexと対応付ける方法

編集履歴

回答編集履歴

12

テキスト修正

2020/09/26 07:00

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -104,7 +104,7 @@
104
104
 
105
105
 
106
106
 
107
- に回答します。以下の手順でその式を導いています。
107
+ に回答します。
108
108
 
109
109
 
110
110
 

11

テキスト修正

2020/09/26 07:00

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -168,7 +168,7 @@
168
168
 
169
169
  ```
170
170
 
171
- が得られました。これを満たす、最大の非負整数 `i` を求めればよいので、 `i` を求める式をPythonで書くと
171
+ が得られました。これを満たす最大の非負整数が求めたい`i`になります。それは、右辺の値の小数部分を切り捨てれば得られますので、`i` を求める式をPythonで書くと
172
172
 
173
173
  ```python
174
174
 

10

テキスト修正

2020/09/26 06:32

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -108,19 +108,31 @@
108
108
 
109
109
 
110
110
 
111
- `i` （≧0）行目の先頭（0列目)の要素は、`i * (i+1) / 2` です。たとえば、 i = 3 の行では、先頭要素は、`3 * (3 + 1) / 2` から得られる `6`です。これを使うと、与えられた `ele` が配置される行インデクス`i` は、以下を満たす最大の非負整数です。
111
+ なお、以下の説明で、プログラムのコードではなく数式の中では、乗算記号を省略します。また、`i^2` は `i` の二乗を表すものとします。
112
+
113
+
114
+
115
+ まず、`i` （≧0）行目の先頭（0列目)の要素は、
112
116
 
113
117
  ```
114
118
 
115
- i * (i+1) / 2 ≦ ele
119
+ i (i+1) / 2
116
120
 
117
121
  ```
118
122
 
119
- 上記の不等式を変形して、左辺が `i` になるようにします。まず、両辺を２倍し、左辺のカッコを展開します。（以下で、`i^2` は `i` の二乗を表すとします）
123
+ です。たとえば、 i = 3 の行の先頭要素は、上記の式の`i`に3を代入した `3 (3 + 1) / 2` から得られる `6`です。上記の先頭要素の式を使うと、与えられた `ele` が配置される行インデクス`i` は、以下の不等式
120
124
 
121
125
  ```
122
126
 
127
+ i (i+1) / 2 ≦ ele
128
+
129
+ ```
130
+
131
+ を満たす最大の非負整数です。この不等式を変形して、左辺が `i` になるようにしていきます。まず、両辺を２倍し、左辺のカッコを展開します。
132
+
133
+ ```
134
+
123
- i^2 + i ≦ 2 * ele
135
+ i^2 + i ≦ 2ele
124
136
 
125
137
  ```
126
138
 
@@ -128,7 +140,7 @@
128
140
 
129
141
  ```
130
142
 
131
- i^2 + i + 0.25 ≦ 2 * ele + 0.25
143
+ i^2 + i + 0.25 ≦ 2ele + 0.25
132
144
 
133
145
  ```
134
146
 
@@ -136,7 +148,7 @@
136
148
 
137
149
  ```
138
150
 
139
- (i + 0.5)^2 ≦ 2 * ele + 0.25
151
+ (i + 0.5)^2 ≦ 2ele + 0.25
140
152
 
141
153
  ```
142
154
 
@@ -144,7 +156,7 @@
144
156
 
145
157
  ```
146
158
 
147
- i + 0.5 ≦ √(2 * ele + 0.25) /* = 2*elm+0.25 の平方根 */
159
+ i + 0.5 ≦ √(2ele + 0.25)
148
160
 
149
161
  ```
150
162
 
@@ -152,7 +164,7 @@
152
164
 
153
165
  ```
154
166
 
155
- i ≦ √(2 * ele + 0.25) - 0.5
167
+ i ≦ √(2ele + 0.25) - 0.5
156
168
 
157
169
  ```
158
170
 
@@ -164,7 +176,7 @@
164
176
 
165
177
  ```
166
178
 
167
- となります。`i` が得られると、列インデクス`j` は、`ele` と 行の先頭要素`i * (i+1) / 2` との差なので
179
+ となります。`i` が得られると、列インデクス`j` は、`ele` と 行の先頭要素`i (i+1) / 2` との差なので
168
180
 
169
181
  ```python
170
182
 

9

テキスト修正

2020/09/26 06:24

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -104,15 +104,11 @@
104
104
 
105
105
 
106
106
 
107
- に回答します。以下のような考え方で、その式を導いています。
107
+ に回答します。以下の手順でその式を導いています。
108
108
 
109
109
 
110
110
 
111
- - `i` （≧0）行目の先頭（0列目)の要素は、`i * (i+1) / 2` です。たとえば、 i = 3 の行では、先頭要素は、`3 * (3 + 1) / 2` から得られる `6`です。
111
+ `i` （≧0）行目の先頭（0列目)の要素は、`i * (i+1) / 2` です。たとえば、 i = 3 の行では、先頭要素は、`3 * (3 + 1) / 2` から得られる `6`です。これを使うと、与えられた `ele` が配置される行インデクス`i` は、以下を満たす最大の非負整数です。
112
-
113
-
114
-
115
- - 上記を使うと、与えられた `ele` が配置される行のインデクス`i` は、以下を満たす最大の非負整数です。
116
112
 
117
113
  ```
118
114
 
@@ -120,7 +116,7 @@
120
116
 
121
117
  ```
122
118
 
123
- 上記の両辺を２倍し、左辺のカッコを展開します。（以下で、i^2 は i の二乗を表すとします）
119
+ 上記の不等式を変形して、左辺が `i` になるようにします。まず、両辺を２倍し、左辺のカッコを展開します。（以下で、`i^2` は `i` の二乗を表すとします）
124
120
 
125
121
  ```
126
122
 
@@ -128,7 +124,7 @@
128
124
 
129
125
  ```
130
126
 
131
- 両辺に0.25を加えます。
127
+ 両辺に `0.25` を加えて、
132
128
 
133
129
  ```
134
130
 
@@ -136,7 +132,7 @@
136
132
 
137
133
  ```
138
134
 
139
- 左辺を因数分解して
135
+ としておいて、左辺を因数分解すると
140
136
 
141
137
  ```
142
138
 
@@ -144,7 +140,7 @@
144
140
 
145
141
  ```
146
142
 
147
- となるので、両辺の平方根をとって、
143
+ となります。両辺の値は0より大きく、`i + 0.5`も0より大きいので、両辺の平方根をとると以下が得られます。
148
144
 
149
145
  ```
150
146
 
@@ -152,7 +148,7 @@
152
148
 
153
149
  ```
154
150
 
155
- より、
151
+ 左辺の `0.5` を右辺に移項すると、左辺が`i` の不等式
156
152
 
157
153
  ```
158
154
 
@@ -160,7 +156,7 @@
160
156
 
161
157
  ```
162
158
 
163
- を満たす、最大の非負整数 i を求めればよいことになります。この条件から i を求める式をPythonで書くと
159
+ が得られました。これを満たす、最大の非負整数 `i` を求めればよいので、 `i` を求める式をPythonで書くと
164
160
 
165
161
  ```python
166
162
 
@@ -168,7 +164,7 @@
168
164
 
169
165
  ```
170
166
 
171
- となります。i が得られると、j は、ele と 行の先頭要素`i * (i+1) / 2` との差なので
167
+ となります。`i` が得られると、列インデクス`j` は、`ele` と 行の先頭要素`i * (i+1) / 2` との差なので
172
168
 
173
169
  ```python
174
170
 

8

テキスト修正

2020/09/26 06:00

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -96,7 +96,15 @@
96
96
 
97
97
 
98
98
 
99
+ コメントからいただきました
100
+
101
+
102
+
103
+ > ただ，もしよろしければ，int( math.sqrt( 2ele+0.25 ) - 0.5 ) がどこからやってきたか教えてもらうことは可能でしょうか？
104
+
105
+
106
+
99
- 以下、アルゴリスムの考え方を示します。
107
+ に回答します。以下のような考え方で、その式を導いています。
100
108
 
101
109
 
102
110
 

7

テキスト修正

2020/09/25 10:48

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -100,9 +100,7 @@
100
100
 
101
101
 
102
102
 
103
- - `i` （≧0）行目の先頭（0列目)の要素は、`i * (i+1) / 2` です。たとえば、 i = 3 の行では、先頭要素は、
103
+ - `i` （≧0）行目の先頭（0列目)の要素は、`i * (i+1) / 2` です。たとえば、 i = 3 の行では、先頭要素は、`3 * (3 + 1) / 2` から得られる `6`です。
104
-
105
- `3 * (3 + 1) / 2` から得られる `6`です。
106
104
 
107
105
 
108
106
 

6

テキスト修正

2020/09/25 08:31

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -110,7 +110,7 @@
110
110
 
111
111
  ```
112
112
 
113
- i * (i+1) / 2 ≦ elm
113
+ i * (i+1) / 2 ≦ ele
114
114
 
115
115
  ```
116
116
 
@@ -118,7 +118,7 @@
118
118
 
119
119
  ```
120
120
 
121
- i^2 + i ≦ 2 * elm
121
+ i^2 + i ≦ 2 * ele
122
122
 
123
123
  ```
124
124
 
@@ -126,7 +126,7 @@
126
126
 
127
127
  ```
128
128
 
129
- i^2 + i + 0.25 ≦ 2 * elm + 0.25
129
+ i^2 + i + 0.25 ≦ 2 * ele + 0.25
130
130
 
131
131
  ```
132
132
 
@@ -134,7 +134,7 @@
134
134
 
135
135
  ```
136
136
 
137
- (i + 0.5)^2 ≦ 2 * elm + 0.25
137
+ (i + 0.5)^2 ≦ 2 * ele + 0.25
138
138
 
139
139
  ```
140
140
 
@@ -142,7 +142,7 @@
142
142
 
143
143
  ```
144
144
 
145
- i + 0.5 ≦ √(2 * elm + 0.25) /* = 2*elm+0.25 の平方根 */
145
+ i + 0.5 ≦ √(2 * ele + 0.25) /* = 2*elm+0.25 の平方根 */
146
146
 
147
147
  ```
148
148
 
@@ -150,7 +150,7 @@
150
150
 
151
151
  ```
152
152
 
153
- i ≦ √(2 * elm + 0.25) - 0.5
153
+ i ≦ √(2 * ele + 0.25) - 0.5
154
154
 
155
155
  ```
156
156
 

5

テキスト修正

2020/09/25 08:30

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -89,3 +89,85 @@
89
89
 
90
90
 
91
91
  参考になれば幸いです。
92
+
93
+
94
+
95
+ ### 追記
96
+
97
+
98
+
99
+ 以下、アルゴリスムの考え方を示します。
100
+
101
+
102
+
103
+ - `i` （≧0）行目の先頭（0列目)の要素は、`i * (i+1) / 2` です。たとえば、 i = 3 の行では、先頭要素は、
104
+
105
+ `3 * (3 + 1) / 2` から得られる `6`です。
106
+
107
+
108
+
109
+ - 上記を使うと、与えられた `ele` が配置される行のインデクス`i` は、以下を満たす最大の非負整数です。
110
+
111
+ ```
112
+
113
+ i * (i+1) / 2 ≦ elm
114
+
115
+ ```
116
+
117
+ 上記の両辺を２倍し、左辺のカッコを展開します。（以下で、i^2 は i の二乗を表すとします）
118
+
119
+ ```
120
+
121
+ i^2 + i ≦ 2 * elm
122
+
123
+ ```
124
+
125
+ 両辺に0.25を加えます。
126
+
127
+ ```
128
+
129
+ i^2 + i + 0.25 ≦ 2 * elm + 0.25
130
+
131
+ ```
132
+
133
+ 左辺を因数分解して
134
+
135
+ ```
136
+
137
+ (i + 0.5)^2 ≦ 2 * elm + 0.25
138
+
139
+ ```
140
+
141
+ となるので、両辺の平方根をとって、
142
+
143
+ ```
144
+
145
+ i + 0.5 ≦ √(2 * elm + 0.25) /* = 2*elm+0.25 の平方根 */
146
+
147
+ ```
148
+
149
+ より、
150
+
151
+ ```
152
+
153
+ i ≦ √(2 * elm + 0.25) - 0.5
154
+
155
+ ```
156
+
157
+ を満たす、最大の非負整数 i を求めればよいことになります。この条件から i を求める式をPythonで書くと
158
+
159
+ ```python
160
+
161
+ i = int(math.sqrt(2*ele+0.25) - 0.5)
162
+
163
+ ```
164
+
165
+ となります。i が得られると、j は、ele と 行の先頭要素`i * (i+1) / 2` との差なので
166
+
167
+ ```python
168
+
169
+ j = ele - int(i*(i+1)/2)
170
+
171
+ ```
172
+
173
+ で得ることができます。

4

テキスト修正

2020/09/25 08:22

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -10,11 +10,11 @@
10
10
 
11
11
 
12
12
 
13
- def get_mtx_idx(elm):
13
+ def get_mtx_idx(ele):
14
14
 
15
- i = int(math.sqrt(2*elm+0.25) - 0.5)
15
+ i = int(math.sqrt(2*ele+0.25) - 0.5)
16
16
 
17
- j = elm - int(i*(i+1)/2)
17
+ j = ele - int(i*(i+1)/2)
18
18
 
19
19
  return i, j
20
20
 
@@ -26,9 +26,9 @@
26
26
 
27
27
  ```python
28
28
 
29
- for elm in range(21):
29
+ for ele in range(21):
30
30
 
31
- print(f'{elm}: {get_mtx_idx(elm)}')
31
+ print(f'{ele}: {get_mtx_idx(ele)}')
32
32
 
33
33
  ```
34
34
 

3

テキスト修正

2020/09/25 07:54

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -12,7 +12,7 @@
12
12
 
13
13
  def get_mtx_idx(elm):
14
14
 
15
- i = int(math.sqrt(0.25+2*elm) - 0.5)
15
+ i = int(math.sqrt(2*elm+0.25) - 0.5)
16
16
 
17
17
  j = elm - int(i*(i+1)/2)
18
18
 

2

テキスト修正

2020/09/25 07:43

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -10,7 +10,7 @@
10
10
 
11
11
 
12
12
 
13
- def indexOf(elm):
13
+ def get_mtx_idx(elm):
14
14
 
15
15
  i = int(math.sqrt(0.25+2*elm) - 0.5)
16
16
 
@@ -28,7 +28,7 @@
28
28
 
29
29
  for elm in range(21):
30
30
 
31
- print(f'{elm}: {indexOf(elm)}')
31
+ print(f'{elm}: {get_mtx_idx(elm)}')
32
32
 
33
33
  ```
34
34
 

1

テキスト修正

2020/09/25 07:33

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -1,6 +1,4 @@
1
1
  こんにちは
2
-
3
-
4
2
 
5
3
  Pythonを使いました。
6
4
 
@@ -14,7 +12,7 @@
14
12
 
15
13
  def indexOf(elm):
16
14
 
17
- i = int(math.sqrt(0.25+2*elm)- 0.5)
15
+ i = int(math.sqrt(0.25+2*elm) - 0.5)
18
16
 
19
17
  j = elm - int(i*(i+1)/2)
20
18