---
# System prepended metadata

title: 資訊一乙Week12作業

---

# 資訊一乙Week12作業

## 題目敘述
給定一個數字 n，請你產生編號 1 ~ n 按照小到大排序且沒重複數字的卡片。編號 1
的卡片在最前面（top），編號 n 的卡片在最後面（bottom）。若目前有至少兩張牌以上的
話，需要按照以下的準則直到卡片只剩下一張：
● 將目前的 top 丟掉，再將新的 top 移到所有卡片的最後方。
　　以 1, 2, 3 這三張牌舉例子，1 為 top，3 為 bottom。首先會先將 top 的牌丟掉，目前
就剩下 2, 3，再來將新的 top，也就是 2 移到所有卡片的最後方，也就是變成 3, 2。
　　請寫一支程式能夠顯示丟掉卡片的順序及顯示出最後丟掉的一張牌。

輸入格式：
　　有多行測資，每行有一非負整數 n（0 <= n <= 50）。若 n 為 0 時，結束程式。
  
輸出格式：
　　根據每筆測資輸出兩行。第一行顯示丟掉卡牌的順序；第二行顯示最後一張牌的編
號。每行最前方或最後方都不會有多餘的空格，輸出格式請參考範例輸出。

___

範例輸入
Example 1.
7
19

Output:
Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6

Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
___
## 基本Function
### makenode
第一個就是...make node
```c
NODE* makenode(int val){
    NODE* new = malloc(sizeof(NODE));
    new->next = NULL;
    new->val = val;
    return new;
}
```

### push東西到stack裡面
啊好像用queue比較好
隨便啦都寫了
```c
void pushTop(NODE* obj, int val){
    NODE* new = makenode(val);
    new->next = obj->next;
    obj->next = new;
}
```
### 取top值
```c
int takeTop(NODE* obj){
    return obj->next->val;
}
```
### 取最上面的值之後刪除top
```c
int takeAndPop(NODE* obj){
    int theVal = takeTop(obj);
    NODE* temp = obj->next;
    obj->next = obj->next->next;
    free(temp);
    return theVal;
}
```
基本上上面這些我相信一乙前幾個禮拜都有寫過
___
### 取最後一項的指標
就突然想到等一下應該會有需要用到取最後一項的指標的東東
所以就寫了以備不時之需
```c
NODE* takeButtonPtr(NODE* obj){
    NODE* current = obj;
    while (current->next){
        current = current->next;
    }
    return current;
}
```
### 主要邏輯(圖解)
取最上面的值之後刪除top，然後再讓新top變buttom(最後一項)~~(是這樣翻嗎XD)~~
這裡就給大家圖解，用這張圖的邏輯就可以達到這個效果
![](https://i.imgur.com/pj2UYff.png)

```cpp
int takePopTurnToBack(NODE* obj, NODE* button){
    int theVal = takeAndPop(obj);
    button->next = obj->next;
    obj->next = obj->next->next;
    button->next->next = NULL;
    //button = button->next;
    return theVal;
}
```
## main函式~~沒有炸雞~~
```cpp
int main(){
    
    //repeat
    while (1){

        //input
        int target = 0;
        scanf ("%d", &target);

        //if input == 0, break
        if (!target){
            break;
        }

        //make the linked list
        NODE* theList = makenode(0);

        /*
        use "stack way" to push the element into the list
        so its actually "from target to 1", 
        but not "1 to target"
        */
        for (int i=target; i>=1; --i){
            pushTop(theList, i);
        }

        //no element discarded when target is 1
        if (target == 1){
            printf ("Discarded cards:\n");
        }
        else{
            printf ("Discarded cards: ");
        }

        //if there have a second node, then we need to discard node
        while (theList->next->next){
            //NODE* button = takeButtonPtr(theList);
            int ans = takePopTurnToBack(theList, takeButtonPtr(theList));

            //if theres only one node after discarded a node, then it need to '\n'
            if (!(theList->next->next)){
                printf ("%d\n", ans);
            }
            else{
                printf ("%d, ", ans);
            }
        }

        //print last node value
        printf ("Remaining card: %d\n", theList->next->val);

        //free remaining node
        free(theList->next);
        free(theList);
    }
}
```
我的寫法
寫得不好的話鞭小力一點