cs50 problem:cash

Posted on | | Views:
Symbols count in article: 1.1k | Reading time ≈ 1 mins.

casher
這題是cs50的cash問題，用此問題順便介紹Greedy Algorithm。

背景

類似圖片的放零錢遊戲，有quarters($25), dimes($10), nickels($5)和pennies($1)，要從最大金額放到最小金額，而且要用最少的硬幣數量得到該金額。假設有41元，可以算出25元硬幣1個，10元硬幣1個，5元硬幣一個和1元硬幣1個，所以最少需要四個硬幣。

Greedy Algorithm

中文稱作貪婪演算法，一種每一步都使用當下狀態的最佳解(最有利選擇)，從中希望能導致所有選擇中的最佳解。

Code

程式碼用C語言撰寫，有任何問題可以留言討論。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "cs50.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main()
{
    float cash = 0;
    int quarters = 25, dimes = 10, nickels = 5, pennis = 1, number = 0;

    while(1)
    {

        printf("change owed:");
        cash = get_float();
        if (cash < 0)
            continue;
        cash *= 100;

        cash = (int)round(cash);
        number = cash / quarters;
        cash = (int)cash % quarters;

        cash = (int)cash;
        number += (cash / dimes);
        cash = (int)cash % dimes;

        cash = (int)cash;
        number += (cash / nickels);
        cash = (int)cash % nickels;

        cash = (int)cash;
        number += cash;
        break;
    }

    printf("%d\n", number);
    return 0;

}