質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.60%

  • PHP

    19854questions

    PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

数値の掛け算の組み合わせを知りたい

解決済

回答 5

投稿

  • 評価
  • クリップ 2
  • VIEW 1,201

re-24

score 250

以下のように配列で、数値が与えられます。
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

この中から組み合わせで掛け算した結果を取得したいです。
また、何個の数値の掛け算の結果かも取得したいです。

結果イメージとして
[
15=>2, // 3*5
21=>2, // 3*7
・・・(略)・・・
105=>3, // 3*5*7
165=>3, // 3*5*11
・・・(略)・・・
1155=>4, // 3*5*7*11
・・・(略)・・・
]
(演算結果)=>(かけた数値の個数)
のような結果一覧を取得したいです

よろしくお願いします。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+4

難しいことを考えずにサッと解くなら再帰すると簡単でしょうかね。

<?php
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

$result = [];

function func(&$result, $list, $i = 0, $val = 1, $cnt = 0, $expr = "")
{
    if ($i < count($list)) {
        func($result, $list, $i+1, $val*$list[$i], $cnt+1, "$expr*{$list[$i]}");
        func($result, $list, $i+1, $val, $cnt, $expr);
    } else if ($val > 1) {
        $result[] = [$val, $cnt, trim($expr, '*')];
    }
}

func($result, $prime_list);
//print_r($result);

foreach ($result as list ($val, $cnt, $expr)) {
    echo "$expr = $val ... ($cnt)\n";
}

最後の引数 $expr は結果の確認のために設けているだけなので無くてもいいです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/10 11:35

    項が一つしかないものを除外するのであれば

    } else if ($val > 1) {



    } else if ($cnt > 1) {

    とかにしてください。

    キャンセル

  • 2015/06/13 13:38

    私にとって、一番理解しやすかったものを選ばせていただきました。
    再帰処理以外での方法も、後学のために試してみようかと思います。

    多くの回答ありがとうございました。

    キャンセル

0

2 がリストに無いのが気になりますが・・

まず前提として、同じ素数は1回しか使われないですか?
例えば 3x3 はNG

私ならそうですね、この程度の数なら最初に 全パターンのリストを作ります
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
各素数は 10個ですので
2の10乗の組み合わせです。

全ての組み合わせに関してループし、array_push(演算結果,個数)
をすれば良いでしょう

全ての組み合わせは色々とやり方はありますが
愚直に10重ループにしても出来ますし
2ビット数という事に注目すると 簡単に処理出来ると思います



投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

こんにちは。

問題の核になるのは
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]; 
という配列を集合とみて、これの冪集合(power set)の要素をもれなく
生成するロジックをどう書くか?ということかと思いました。

なので、冪集合を作り出すロジックを調べるなどして、以下が出来ました。

<?php

# ---------------------------------------------
# 与えられた配列を集合とみなして、これの冪集合
# に相当する配列を作成して返す。
# ---------------------------------------------
function beki($list) {
  $result = []; 
  $n = count($list);
  
  for ( $i =0; $i < (1<<$n); ++ $i ) { 
    $a = []; 
    for ( $j = 0; $j < $n; ++ $j ) { 
      if ( ($i >> $j) & 1 ) { 
        $a[] = $list[$j];
      }   
    }   
    $result[] = $a; 
  }
  return $result;
}

# 与題の素数リスト
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];

# べき集合に相当するリストを作成する。
$power_list = beki($prime_list);

# 与題に沿った出力をするための配列作成
$results = array();

foreach ( $power_list as $list ) { 
  if ( count($list)==0 ) continue;

  $product = 1;
  foreach ( $list as $e ) 
    $product *= $e; 

  $results[$product] = count($list);
}

# 確認のための出力
foreach( $results as $product => $count ) { 
  echo "$product => $count\n"; 
}
これを実行すると、以下のような出力を得ました。

3 => 1
5 => 1 
15 => 2 
7 => 1 
21 => 2 
・・・
2865149859 => 8
4775249765 => 8
14325749295 => 9
6685349671 => 8
20056049013 => 9
33426748355 => 9
100280245065 => 10

そして電卓で、3×5×・・・×29×31 を計算したら確かに
100280245065
となって出力の最終行と合っていて、正直ほっとしている次第です。

面白い問題、ありがとうございました。


投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

2ビット数という事に注目すると 簡単に処理出来ると思います

2ビットというか各項を1ビットで表現する感じでしょうかね。

試しにやってみました。

<?php
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
$result = [];
$max = 1 << count($prime_list);

for ($i=0; $i<$max; $i++) {
    $val = 1;
    $cnt = 0;
    $expr = "";
    for ($j=0,$k=$i; $k; $j++,$k=$k>>1) {
        if ($k & 1) {
            $val *= $prime_list[$j];
            $cnt++;
            $expr = "$expr*{$prime_list[$j]}";
        }
    }
    if ($cnt > 1) {
        $result[] = [$val, $cnt, trim($expr, '*')];
    }
}

foreach ($result as list ($val, $cnt, $expr)) {
    echo "$expr = $val ... ($cnt)\n";
}

----

あるいは無駄に配列関数を駆使してみたり

<?php
$prime_list = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31];
$result = [];
$max = 1 << count($prime_list);

for ($i=0; $i<$max; $i++) {
    $arr = array_filter(array_map(
        function ($a, $b) { return $a * $b; },
        $prime_list,
        preg_split("//", strrev(sprintf("%b", $i)), -1, PREG_SPLIT_NO_EMPTY)
    ));
    if (count($arr) > 1) {
        $result[] = [array_product($arr), count($arr), implode("*", $arr)];
    }
}

foreach ($result as list ($val, $cnt, $expr)) {
    echo "$expr = $val ... ($cnt)\n";
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/10 13:51

    2進数と書いたつもりが ミスってましたすみません

    キャンセル

0

実装方針だけを述べます。

1. 0 か 1 を 10 個並べた組み合わせを順番に得ることができる stream  をつくる。
2. 得られた item (0,1 を要素とする 10 個の配列) に対して
   val = 1
   num = 0
   for i on [0..10]
     if item[i] != 0
        val *= prime_list[i]
        num ++
   として、掛け算の結果 (val)、掛け算につかった要素の個数 (num) を得ます。
3. 上で得た val, num を 結果として蓄積します。
   蓄積方法としては、 キーを val, 値を num にした hash を使う。
 (素数の掛け算なので、val には重複がない。
    もし、素数のリストでなければ、掛け算結果に重複があり得えます。
    その場合は hash の val は 配列にする)

すでに別の回答にあるように
1 の部分は strem でなく、 for でループを組んで 0 か 1 を 10 個並べた組み合わせを
得ることも可能です。

上の方法では、同じ掛け算を何回も行うことになります。
掛け算の実施回数を減らことを考えるなら、
  使う要素の数が1つ増えたときは 過去の掛け算の結果に 増えた要素を1回 掛け算するようにする
という工夫をすることも可能です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.60%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • PHP

    19854questions

    PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。