Пример 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
Си в UNIX

Назад | Содержание | Вперед