fork(2) download 
  1. <?php
  2. mb_internal_encoding('utf-8');
  3.  
  4. // Банкомат
  5.  
  6. // Требуемая сумма
  7. $amount = 6600;
  8.  
  9. // Ответ:  сумма размены "0" => "$amount", номиналы и их количество "bill" => "count"
  10. $ans = array ($amount); 
  11.  
  12. // Номиналы банкнот, количество
  13. $bills = Array (
  14.                 1 => Array (200, 3),
  15.                 2 => Array (500, 1),
  16.                 3 => Array (2000, 4),
  17.                 4 => Array (5000, 1)
  18. );
  19.  
  20. $INF=1000000;           // Значение константы
  21. $Results[$i][$m];       // Массив в котором мы храним результат
  22.  
  23. // Для всех сумм банкнотой 0 размен не ввозможен
  24. for ($i = 0; $i<=$amount    ; $i++) {    
  25.     $Results[0][$i] = $INF;}
  26.  
  27. // Если просят разменять сумму 0, гордо протягиваем пустую ладонь.
  28. for ($i = 0; $i<=4; $i++) {    
  29.     $Results[$i][0] = 0;
  30. }
  31.  
  32. // m - сумма, которую нужно выдать, увеличиваем сумму от 1 до требуемой $amount
  33. for($m=1; $m<=$amount; $m++) {
  34.  
  35.     // Перебираем все номиналы банкнот
  36.     foreach ($bills as $i => $value) {
  37.  
  38.         // По умолчанию, текущую сумму можно выдать банкнотой предыдущего номинала.                       
  39.         $Results[$i][$m] =  $Results[$i-1][$m];
  40.  
  41.         // Есть ли банкноты текущего номинала и текущую сумму можно разменять текущим номиналом           
  42.         if ($value[1]>0 && $m>= $value[0]) {
  43.  
  44.             /*  Перебераем количество банкнот текущего номинала
  45.                 от минимально требуемого (или того что есть) до 1 */
  46.             for ($l=min($value[1], intval(floor($m/$value[0]))); $l>=1; $l--) {
  47.  
  48.                 /*  Выбираем минимальное количество банкнот для размена между данной банкнотой и предыдущей
  49.                     если сумму меняем текущей банкнотой, то записываем количество банкнот
  50.                     для данного номинала и количество монет предыдущих номиналов, для размена остатка суммы  */
  51.                 $Results[$i][$m] =  min($Results[$i][$m], $Results[$i-1][$m - $l * $value[0]] + $l); 
  52.             }
  53.         }
  54.     }
  55. }   
  56.  
  57. // Рекурсивная Няша, считает банкноты для размены требуемой суммы для Анона
  58. // аргументы: массив с результатом, банкноты (номинал/кол-во),  кол-во номиналов, сумма для выдачи
  59. function findAnsRecur($Results, $bills, $i, $amount, $ans) {
  60.  
  61.     if ($Results[$i][$amount] == 0) { // финиш
  62.         printAns ($ans);
  63.  
  64.     /*  если для размена текущей суммы количество банкнот прошлого номинала нужно столько же,
  65.         то переходим к предыдущему номиналу */
  66.     } elseif ($Results[$i-1][$amount] == $Results[$i][$amount]) { 
  67.         $i--;
  68.         findAnsRecur($Results, $bills, $i, $amount, $ans);
  69.  
  70.     /*  если текущую сумму можно несколько раз выдать текущей банкнотой, делаем это,
  71.         и добавляем текущую банкноту к результату и уменьшаем сумму выдачи на текущий номинал*/
  72.     } elseif ($Results[$i][$amount] >= $Results[$i][$amount-$bills[$i][0]]) {
  73.         $ans[$bills[$i][0]]++; 
  74.         $amount -= $bills[$i][0];
  75.         findAnsRecur($Results, $bills, $i, $amount, $ans);
  76.  
  77.     /*  если остаток текущей суммы, после размена текущей банкнотой, можно выдать только
  78.         банкнотой предыдущего номинала, так тому и быть, + 1 к результату, переходим к
  79.         предыдущему номиналу и уменьшаем сумму выдачи на текущий номинал */   
  80.     } else {  
  81.         //$ans[] = $bills[$i][0];
  82.         $ans[$bills[$i][0]]++;
  83.         $i--;
  84.         $amount -= $bills[$i][0];    
  85.         findAnsRecur($Results, $bills, $i, $amount, $ans);  
  86.     }
  87. }
  88. // Проверяем существует ли ответ для данной суммы, зовем рекурсивную Няшу или ругаемся.
  89. function checkAns($Results, $bills, $i, $amount, $ans) {
  90.     if ($Results[$i][$amount]==$INF) {
  91.         $ans=NULL;      
  92.     } else {
  93.         $ans = findAnsRecur($Results, $bills, $i, $amount, $ans);
  94.     }
  95. }
  96.  
  97. // Выводим результат
  98. function printAns ($ans) {
  99.  
  100.     echo "Сумма: {$ans[0]}\n";
  101.  
  102.     if ($ans==NULL) {
  103.         echo "Требуемую сумму выдать невозможно";
  104.     } else {
  105.         echo "Выдача возможна, число купюр:\n";
  106.  
  107.         foreach($ans as $bill=>$count) {
  108.             if ($bill!=0) {
  109.                 echo "{$count}x{$bill}" . " ";
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115. // Запускаем проверку
  116. checkAns($Results, $bills, count($bills), $amount, $ans) ;
  117.  
  118. ?>
Success #stdin #stdout #stderr 0.11s 52472KB
comments (?)
stdin 
Standard input is empty
stdout 
Сумма: 6600
Выдача возможна, число купюр:
3x2000 3x200
stderr 
PHP Notice:  Undefined variable: Results in /home/4gaZXo/prog.php on line 21
PHP Notice:  Undefined variable: i in /home/4gaZXo/prog.php on line 21
PHP Notice:  Undefined variable: m in /home/4gaZXo/prog.php on line 21
PHP Notice:  Undefined variable: INF in /home/4gaZXo/prog.php on line 90
PHP Notice:  Undefined offset: 2000 in /home/4gaZXo/prog.php on line 73
PHP Notice:  Undefined offset: 200 in /home/4gaZXo/prog.php on line 73
https://ideone.com/y7Fxkp
language:
PHP (php 7.3.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!