Пример 1

/* Задача о размене монеты:
 * Поиск всех возможных коэффициентов a0 .. an разложения числа  S
 * в виде
 *      S = a0 * c0 + a1 * c1 + ... + an * cn
 * где веса c0 .. cn заданы заранее и упорядочены.
 * Веса и коэффициенты неотрицательны (ai >= 0, ci >= 0).
 */

#include <stdio.h>

/* Достоинства разменных монет (веса ci) */
int cost[] = {
        1, 2, 3, 5, 10, 15, 20, 50, 100, 300, 500  /* копеек */
};

#define N       (sizeof cost / sizeof(int))
int count[ N ];         /* число монет данного типа (коэффициенты ai) */
long nvar;              /* число вариантов */

main( ac, av ) char *av[];
{
    int coin;

    if( ac == 1 ){
        fprintf( stderr, "Укажите, какую монету разменивать: %s число\n",
                av[0] );
        exit(1);
    }
    coin = atoi( av[1] );
    printf( "          Таблица разменов монеты %d коп.\n", coin );
printf( " Каждый столбец содержит количество монет указанного достоинства.\n" );
printf( "-------------------------------------------------------------------\n" );
printf( "| 5р. | 3р. | 1р. | 50к.| 20к.| 15к.| 10к.|  5к.|  3к.|  2к.|  1к.|\n" );
printf( "-------------------------------------------------------------------\n" );

    change( N-1, coin );

printf( "-------------------------------------------------------------------\n" );
    printf( "Всего %ld вариантов\n", nvar );
}

/* рекурсивный размен */
change( maxcoin, sum )
        int sum;        /* монета, которую меняем */
        int maxcoin;    /* индекс по массиву cost[] монеты максимального
                         * достоинства, допустимой в данном размене.
                         */
{
        register i;

        if( sum == 0 ){  /* вся сумма разменяна */
                /* распечатать очередной вариант */
                putchar( '|' );
                for( i = N-1 ; i >= 0 ; i-- )
                        if( count[i] )
                            printf(" %3d |", count[ i ] );
                        else
                            printf("     |" );
                putchar( '\n' );
                nvar++;
                return;
        }
        if( sum >= cost [ maxcoin ] ){
            /* если можно выдать монету достоинством cost[maxcoin] ,
             * то выдать ее:
             */
            count[ maxcoin ] ++;   /* посчитали выданную монету */

       /* размениваем остаток суммы :
        * Первый аргумент - может быть можно дать еще одну такую монету ?
        * Второй аргумент - общая сумма убавилась на одну монету cost[maxcoin].
        */
            change( maxcoin, sum - cost[maxcoin] );

            count[ maxcoin ] --;   /* ... Теперь попробуем иной вариант ... */
        }

        /* попробовать размен более мелкими монетами */
        if( maxcoin )
                change( maxcoin-1, sum );
}

© Copyright А. Богатырев, 1992-95 www.abyss-group.narod.ru
Си в UNIX