試合中のペアリング回数の問題について述べる

試合中のペアリング回数
質問:試合中のチーム数を表す整数nをあげます.試合は独特の試合制に従っている.
現在のチーム数が偶数であれば、各チームは別のチームとペアを組む.全部でn/2試合が行われ、n/2チームが次のラウンドに進出する.現在のチーム数が奇数であれば、ランダムにラウンドして1つのチームに昇格し、残りのチームがペアになります.合計(n-1)/2試合が行われ、(n-1)/2+1チームが次のラウンドに進出する.優勝チームが決まるまで試合で行われたペアリングの回数を返す.
構想:例:入力:n=7出力:6解釈:試合詳細:

第1ラウンド:チーム数=7、ペアリング回数=3、4チームが昇格.

第2ラウンド:チーム数=4、ペアリング回数=2、2チーム昇格.

第3ラウンド:チーム数=2、ペアリング回数=1で優勝チームを1本決める.合計ペアリング数=3+2+1=6

入力:n=14出力:13解釈:試合詳細:

第1ラウンド:チーム数=14、ペア数=7、7チーム昇格.

第2ラウンド:チーム数=7、ペアリング回数=3、4チームが昇格.

第3ラウンド:チーム数=4、ペアリング回数=2、2チーム昇格.

第4ラウンド:チーム数=2、ペアリング回数=1で優勝チームを1本決める.合計ペアリング数=7+3+2+1=13

方法1:テーマの要求に従って反復して和を求める

class Solution {
     
public:
    int numberOfMatches(int& n) const {
     
        if(n <= 1) return 0;
        auto count = 0;
        while(n > 1) {
     
            count += n / 2;
            n = n & 1 ? (n + 1) / 2 : n / 2;
        }
        return count;
    }
};

方法2:再帰

class Solution {
     
public:
    int numberOfMatches(int n) const {
     
        if(n <= 1) return 0;
        return n / 2 + numberOfMatches((n + 1) / 2);
    }
};

方法3:発見を通じて、私たちのペアリング回数は常にチーム数の1を減らすことに等しい.

class Solution {
     
public:
    int numberOfMatches(int n) {
     
        if(n <= 1) return 0;
        return n - 1;
    }
};