同学找我写了一个简单的找零的贪婪算法，中间遇到了一个不了解的知识点，所以顺便记录下来吧

问题描述：

日常交易中找遇到找零钱时，您可能希望最大限度地减少给客户找零的硬币数量，以免您用完了硬币或惹恼客户！。幸运的是，计算机科学已经为收银员提供了最小化硬币数量的方法：贪婪算法。

贪婪算法是一种“在寻找答案时始终采用最佳局部解决方案的算法”。贪婪算法为某些优化问题找到了整体或全局最优解决方案，但对于某些其他问题，只能找到次优的满意解决方案。

假设收银员的抽屉里有用不完的四种硬币：25¢，10¢，5¢和1¢，他需要找给客户找零。如何决定将哪些硬币交给顾客呢？如果你欠某个顾客41美分，那么局部最佳解决方案是拿出一个25美分。 这会将41¢问题减少到16¢问题，因为41 - 25 = 16.也就是说，余数是一个类似但更小的问题。毋庸置疑，另一个25美分的价格会太大，所以你会转向拿出一个10美分，问题的尺度减少到了6美分的问题。这时，你在拿出一个5¢，最后一个1¢，问题就解决了。客户收到一个25¢，10¢，5¢和1¢：总共四个硬币。

实现细节

程序命名为 cash.c。实现的功能是先询问用户找零的数目，然后打印出组成这些零钱的最少的硬币数目。

  • 定义并调用函数 get_positive_float 从用户那里得到一个正的浮点数，用 printf 把答案打印出来。假设收银员的抽屉里只有用不完的四种硬币：25¢，10¢，5¢和1¢，
    • 如果顾客交给收银员$10买 25¢ 的报纸，需要找零$9.75，运行程序时输入9.75.
  • 用户的输入如果不是合法的浮点数，或者是负的浮点数，程序应该不断提醒用户输入正的浮点数。
  • 最后输出一个整数（最少的硬币数量）加回车。
  • 注意浮点数内在的不精确特性。计算找零方案时可以考虑把输入的元转化成分 即把输入的数字从 float 转化位 int，防止不精确带来的误差。
  • 计算完分后，需要调用定义在库math.h中的函数 round,. 将输入四升五入至最近的整数。如：运行输入找零 0.20元, 下面的语句可以找零的元转换为分：
  • int coins = round(dollars * 100);

这样可以把0.20转换为 20.

代码如下：

#include <stdio.h>
int get_positive_float();
int main(){
    int a[]={25,10,5,1};
    int b[]={0,0,0,0};
    bool flag;
    int value1=get_positive_float();
    for(;value1;)
    {
        flag=false;
        if(value1>=a[0])
        {value1-=a[0];b[0]++;}
        else if(value1>=a[1])
        {value1-=a[1];b[1]++;}
        else if(value1>=a[2])
        {value1-=a[2];b[2]++;}
        else if(value1>=a[3])
        {value1-=a[3];b[3]++;}
        else {flag=true; break;}
        
    }
    printf("%d\n",b[0]+b[1]+b[2]+b[3]);
    getchar();
    getchar();
    return 0;
}

int get_positive_float()
{
    float value=0;
    printf("请输入要找零的金额:\n");
    while (1)
    {
    if(scanf("%f",&value)&&value>=0)  
    return (int)value*100;
    else {printf("请输入合法的数字\n");scanf("%s");continue;}
    }
}

测试截图：

image-20210607001931127

为了实现判断输入内容是否合法，其中的get_positive_float函数，我最开始是这样写的

int get_positive_float()
{
    float value=0;
    printf("请输入要找零的金额:\n");
    while (1)
    {
    if(scanf("%f",&value)&&value>=0)  
    return (int)value*100;
    else {printf("请输入合法的数字\n");continue;}
    }
}

如果输入数字，应该是没有什么问题的，但是当输入一个字符的时候，炸了，疯狂执行else不停

问了问大佬们才了解到

scanf读入失败会把输入留在缓冲区

格式化字符串(format string)　　

　　格式化字符串规定了 scanf 等函数如何从输入缓冲 stdin 中读取数据，其组成字符的含义如下所示：

　　(1)空白字符(whitespace)。**scanf 会读取并忽略在 stdin 中下一个非空白字符之前的所有空白字符(空格、换行和 tab)**，然后读取格式化字符串中规定格式的数据。若格式化字符串中包含空白字符，则该空白字符会与输入缓冲区中任意数量的连续空白字符相匹配，并将其从缓冲区中清除(包括0个)。例如格式化字符串”%d %d”，会要求 scanf 首先从缓冲区中读取一个整型(若之前存在空白字符则跳过)，再跳过输入缓冲区中连续的空白字符(与格式化字符串中的空白字符匹配)，最后再读取一个整形；

　　(2)非空白字符(non whitespace)。对于格式化字符串中既非空白字符又不是格式说明符(format specifier,由%标识)的一部分的字符，scanf 会尝试从 stdin 中读取输入，并将输入与该字符比较，若匹配，则继续进行后续读取，若不匹配，则函数返回错误信息；

　　(3)格式说明符。以 % 开头的用于指定输入数据格式的字符。如 %d 指定需要读取一个整形，%s 需要读取一个字符串。scanf 等函数首先根据格式说明符尝试去解析 stdin 中的数据，如对于 %d ，scanf 会尝试对 stdin 中已有数据以整型的格式进行解析。若解析成功，则将上述解析结果存放到指定的内存中，若解析失败，如 stdin 中仅存在一个字符 ‘a’，scanf 会退出并返回，但是上述不匹配的数据并不会从缓冲区中清除，后续的 scanf 调用仍从上述输入开始读取；

摘自scanf函数读取缓冲区数据的问题 - yhjoker - 博客园 (cnblogs.com)，这篇文章感觉对scanf之类输入函数讲的挺好的。

也就是说，scanf读入失败后，输入的东西还在缓冲区中，下次执行scanf还是从原处继续读上一次的内容，所以死循环了

然后一位大佬提示说，可以使用%s再读一遍，清一下缓存

然后就有了最终版：

int get_positive_float()
{
    float value=0;
    printf("请输入要找零的金额:\n");
    while (1)
    {
    if(scanf("%f",&value)&&value>=0)  
    return (int)value*100;
    else {printf("请输入合法的数字\n");scanf("%s");continue;}
    }
}

一个测试工程师走进一家酒吧，要了一杯啤酒
一个测试工程师走进一家酒吧，要了一杯咖啡
一个测试工程师走进一家酒吧，要了0.7杯啤酒
一个测试工程师走进一家酒吧，要了-1杯啤酒
一个测试工程师走进一家酒吧，要了2^32杯啤酒
一个测试工程师走进一家酒吧，要了一杯洗脚水
一个测试工程师走进一家酒吧，要了一杯蜥蜴
一个测试工程师走进一家酒吧，要了一份asdfQwer@24dg!&*(@
一个测试工程师走进一家酒吧，什么也没要
一个测试工程师走进一家酒吧，又走出去又从窗户进来又从后门出去从下水道钻进来
一个测试工程师走进一家酒吧，又走出去又进来又出去又进来又出去，最后在外面把老板打了一顿
一个测试工程师走进一
一个测试工程师走进一家酒吧，要了一杯烫烫烫的锟斤拷
一个测试工程师走进一家酒吧，要了NaN杯Null
1T测试工程师冲进一家酒吧，要了500T啤酒咖啡洗脚水野猫狼牙棒奶茶
1T测试工程师把酒吧拆了
一个测试工程师化装成老板走进一家酒吧，要了500杯啤酒并且不付钱
一万个测试工程师在酒吧门外呼啸而过
一个测试工程师走进一家酒吧，要了一杯啤酒’;DROP TABLE 酒吧
测试工程师们满意地离开了酒吧。
然后一名顾客点了一份炒饭，酒吧炸了

以上