teratail
回答率
85.48%
質問するログイン新規登録
トップPHPに関する質問数値の掛け算の組み合わせを知りたい

編集履歴

回答編集履歴

7

テキスト修正

2015/06/10 06:22

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -10,9 +10,9 @@
10
10
 
11
11
  ```
12
12
 
13
- という配列を集合とみて、これの冪集合（power set）の要素を生成する
13
+ という配列を集合とみて、これの冪集合（power set）の要素をもれなく
14
14
 
15
- ロジックをどう書くか？ということかと思いました。
15
+ 生成するロジックをどう書くか？ということかと思いました。
16
16
 
17
17
 
18
18
 

6

テキスト修正

2015/06/10 06:22

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -10,9 +10,9 @@
10
10
 
11
11
  ```
12
12
 
13
- という配列を集合とみて、これの冪集合（power set）を生成するロジックを
13
+ という配列を集合とみて、これの冪集合（power set）の要素を生成する
14
14
 
15
- どう書くか？ということかと思いました。
15
+ ロジックをどう書くか？ということかと思いました。
16
16
 
17
17
 
18
18
 

5

テキスト修正

2015/06/10 06:04

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -1 +1,165 @@
1
+ こんにちは。
2
+
3
+
4
+
5
+ 問題の核になるのは
6
+
7
+ ```lang-php
8
+
9
+ $prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
10
+
11
+ ```
12
+
13
+ という配列を集合とみて、これの冪集合（power set）を生成するロジックを
14
+
15
+ どう書くか？ということかと思いました。
16
+
17
+
18
+
19
+ なので、冪集合を作り出すロジックを調べるなどして、以下が出来ました。
20
+
21
+
22
+
23
+ ```lang-php
24
+
25
+ <?php
26
+
27
+
28
+
29
+ # ---------------------------------------------
30
+
31
+ # 与えられた配列を集合とみなして、これの冪集合
32
+
33
+ # に相当する配列を作成して返す。
34
+
35
+ # ---------------------------------------------
36
+
37
+ function beki($list) {
38
+
39
+ $result = [];
40
+
41
+ $n = count($list);
42
+
43
+
44
+
45
+ for ( $i =0; $i < (1<<$n); ++ $i ) {
46
+
47
+ $a = [];
48
+
49
+ for ( $j = 0; $j < $n; ++ $j ) {
50
+
51
+ if ( ($i >> $j) & 1 ) {
52
+
53
+ $a[] = $list[$j];
54
+
55
+ }
56
+
57
+ }
58
+
59
+ $result[] = $a;
60
+
61
+ }
62
+
63
+ return $result;
64
+
65
+ }
66
+
67
+
68
+
69
+ # 与題の素数リスト
70
+
71
+ $prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
72
+
73
+
74
+
75
+ # べき集合に相当するリストを作成する。
76
+
77
+ $power_list = beki($prime_list);
78
+
79
+
80
+
81
+ # 与題に沿った出力をするための配列作成
82
+
83
+ $results = array();
84
+
85
+
86
+
87
+ foreach ( $power_list as $list ) {
88
+
89
+ if ( count($list)==0 ) continue;
90
+
91
+
92
+
93
+ $product = 1;
94
+
95
+ foreach ( $list as $e )
96
+
97
+ $product *= $e;
98
+
99
+
100
+
101
+ $results[$product] = count($list);
102
+
103
+ }
104
+
105
+
106
+
107
+ # 確認のための出力
108
+
109
+ foreach( $results as $product => $count ) {
110
+
111
+ echo "$product => $count\n";
112
+
113
+ }
114
+
115
+ ```
116
+
1
- 与題を勘違いしていたので削除します。済みませんでした。
117
+ これを実行すると、以下のような出力を得ました。
118
+
119
+ ---
120
+
121
+ 3 => 1
122
+
123
+
124
+
125
+ 5 => 1
126
+
127
+ 15 => 2
128
+
129
+ 7 => 1
130
+
131
+ 21 => 2
132
+
133
+ ・・・
134
+
135
+ 2865149859 => 8
136
+
137
+ 4775249765 => 8
138
+
139
+ 14325749295 => 9
140
+
141
+ 6685349671 => 8
142
+
143
+ 20056049013 => 9
144
+
145
+ 33426748355 => 9
146
+
147
+ 100280245065 => 10
148
+
149
+ ---
150
+
151
+
152
+
153
+ そして電卓で、3×5×・・・×29×31　を計算したら確かに
154
+
155
+ 100280245065
156
+
157
+ となって出力の最終行と合っていて、正直ほっとしている次第です。
158
+
159
+
160
+
161
+ 面白い問題、ありがとうございました。
162
+
163
+
164
+
165
+

4

テキスト修正

2015/06/10 06:02

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -1 +1 @@
1
- 与題を勘違いしていたので削除します。
1
+ 与題を勘違いしていたので削除します。済みませんでした。

3

与題を勘違いしていたので削除します。

2015/06/10 03:22

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -1,171 +1 @@
1
- こんにちは。
2
-
3
-
4
-
5
- 因数リストの小さいほうから、割れるだけ割りながら、
6
-
7
- それぞれの指数を算出するという、**手計算そのまま**の
8
-
9
- アルゴリズムでやってみました。
10
-
11
-
12
-
13
- 以下、自分の手元にある環境で作成したソースと実行結果です。
14
-
15
- ---
16
-
17
- [ykt68@sakura-vps] php -v
18
-
19
-
20
-
21
- PHP 5.6.7 (cli) (built: Mar 21 2015 20:27:49)
22
-
23
- Copyright (c) 1997-2015 The PHP Group
24
-
25
- Zend Engine v2.6.0, Copyright (c) 1998-2015 Zend Technologies
26
-
27
- with Zend OPcache v7.0.4-dev, Copyright (c) 1999-2015, by Zend Technologies
28
-
29
- [ykt68@sakura-vps] cat q11043.php
30
-
31
- ```lang-php
32
-
33
- <?php
34
-
35
- /**
36
-
37
- * 整数 $target を $prime_listの素数で因数分解して、
38
-
39
- * その結果を配列にして返す。
40
-
41
- */
42
-
43
- function factorize($target)
44
-
45
- {
46
-
47
- // targetが0のときは空の配列を返す。
48
-
49
- if ( $target == 0 )
50
-
51
- return array();
52
-
53
-
54
-
55
- // 因数の配列
56
-
57
- $prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
58
-
59
-
60
-
61
- // 結果を格納する配列
62
-
63
- $resultArray = array();
64
-
65
-
66
-
67
- // 因数リストについてループ
68
-
69
- foreach ($prime_list as $prime) {
70
-
71
-
72
-
73
- // 現在の因数の指数（何回割れるか)を算出
74
-
75
- $exponent = dividableCount($target, $prime);
76
-
77
-
78
-
79
- // 指数が0より大きい場合(＝1回以上割れる場合)
80
-
81
- if ( $exponent > 0 )
82
-
83
- //結果の配列に入れる。
84
-
85
- $resultArray[$prime] = $exponent;
86
-
87
-
88
-
89
- // 対象を(現在の因数^指数)で割って更新
90
-
91
- $target /= pow($prime, $exponent);
92
-
93
- }
94
-
95
- }
96
-
97
-
98
-
99
- // 結果を返す。
1
+ 与題を勘違いしていたので削除します。
100
-
101
- return $resultArray;
102
-
103
- }
104
-
105
-
106
-
107
- /**
108
-
109
- * 整数$a が 整数$div で何回割ることができるを返す。
110
-
111
- *
112
-
113
- * 例) $a = 4125, $div = 5 なら 3 を返す。
114
-
115
- */
116
-
117
- function dividableCount($a, $b)
118
-
119
- {
120
-
121
- $count = 0;
122
-
123
-
124
-
125
- while ( $a % $b == 0 ) {
126
-
127
- $count ++;
128
-
129
- $a /= $b;
130
-
131
- }
132
-
133
-
134
-
135
- return $count;
136
-
137
- }
138
-
139
-
140
-
141
- $result = factorize(4125);
142
-
143
-
144
-
145
- var_dump($result);
146
-
147
- ```
148
-
149
- [ykt68@sakura-vps] php -q q11043.php
150
-
151
- array(3) {
152
-
153
- [3]=>
154
-
155
- int(1)
156
-
157
- [5]=>
158
-
159
- int(3)
160
-
161
- [11]=>
162
-
163
- int(1)
164
-
165
- }
166
-
167
- [ykt68@sakura-vps]
168
-
169
- ---
170
-
171
- 参考になれば幸いです。

2

ソース修正

2015/06/10 03:21

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -76,17 +76,21 @@
76
76
 
77
77
 
78
78
 
79
- // 指数が0より大きい場合、結果の配列に入れる。
79
+ // 指数が0より大きい場合(＝1回以上割れる場合)
80
80
 
81
81
  if ( $exponent > 0 )
82
+
83
+ //結果の配列に入れる。
82
84
 
83
85
  $resultArray[$prime] = $exponent;
84
86
 
85
87
 
86
88
 
87
- // 対象を(現在の因数^指数)で割って更新
89
+ // 対象を(現在の因数^指数)で割って更新
88
90
 
89
- $target /= pow($prime, $exponent);
91
+ $target /= pow($prime, $exponent);
92
+
93
+ }
90
94
 
91
95
  }
92
96
 

1

テキスト修正

2015/06/10 03:19

投稿

jun68ykt
jun68ykt

スコア9058

test CHANGED
@@ -34,7 +34,7 @@
34
34
 
35
35
  /**
36
36
 
37
- * 整数 $target を $prime_listで因数分解して
37
+ * 整数 $target を $prime_listの素数で因数分解して、
38
38
 
39
39
  * その結果を配列にして返す。
40
40
 
@@ -52,7 +52,7 @@
52
52
 
53
53
 
54
54
 
55
- // 因数分解する素数の配列
55
+ // 因数の配列
56
56
 
57
57
  $prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
58
58
 
@@ -64,7 +64,7 @@
64
64
 
65
65
 
66
66
 
67
- // 素数リストについてループ
67
+ // 因数リストについてループ
68
68
 
69
69
  foreach ($prime_list as $prime) {
70
70