排队找零问题：5元商品的巧妙排队方案

有10个人排队购买一件价格为5元的商品，其中一半人拿一张10元人民币，另一半人拿一张5元人民币。为了避免售货员在售货过程中出现找钱困难，需要找到合适的排队方案。

假设售货员一开始没有准备零钱。

贪心算法C语言实现

#include<stdio.h>

int main()
{
    int i,j,k;
    int a[10]={5,5,5,5,5,10,10,10,10,10}; //初始化10个人的钱数
    for(i=0;i<10;i++)  //第一个人取5元
    {
        if(a[i]==5)  //如果第i个人有5元
        {
            for(j=0;j<10;j++)  //从第i+1个人开始找
            {
                if(a[j]==10)  //如果第j个人有10元
                {
                    a[i]=10;  //第i个人取10元
                    a[j]=5;  //第j个人取5元
                    break;  //找到就退出
                }
            }
        }
    }
    for(i=0;i<10;i++)  //第一个人取10元
    {
        if(a[i]==10)  //如果第i个人有10元
        {
            for(j=0;j<10;j++)  //从第i+1个人开始找
            {
                if(a[j]==5)  //如果第j个人有5元
                {
                    for(k=j+1;k<10;k++)  //从第j+1个人开始找
                    {
                        if(a[k]==10)  //如果第k个人有10元
                        {
                            a[i]=5;  //第i个人取5元
                            a[j]=10;  //第j个人取10元
                            a[k]=5;  //第k个人取5元
                            break;  //找到就退出
                        }
                    }
                }
            }
        }
    }
    for(i=0;i<10;i++)  //输出所有排队方案
    {
        printf("%d ",a[i]);
    }
    return 0;
}

分析

该代码使用贪心算法，通过循环遍历所有可能的情况，找到满足条件的排队方案。具体思路如下：

初始化数组，表示每个人的钱数。
循环遍历每个位置，找到第一个拿着5元的人。
从下一个位置开始查找，找到第一个拿着10元的人，交换他们的钱数。
循环遍历每个位置，找到第一个拿着10元的人。
从下一个位置开始查找，找到第一个拿着5元的人，继续从下一个位置查找拿着10元的人，交换他们的钱数。
输出最终的排队方案。

总结

通过贪心算法，可以有效解决排队找零问题，避免售货员找钱困难。该算法简单易懂，且能够找到所有可能的排队方案。