数か月前に面接の準備のために書いていたコードを見つけました。
私が持っていたコメントによると、それはこの問題を解決しようとしていました:
セント単位のドル価値 (例: 200 = 2 ドル、1000 = 10 ドル) が与えられた場合、そのドル価値を構成するコインのすべての組み合わせを見つけます。ペニー (1¢)、ニッケル (5¢)、ダイム (10¢)、クォーター (25¢) のみが許可されています。
たとえば、100 が与えられた場合、答えは次のようになります。
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
これは、反復と再帰の両方の方法で解決できると思います。私の再帰的な解決策は非常にバグが多く、他の人がこの問題をどのように解決するのか疑問に思っていました。この問題の難しい部分は、可能な限り効率的にすることでした。
私はずっと前にこれを調べました、そしてあなたはそれについての私の小さな記事を読むことができます. これがMathematica のソースです。
生成関数を使用することで、問題に対する閉形式の定時間解を得ることができます。Graham、Knuth、および Patashnik のConcrete Mathematicsはこのための本であり、問題のかなり広範な議論が含まれています。基本的に、 n番目の係数がnドルの変更方法の数である多項式を定義します。
この記事の 4 ～ 5 ページでは、Mathematica (またはその他の便利なコンピューター代数システム) を使用して、3 行のコードで数秒で 10^10^6 ドルの答えを計算する方法が示されています。
(これはかなり前のことで、75Mhz Pentium では数秒かかります...)
注：これはウェイの数のみを示しています。
スカラ関数:
def countChange(money: Int, coins: List[Int]): Int =
if (money == 0) 1
else if (coins.isEmpty || money < 0) 0
else countChange(money - coins.head, coins) + countChange(money, coins.tail)
私は再帰的な解決策を好みます。金種のリストがいくつかあります。最小のものが残りの通貨額を均等に分割できる場合、これは問題なく機能するはずです。
基本的に、あなたは最大の金種から最小の金種に移動します。
再帰的に、
これがあなたが述べた問題の私のPythonバージョンです。200セントです。私は1463の方法を取得します。このバージョンでは、すべての組み合わせと最終的なカウントの合計が出力されます。
#!/usr/bin/python
# find the number of ways to reach a total with the given number of combinations
cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}
def count_combs(left, i, comb, add):
if add: comb.append(add)
if left == 0 or (i+1) == len(denominations):
if (i+1) == len(denominations) and left > 0:
if left % denominations[i]:
return 0
comb.append( (left/denominations[i], demoninations[i]) )
i += 1
while i < len(denominations):
comb.append( (0, denominations[i]) )
i += 1
print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
return 1
cur = denominations[i]
return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))
count_combs(cents, 0, [], None)
スカラ関数:
def countChange(money: Int, coins: List[Int]): Int = {
def loop(money: Int, lcoins: List[Int], count: Int): Int = {
// if there are no more coins or if we run out of money ... return 0
if ( lcoins.isEmpty || money < 0) 0
else{
if (money == 0 ) count + 1
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
}
}
val x = loop(money, coins, 0)
Console println x
x
}
コードはこの問題を解決するために Java を使用しており、これも機能します... この方法は、ループが多すぎるため適切ではないかもしれませんが、実際には簡単な方法です。
public class RepresentCents {
public static int sum(int n) {
int count = 0;
for (int i = 0; i <= n / 25; i++) {
for (int j = 0; j <= n / 10; j++) {
for (int k = 0; k <= n / 5; k++) {
for (int l = 0; l <= n; l++) {
int v = i * 25 + j * 10 + k * 5 + l;
if (v == n) {
count++;
} else if (v > n) {
break;
}
}
}
}
}
return count;
}
public static void main(String[] args) {
System.out.println(sum(100));
}
}
サブ問題は典型的な動的計画問題です。
/* Q: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars),
find the number of combinations of coins that make up the dollar value.
There are only penny, nickel, dime, and quarter.
(quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent) */
/* A:
Reference: http://andrew.neitsch.ca/publications/m496pres1.nb.pdf
f(n, k): number of ways of making change for n cents, using only the first
k+1 types of coins.
+- 0, n < 0 || k < 0
f(n, k) = |- 1, n == 0
+- f(n, k-1) + f(n-C[k], k), else
*/
#include <iostream>
#include <vector>
using namespace std;
int C[] = {1, 5, 10, 25};
// Recursive: very slow, O(2^n)
int f(int n, int k)
{
if (n < 0 || k < 0)
return 0;
if (n == 0)
return 1;
return f(n, k-1) + f(n-C[k], k);
}
// Non-recursive: fast, but still O(nk)
int f_NonRec(int n, int k)
{
vector<vector<int> > table(n+1, vector<int>(k+1, 1));
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
if (i < 0 || j < 0) // Impossible, for illustration purpose
{
table[i][j] = 0;
}
else if (i == 0 || j == 0) // Very Important
{
table[i][j] = 1;
}
else
{
// The recursion. Be careful with the vector boundary
table[i][j] = table[i][j-1] +
(i < C[j] ? 0 : table[i-C[j]][j]);
}
}
}
return table[n][k];
}
int main()
{
cout << f(100, 3) << ", " << f_NonRec(100, 3) << endl;
cout << f(200, 3) << ", " << f_NonRec(200, 3) << endl;
cout << f(1000, 3) << ", " << f_NonRec(1000, 3) << endl;
return 0;
}
これは本当に古い質問ですが、他のすべてよりも小さいと思われるJavaで再帰的なソリューションを思いついたので、ここに行きます-
public static void printAll(int ind, int[] denom,int N,int[] vals){
if(N==0){
System.out.println(Arrays.toString(vals));
return;
}
if(ind == (denom.length))return;
int currdenom = denom[ind];
for(int i=0;i<=(N/currdenom);i++){
vals[ind] = i;
printAll(ind+1,denom,N-i*currdenom,vals);
}
}
改良点:
public static void printAllCents(int ind, int[] denom,int N,int[] vals){
if(N==0){
if(ind < denom.length) {
for(int i=ind;i<denom.length;i++)
vals[i] = 0;
}
System.out.println(Arrays.toString(vals));
return;
}
if(ind == (denom.length)) {
vals[ind-1] = 0;
return;
}
int currdenom = denom[ind];
for(int i=0;i<=(N/currdenom);i++){
vals[ind] = i;
printAllCents(ind+1,denom,N-i*currdenom,vals);
}
}
セットJの値を使用してiセントを作成する組み合わせのセットをC（i、J）とします。
Cは次のように定義できます。
（first（J）は、決定論的な方法で集合の要素を取ります）
それはかなり再帰的な関数であることがわかります...そしてメモ化を使用する場合はかなり効率的です;）
# short and sweet with O(n) table memory
#include <iostream>
#include <vector>
int count( std::vector<int> s, int n )
{
std::vector<int> table(n+1,0);
table[0] = 1;
for ( auto& k : s )
for(int j=k; j<=n; ++j)
table[j] += table[j-k];
return table[n];
}
int main()
{
std::cout << count({25, 10, 5, 1}, 100) << std::endl;
return 0;
}
これがPythonでの私の答えです。再帰を使用しません。
def crossprod (list1, list2):
output = 0
for i in range(0,len(list1)):
output += list1[i]*list2[i]
return output
def breakit(target, coins):
coinslimit = [(target / coins[i]) for i in range(0,len(coins))]
count = 0
temp = []
for i in range(0,len(coins)):
temp.append([j for j in range(0,coinslimit[i]+1)])
r=[[]]
for x in temp:
t = []
for y in x:
for i in r:
t.append(i+[y])
r = t
for targets in r:
if crossprod(targets, coins) == target:
print targets
count +=1
return count
if __name__ == "__main__":
coins = [25,10,5,1]
target = 78
print breakit(target, coins)
出力例
...
1 ( 10 cents) 2 ( 5 cents) 58 ( 1 cents)
4 ( 5 cents) 58 ( 1 cents)
1 ( 10 cents) 1 ( 5 cents) 63 ( 1 cents)
3 ( 5 cents) 63 ( 1 cents)
1 ( 10 cents) 68 ( 1 cents)
2 ( 5 cents) 68 ( 1 cents)
1 ( 5 cents) 73 ( 1 cents)
78 ( 1 cents)
Number of solutions = 121
var countChange = function (money,coins) {
function countChangeSub(money,coins,n) {
if(money==0) return 1;
if(money<0 || coins.length ==n) return 0;
return countChangeSub(money-coins[n],coins,n) + countChangeSub(money,coins,n+1);
}
return countChangeSub(money,coins,0);
}
Scala プログラミング言語では、次のようにします。
def countChange(money: Int, coins: List[Int]): Int = {
money match {
case 0 => 1
case x if x < 0 => 0
case x if x >= 1 && coins.isEmpty => 0
case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)
}
}
両方: 高から低まですべての金種を反復し、金種の 1 つを取得し、必要な合計から減算し、残りを再帰します (利用可能な金種が現在の反復値以下になるように制約します)。
ふふ、今はバカみたい。以下に非常に複雑な解決策がありますが、これは解決策であるためそのままにしておきます。簡単な解決策は次のとおりです。
// Generate a pretty string
val coinNames = List(("quarter", "quarters"),
("dime", "dimes"),
("nickel", "nickels"),
("penny", "pennies"))
def coinsString =
Function.tupled((quarters: Int, dimes: Int, nickels:Int, pennies: Int) => (
List(quarters, dimes, nickels, pennies)
zip coinNames // join with names
map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
map (t => t._1 + " " + t._2) // qty name
mkString " "
))
def allCombinations(amount: Int) =
(for{quarters <- 0 to (amount / 25)
dimes <- 0 to ((amount - 25*quarters) / 10)
nickels <- 0 to ((amount - 25*quarters - 10*dimes) / 5)
} yield (quarters, dimes, nickels, amount - 25*quarters - 10*dimes - 5*nickels)
) map coinsString mkString "\n"
これが他の解決策です。この解決策は、各コインが他のコインの倍数であるため、コインで表すことができるという観察に基づいています。
// Just to make things a bit more readable, as these routines will access
// arrays a lot
val coinValues = List(25, 10, 5, 1)
val coinNames = List(("quarter", "quarters"),
("dime", "dimes"),
("nickel", "nickels"),
("penny", "pennies"))
val List(quarter, dime, nickel, penny) = coinValues.indices.toList
// Find the combination that uses the least amount of coins
def leastCoins(amount: Int): Array[Int] =
((List(amount) /: coinValues) {(list, coinValue) =>
val currentAmount = list.head
val numberOfCoins = currentAmount / coinValue
val remainingAmount = currentAmount % coinValue
remainingAmount :: numberOfCoins :: list.tail
}).tail.reverse.toArray
// Helper function. Adjust a certain amount of coins by
// adding or subtracting coins of each type; this could
// be made to receive a list of adjustments, but for so
// few types of coins, it's not worth it.
def adjust(base: Array[Int],
quarters: Int,
dimes: Int,
nickels: Int,
pennies: Int): Array[Int] =
Array(base(quarter) + quarters,
base(dime) + dimes,
base(nickel) + nickels,
base(penny) + pennies)
// We decrease the amount of quarters by one this way
def decreaseQuarter(base: Array[Int]): Array[Int] =
adjust(base, -1, +2, +1, 0)
// Dimes are decreased this way
def decreaseDime(base: Array[Int]): Array[Int] =
adjust(base, 0, -1, +2, 0)
// And here is how we decrease Nickels
def decreaseNickel(base: Array[Int]): Array[Int] =
adjust(base, 0, 0, -1, +5)
// This will help us find the proper decrease function
val decrease = Map(quarter -> decreaseQuarter _,
dime -> decreaseDime _,
nickel -> decreaseNickel _)
// Given a base amount of coins of each type, and the type of coin,
// we'll produce a list of coin amounts for each quantity of that particular
// coin type, up to the "base" amount
def coinSpan(base: Array[Int], whichCoin: Int) =
(List(base) /: (0 until base(whichCoin)).toList) { (list, _) =>
decrease(whichCoin)(list.head) :: list
}
// Generate a pretty string
def coinsString(base: Array[Int]) = (
base
zip coinNames // join with names
map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
map (t => t._1 + " " + t._2)
mkString " "
)
// So, get a base amount, compute a list for all quarters variations of that base,
// then, for each combination, compute all variations of dimes, and then repeat
// for all variations of nickels.
def allCombinations(amount: Int) = {
val base = leastCoins(amount)
val allQuarters = coinSpan(base, quarter)
val allDimes = allQuarters flatMap (base => coinSpan(base, dime))
val allNickels = allDimes flatMap (base => coinSpan(base, nickel))
allNickels map coinsString mkString "\n"
}
たとえば、37 コインの場合は次のようになります。
scala> println(allCombinations(37))
0 quarter 0 dimes 0 nickels 37 pennies
0 quarter 0 dimes 1 nickel 32 pennies
0 quarter 0 dimes 2 nickels 27 pennies
0 quarter 0 dimes 3 nickels 22 pennies
0 quarter 0 dimes 4 nickels 17 pennies
0 quarter 0 dimes 5 nickels 12 pennies
0 quarter 0 dimes 6 nickels 7 pennies
0 quarter 0 dimes 7 nickels 2 pennies
0 quarter 1 dime 0 nickels 27 pennies
0 quarter 1 dime 1 nickel 22 pennies
0 quarter 1 dime 2 nickels 17 pennies
0 quarter 1 dime 3 nickels 12 pennies
0 quarter 1 dime 4 nickels 7 pennies
0 quarter 1 dime 5 nickels 2 pennies
0 quarter 2 dimes 0 nickels 17 pennies
0 quarter 2 dimes 1 nickel 12 pennies
0 quarter 2 dimes 2 nickels 7 pennies
0 quarter 2 dimes 3 nickels 2 pennies
0 quarter 3 dimes 0 nickels 7 pennies
0 quarter 3 dimes 1 nickel 2 pennies
1 quarter 0 dimes 0 nickels 12 pennies
1 quarter 0 dimes 1 nickel 7 pennies
1 quarter 0 dimes 2 nickels 2 pennies
1 quarter 1 dime 0 nickels 2 pennies
私のこのブログ エントリは、 XKCD コミックのフィギュアのナップザックのような問題を解決します。items辞書と値を簡単に変更するとexactcost、問題のすべての解決策も得られます。
問題が最小のコストを使用する変更を見つけることであった場合、最も価値の高いコインをできるだけ多く使用する単純な貪欲なアルゴリズムは、コインと目標額の組み合わせによってはうまくいかない可能性があります。たとえば、値が 1、3、および 4 のコインがあるとします。目標金額が 6 の場合、値 3 のコインを 2 枚ずつ使用できることが容易にわかる場合、貪欲アルゴリズムは値 4、1、および 1 の 3 枚のコインを提案する可能性があります。
public class Coins {
static int ac = 421;
static int bc = 311;
static int cc = 11;
static int target = 4000;
public static void main(String[] args) {
method2();
}
public static void method2(){
//running time n^2
int da = target/ac;
int db = target/bc;
for(int i=0;i<=da;i++){
for(int j=0;j<=db;j++){
int rem = target-(i*ac+j*bc);
if(rem < 0){
break;
}else{
if(rem%cc==0){
System.out.format("\n%d, %d, %d ---- %d + %d + %d = %d \n", i, j, rem/cc, i*ac, j*bc, (rem/cc)*cc, target);
}
}
}
}
}
}
O'reily の著書「Python For Data Analysis」で、このきちんとしたコードを見つけました。遅延実装と int 比較を使用しており、小数を使用して他の宗派に変更できると思います。それがどのように機能するか教えてください！
def make_change(amount, coins=[1, 5, 10, 25], hand=None):
hand = [] if hand is None else hand
if amount == 0:
yield hand
for coin in coins:
# ensures we don't give too much change, and combinations are unique
if coin > amount or (len(hand) > 0 and hand[-1] < coin):
continue
for result in make_change(amount - coin, coins=coins,
hand=hand + [coin]):
yield result/*
* make a list of all distinct sets of coins of from the set of coins to
* sum up to the given target amount.
* Here the input set of coins is assumed yo be {1, 2, 4}, this set MUST
* have the coins sorted in ascending order.
* Outline of the algorithm:
*
* Keep track of what the current coin is, say ccn; current number of coins
* in the partial solution, say k; current sum, say sum, obtained by adding
* ccn; sum sofar, say accsum:
* 1) Use ccn as long as it can be added without exceeding the target
* a) if current sum equals target, add cc to solution coin set, increase
* coin coin in the solution by 1, and print it and return
* b) if current sum exceeds target, ccn can't be in the solution, so
* return
* c) if neither of the above, add current coin to partial solution,
* increase k by 1 (number of coins in partial solution), and recuse
* 2) When current denomination can no longer be used, start using the
* next higher denomination coins, just like in (1)
* 3) When all denominations have been used, we are done
*/
#include <iostream>
#include <cstdlib>
using namespace std;
// int num_calls = 0;
// int num_ways = 0;
void print(const int coins[], int n);
void combine_coins(
const int denoms[], // coins sorted in ascending order
int n, // number of denominations
int target, // target sum
int accsum, // accumulated sum
int coins[], // solution set, MUST equal
// target / lowest denom coin
int k // number of coins in coins[]
)
{
int ccn; // current coin
int sum; // current sum
// ++num_calls;
for (int i = 0; i < n; ++i) {
/*
* skip coins of lesser denomination: This is to be efficient
* and also avoid generating duplicate sequences. What we need
* is combinations and without this check we will generate
* permutations.
*/
if (k > 0 && denoms[i] < coins[k - 1])
continue; // skip coins of lesser denomination
ccn = denoms[i];
if ((sum = accsum + ccn) > target)
return; // no point trying higher denominations now
if (sum == target) {
// found yet another solution
coins[k] = ccn;
print(coins, k + 1);
// ++num_ways;
return;
}
coins[k] = ccn;
combine_coins(denoms, n, target, sum, coins, k + 1);
}
}
void print(const int coins[], int n)
{
int s = 0;
for (int i = 0; i < n; ++i) {
cout << coins[i] << " ";
s += coins[i];
}
cout << "\t = \t" << s << "\n";
}
int main(int argc, const char *argv[])
{
int denoms[] = {1, 2, 4};
int dsize = sizeof(denoms) / sizeof(denoms[0]);
int target;
if (argv[1])
target = atoi(argv[1]);
else
target = 8;
int *coins = new int[target];
combine_coins(denoms, dsize, target, 0, coins, 0);
// cout << "num calls = " << num_calls << ", num ways = " << num_ways << "\n";
return 0;
}
簡単な Java ソリューション:
public static void main(String[] args)
{
int[] denoms = {4,2,3,1};
int[] vals = new int[denoms.length];
int target = 6;
printCombinations(0, denoms, target, vals);
}
public static void printCombinations(int index, int[] denom,int target, int[] vals)
{
if(target==0)
{
System.out.println(Arrays.toString(vals));
return;
}
if(index == denom.length) return;
int currDenom = denom[index];
for(int i = 0; i*currDenom <= target;i++)
{
vals[index] = i;
printCombinations(index+1, denom, target - i*currDenom, vals);
vals[index] = 0;
}
}
さまざまな組み合わせも出力する以下の Java ソリューション。わかりやすい。アイデアは
合計 5
解決策は
5 - 5(i) times 1 = 0
if(sum = 0)
print i times 1
5 - 4(i) times 1 = 1
5 - 3 times 1 = 2
2 - 1(j) times 2 = 0
if(sum = 0)
print i times 1 and j times 2
and so on......
各ループの残りの合計が金種よりも少ない場合、つまり残りの合計 1 が 2 未満の場合は、ループを中断します。
以下の完全なコード
間違いがあれば訂正してください
public class CoinCombinbationSimple {
public static void main(String[] args) {
int sum = 100000;
printCombination(sum);
}
static void printCombination(int sum) {
for (int i = sum; i >= 0; i--) {
int sumCopy1 = sum - i * 1;
if (sumCopy1 == 0) {
System.out.println(i + " 1 coins");
}
for (int j = sumCopy1 / 2; j >= 0; j--) {
int sumCopy2 = sumCopy1;
if (sumCopy2 < 2) {
break;
}
sumCopy2 = sumCopy1 - 2 * j;
if (sumCopy2 == 0) {
System.out.println(i + " 1 coins " + j + " 2 coins ");
}
for (int k = sumCopy2 / 5; k >= 0; k--) {
int sumCopy3 = sumCopy2;
if (sumCopy2 < 5) {
break;
}
sumCopy3 = sumCopy2 - 5 * k;
if (sumCopy3 == 0) {
System.out.println(i + " 1 coins " + j + " 2 coins "
+ k + " 5 coins");
}
}
}
}
}
}
Java ソリューション
import java.util.Arrays;
import java.util.Scanner;
public class nCents {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int cents=input.nextInt();
int num_ways [][] =new int [5][cents+1];
//putting in zeroes to offset
int getCents[]={0 , 0 , 5 , 10 , 25};
Arrays.fill(num_ways[0], 0);
Arrays.fill(num_ways[1], 1);
int current_cent=0;
for(int i=2;i<num_ways.length;i++){
current_cent=getCents[i];
for(int j=1;j<num_ways[0].length;j++){
if(j-current_cent>=0){
if(j-current_cent==0){
num_ways[i][j]=num_ways[i-1][j]+1;
}else{
num_ways[i][j]=num_ways[i][j-current_cent]+num_ways[i-1][j];
}
}else{
num_ways[i][j]=num_ways[i-1][j];
}
}
}
System.out.println(num_ways[num_ways.length-1][num_ways[0].length-1]);
}
}
このパズルを C# で実装しましたが、他の回答とはちょっと違うと思います。さらに、アルゴリズムをより理解しやすくするためにコメントを追加しました。とても素敵なパズルでした。
大きいコインから始めて、すべてを見Q,D,Nて、残りをペニーで埋めます。
だから私は 0 クォーター、0 ダイム、0 ニッケル、残りはペニーから始めることができます。
($Amount / $Change) + 1$Amount は入力パラメータで、$Change は [Q]uarter または [D]ime または [N]ickel です。したがって、入力パラメータが $1 であると仮定すると、
qLoopコード内の変数dLoopコード内の変数nLoopコード内の変数各ループで、外側のループからのリマインダーを使用する必要があることに注意してください。
例として、1 四半期 (ここで q は 1) を選択すると、$1 - 0.25 が内側のループ (Dime ループ) に残ります。
static void CoinCombination(decimal A)
{
decimal[] coins = new decimal[] { 0.25M, 0.10M, 0.05M, 0.01M };
// Loop for Quarters
int qLoop = (int)(A / coins[0]) + 1;
for (int q = 0; q < qLoop; q++)
{
string qS = $"{q} quarter(s), ";
decimal qAmount = A - (q * coins[0]);
Console.Write(qS);
// Loop for Dimes
int dLoop = (int)(qAmount / coins[1]) + 1;
for (int d = 0; d < dLoop; d++)
{
if (d > 0)
Console.Write(qS);
string dS = $"{d} dime(s), ";
decimal dAmount = qAmount - (d * coins[1]);
Console.Write(dS);
// Loop for Nickels
int nLoop = (int)(dAmount / coins[2]) + 1;
for (int n = 0; n < nLoop; n++)
{
if (n > 0)
Console.Write($"{qS}{dS}");
string nS = $"{n} nickel(s), ";
decimal nAmount = dAmount - (n * coins[2]);
Console.Write(nS);
// Fill up with pennies the remainder
int p = (int)(nAmount / coins[3]);
string pS = $"{p} penny(s)";
Console.Write(pS);
Console.WriteLine();
}
Console.WriteLine();
}
Console.WriteLine();
}
}
出力
Isogenic Game Engine を使用して HTML5 で作成している BlackJack ゲームで、非常に単純なループを使用してこれを解決しました。カードの上にあるブラックジャック テーブルの賭け金から賭けを構成するために使用されたチップを示すブラックジャック ゲームのビデオを見ることができます: http://bit.ly/yUF6iw
この例では、betValue は、「コイン」または「チップ」などに分割したい合計値に等しくなります。
chipValues 配列項目をコインまたはチップの価値に設定できます。アイテムが最低額から最高額 (ペニー、ニッケル、10 セント硬貨) に並べられていることを確認してください。
JavaScript は次のとおりです。
// Set the total that we want to divide into chips
var betValue = 191;
// Set the chip values
var chipValues = [
1,
5,
10,
25
];
// Work out how many of each chip is required to make up the bet value
var tempBet = betValue;
var tempChips = [];
for (var i = chipValues.length - 1; i >= 0; i--) {
var chipValue = chipValues[i];
var divided = Math.floor(tempBet / chipValue);
if (divided >= 1) {
tempChips[i] = divided;
tempBet -= divided * chipValues[i];
}
if (tempBet == 0) { break; }
}
// Display the chips and how many of each make up the betValue
for (var i in tempChips) {
console.log(tempChips[i] + ' of ' + chipValues[i]);
}
明らかに最後のループを実行する必要はなく、最終的な配列値を console.log に記録するだけです。