---
tags: homework, 109, cpi
title: '[109-cpi] HW11'
---
# Homework 11
> Week 14 (12/14), Due: 12/21 09:00:00
* 範圍：**Pointer**
* NOJ
---
## Reorder
> [name=映達]
### Description
<style>
.ll-orange {
color: #ED7D31;
font-weight: bold;
}
.ll-blue {
color: #4472C4;
font-weight: bold;
}
</style>
給定一個數列
$$
\{0,\, 1,\, 2,\, \cdots,\, N\}
$$
請實作一個函式 `uintptr_t * reorder(uintptr_t * head)` ，將其重新排序為:
$$
\{N-1,\, N-3,\, N-5,\, \cdots,\, N,\, N-2,\, N-4,\, \cdots\}
$$
在本題中，上述數列將以一個「linked list」來表示。數列中的**每一項，皆由 $2$ 個元素所組成**：
- **`node`**：*uintptr_t [2]*，linked list 的本體。
- **`num`**：*int*，數列中的某項數字。
每一個 `node` 皆存有兩個數值（address）。
- **`[0]`**：`num` 的 <span class="ll-orange">address</span>。
- **`[1]`**：下一個 `node` 的 <span class="ll-blue">address</span>。
每一個 `num` 存放數列中的一個數字。
整個 $\{0,\, 1,\, 2,\, \cdots,\, N\}$ 的數列用以上的方法表示為：
Linked list 最後一項的 `node[1]` 將指向 `NULL` 。
#### 參數
- **`uintptr_t * head`**
指向 linked list 的第一個 `node`。
#### 回傳值
- **`uintptr_t * new_head`**
指向重新排列後的 linked list 的第一個 `node` 。
請下載模板（[載點](https://drive.google.com/file/d/1203iwKu2wWInAXpJsPWi-6q6VclgHl-w/view?usp=sharing)）後，實作位於 `reorder.c` 中的 `uintptr_t * reorder(uintptr_t * head)`，並依照以下輸入、輸出驗證你的程式是否正確。
編譯指令：`gcc -std=c11 -O2 main.c reorder.c`。
#### <span style="color: red">注意！</span>若使用以下的方法，將導致 <span style="color: #2196f3">R</span>~unTime~<span style="color: #2196f3">E</span>~rror~：
- 直接改變數列中的值（黑色方塊內的值）
- 改變<span class="ll-orange">橘色箭頭</span>指向的位置
- 在串列（上圖）中任何一部分使用自行分配（calloc, malloc, etc.）的記憶體。
請透過改變「<span class="ll-blue">指向的</span><span class="ll-orange">下一項</span>」來完成；總的來說，你只能改變<span class="ll-blue">藍色箭頭</span>指向的位置。
### Input
一個正整數 $n$。代表數列 $\{0,\, 1,\, 2,\, \cdots,\, n-1\}$。
- $1 \le n \lt 100$
### Output
重新排列後的數列
$$
\{N-1,\, N-3,\, N-5,\, \cdots,\, N,\, N-2,\, N-4,\, \cdots\}
$$
其中
$$
N = n - 1
$$
#### Subtasks
| | Limits |Score |
|:---|:---------|-----:|
| #0 | 無其他限制 | $100$ |
| **Total** | | $100$ |
### Example Input 0
```
1
```
### Example Output 0
```
0
```
### Example Input 1
```
2
```
### Example Output 1
```
0 1
```
### Example Input 2
```
5
```
### Example Output 2
```
3 1 4 2 0
```
### Example Input 3
```
10
```
### Example Output 3
```
8 6 4 2 0 9 7 5 3 1
```
### Example Input 4
```
17
```
### Example Output 4
```
15 13 11 9 7 5 3 1 16 14 12 10 8 6 4 2 0
```
### Hint
---
## 極黑蝴蝶結的奇妙冒險
> [name=博傑]
### Description
極黑蝴蝶結，那是書記每天配戴在頭上的，身分象徵一樣的東西。然而就在某一天的中午，它卻突然不見了，不得已之下書記只好換上了備用的「超黑蝴蝶結」，踏上了尋找極黑蝴蝶結的旅程。
> 極黑蝴蝶結示意圖
她苦思良久之後，覺得應該在今天經過的某個地方掉的，只是因為書記沒辦法記住今天經過所有的地方，需要走到現場才能回憶起再上一個走過的地點，所以她需要走訪她今天經過的每個地點。
不過，因為人類的記憶是會有誤差的，所以書記可能會記錯走過的路，例如說以下這種情況：
因為在點 $F$ 這邊誤將上一個地點記成有紅色標記的點，而非正確的藍色道路，因此便陷入了一個無限循環。
不過書記她也有可能成功地找到了極黑蝴蝶結，此時道路看起來會如下圖所示：
她成功地在點 $T$ 找回蝴蝶結，因此就不用再向前追溯了。
本題中將道路資訊儲存在指標中，並以 `NULL`（也就是 `0`）表示終點，其中地址數值僅為示意，並非實際電腦中的位址看起來的樣子，如下圖所示：
上圖可以看到我們從位址為 `0x123` 的指標開始走訪，會依序經過 `0x123`、`0x345`、`0x789`、`0x84f` 這幾個位址，並且在 `0x84f` 這個位址遇到 `NULL`（按照前面題序所述，這裡就是路徑終點）。
走訪的程式碼大概會像是這樣：
```c=
#include <stdio.h>
#include <stdint.h>
int main()
{
uintptr_t *a = (uintptr_t *)0x123;
while(a != NULL)
{
a = (uintptr_t *)*a;
printf("%p\n", a);
}
return 0;
}
```
不過需要注意的是，直接執行以上程式碼會出現 *Segementation fault* 的錯誤，這是因為記憶體沒有正確設定所導致，至於如何設定可以參考以下的 `main.c` 當中的實作。
現在告訴你起點，請你實作一個函式，假如給定的道路中存在無限循環，請你回傳循環的起點（圖中紅色標記的點），否則回傳 `NULL`（代表書記成功找到了蝴蝶結，可喜可賀）。
#### 本題檔案
##### find_bow.h
同學需要實作的部分。
```c=
#include <stdint.h>
uintptr_t *find_bow(uintptr_t *start_pos);
```
##### main.c
本題評測檔案，無須上傳也無法修改。
```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include "find_bow.h"
int main()
{
// 設定記憶體
int n, m;
scanf("%d %d", &n, &m);
n += m;
uintptr_t **locations = (uintptr_t **)calloc(n, sizeof(uintptr_t *));
for (int i = 0; i < n; i++)
locations[i] = (uintptr_t *)malloc(sizeof(uintptr_t));
for (int i = 0; i < n - 1; i++)
*locations[i] = locations[i + 1];
*locations[n - 1] = n == m ? NULL : locations[m];
// 尋找環的起點
uintptr_t *bow = find_bow(locations[0]);
uintptr_t *excepted = n == m ? NULL : locations[m];
// 檢查
puts(bow == excepted ? "1" : "0");
return 0;
}
```
### Input
一行以單個空白分隔的兩個整數 $n, m$，分別代表環上跟環以外的點數量。
#### Limits
- $0 \le n \le 10^5$
- $0 \le m \le 10^5$
- $0 \lt n + m$
### Output
本題輸出 `1` 時則表示 AC。
#### Subtasks
| | Limits | Score |
|:--------- |:---------- | -----:|
| #0 | $n = 0$ | $50$ |
| #1 | 無其他限制 | $50$ |
| **Total** | | $100$ |
| | | |
### Hint
- 可將走過的所有節點存下來，遇到第一個重複的就回傳。
- 其實最後書記是在身上找到蝴蝶結的，並沒有掉在路上。
---
## Boss. Chi's Poker
> [name=育辰]
### Description
* #### [前測測資](https://drive.google.com/file/d/18DxsV5VNd9IcIuabov7SgU_2DV_ipiJz/view?usp=sharing)
* #### [template](https://drive.google.com/file/d/1667rmOWlADFKJ3AkbDxoxCblLqY1jym5/view?usp=sharing)
> **template** 已經幫同學把三份檔案合在一起，方便你在Codeblocks上直接編譯，請實作 **card.c**部分，上繳時請參考題述的 **card.c**，把該註解的東西註解後上傳。
<center><img src=https://i.imgur.com/UZ0aUr7.jpg width=280 height=280> </img></center>
Boss. Chi 是一位非常有責任感的老師，也很有熱忱...希望學生學到滿滿的知識，哀鴻遍野的慘叫映照著其內心的狂熱，他...總是用冷酷無情的外表包裝...就是這樣一位老師...\
\
\
\
\
不過...人生嘛...難免遇到調皮搗蛋的學生，\
有一天咪路修了 Boss. Chi的課...
<center><img src=https://i.imgur.com/AgSfbum.png width=150 height=150> </img></center>
(圖片取至 https://www.luoow.com/dc_news/comic_ZmUD)
他是個問題學生，總在上課時擺動他的沙鈴，一再地干擾 Boss. Chi的講課。有一次 Boss. Chi正在介紹他最熱愛的撲克牌(*Poker*)，又受到搗亂，心中燃起無名火便向學生咪路提出了挑戰。\
\
\
**<Boss. Chi>**\
：既然你上課那麼認真，都在玩沙鈴，我就來考考你吧？\
：我們上到了指標，我會給你主程式 <font color="blue"> main.c</font> 跟標頭檔 <font color="blue">card.h</font>\
：我要你實現我最熱愛的撲克牌，寫完整 <font color="red">card.c</font>的函式\
：做出 洗牌、列印牌堆、發牌、排序 等四個功能\
：**若你做不出來就是死當。**
**<咪路>**\
：咪路, 咪路, 咪路 mo depon (無奈貌)
雖然咪路施展魔法變出了程式，可是上課都沒聽就變出失敗的程式了...請你幫幫他，解救要被當掉的命運吧！
---
### 內容說明
卡牌大小範圍為 $[1,10000]$，存放在 `card[]` 的陣列中。\
\
接著會有一個陣列，裡面存放的是**指標**，其宣告為：
`int *deck[num]`\
在`deck`中，第 $\text{i-th}$ 會對應到 `card` 中的第 $\text{i-th}$ 的位址。\
\
舉例來說：
```cpp
deck[0] = &card[0];
```
因此，只要寫 `*(deck[0])` 就能取得 `card[0]` 的數值。
起初程式會輸入 `num` 表示會有多少個卡牌，再有一整數 `pep_num` 表示有幾個人跟 Boss. chi 一同玩撲克牌，接著再以一行共 `num` 個數字依序代表牌的數值。
卡牌數字不會重複，且不超過 **9999** 張牌， `deck`的末端會儲存 `NULL`，例如今天輸入`5`張牌，依序存放在 deck[0],[1],[2],...[4]，而`deck[5]`則會存放 `NULL`表示**牌堆的盡頭**。
---
#### 洗牌 (shuffle)
假設有`n` 張牌，起初先將牌分為兩半，若 `n` 為奇數，則前半的牌堆數會多一張，偶數則正好一半一半。\
\
如果洗牌後的牌依序為 $R_1, R_2, R_3, \cdots, R_n$，\
則前半的第一張牌當作 $R_1$, 後半第一張牌當作 $R_2$, 前半第二張牌當作 $R_3$ 依此類堆。
\
\
例如給定 `1 4 2 5 3`，則：
1. 前半：`1 4 2`
2. 後半：`5 3`
洗牌後：`1 5 4 3 2`
---
#### 印牌 (print_card)
依序列印傳入的所有牌，輸出彼此“間"以一個空格隔開(意即，最後一個數字後面不應該有空格)，最末需換行
\
如輸入沒有任何手牌，請輸出 `No card!`並換行回傳`1`，結束該函式。
---
#### 發牌 (distribute_cards)
傳入玩家數量、手牌堆的位址陣列，以及指向各個玩家手牌的 `indextopep` (三重指標)
起初，他開了 `pep_num` 數格雙重指標陣列，接著對於該陣列中每個元素，再開了 `num+1` 個指標陣列，該陣列中每個元素指向牌的位址。
(參考圖示)\
如 `pep_num[0]` 表示 第`0`位玩家的手牌，`pep_num[0][5]`則表示第`0`位玩家的第`5`張手牌 (index從0開始)。
實作時，請按照玩家順序發牌，例如 `pep_num = 5`，則發牌依序給 `0` `1` `2` `3` `4` `0` `1` ...序號的玩家，直到沒有牌為止，每位玩家手牌末端請存放 `NULL`，實作時請把結果放到`indextopep`內，如：
```cpp
indextopep[index_to_pep][i] = deck[i];
```
---
#### 排序 (sort_by_deviation_from_mean)
傳入牌堆位址的陣列，請按照 **離均差** 大小做排序(平均若有小數點請**無條件捨去**)，小的在前面，若 **離均差 大小相同**，則按照其原本數值排序，<b><font color="red">大的放前</font></b>。
例如：\
輸入 `1 4 2 5 3`，其平均為 $\frac{1+4+2+5+3}{5}=3$，離均差表示該數與平均的**差**，也就是說上述會更換成：\
$\to 1-3, \ 4-3, \ 2-3, \ 5-3, \ 3-3$\
$\to -2, \ 1, \ -1, \ 2, \ 0$\
$\to 2, \ 1, \ 1, \ 2, \ 0$
最終排序應為 `3 4 2 5 1`，你會發現離平均越近的越前面，如果離平均一樣近的則較大的數字在前。
---
#### Explain Output
使用助教提供的 main.c輸出後，會先將輸入的牌洗一次後輸出，接著依序發給各個玩家，會印出各個玩家當前的手牌狀況，再最後以新方法排序後，輸出新的排序結果。
1. shuffle的結果
2. 發牌後各玩家手牌狀況
3. 新的排序後的結果
---
* **card.h**
> 函式宣告的原型檔案
```cpp=
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int count_the_number(int *deck[]);
void shuffle(int *deck[]);
bool print_card(int *deck[]);
void distribute_cards(int *deck[], int **all_hand[], int pep_num);
void sort_by_deviation_from_mean(int *deck[]);
```
---
* **card.c**\
<b><font color="red">你應該實作的檔案</font></b>
```cpp=
#include "card.h"
int count_the_number(int *deck[]){
//optional
//計算牌堆數量
//
}
void shuffle(int *deck[]){
//洗牌
//
}
bool print_card(int *deck[]){
//1: 表示無牌，0表示正常有牌
//列印牌堆
//
//return 無牌(1) or 有牌(0)
}
void distribute_cards(int *deck[], int **all_hand[], int pep_num){
//發牌
//順序：第1到第pep_num個人依序發放
//
}
void sort_by_deviation_from_mean(int *deck[]){
//排序
//比較：按"離均差"排序，相同時按照原始數字大小排序 (小在前、大在後)
//
}
```
---
* **main.c**
```cpp=
#include "card.h"
int main(){
int num = 0, pep_num = 0;
scanf("%d %d", &num, &pep_num);
int *deck[num + 1], card[num + 1];
int index = 0;
//設定指向玩家手牌的陣列 (index 1代表第一個玩家的手牌... 依此類推)
int ***indextopep = calloc(pep_num, sizeof(int **));
//對於indextopep的pep_num個指標，每個再開手牌長度的陣列
//理想設定方式應該是 (num / pep_num) * (pep_num + 1)
//因為發放手牌方式是平均分發，只需取 pep_num 整數倍的上限就好
for (int i = 0 ; i < pep_num ; i++)
indextopep[i] = calloc(num + 1, sizeof(int *));
//指標設定，deck指向card相對應位置上
for (int i = 0 ; i < num ; i++){
scanf("%d", &(card[index]));
deck[index] = &(card[index]);
index++;
}
//末端設為0
deck[index] = NULL;
//洗牌
shuffle(deck);
//如果沒牌直接跳出程式
if (print_card(deck))
return 0;
printf("\n------STATUS------\n");
//發牌
distribute_cards(deck, indextopep, pep_num);
//依序印出玩家手牌狀況
for (int i = 0 ; i < pep_num ; i++){
printf("Player %d: ", i+1);
print_card(indextopep[i]);
}
printf("------------------\n");
//新的排序結果
sort_by_deviation_from_mean(deck);
printf("New sort: ");
print_card(deck);
return 0;
}
```
---
#### Subtasks
| | Limits |Score |
|:---|:---------|-----:|
| #0 |(1)牌堆有幾張牌，數字就到多少, (2)玩家只有一位, (3) 牌堆不會為空, (4) 牌堆數恰為偶數| $35$ |
| #1 |玩家只有一位| $25$ |
| #2 |牌堆牌數恰為玩家數量的倍數| $25$ |
| #3 |無其他限制| $15$ |
| **Total** | | $100$ |
---
### Input
* 第一行：兩個整數，分別代表牌堆數量 *num*、玩家人數 *pep_num*
* 第二行：共 *num* 個整數，$d_i$，依序表示牌的數值大小
#### Limit
* $9999 \geq \text{num} \geq 0$
* $\text{pep_num} > 0$
* $10000 \geq d_i \geq 1$
### Output
* 只需處理 `print_card`，列印時數字**間**以空格隔開，意即最後一個數字後面不該有空格，最末需換行。
### Example Input 0
```
4 1
1 2 3 4
```
### Example Output 0
```
1 3 2 4
------STATUS------
Player 1: 1 3 2 4
------------------
New sort: 2 3 1 4
```
### Example Input 1
```
8 1
1 2 3 4 5 6 7 8
```
### Example Output 1
```
1 5 2 6 3 7 4 8
------STATUS------
Player 1: 1 5 2 6 3 7 4 8
------------------
New sort: 4 5 3 6 2 7 1 8
```
### Example Input 2
```
6 1
6 1 5 2 4 3
```
### Example Output 2
```
6 2 1 4 5 3
------STATUS------
Player 1: 6 2 1 4 5 3
------------------
New sort: 3 4 2 5 1 6
```
### Example Input 3
```
0 1
```
### Example Output 3
```
No card!
```
### Example Input 4
```
6 1
10000 5832 1 2 3 4
```
### Example Output 4
```
10000 2 5832 3 1 4
------STATUS------
Player 1: 10000 2 5832 3 1 4
------------------
New sort: 4 3 2 1 5832 10000
```
### Example Input 5
```
5 1
1 2 3 4 5
```
### Example Output 5
```
1 4 2 5 3
------STATUS------
Player 1: 1 4 2 5 3
------------------
New sort: 3 4 2 5 1
```
### Example Input 6
```
10 5
982 321 546 3 2 6 9 2 39 100
```
### Example Output 6
```
982 6 321 9 546 2 3 39 2 100
------STATUS------
Player 1: 982 2
Player 2: 6 3
Player 3: 321 39
Player 4: 9 2
Player 5: 546 100
------------------
New sort: 100 321 39 9 6 3 2 2 546 982
```
### Example Input 7
```
5 8
1 2 3 4 5
```
### Example Output 7
```
1 4 2 5 3
------STATUS------
Player 1: 1
Player 2: 4
Player 3: 2
Player 4: 5
Player 5: 3
Player 6: No card!
Player 7: No card!
Player 8: No card!
------------------
New sort: 3 4 2 5 1
```
### Hint
* 你可以選擇實作 `count_the_number`，累加至`deck[i]`為`NULL`就停止去計算排堆數量
* 洗牌請格外注意**前半**牌數量的處理，以紙筆模擬下方可寫出式子，而建議再宣告一個 `int *deck_co[]`，將洗牌的狀況先放到裡面，最後再依序複製給 `deck`處理比較簡單
* 牌堆盡頭會儲存 `NULL`，不要忘記。
* 列印時，當 `i !=0` 時就印空格，就可以達到 **數字間以空格間隔**，務必記得換行。
* 洗牌建議用一個 `flag_null`，去記錄當前是不是到牌的末端了，如果是則接下來依序賦予剩下的玩家手牌末端為 `NULL`即可完成，第幾位應該為 `i%pep_num`，至於手牌第幾張則請同學嘗試看看。
* 承上，如果牌堆有 `4`張牌，玩家有 `3`人，迴圈跑的時候，到大於`4`且為`3`的倍數的最小數字(即`6`)，這樣會比較好處理，而這要怎麼計算一樣是關鍵！ (跟上面的提示一樣，請利用 `%` `/`)
* 排序處理時，不用擔心 $count=0$，因為牌堆為空時主程式已經處理跳出了，先計算 `sum`再直接除以`count`，任何排序法都行，注意交換時 `temp`的型態宣告(你是指標)，比較時應該會用到 `abs`(絕對值)，也千萬不要拿位址去比較，要比較的是牌的數值。
* 本題改編至 [Card shuffling](https://judgegirl.csie.org/problem/0/206)，為`Judge Girl` 題目
---
[Judge Girl](https://judgegirl.csie.org/problems/domain/0#7)
---
## Maximum in Pointer Array
> [name=Judge Girl]
### Description
Write a function that finds the maximum value pointed by elements of a pointer array.
```c=
int max(int *iptr[], int n);
```
This function returns the maximum integer pointed by the pointers in the array iptr. Note that each element in iptr is a pointer to an integer.
The main program is as follows.
```c=
#include <stdio.h>
#include "max.h"
int main() {
int n, i;
int array[100];
int *iptr[100];
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &(array[(i + 3) % n]));
iptr[i] = &(array[(i + 3) % n]);
}
printf("%d\n", max(iptr, n));
return 0;
}
```
### Input
There are two lines in the input. The first line has $n$. The second line has $n$ integers.
#### Limits
$n \le 100$
### Output
There is one lines in the output. The first line has the maximum integer as in the description.
### Sample Input
```
5
0 20 -3 4 5
```
### Sample Output
```
20
```
### Hint
* 原題搬運至[Judge Girl](https://judgegirl.csie.org/problem/0/23)
---
## Function Evaluation
> [name=Judge Girl]
### Description
Write a function to evaluate $f(x, y) = 4*x − 6*y$ for a lot of $x$ and $y$. The prototype of the function is as follows.
```c=
int evaluate_f(int *iptr[], int n, int *index);
```
Each pointer in `iptr` points to an array of two integers. The first integer is $x$, and the second integer is $y$. The length of the pointer array is $n$, so there are $n$ pairs of $x$ and $y$ that you need to evaluate $f(x,y)$. Compute these $f(x,y)$ and return the maximum as the return value of `evaluate_f`. Also you need to set index so that it becomes the index into `iptr` where the maximum happens. If the maximum value can be evaluated from multiple $(x,y)$ pairs, set the index to be the smallest among them. For example, if the $x$ and $y$ pointed by `iptr[3]` and `iptr[5]` both have the maximum $f(x,y)=100$, then `evaluate_f` should return $100$ and index should be set to $3$. Variable $n$ is always positive.
### Input
$n \gt 0$
We may test your program in the following code:
```c=
#include <stdio.h>
#include "evaluate_f.h"
int main(){
int a[] = { 9, 7 };
int b[] = { 3, 2 };
int c[] = { 3, 2 };
int d[] = { 9, 7 };
int *iptr[] = { a, b, c, d };
int max, index;
max = evaluate_f(iptr, 4, &index);
printf("%d %d\n", max, index);
}
```
### Output
### Sample Input
```
```
### Sample Output
```
```
### Hint
* 原題搬運至[Judge Girl](https://judgegirl.csie.org/problem/0/190)
Sign in with Wallet
Connect another wallet