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

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

ただいまの
回答率

90.48%

  • アルゴリズム

    421questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

「3 Coins Shop」の商品価格

解決済

回答 6

投稿 編集

  • 評価
  • クリップ 4
  • VIEW 969

tkturbo

score 4974

前提・実現したいこと

注)困っていることではありません。好奇心からの質問です。

下記のような課題があったとします。

1円、5円、10円、50円、100円、500円の各硬貨を3枚組み合わせて得られる金額をすべて列挙しなさい。
ただし、回答に使用できる組み合わせで5円、50円、500円の各硬貨は最大1枚までしか使用できません。

(JR新宿駅で「3CoinsShop」なる看板を見てふと思いついた問題です。)

期待される回答は下記のようになるはずですが。。。

金額 - 組合せ
  3円 -  1円×37円 -  1円×2枚+  5円×112円 -  1円×2枚+ 10円×116円 -  1円×1枚+  5円×1枚+ 10円×121円 -  1円×1枚+ 10円×225円 -  5円×1枚+ 10円×230円 - 10円×352円 -  1円×2枚+ 50円×156円 -  1円×1枚+  5円×1枚+ 50円×161円 -  1円×1枚+ 10円×1枚+ 50円×165円 -  5円×1枚+ 10円×1枚+ 50円×170円 - 10円×2枚+ 50円×1102円 -  1円×2枚+100円×1106円 -  1円×1枚+  5円×1枚+100円×1111円 -  1円×1枚+ 10円×1枚+100円×1115円 -  5円×1枚+ 10円×1枚+100円×1120円 - 10円×2枚+100円×1151円 -  1円×1枚+ 50円×1枚+100円×1155円 -  5円×1枚+ 50円×1枚+100円×1160円 - 10円×1枚+ 50円×1枚+100円×1201円 -  1円×1枚+100円×2205円 -  5円×1枚+100円×2210円 - 10円×1枚+100円×2250円 - 50円×1枚+100円×2300円 -100円×3502円 -  1円×2枚+500円×1506円 -  1円×1枚+  5円×1枚+500円×1511円 -  1円×1枚+ 10円×1枚+500円×1515円 -  5円×1枚+ 10円×1枚+500円×1520円 - 10円×2枚+500円×1551円 -  1円×1枚+ 50円×1枚+500円×1555円 -  5円×1枚+ 50円×1枚+500円×1560円 - 10円×1枚+ 50円×1枚+500円×1601円 -  1円×1枚+100円×1枚+500円×1605円 -  5円×1枚+100円×1枚+500円×1610円 - 10円×1枚+100円×1枚+500円×1650円 - 50円×1枚+100円×1枚+500円×1700円 -100円×2枚+500円×1

皆さんが得意としている言語で解くならどんなふうになりますか?

回答例

javascriptで書いてみました。

{
  let arr=[1,1,1,5,10,10,10,50,100,100,100,500];
  let keys=[];
  for(let i = 0; i < arr.length; i++)
    for(let j = i+1; j < arr.length; j++)
      for(let k = j+1; k < arr.length; k++){
        let val = arr[i]+arr[j]+arr[k];
        keys[val]=val;
      };
  for(key in keys){ console.log(key); }
}


回答お待ちしていますm(_ _)m
16/05/06.11:05追記:できれば回答例の表記からは乖離したものがいただけると嬉しいです。

  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2016/05/09 14:42

    こちらの質問が他のユーザから「問題・課題が含まれていない質問」という指摘を受けました
    teratailでは、漠然とした興味から票を募るような質問や、意見の主張をすることを目的とした投稿は推奨していません。
    「編集」ボタンから編集を行い、質問の意図や解決したい課題を明確に記述していただくと回答が得られやすくなります。

回答 6

checkベストアンサー

+1

ちょっとした工夫を思いついてしまったので、そのコードを書いてしまいます(Java8)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q34167_2 {
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 50, 100, 500};

        // 一枚しか使えない硬貨
        List<Integer> once = Arrays.asList(new Integer[]{5, 50, 500});
        List<Integer> total = new ArrayList<>();
        for (int i = 0; i < coins.length; i++) {

            // 一枚しか使えない硬貨を前のステップで使っていた場合には次の硬貨から、そうでなければ同じ硬貨から選択
            for(int j = once.contains(coins[i]) ? i + 1 : i; j < coins.length ; j++) {
                for (int k = once.contains(coins[j]) ? j + 1 : j; k < coins.length; k++){
                    total.add(coins[i] + coins[j] + coins[k]);
                }
            }
        }
        total.stream().sorted().forEach(System.out::println);
    }

}


更にこれをなんとかStreamで書けないか試してみた…が、余り綺麗に書けなかったです。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Q34167_2 {
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 50, 100, 500};

        // 一枚しか使えない硬貨
        List<Integer> once = Arrays.asList(new Integer[]{5, 50, 500});

        // Stream内のListの最後の番号に応じ、次の番号を詰めたすべてのパターンのListのStreamを返す
        Function<List<Integer>, Stream<List<Integer>>> f = 
                e -> {
                    int last = e.get(e.size() - 1);
                    if (once.contains(coins[last])){
                        last++;
                    }
                    return IntStream.range(last, coins.length).mapToObj(i -> {
                        List<Integer> l = new ArrayList<>(e);
                        l.add(i);
                        return l;
                    });
                };

        IntStream.range(0, coins.length).mapToObj(i -> {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            return list;
        }).flatMap(f).flatMap(f)
        .mapToInt(e -> e.stream().mapToInt(i -> coins[i]).sum())
        .sorted().forEach(System.out::println);
    }

}

旧回答

この手の問題では、制約の厳しいものから考えることが鉄則です。今回の場合、「5円、50円、500円は最大1枚しか使えない」という制約があるので、これから考えます。

ある硬貨の組み合わせで、5円、50円、500円はそれぞれ「使う」か「使わない」かの2つの選択肢があります。全部使っても3枚に収まるので、各硬貨の選択は他の硬貨を使うか使わないかに影響を受けません。そうすると、2^3=8通りの組み合わせが出てきます。その「枚数」と「金額」をセットにしておきます。

残りの1円、10円、100円については3枚まで使えるわけですが、こう考えます。

  1. それぞれ「使う」か「使わない」かで2つずつ選択肢
  2. 使う硬貨が0種なら0円。
    1種類ならそれを1~3枚のうち何枚使うか。
    2種類ならどっちを2枚使うか、あるいはどちらも1枚ずつか。
    3種類なら1枚ずつで確定

そして、最初の5円、50円、500円硬貨の枚数-金額ペアと照らし合わせ、合計3枚になるように足し合わせればできます。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/05/06 17:14 編集

    回答ありがとうございます。
    考え方はなるほどその通りですが、コード化するとこんな感じですかね?

    {
     let t=[], v=[];
     /* 3枚まで使える部分全組合せ生成 */
     [1,10,100].forEach((a,i,ar)=>{
      t[a]=a;
      ar.forEach((b,j,br)=>{
       t[a+b]=a+b;
       br.forEach((c)=>{t[a+b+c]=a+b+c;});
      });
     });
     /* 1枚しか使えない部分と合成 */
     t.forEach((e)=>{
      let mod = e%3;
      if(mod==0){ v[e]=e; }
      else {
       [5,50,500].forEach((a, i, s)=>{
        if(mod==2){v[e+a]=e+a;}
        else{s.slice(i+1).forEach((b)=>{v[e+a+b]=e+a+b});}
       });
      }
     });
     /* 1枚しか使えない硬貨のみで価格生成 */
     v[555]=555;
     v.forEach((e)=>console.log(e));
    }

    。。。かえって難しくなってしまった感が。。。orz
    #コード整形のためインデントを全角スペースにしています。
    #試すときは全角スペース→半角スペースなりタブなりに要変換

    キャンセル

  • 2016/05/06 17:58

    ちなみに、先に「1円、10円、100円」の組合せを生成しているのは、こちらの方が使用枚数判定が楽だったからです。

    キャンセル

  • 2016/05/06 18:59

    ええ、私もこの回答文を書いてる時にほかの人の簡素な回答が出てくるのを見て、「自分が逆にめんどくさいこと考えてるなぁ」と思って投稿を躊躇しておりました。

    キャンセル

  • 2016/05/10 11:38

    追加コードありがとうございます。
    便利なライブラリや配列メソッドが列挙される中、ロジックで工夫できないかいろいろと考えていただいたのでこちらをベストアンサーとさせていただきたいと思います。

    キャンセル

+1

こんにちは。

ちょっと頭休めにトライしてみました。
短いコードと言う意味では既に最適化できている印象ですし、アルゴリズムの解き方と言うよりは言語によってどのように書けるのかに興味をお持ちのように見えました。
C++は、そこそこ元ソースに忠実に書けます。C++11を使ってできるだけ元ソースに近づけてみました。

#include <type_traits>
#include <set>
#include <iostream>
using namespace std;

int main()
{
    unsigned arr[]={1,1,1,5,10,10,10,50,100,100,100,500};
    set<unsigned> keys;
    for (size_t i = 0; i < extent<decltype(arr)>::value; i++)
        for (size_t j = i+1; j < extent<decltype(arr)>::value; j++)
            for (size_t k = j+1; k < extent<decltype(arr)>::value; k++) {
                unsigned val = arr[i]+arr[j]+arr[k];
                keys.emplace(val);
            }
    for (auto key : keys) cout << key << "\n";

    return 0;
}

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/05/06 11:04

    回答ありがとうございます。
    やはりCをベースにした言語だと表現が似てしまいますねぇ。

    キャンセル

+1

ライブラリありそうだなーと探してみました。

from itertools import permutations

arr = [1,1,1,5,10,10,10,50,100,100,100,500]
keys = set()
for x in permutations(arr, 3):
    keys.add(sum(x))
for x in sorted(keys):
    print x
from itertools import permutations
print sorted(set([sum(x) for x in permutations([1,1,1 ,5,10,10,10,50,100,100,100,500], 3)]))

実行結果はこちら: http://ideone.com/Vy52JY

検索中に、こんな記事を見つけました。わけがわからない。
全ての組み合わせを作る

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/05/06 11:28

    回答ありがとうございます。
    おお、permutations便利だなぁ!
    そしてリンク先はやっぱり難解だった件orz

    キャンセル

  • 2016/05/06 12:27

    まちがえた……。 permutations ではなくて combinations のほうが速いですね。1320個 vs. 220個。

    キャンセル

  • 2016/05/06 12:36

    なるほど、permutationsだと順列([a,b]と[b,a]は別の組合せ)、combinationsだと順序無視の組合せ([a,b]と[b,a]は同じ組合せ)だから、計算量が違うのですね。
    #しかし私の回答例でも無駄な計算をやっているのでそこは改善したいポイント。

    キャンセル

+1

Scalaなら 1行で 書けます。

object Main extends App {
  List(1,1,1,5,10,10,10,50,100,100,100,500).combinations(3).foreach(println)
}


実行結果はこちら: http://scastie.org/16988

これはScalaが 順列、組み合わせ、冪集合 を生成する関数を標準で持っているからですね。
Scala Codebook 順列、組み合わせ、冪集合を生成する

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/05/06 11:31

    回答ありがとうございます。
    1Linerはすごいなぁ!
    そしてScalaのcombinationsメソッド、便利だなぁ!

    キャンセル

+1

バッチファイルで作ってみました。

@echo off
setlocal ENABLEDELAYEDEXPANSION

set arr=1 1 1 5 10 10 10 50 100 100 100 500
call :prepare %arr%
for /L %%I in (1,1,%length%) do (
    set /A j = %%I + 1
    for /L %%J in (!j!,1,%length%) do (
        set /A k = %%J + 1
        for /L %%K in (!k!,1,%length%) do (
            set /A val = arr[%%I] + arr[%%J] + arr[%%K]
            set sval=00!val!
            set sval=!sval:~-3!
            set keys[!sval!]=!val!
        )
    )
)
for /F "tokens=2 delims==" %%A in ('set keys[') do echo %%A
goto :eof

:prepare
set /A length=0
:getlength_1
if "%1" == "" goto :eof
set /A length += 1
set arr[%length%]=%1
shift
goto :getlength_1

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/05/08 14:14

    回答ありがとうございます。
    MS-DOSで回答されるとは思ってませんでしたw

    キャンセル

+1

ruby で書いてみました。

require 'awesome_print'

ans = [1,1,1,5,10,10,10,50,100,100,100,500].combination(3).group_by {|coins| coins.inject(:+)}

ap ans.keys.sort
ans.sort.each { |k, v| p "#{k}: #{v}" }


実行結果

[
    [ 0] 3,
    [ 1] 7,
    [ 2] 12,
    [ 3] 16,
    [ 4] 21,
    [ 5] 25,
    [ 6] 30,
    [ 7] 52,
    [ 8] 56,
    [ 9] 61,
    [10] 65,
    [11] 70,
    [12] 102,
    [13] 106,
    [14] 111,
    [15] 115,
    [16] 120,
    [17] 151,
    [18] 155,
    [19] 160,
    [20] 201,
    [21] 205,
    [22] 210,
    [23] 250,
    [24] 300,
    [25] 502,
    [26] 506,
    [27] 511,
    [28] 515,
    [29] 520,
    [30] 551,
    [31] 555,
    [32] 560,
    [33] 601,
    [34] 605,
    [35] 610,
    [36] 650,
    [37] 700
]
"3: [[1, 1, 1]]"
"7: [[1, 1, 5], [1, 1, 5], [1, 1, 5]]"
"12: [[1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10], [1, 1, 10]]"
"16: [[1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10], [1, 5, 10]]"
"21: [[1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10], [1, 10, 10]]"
"25: [[5, 10, 10], [5, 10, 10], [5, 10, 10]]"
"30: [[10, 10, 10]]"
"52: [[1, 1, 50], [1, 1, 50], [1, 1, 50]]"
"56: [[1, 5, 50], [1, 5, 50], [1, 5, 50]]"
"61: [[1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50], [1, 10, 50]]"
"65: [[5, 10, 50], [5, 10, 50], [5, 10, 50]]"
"70: [[10, 10, 50], [10, 10, 50], [10, 10, 50]]"
"102: [[1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100], [1, 1, 100]]"
"106: [[1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100], [1, 5, 100]]"
"111: [[1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100], [1, 10, 100]]"
"115: [[5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100], [5, 10, 100]]"
"120: [[10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100], [10, 10, 100]]"
"151: [[1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100], [1, 50, 100]]"
"155: [[5, 50, 100], [5, 50, 100], [5, 50, 100]]"
"160: [[10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100], [10, 50, 100]]"
"201: [[1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100], [1, 100, 100]]"
"205: [[5, 100, 100], [5, 100, 100], [5, 100, 100]]"
"210: [[10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100], [10, 100, 100]]"
"250: [[50, 100, 100], [50, 100, 100], [50, 100, 100]]"
"300: [[100, 100, 100]]"
"502: [[1, 1, 500], [1, 1, 500], [1, 1, 500]]"
"506: [[1, 5, 500], [1, 5, 500], [1, 5, 500]]"
"511: [[1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500], [1, 10, 500]]"
"515: [[5, 10, 500], [5, 10, 500], [5, 10, 500]]"
"520: [[10, 10, 500], [10, 10, 500], [10, 10, 500]]"
"551: [[1, 50, 500], [1, 50, 500], [1, 50, 500]]"
"555: [[5, 50, 500]]"
"560: [[10, 50, 500], [10, 50, 500], [10, 50, 500]]"
"601: [[1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500], [1, 100, 500]]"
"605: [[5, 100, 500], [5, 100, 500], [5, 100, 500]]"
"610: [[10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500], [10, 100, 500]]"
"650: [[50, 100, 500], [50, 100, 500], [50, 100, 500]]"
"700: [[100, 100, 500], [100, 100, 500], [100, 100, 500]]"

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/05/09 13:13

    回答ありがとうございます。
    「配列」「combination」でググろうとすると「ruby 配列 combination」が検索候補に挙がってきますね。
    ひょっとしてrubyで実装されたのが元祖なんでしょうか?

    キャンセル

関連した質問

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

  • アルゴリズム

    421questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。