C++ 淘汰赛

2025年3月25日 | 阅读 4 分钟

C++ 淘汰赛 包括从 1 到 n 的数字一个接一个地移除，直到只剩下一个。每一轮都从左到右移除，然后改变方向。每一轮中，一半剩余的元素被移除。解决这个问题的实用方法是迭代或递归解决方案，并记录其起始位置、淘汰方向和步长。由于利用淘汰过程中的模式在最佳情况下会给出 O(logn) 的时间复杂度，因此该方法是最好的。淘汰赛是算法学习的适当测试，因为它强调了 C++ 中的关键概念，如循环、条件和优化。

C++ 中的淘汰赛程序要求对数据结构、算法以及某些情况下的递归有很好的理解。下面是对一个流行的淘汰赛变体的回顾。

问题描述： 根据问题描述，给定一个整数 n，表示从 1 到 n 的数字序列，必须使用以下标准淘汰数字：

组件应从左到右移除。
第一轮之后，从右到左移除项目。
沿着这些方向继续，直到只剩下一个数字。
返回最后一个数字。

算法方法

递归方法： 由于问题包含交替淘汰模式，因此递归可以使解决方案更简单。
迭代方法： 使用循环并监控步长、当前范围和淘汰方向也证明是有效的。
数学观察： 通常使用公式化或简化计算的方法，通过观察数字淘汰的模式来发现解决方案。

复杂度

复杂度考虑： 由于每轮元素数量减半，因此时间复杂度通常是对数级的，即 O(logn)。

示例 1

让我们举一个例子来说明 C++ 中的淘汰赛。

#include <iostream>
using namespace std;

int eliminationGame(int n) {
    bool leftToRight = true; // Start eliminating from left to right
    int remaining = n;
    int step = 1;
    int head = 1;

    while (remaining > 1) {
        // Move the head based on the elimination direction
        if (leftToRight || remaining % 2 == 1) {
            head += step;
        }
        // Halve the remaining elements, double the step size, and toggle direction
        remaining /= 2;
        step *= 2;
        leftToRight = !leftToRight;
    }

    return head;
}

int main() {
    int n = 9;
    cout << "The last remaining number is: " << eliminationGame(n) << endl;
    return 0;
}   

输出

 
The last remaining number is: 6

示例 2

让我们再举一个例子来说明 C++ 中的淘汰赛。

#include <iostream>
using namespace std;

int eliminationGameHelper(int n, bool leftToRight) {
    // Base case: if only one element is left, return it
    if (n == 1) return 1;

    // If moving left-to-right, the result is the first in the reduced list
    // If moving right-to-left and n is even, the result is also the first in the reduced list
    if (leftToRight || n % 2 == 1) {
        return 2 * eliminationGameHelper(n / 2, !leftToRight);
    } else {
        return 2 * eliminationGameHelper(n / 2, !leftToRight) - 1;
    }
}

int eliminationGame(int n) {
    return eliminationGameHelper(n, true);  // Start with left-to-right elimination
}

int main() {
    int n = 9;
    cout << "The last remaining number is: " << eliminationGame(n) << endl;
    return 0;
}   

输出

 
The last remaining number is: 6

说明

递归函数： GameHelper 函数接收布尔值 leftToRight（淘汰方向）和淘汰数 n（剩余组件数量）作为输入。
基本情况： 如果 n = 1，则只剩下一个元素，返回 1。
递归情况： 如果我们是从右到左进行，或者 n 是奇数，则递归结果会加倍。
当 n 是偶数时，右到左会使递归结果偏移 1。
包装函数： 当游戏需要帮助时，removalDirection 最初设置为从左到右。

结论

总而言之，淘汰赛要求有效地管理淘汰轮次和巧妙地操作序列。它测试候选人在 C++ 递归和迭代技术方面的熟练程度。这个问题可以应用于大型输入，因为它通过交替淘汰方向并每轮减小序列大小来优化对数时间复杂度。递归和迭代方法只是实现，可以帮助学习者更深入地了解条件、数据处理和序列背后的数学原理。总的来说，淘汰赛简化了重要的 C++ 编程概念，并提供了一种相当有趣的方式来审视代码优化和算法效率。

下一主题C++ 中的 Hierholzer 算法

C++ 淘汰赛

算法方法

复杂度

示例 1

示例 2

说明

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 淘汰赛

算法方法

复杂度

示例 1

示例 2

说明

结论

相关帖子

C++ std::common_type T1, T2 ::type 函数

在 C++ 中交换不同容器的子范围

C++ std::not_fn 函数

C++ 中的中途相遇算法

C++ 中查找 N 个坐标对之间的最大曼哈顿距离

C++ 中的 Enneacontahexagon 数

C++ 类中的辅助函数

C++ 中如何将二维矩阵旋转 90 度

C++ 中的 std::memory_order 枚举

如何在 C++ 中实现反向 DNS 查询缓存

订阅 Tpoint Tech

联系信息

关注我们

教程