Размен 100 рублей монетами 2, 5 и 10 [требует правки]

383

20 октября 2017, 12:14

Здравствуйте. Как посчитать аналитически число вариантов размена 100 рублей монетами по 10, 5 и 2 рубля? Как выглядит код прямого перебора?

UPD. Благодарю @Alexander Zonov за код на C. Вот код на Java:

public class Main {
    public static void main(String[] args) {
        int i, j, k, count = 0;
        for (i = 0; i <= 100; i+=2)
            for (j = i; j <= 100; j+=5)
                for (k = j; k <= 100; k+=10)
                    if (k == 100){
                        System.out.printf("%d * 2 + %d * 5 + %d * 10\n", i/2, (j-i)/5, (k-j)/10);
                        count++;
                    }
        System.out.println("Число вариантов равно " + count);
    }
}

Вот код на C++:

#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
    const int SUM = 100;
    int i, j, k, count = 0;
    for (i = 0; i <= SUM; i+=2)
        for (j = i; j <= SUM; j+=5)
            for (k = j; k <= SUM; k+=10)
                if (k == SUM){
                    count++;
                    printf("%d * 2 + %d * 5 + %d * 10, count %d\n", i/2, (j-i)/5, (k-j)/10, count);
                }       
    printf("Число вариантов размена равно %d\n", count);
    return 0;
}

Answer 1

Простейший вариант аналитически получается как коэффициент при в разложении в степенной ряд

(см. задачу 7.2.1.4-11 из Искусства программирования Кнута, том 4А).

Там же можно найти соответствующие алгоритмы. Замечу только, что для реально больших чисел и большого количества номиналов можно просто не дожить до конца тупого перебора.

Answer 2

Тупым перебором примерно так:

#include <stdio.h>
int main()
{
    int i, j, k;
    for (i = 0; i <= 100; i+=2)
        for (j = i; j <= 100; j+=5)
            for (k = j; k <= 100; k+=10)
                if (k == 100)
                    printf("%d * 2 + %d * 5 + %d * 10\n", i/2, (j-i)/5, (k-j)/10);
    return 0;
}

https://ideone.com/4egbO3

Вот тот же "метод тыка", только без фиксированных циклов (в ответ на часть критики в комментариях):

int main()
{
    int M = 1000;
    int numbers[] = {17, 19, 23, 29, 31, 37};
    int N = sizeof(numbers) / sizeof(numbers[0]);
    int values[N], count = 0, i, v;
    for (i = 0; i < N; i++) values[i] = 0;
    while (1) {
        if ((M - values[0]) % numbers[0] == 0)
            count++;
        for (i = 1; i < N; i++) {
            v = values[i] + numbers[i];
            if (v > M) continue;
            break;
        }
        if (i == N) break;
        while (i >= 0) values[i--] = v;
    }
    printf("count = %d\n", count);
    return 0;
}

https://ideone.com/O5OwR7