Zerojudge 基礎題庫d461 班際籃球賽

- 11月 30, 2019

解了這麼多數學題，今天來解一些生活應用問題吧。
當然，要解就要解最簡單的~

當我看到題目的那一刻，我已經想到如何解了

如果有十個班級，你要怎麼分?
反正一場籃球比賽最多兩個班級PK對吧
所以每一階我可以有10/2場比賽，也就是五場比賽
五場比賽，代表會有五個班級會被淘汰掉，所以這階比賽後會剩下10-5，也就是5個班級
然後5/2 = 2...1，5-2 = 3
再來3/2 = 1...1，3-1 = 2
最後2/2 = 1，2-1=1 也就是WINNER!

看到這裡，來寫流程吧:

準備工作:
設n為比賽總次數，初始值是0
設k為剩餘班級數
設kill為每階淘汰人數

輸入k

開始解題:
kill = k/2 (無條件捨去)
n = n + kill (淘汰人數等於比賽人數)
k = k - kill (算剩下人數)
...
直到k = 1為止

輸出:
n

轉成程式碼吧:

#include <iostream>
using namespace std;
int main()
{
    /*準備工作*/
    //設n為比賽總次數
    int n = 0;

    //設k為剩餘班級數
    int k;

    //設kill為每階淘汰人數
    int kill;

    //輸入k
    cin >> k;

    /*開始解題*/
    while(k != 1)      //直到k = 1為止
    {
        kill = k/2;    //(無條件捨去)
        n = n + kill;  //(淘汰人數等於比賽人數)
        k = k - kill;  //(算剩下人數)
    }

    /*輸出*/
    cout << n;
}