C 程式設計/初學者練習
- 變數名可以以數字開頭嗎？
- 變數名可以以印刷符號開頭嗎（例如 #、*、_）？
- 舉一個 C 變數名的例子，它將不起作用。為什麼它不起作用？
- 列出 C 中至少三種資料型別。
- 在您的計算機上，每個資料型別需要多少記憶體？
- 哪些資料型別可以互換使用？為什麼？
- 這些使用是否存在任何限制？
- 如果有，它們是什麼？
- 是否需要做任何特殊的事情才能使用替代資料型別？
- 我們用於資料型別的名稱（例如“int”、“float”）可以作為變數使用嗎？
- 您將如何將值 3.14 賦值給名為 pi 的變數？
- 是否可以將int賦值給double？
- 反過來是否可行？
- 新學生常犯的一個錯誤是反轉賦值語句。假設您想將變數“pi”中儲存的值賦值給另一個變數，例如“pi2”。
- 正確的語句是什麼？
- 反過來是什麼？這是否是一個有效的 C 語句（即使它給出錯誤的結果）？
- 如果您想將一個常量值（如 3.1415）賦值給“pi2”
- a. 正確的語句將是什麼樣子？
- b. 反過來將是一個有效的 C 語句還是無效的 C 語句？
1. 編寫一個程式，提示使用者輸入一個字串（選擇最大長度），並列印其反轉。
2. 編寫一個程式，提示使用者輸入一個句子（同樣，選擇最大長度），並將每個單詞單獨列印在一行上。
1. 編寫一個函式，輸出一個高度和寬度為n的直角等腰三角形，因此n = 3將看起來像
* ** ***
2. 編寫一個函式，輸出一個高度為2n-1，寬度為n的側向三角形，因此n = 4的輸出將為
* ** *** **** *** ** *
3. 編寫一個函式，輸出一個高度為n，寬度為2n-1的直角三角形；n = 6的輸出將為
*
***
*****
*******
*********
***********
1. 構建一個程式，其中控制從 main 傳遞到四個不同的函式，並進行 4 次呼叫。
2. 現在在 main 中建立一個 while 迴圈，並在其中包含函式呼叫。在迴圈開始時請求輸入。如果使用者按下 Q，則結束 while 迴圈。
3. 接下來新增條件語句，以便在使用者輸入數字時呼叫函式，例如 1 呼叫 function1，2 呼叫 function 2 等。
4. 讓 function 1 呼叫 function a，function a 呼叫 function b，function b 呼叫 function c
5. 繪製一個程式流程圖，使用箭頭指示控制流向。
1. 編寫一個函式來檢查整數是否為負數；宣告應類似於 bool is_positive(int i)；
2. 編寫一個函式，將浮點數提高到整數冪，例如，當您使用它時
float a = raise_to_power(2, 3); //a gets 8
float b = raise_to_power(9, 2); //b gets 81
float raise_to_power(float f, int power); //make this your declaration
1. 編寫一個函式來計算一個數是否為素數。如果它是素數則返回 1，如果不是素數則返回 0。
2. 編寫一個函式來確定小於 n 的素數數量。
3. 編寫一個函式來使用牛頓法查詢平方根。
4. 編寫函式來計算三角函式。
5. 嘗試編寫一個隨機數生成器。
6. 編寫一個函式來確定 2 到 100 之間的素數。
1. 編寫一個 C 程式，使用給定長度 n 生成一個隨機整數陣列，並使用歸併排序演算法對其進行遞迴排序。
- 歸併排序演算法是一個遞迴演算法。
- 對一個元素陣列進行排序很容易。
- 對兩個一個元素陣列進行排序，需要合併操作。合併操作將兩個已排序的陣列視為列表，並比較列表的頭部，哪個頭部較小，該元素就被放在已排序的列表上，並且該列表的頭部就被剔除，因此下一個元素成為該列表的頭部。這樣做直到其中一個列表耗盡，然後將另一個列表複製到已排序列表的末尾。
- 遞迴發生是因為合併兩個一個元素陣列會產生一個兩個元素的已排序陣列，該陣列可以與以相同方式產生的另一個兩個元素的已排序數組合並。這會產生一個已排序的 4 元素陣列，同樣適用於另一個已排序的 4 元素陣列。
- 因此，基本的歸併排序是檢查要排序的列表的大小，如果它大於 1，則將陣列分成兩部分，並對兩個部分再次呼叫歸併排序。之後，在大小相同的臨時空間中合併兩個部分，然後將最終的已排序陣列複製回原始陣列。
2. 二叉堆
- 二叉最大堆或最小堆是一種有序結構，其中某些節點保證大於其他節點，例如父節點與兩個子節點。二叉堆可以儲存在一個數組中，其中，
- 給定一個位置i（父節點），i*2是左子節點，i*2+1是右子節點。
- （C 陣列從位置 0 開始，但 0 * 2 = 0，0 *2 + 1= 1，這是不正確的，因此將堆從位置 1 開始，或者為父節點到子節點的計算新增 1，併為子節點到父節點的計算減去 1）。
- 嘗試使用鉛筆和紙張對其進行建模，使用 10 個隨機未排序的數字，並將它們中的每一個插入到一個包含 10 個元素的“堆排序”陣列中。
- 要插入堆，請尾部新增，然後如果更高，則交換父節點，直到父節點更高。
- 要刪除堆的頂部，請將尾部移到頂部，然後推遲更高子節點或下沉，直到沒有子節點更高。
- 嘗試使用筆和紙來計算數字 10、4、6、3、5、11。
- 答案是 11、5、10、3、4、6。
- 練習：現在嘗試使用從尾到頂和向下篩選（或交換更高子節點）的方法移除 11, 5, 10, 3, 4, 6 中的每個頂部元素，以獲得數字
降序排列。
- 優先順序佇列允許元素以優先順序插入，並根據優先順序提取。（這可能很有用，如果元素具有配對結構，一部分是鍵，另一部分是資料。否則，它只是排序機制）。
- 練習：使用上述插入到尾部/挑戰父節點和刪除頭部/最後到頭部/延遲更高子節點技術，實現堆排序或優先順序佇列。
迪傑斯特拉演算法是一種使用優先順序佇列的搜尋演算法。它從將起始節點插入優先順序佇列中，優先順序值為 0 開始。所有其他節點都以優先順序值為 N 插入。每個節點都有一個指向其他節點的鄰接列表、到起始節點的當前距離和指向用於計算當前節點的先前節點的先前指標。鄰接列表的替代方案是鄰接矩陣，它需要 n x n 布林鄰接關係。
該演算法基本上迭代優先順序佇列，移除頭部節點，檢查相鄰節點，並使用頭部節點距離與相鄰節點距離的總和更新距離。
在更新每個節點之後，對該節點使用額外的操作 **“更新優先順序”**
當節點的距離小於其父節點（對於此優先順序佇列，父節點的距離小於子節點）時，節點將與父節點交換。
在此之後，當節點的距離大於一個或多個子節點的距離時，它將與距離最小的子節點交換，因此距離最小的子節點成為距離更大的兄弟節點的父節點，以及距離更大的當前節點的父節點。
透過更新優先順序，當前節點的相鄰節點的回溯指標將更改為當前節點。
當目標節點成為移除的當前節點時，該演算法結束，並且可以透過跟蹤回溯指標記錄到起始節點的路徑，然後執行諸如快速排序分割槽之類的操作來反轉陣列的順序，以給出從起始節點到目標節點的最短路徑。
3. 編寫一個 C 程式，使用快速排序分割槽交換演算法遞迴排序。
- 你可以使用 Q1 中的“驅動程式”或隨機數測試資料。在歸併排序中。這被稱為“重用”，在一般情況下是鼓勵的。
- 重用的優勢是編寫時間、除錯時間和測試時間更少。
- 分割槽交換的概念是隨機選擇一個分割槽元素，並將需要排序的所有內容放入 3 個等價類
類：小於分割槽值的元素，分割槽元素，以及大於（和等於）分割槽值的元素。
- 這可以在不分配超過一個用於交換兩個元素的臨時元素空間的情況下完成。例如，用於整數資料的臨時整數。
- 但是，使用原始陣列空間應該放置分割槽元素的位置是未知的。
- 這通常透過將分割槽放置在要排序的陣列的末尾來實現，然後放置兩個指標，一個在陣列的開頭，
另一個在分割槽元素旁邊的元素上，並重復掃描左指標向右，右指標向左。
- 左掃描在找到大於或等於分割槽的元素時停止，右掃描在找到小於分割槽值的元素時停止，
並交換它們，這會使用額外的臨時空間。
- 如果左掃描到達分割槽元素，它將始終停止，它是最後一個元素；這意味著整個陣列都小於分割槽值。
- 如果右掃描到達第一個元素，則整個陣列都大於分割槽，需要對其進行測試，否則掃描不會停止。
- 當左指標和右指標交叉時，外迴圈退出。在交換之前應測試指標交叉和外迴圈退出
否則，右指標可能會交換之前由左指標掃描過的小於分割槽元素。
- 最後，需要將分割槽元素放置在左分割槽和右分割槽之間，一旦指標交叉。
- 在指標交叉時，左指標可能停留在分割槽元素在陣列中的最後一個位置，而右指標沒有越過
最後一個元素之前的元素。當所有元素都小於分割槽時，就會發生這種情況。
- 如果選擇右指標與分割槽交換，則會導致錯誤狀態，其中左陣列的最後一個元素將小於分割槽元素的值。
- 如果選擇左指標與分割槽交換，則左陣列將小於分割槽，並且分割槽將與值大於分割槽或分割槽本身的元素交換。
- 必須檢查對 2 元素 **無序** 陣列進行快速排序的極端情況。
- 左指標停留在第一個 **無序** 元素上。右指標從第一個 **無序** 元素開始，但外迴圈退出，因為它是最左邊的元素。然後，分割槽元素與左指標的第一個元素交換，現在這兩個元素 **有序**。
- 在 2 元素 **有序** 陣列的情況下，最左邊的指標跳過第一個元素，它小於分割槽，並在分割槽上停止。右指標從第一個元素開始，並退出，因為它是在第一個位置。指標已經交叉，所以外迴圈退出。分割槽與自身交換，因此保持了順序。
- 完成交換後，應遞增左指標並遞減右指標，因此不會再次掃描相同的位置，因為可能導致無限迴圈（可能是在左指標在元素等於或大於分割槽時退出，而右元素等於分割槽值時）。一種實現方法，Sedgewick，以左指標減一和右指標
加一作為預期的初始掃描位置，並使用前遞增和前遞減運算子，例如 ( ++i, --i )。