CS50--Week1--Cash和Credit

week1的第三题

1.找零（贪心算法）

在进行找零时，希望尽量减少为每位顾客分配的硬币数量。假设收银员欠客户一些零钱，收银员的抽屉里有 25 美分、10 美分、5 美分硬币和1 美分硬币，要解决的问题是怎样选择硬币及数量才能使找零的硬币数量最少。比如需要找零41美分，按照贪心算法，需要找以上四种硬币各1个才能保证数额正确且硬币数最少。这个尽快找大面额硬币就能保证找的硬币数最少，具体如下：

#include 
#include 
#include 
int main(void)
{
    int c25=25,c10=10,c5=5,c1=1;//定义四种硬币
    float change=get_float("The change is($):\n");//输入找零钱数，单位为美元 
    while(change<=0)//找零小于等于0时重新输入
    {
        change=get_float("The change is($):\n");
    }

    int changes=ceil(change*100);//美元转化为美分

    int n1,n2,n3,n4;//定义每种找零的硬币数量


    n1=changes/c25;
    n2=(changes%c25)/c10;
    n3=((changes%c25)%c10)/c5;
    n4=(((changes%c25)%c10)%c5)/c1;
    printf("The number of total coins is %i\n",n1+n2+n3+n4); //总数量         
    printf("25,10,5,1:  %i,%i,%i,%i\n",n1,n2,n3,n4);//各自数量
}

其中包含math头文件是采用ceil函数进行float和int的转化。

结果如下：

2. 信用卡

信用卡或借记卡的卡号是需要进行验证来确定卡的真假的，验证方法一般为Luhn算法，具体描述如下：

1.从卡号的倒数第二个数字开始，每隔一个数字乘以 2，然后将每一位得出的商按个位上的数字加十位上的数字全部相加（只有一位的话按照十位为0相加）。

2.将第一步的总和与未乘以 2 的位数上的的总和相加。

3.如果总数的最后一位数字是 0，则该卡号是有效的！

算法不复杂，就是操作繁琐，卡号用的longlong,先求取卡号的总位数，再把卡号每位数字都求出来，同时把要×2的和不×2的分开，要×2的乘2后再拆分成个位和十位相加，不乘2的直接相加，把俩结果相加对10求余即可判断个位是否为0.具体程序如下：

#include 
#include 

int main()
{
    long long card,card1;//长长整形；长整形不能记录13甚至15位的整数；
    int sum = 0,sum1=0;//sum记录未×2的那些位的和；sum1记录×2后再拆分相加的和；
    scanf_s("%lld", &card);
    card1 = card;       //将卡号赋值给card和card1；
    int i;
    for (i = 0; card != 0; i++)//求取卡号总位数
    {
        card /= 10;
    }
    int digit = i;//记录卡总位数

    int arr[20];//存储卡号每位的值；
    int arr1[20];//存储要×2的那些位；

    for (int j = 0; j < digit; j++)
    {
        
        arr[j] = card1 % 10;
        card1 /= 10;
        
        if (j % 2 != 0)//判断是否是要x2的位
        {
            arr1[(j-1)/2]=arr[j]*2;//存储要×2的那些位；
        }
        else
            sum += arr[j];//不需要*2的那些位先加起来；
    }

    //判断需要*2的那些位的位数；
    int count = 0;
    if (digit % 2 != 0)
        count = (digit - 1) / 2;
    else
        count = ceil(digit/2);

    //arr1中每个数拆成十位和个位，就算是一位也拆成十位和个位，直接相加；
    for (int k = 0; k < count; k++)
    {
        sum1 += arr1[k] % 10;
        arr1[k] /= 10;
        sum1 += arr1[k] % 10;
    }

    if ((sum+sum1) % 10 == 0)
        printf("the card is legit!\n");
    else
        printf("the card is illegit!\n");



}

运行结果：

输入合法卡号4003600000000014显示legit。

输入非法卡号4003600000000016显示illegit。

题目来源：https://docs.cs50.net/2019/x/psets/1/index.html