前提・実現したいこと
注）困っていることではありません。好奇心からの質問です。
下記のような課題があったとします。
1円、5円、10円、50円、100円、500円の各硬貨を3枚組み合わせて得られる金額をすべて列挙しなさい。
ただし、回答に使用できる組み合わせで5円、50円、500円の各硬貨は最大1枚までしか使用できません。
(JR新宿駅で「3CoinsShop」なる看板を見てふと思いついた問題です。)
期待される回答は下記のようになるはずですが。。。
金額 - 組合せ
3円 - 1円×3枚
7円 - 1円×2枚＋ 5円×1枚
12円 - 1円×2枚＋ 10円×1枚
16円 - 1円×1枚＋ 5円×1枚＋ 10円×1枚
21円 - 1円×1枚＋ 10円×2枚
25円 - 5円×1枚＋ 10円×2枚
30円 - 10円×3枚
52円 - 1円×2枚＋ 50円×1枚
56円 - 1円×1枚＋ 5円×1枚＋ 50円×1枚
61円 - 1円×1枚＋ 10円×1枚＋ 50円×1枚
65円 - 5円×1枚＋ 10円×1枚＋ 50円×1枚
70円 - 10円×2枚＋ 50円×1枚
102円 - 1円×2枚＋100円×1枚
106円 - 1円×1枚＋ 5円×1枚＋100円×1枚
111円 - 1円×1枚＋ 10円×1枚＋100円×1枚
115円 - 5円×1枚＋ 10円×1枚＋100円×1枚
120円 - 10円×2枚＋100円×1枚
151円 - 1円×1枚＋ 50円×1枚＋100円×1枚
155円 - 5円×1枚＋ 50円×1枚＋100円×1枚
160円 - 10円×1枚＋ 50円×1枚＋100円×1枚
201円 - 1円×1枚＋100円×2枚
205円 - 5円×1枚＋100円×2枚
210円 - 10円×1枚＋100円×2枚
250円 - 50円×1枚＋100円×2枚
300円 -100円×3枚
502円 - 1円×2枚＋500円×1枚
506円 - 1円×1枚＋ 5円×1枚＋500円×1枚
511円 - 1円×1枚＋ 10円×1枚＋500円×1枚
515円 - 5円×1枚＋ 10円×1枚＋500円×1枚
520円 - 10円×2枚＋500円×1枚
551円 - 1円×1枚＋ 50円×1枚＋500円×1枚
555円 - 5円×1枚＋ 50円×1枚＋500円×1枚
560円 - 10円×1枚＋ 50円×1枚＋500円×1枚
601円 - 1円×1枚＋100円×1枚＋500円×1枚
605円 - 5円×1枚＋100円×1枚＋500円×1枚
610円 - 10円×1枚＋100円×1枚＋500円×1枚
650円 - 50円×1枚＋100円×1枚＋500円×1枚
700円 -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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
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枚まで使えるわけですが、こう考えます。
- それぞれ「使う」か「使わない」かで2つずつ選択肢
- 使う硬貨が0種なら0円。
1種類ならそれを1~3枚のうち何枚使うか。
2種類ならどっちを2枚使うか、あるいはどちらも1枚ずつか。
3種類なら1枚ずつで確定
そして、最初の5円、50円、500円硬貨の枚数-金額ペアと照らし合わせ、合計3枚になるように足し合わせればできます。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+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;
}投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+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 xfrom 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
検索中に、こんな記事を見つけました。わけがわからない。
全ての組み合わせを作る
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+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 順列、組み合わせ、冪集合を生成する
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+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投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+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]]"投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 90.41%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
質問への追記・修正、ベストアンサー選択の依頼
2016/05/09 14:42
こちらの質問が他のユーザから「問題・課題が含まれていない質問」という指摘を受けました
teratailでは、漠然とした興味から票を募るような質問や、意見の主張をすることを目的とした投稿は推奨していません。
「編集」ボタンから編集を行い、質問の意図や解決したい課題を明確に記述していただくと回答が得られやすくなります。