Определите минимальное количество монет, необходимое для внесения изменений, используя жадный подход

Question

В качестве задания для моего курса по разработке и анализу алгоритмов меня попросили определить минимальное количество монет, необходимое для внесения изменений, используя жадный подход. Я придумал этот интуитивный подход:

#include<stdio.h>
#include<stdlib.h>

int main(){
  int hundreds=0,tens=0,ones=0,sum=0;

  printf("Enter a sum of money in range 1 to 999\n");
  scanf("%d",&sum);
  while(sum!=0) {
    if (sum<10&&sum>=1){
      ones=sum/1;
      sum-=ones;
    }
    else if(sum>=10&&sum<100){
      tens=sum/10;
      sum-=tens*10;
    }
    else if(sum>=100&&sum<=999){
      hundreds=sum/100;
      sum-=hundreds*100;
    }
    else{
      printf("Error");
      exit(0);
    }
  }

  printf("%d $100, %d $10, %d $1",hundreds,tens,ones);
  return 0;
}

Этот подход жадный? Как мне доказать, что программа правильная и использует жадный подход?

Answer 1

Это действительно жадный подход, но вам нужно изменить порядок if-then-else.В общем, жадный означает потреблять в текущий момент наибольшее количество, которое вы можете потреблять.

Сначала вам нужно проверить, какая самая большая монета.Нет необходимости в цикле while.

if(sum>=100) {
  hundreds=sum/100;
  sum-=hundreds*100;
}
if(sum>=10){
  tens=sum/10;
  sum-=tens*10;
} 
ones = sum; 

Answer 2

Ваш код недостаточно жадный, потому что он может быть худшим:

#include<stdio.h>
#include<stdlib.h>

int main(){
  int hundreds=0,tens=0,ones=0,sum=0;

  printf("Enter a sum of money in range 1 to 999\n");
  if ((scanf("%d",&sum) == 1) && (sum >= 1) && (sum <= 999)) {
    while(sum!=0) {
      if (sum<10&&sum>=1){
        ones += 1;
        sum -= 1;
      }
      else if(sum>=10&&sum<100){
        tens += 1;
        sum -= 10;
      }
      else if(sum>=100&&sum<=999){
        hundreds += 1;
        sum -= 100;
      }
      else{ /* impossible case in fact */
        printf("Error");
        exit(0);
      }
    }

    printf("%d $100, %d $10, %d $1\n",hundreds,tens,ones);
  }
  return 0;
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra g.c
pi@raspberrypi:/tmp $ ./a.out
Enter a sum of money in range 1 to 999
997
9 $100, 9 $10, 7 $1

---

Как мне доказать, что программа правильная

(жадный) способ доказать, что код верен, - использовать грубую силу, чтобы проверить все результаты от 1 до 999:

#include<stdio.h>
#include<stdlib.h>

int main(){
  int n;

  for (n = 1; n <= 999; ++n) {
    /* the algo */
    int hundreds=0,tens=0,ones=0, sum = n;

    while(sum!=0) {
      if (sum<10&&sum>=1){
        ones += 1;
        sum -= 1;
      }
      else if(sum>=10&&sum<100){
        tens += 1;
        sum -= 10;
      }
      else if(sum>=100&&sum<=999){
        hundreds += 1;
        sum -= 100;
      }
      else{ /* impossible case in fact */
        printf("Error");
        exit(0);
      }
    }

    /* check */
    if ((hundreds*100 + tens*10 + ones) != n) {
      printf("error for %d : %d $100, %d $10, %d $1\n",n, hundreds,tens,ones);
      exit(0);
    }
  }
  puts("all ok");
  return 0;
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra g.c
pi@raspberrypi:/tmp $ ./a.out
all ok

Answer 3

следующий предложенный код:

1. чисто компилирует
2. не включает заголовочные файлы, содержимое которых не используется
3. следует аксиоме: только один оператор на строку и (самое большее) одно объявление переменной на оператор.
4. выполняет желаемую функциональность
5. выполняет соответствующую проверку ошибок
6. выполняет «жадный» алгоритм потребления как можно большего количества «денег» как можно быстрее, используя наименьшее количество «счетов»

и теперь предложенный код:

#include <stdio.h>


int main( void )
{
    int sum;

    do
    {
        printf("Enter a sum of money in range 1 to 999\n");
        if( scanf("%d",&sum) != 1)
        {
            fprintf( stderr, "scanf failed\n");
            return -1;
        }       
    } while( sum<0 || sum>999 );

    int hundreds = sum/100;
    sum          = sum % 100;
    int tens     = sum/10;
    sum          = sum % 10;
    int ones     = sum;

    printf("%d $100, %d $10, %d $1\n",hundreds,tens,ones);
}

В предлагаемом коде игнорируются (американские) счета на сумму 50, 20, 5 и 2 долларов США