Написать программу, которая определяет количество способов выплатить сумму n c помощью купюр достоинством 5,10,20,100 и монетой в 1 рубль

Question

#define _CRT_SECURE_NO_WARNINGS
#include <locale.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <Windows.h>
#include <conio.h>

int main()
{
    int n, k,k1, k5, k20, k100;
    printf("Vvedite vash cash money n:");
    scanf_s("%d", &n);
    k = 0;
    for(k100=0; k100<=n/10;k100++)
        for(k20=0;k20<=(n-10*k100)/20; k20++)
            for (k5 = 0; k5 <= (n - 10 * k100 - 20 * k20) / 2; k5++)
            {
                k1 = n - k100 - 20 * k20 - 5 * k5;
                printf("\n k=%d ", k100);
                printf("\n k=%d", k20);
                printf("\n k=%d", k5);
                printf("\n k=%d", k1);
                k = k + 1;
            } 
    printf("\nChislo sposobov ravno k= \n", k);
    system("pause");
    return 0;
}

Попробовал сделать еще чтобы красиво выводило, но как-то криво вышло

Answer 1

Самый простой способ:

int main()
{
    int n;
    scanf("%d",&n);
    for(int k100 = n/100; k100 >= 0; --k100)
    {
        for(int k20 = (n-k100*100)/20; k20 >= 0; --k20)
        {
            for(int k10 = (n-k100*100-k20*20)/10; k10 >= 0; --k10)
            {
                for(int k5 = (n-k100*100-k20*20-k10*10)/5; k5 >= 0; --k5)
                {
                    int k1 = n-k100*100-k20*20-k10*10-k5*5;

                    for(int i = 0; i < k100; ++i) printf("100 ");
                    for(int i = 0; i < k20; ++i) printf("20 ");
                    for(int i = 0; i < k10; ++i) printf("10 ");
                    for(int i = 0; i < k5; ++i) printf("5 ");
                    for(int i = 0; i < k1; ++i) printf("1 ");
                    puts("");
                }
            }
        }
    }
}

Только вот вам точно надо не просто посчитать количество, а и вывести? Для суммы в 1000 - это 543686 вариантов, общий размер вывода - более 315 Мбайт... Просто если надо посчитать только количество вариантов - то тогда куда умнее работать динамическим программированием, и это совсем другая задача. С выводом всех вариантов быстрее не справитесь, как бы этот ответ не минусовали :)

Как выяснилось, нужно только количество способов, а не их перечисление...

Вот расчет ТОЛЬКО количества способов. Сумма до миллиона, кому надо больше - сами догадайтесь, что увеличить.

#include <stdio.h>

int coins[5] = { 1, 5, 10, 20, 100 };

long long int save[1000001][5];

long long int get(int n, int k)
{
    if (n < 0 || k < 0) return 0;
    if (k == 0)
    {
        if (n == coins[k]) return 1;
        if (n == 0) return 1;
    }
    else if (n == 0) return 1;

    if (save[n][k]) return save[n][k];
    return (save[n][k] = get(n-coins[k],k) + get(n,k-1));
}
 
int main(int argc, const char * argv[])
{
    int n;
    scanf("%d",&n);
    printf("%d - %lld\n",n,get(n,4));
}

https://ideone.com/68CAS2

БЛОГ НА HUSL

Написать программу, которая определяет количество способов выплатить сумму n c помощью купюр достоинством 5,10,20,100 и монетой в 1 рубль

Ответы (1 шт):