В отношении JavaScript:
=== оператор работает то же == оператор, но это требует, чтобы его операнды не имели только того же значения, но также и того же типа данных.
, Например, образец ниже отобразит 'X и Y, равны', но не 'X и Y идентичны'.
var x = 4;
var y = '4';
if (x == y) {
alert('x and y are equal');
}
if (x === y) {
alert('x and y are identical');
}
Ниже приведена рекурсия с Java-решением для памятки. ниже одного у нас есть 1,2,3,5 в качестве монет и 200 в качестве целевой суммы.
countCombinations(200,new int[]{5,2,3,1} , 0, 0,new Integer[6][200+5]);
static int countCombinations(Integer targetAmount, int[] V,int currentAmount, int coin, Integer[][] memory){
//Comment below if block if you want to see the perf difference
if(memory[coin][currentAmount] != null){
return memory[coin][currentAmount];
}
if(currentAmount > targetAmount){
memory[coin][currentAmount] = 0;
return 0;
}
if(currentAmount == targetAmount){
return 1;
}
int count = 0;
for(int selectedCoin : V){
if(selectedCoin >= coin){
count += countCombinations(targetAmount, V, currentAmount+selectedCoin, selectedCoin,memory);
}
}
memory[coin][currentAmount] = count;
return count;
}
Первая идея:
int combinations = 0;
for (int i = 0; i * 7 <=15; i++) {
for (int j = 0; j * 6 + i * 7 <= 15; j++) {
combinations++;
}
}
(в этом случае '< =' является излишним, но требуется для более общего решения, если вы решите изменить свои параметры)
Решение, предоставленное @Jordi, приятно, но работает крайне медленно. Вы можете попробовать ввести 600 для этого решения и посмотреть, насколько он медленный.
Моя идея - использовать динамическое программирование снизу вверх.
Обратите внимание, что обычно возможная комбинация для денег = m и монет {a, b, c} равна комбинации для
Если ни одна монета не доступна или доступные монеты не могут покрыть требуемую сумму денег, она должна заполнить 0 в блоке соответственно. Если сумма денег равна 0, она должна быть заполнена 1.
public static void main(String[] args){
int[] coins = new int[]{1,2,3,4,5};
int money = 600;
int[][] recorder = new int[money+1][coins.length];
for(int k=0;k<coins.length;k++){
recorder[0][k] = 1;
}
for(int i=1;i<=money;i++){
//System.out.println("working on money="+i);
int with = 0;
int without = 0;
for(int coin_index=0;coin_index<coins.length;coin_index++){
//System.out.println("working on coin until "+coins[coin_index]);
if(i-coins[coin_index]<0){
with = 0;
}else{
with = recorder[i-coins[coin_index]][coin_index];
}
//System.out.println("with="+with);
if(coin_index-1<0){
without = 0;
}else{
without = recorder[i][coin_index-1];
}
//System.out.println("without="+without);
//System.out.println("result="+(without+with));
recorder[i][coin_index] = with+without;
}
}
System.out.print(recorder[money][coins.length-1]);
}
package algorithms;
import java.util.Random;
/**`enter code here`
* Owner : Ghodrat Naderi
* E-Mail: Naderi.ghodrat@gmail.com
* Date : 10/12/12
* Time : 4:50 PM
* IDE : IntelliJ IDEA 11
*/
public class CoinProblem
{
public static void main(String[] args)
{
int[] coins = {1, 3, 5, 10, 20, 50, 100, 200, 500};
int amount = new Random().nextInt(10000);
int coinsCount = 0;
System.out.println("amount = " + amount);
int[] numberOfCoins = findNumberOfCoins(coins, amount);
for (int i = 0; i < numberOfCoins.length; i++)
{
if (numberOfCoins[i] > 0)
{
System.out.println("coins= " + coins[i] + " Count=" + numberOfCoins[i] + "\n");
coinsCount += numberOfCoins[i];
}
}
System.out.println("numberOfCoins = " + coinsCount);
}
private static int[] findNumberOfCoins(int[] coins, int amount)
{
int c = coins.length;
int[] numberOfCoins = new int[coins.length];
while (amount > 0)
{
c--;
if (amount >= coins[c])
{
int quotient = amount / coins[c];
amount = amount - coins[c] * quotient;
numberOfCoins[c] = quotient;
}
}
return numberOfCoins;
}
}
Очень просто с рекурсией:
def countChange(money: Int, coins: List[Int]): Int = {
def reduce(money: Int, coins: List[Int], accCounter: Int): Int = {
if(money == 0) accCounter + 1
else if(money < 0 || coins.isEmpty) accCounter
else reduce(money - coins.head, coins, accCounter) + reduce(money, coins.tail, accCounter)
}
if(money <= 0 || coins.isEmpty) 0
else reduce(money, coins, 0)
}
Это пример в SCALA