CS50 Problemset1

[poanc]

cs50的第一週作業，用C語言完成一些implement

前置作業

課程提供了一套線上IDE(integrated development environment)，可以讓使用者在雲端開發
首先，要去cs50.io創一個你專屬的workplace，如下圖所示

下面就是你的terminal，可以輸入一些指令。寫作業前需要做一些更新及創立資料夾，這些在作業指導裡面都有介紹，這裡就不多做介紹了。此外，題目內都有對題目的背景介紹，有一些還蠻有趣的。

xxx50

help50

cs50有內建一些程式用來幫助debug還有讓你的語法看起來更簡潔更通順，以下語法都是執行在terminal上的

help50 make hello
你可能在將source code轉換成machine code會有一些問題，help50可以將問題用貼近初學者的語言告訴你

help ls hello
除了help50 make hello，你也可以用help50對其他執行程式的錯誤進行解析，如make是一個'程式'，ls也是一個程式

debug50

debug50 ./hello
可以讓程式碼逐句跑，非常好用！

eprintf

eprintf作用和printfㄧ樣，可以印出想要的東西出來，但目的是可以讓使用者偵錯

style50

style50 hello.c
檢查你的語法，空行及空格是否正確

check50

check50 cs50/2018/x/hello
課程助教寫好的test檔，寫完作業後先check是否可以通過test，再上傳

What to Do

1. Implement Hello
2. Implement either of:

• Mario, less comfortable
• Mario, more comfortable

3. Implement either of:

• Cash, less comfortable
• Credit, more comfortable

---

Hello

這題就基本的C語言指令操作

#include<stdio.h>

int main(void)
{
    printf("hello, world\n");
}

---

Mario, less comfortable

這堂課程很貼心，作業有難度分級，對剛接觸computer science的初學者，可以選擇標註less comfortable 的題目來做

$ ./mario
Height: 5
    ##
   ###
  ####
 #####
######

$ ./mario
Height: 3
  ##
 ###
####

這題要在terminal上顯示出馬力歐兄弟遊戲裡面堆疊的方塊，我們要用#(hashtag)來完成它

思考流程

1. 要讓使用者填入要多少樓層，且填入的樓層若超過23層樓，程式會自動要求使用者重新填入
2. 尋找樓層高度及規律hashtag之間的規律

如果要要求使用者填入正確訊息，使用者若填入的資料不正確，程式會要求使用者重新輸入，這個你會怎麼做？可以用迴圈while ，但是我們這裡希望至少要回答一次，所以用do-while會比較好，範例如下

    // height cannot be greater than 23
    int h;
    do
    {
        h = get_int("Height: ");

    }
    while (h > 23 || h < 0);

找出每一層樓，空格和hashtag的關係

    // this loop is for how many floor
    for (int i = 0 ; i < h ; i++)
    {
        // blank decreases from height-1 to zero,
        int a = 1;
        while (a < h - i)
        {
            printf(" ");
            a++;
        }

        // hashtag increases from 2 to height+1
        int b = 0;
        while (b < 2 + i)
        {
            printf("#");
            b++;
        }
    }

---

Mario, more comfortable

做出如下的圖型

$ ./mario
Height: 4
   #  #
  ##  ##
 ###  ###
####  ####

這題難度其實跟less comfortable的差不多，就不多做介紹了

---

Cash, less comfortable

這題是關於greedy algorithm的實做，中文翻作貪婪式演算法，目的是要找出最佳解。詳細定義或是應用，等到之後有時間再深入研究。

美國貨幣價值較大，一元(dollar)之下還有分成quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢)。�這題就是要你以商家的角度，如何有效使用(越少越好)貨幣。

舉例來說，商家要找消費者0.41 dollar，符合greedy algorithm的找法就是
1個quarter (0.41 -> 0.16)
1個dime (0.16 -> 0.06)
1個nickel (0.06 -> 0.01)
1個penny (0.01 -> 0)
這樣的找零方法最節省貨幣的使用

因此，這題是要使用者輸入一個float，程式必須輸出最節省使用貨幣的個數

$ ./cash
Change owed: 0.41
4

這題必須知道浮點數是沒有辦法精準的呈現(inherent imprecision of floating-point values)，這裡就暫且知道這件事情，之後遇到再仔細想想。下面的想法是目前的想法，沒有經過證實，所以可能有錯。

為了要克服這個問題(做作業的時候也卡在這裡蠻久)，我們必須先把浮點數轉換成整數，但因為是浮點數，所以一開始存取就有可能不是你所設想的數(舉例來說：你想要的數字0.1，但是系統存取的數可能是0.10012)，但是這個不精準並沒有偏離原本你設想的數太多，所以我們可以利用取近似值的方法，來拿到你所設想的數。

向使用者索取value of owed change

    //get the owed change n
    float n;
    do
    {
        n = get_float("Change owed: ");
    }
    while (n < 0);

將拿到的值轉換成整數，並且取近似值，避免不精準的浮點數。

    // turn the dollar to cents and round it off
    n = n * 100;
    n = roundf(n);

計算需要用到多少quarter，其他依此類推

    // let int a count the number of coins
    int a = 0;

    // how many quarters can we use
    while (n >= 25)
    {
        n = n - 25;
        a++;
    }

在有些地方你會看到

printf ("%.55f\n", number)

.55是指精確度到小數點後第55位

---

Credit, more comfortable

這題難度較高，相較這週的其他題目，這題有許多小功能要完成

題意直接去題目連結看，這裡就不講。主要講幾個比較重要或我在寫的時候卡住的地方

1. 因為使用者要輸入位數大概為15位的數字，所以資料型態要改為long long(關於資料型態和記憶體所需如容量，會記在week1的筆記)

2. 要去判斷信用卡號是否valid，必須知道怎麼拿到每個位數的數字

3. 判斷信用卡號為哪家信用卡公司，必須知道使用者輸入的號碼為幾位數(number的length)

向使用者索取信用卡號

    long long n;
    do
    {
        n = get_long_long("Number: ");
    }
    while (n < 0);

要拿到每個位數的數字之前，你要知道這串數字是多長(因為長度是依據使用者輸入的數字，要用程式碼去取每位的數字，電腦必須知道你取的'極限'在哪)，因此等於是第1,2項一次解決。

long long不是字串，不能用strlen內建函式去取得長度(javascript是用str.length())，所以我們要自己寫一個code來取得數字位數

//get the p, which equals to the length of the long long n
    long long k = n;
    int p = 0;
    while (k >= 1)
    {
        k = k / 10;
        p++;
    }

這裏多設一個變數k，目的是想要保留n的數值，晚點會用到，不想要為了取得位數而失去n真正的值

取得n的長度之後，就可以去取second-to-last以及每隔兩位數字的值。用loop去索取每個位數。

    int total = 0;
    int i = 0;
    while (p  > 1 + i * 2)
    {
        long num_a = pow(10, 1 + i * 2);

        int w = (n / num_a) % 10 * 2;
        i++;

        if (w >= 10)
        {
            int ten = floor(w / 10);
            int one = w % 10;
            total = total + ten + one ;
        }
        else
        {
            total = total + w;
        }

    }

剩餘的部分依此類推，最後依卡號長度及卡號開頭來判斷信用卡公司，這裡學到boolean expression怎麼表示同時and和or並列的情況。

舉例來說：如果是american expression信用卡，卡號為15位數，開頭要是34或是37，這樣boolean expression怎麼寫？

        if (p == 15 && (floor(n / pow(10, 13)) == 34 || floor(n / pow(10, 13)) == 37))
        {
            printf("AMEX\n");
        }