通过增加坐标直到欧氏距离 <= D 来确定获胜者（C++）

2024 年 08 月 29 日 | 阅读 9 分钟

引言

在此 C++ 方法中，目标是通过系统地递增坐标值，直到从原点开始的欧几里得距离小于或等于指定的 D，来确定一组获胜的坐标。该算法从二维平面上原点 (0,0) 的初始坐标开始，并采用系统递增策略。欧几里得距离，使用距离公式计算，作为确定获胜坐标的标准。此方法确保了对坐标空间的结构化探索，同时递增x和y值，直到满足所需的距离条件。此方法的简洁性和清晰性使其成为系统且可预测地找到指定欧几里得距离内获胜点的有效方式。

程序

#include <iostream>
#include <cmath>
using namespace std;
// Function to calculate Euclidean distance between two points
double calculateDistance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}
int main() {
    int x_winner, y_winner;  // Coordinates of the winning point
    double D;  // Maximum allowed distance
    // Input the maximum allowed distance
    cout << "Enter the maximum distance (D): ";
    cin >> D;
    // Loop to iterate through possible coordinates
    for (int x = 0; ; x++) {
        for (int y = 0; ; y++) {
            // Calculate Euclidean distance for the current coordinates
            double distance = calculateDistance(0, 0, x, y);
            // Check if the distance is less than or equal to D
            if (distance <= D) {
                // If yes, set the winner coordinates and break out of the loops
                x_winner = x;
                y_winner = y;
                break;
            }
        }
        // Break out of the outer loop if a winner is found
        if (calculateDistance(0, 0, x_winner, y_winner) <= D) {
            break;
        }
    }
    // Output the winner coordinates
    cout << "The winner coordinates are: (" << x_winner << ", " << y_winner << ")" << endl;
    return 0;
}

输出

Enter the maximum distance (D): 5
The winner coordinates are: (0, 0)

说明

引言

该代码旨在通过逐渐递增 x 和 y 值来找到一组获胜坐标，直到从原点 (0,0) 到这些坐标的欧几里得距离小于或等于指定的 D。

计算欧几里得距离的函数

calculateDistance 函数使用熟悉的距离公式：sqrt((x2 - x1)^2 + (y2 - y1)^2) 来计算两点之间的欧几里得距离。

主逻辑

用户输入

程序首先提示用户输入允许的最大距离 (D)。

嵌套循环

代码使用嵌套循环遍历可能的坐标值。

距离计算

对于每一组坐标(x, y)，它使用 calculateDistance 函数计算与原点 (0,0) 的欧几里得距离。

获胜条件检查

如果计算出的距离小于或等于指定的 D，则认为这些坐标是获胜的，并且循环中断。

输出

最后，程序输出获胜的坐标。

无限循环

无限循环的使用是故意的。外层循环持续进行，直到找到一组获胜的坐标。内层循环无限期地持续进行，直到满足特定 x 值的获胜条件。这确保了对获胜坐标的系统搜索。

复杂度分析

时间复杂度

由于存在无限循环，代码的时间复杂度并不直接。嵌套循环递增 x 和 y 坐标，直到满足获胜条件，并且此过程可能会无限期地持续进行，直到找到一组合适的坐标。因此，时间复杂度最好描述为无限或无界。

空间复杂度

该代码的空间复杂度很小且恒定。它不使用任何会导致显著内存使用的数据结构或算法。主要的内存消耗与x、y、D、距离以及获胜坐标x_winner 和 y_winner 等变量相关。这些变量占用的内存量是恒定的，与输入值无关。因此，空间复杂度被认为是恒定的或O(1)。

方法 1：使用带步长增量的线性搜索

该方法采用系统线性搜索策略来查找最大欧几里得距离 (D) 内的坐标。

它从原点 (0, 0) 开始，并通过固定的步长迭代地增加 x 和 y 坐标。

程序

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int stepSize = 1;  // Step size for coordinate increment
    double D;  // Maximum allowed distance
    // Input the maximum allowed distance
    cout << "Enter the maximum distance (D): ";
    cin >> D;
    int x = 0, y = 0;
    // Linear search with step increment
    while (true) {
        double distance = sqrt(pow(x, 2) + pow(y, 2));
        // Check if the distance is less than or equal to D
        if (distance <= D) {
            cout << "The winner coordinates are: (" << x << ", " << y << ")" << endl;
            break;
        }
        // Increment coordinates by stepSize
        x += stepSize;
        y += stepSize;
    }
    return 0;
}

输出

Enter the maximum distance (D): 5
The winner coordinates are: (0, 0)

说明

初始化

stepSize 设置为 1，表示在每次迭代中坐标将增加的量。

D 是允许的最大距离，程序将使用它来查找获胜的坐标。

用户输入

用户被提示输入允许的最大距离 (D)。

坐标初始化

x 和 y 初始化为 0，代表二维平面中的起点（原点）。

线性搜索

程序进入无限循环（while (true)）以执行获胜坐标的线性搜索。

对于循环的每次迭代

使用距离公式计算从原点 (0,0) 到当前坐标 (x, y) 的欧几里得距离。

如果计算出的距离小于或等于指定的最大距离 (D)，则当前坐标被视为获胜者。

然后显示获胜的坐标，并中断循环。

增量

如果未满足距离条件，则在每次迭代中将坐标(x 和 y) 按 stepSize 递增。

这种增量确保程序系统地探索二维平面中的不同点。

输出

最终输出显示获胜的坐标，提供满足从原点开始的指定最大距离条件的点。

复杂度分析

时间复杂度

代码的时间复杂度由while (true) 循环中的迭代次数决定。

由于循环以固定的 stepSize 递增x 和 y，直到找到获胜的坐标，因此时间复杂度是迭代次数的线性函数。

如果我们表示迭代次数为 N，则时间复杂度为 O(N)。

空间复杂度

代码的空间复杂度是恒定的(O(1))，因为无论输入如何，它使用的内存量是固定的。

变量stepSize、D、x、y 和 distance 在程序执行期间都占用恒定的内存量。

这些变量所需的空间不随输入的大小而增长。

方法 2：使用二次搜索进行对角线移动

该方法采用系统二次搜索策略来查找最大欧几里得距离 (D) 内的坐标。

它从原点 (0, 0) 开始，并以二次模式增量移动，从而在对角线上覆盖更多区域。

程序

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int D;  // Maximum allowed distance
    // Input the maximum allowed distance
    cout << "Enter the maximum distance (D): ";
    cin >> D;
    int x = 0, y = 0;
    // Quadratic search with diagonal movement
    while (true) {
        double distance = sqrt(pow(x, 2) + pow(y, 2));
        // Check if the distance is less than or equal to D
        if (distance <= D) {
            cout << "The winner coordinates are: (" << x << ", " << y << ")" << endl;
            break;
        }
        // Increment coordinates quadratically
        x += (x >= y) ? x : y;
        y += (x >= y) ? x : y;
    }
    return 0;
}

输出

Enter the maximum distance (D): 5
The winner coordinates are: (0, 0)

说明

用户输入

用户被提示输入允许的最大距离(D)。

坐标初始化

x 和 y 初始化为 0，代表二维平面中的起点（原点）。

带对角线移动的二次搜索

程序进入无限循环（while (true)）以执行带对角线移动的二次搜索以查找获胜的坐标。

对于循环的每次迭代

使用距离公式计算从原点 (0,0) 到当前坐标(x, y) 的欧几里得距离。

如果计算出的距离小于或等于指定的 D，则当前坐标被视为获胜者。

然后显示获胜的坐标，并中断循环。

增量 - 二次移动

如果未满足距离条件，则以二次方式递增坐标 (x 和 y)。

在每次迭代中，将x 和 y 中较大的值添加到x 和 y 中。

这种二次增量模式允许程序更快地覆盖二维平面中的更大区域。

输出

最终输出显示获胜的坐标，提供满足从原点开始的指定最大距离条件的点。

复杂度分析

时间复杂度

时间复杂度取决于while (true) 循环中的迭代次数。

该循环执行二次搜索模式，其中迭代次数受坐标x和y的增长影响。

时间复杂度可视为二次方，表示为O(N^2)，其中N是找到获胜坐标所需的迭代次数。

空间复杂度

空间复杂度是恒定的，表示为O(1)，因为程序的内存使用量与输入值无关。

变量D、x、y 和 distance 在程序执行期间都占用恒定的内存量。

这些变量所需的空间不随输入大小而增长。

方法 3：带收敛的随机搜索

该方法使用随机搜索策略来查找最大欧几里得距离 (D) 内的坐标。

它从指定范围内的随机初始坐标开始，并迭代地随机调整坐标。

程序

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;
int main() {
    int D;  // Maximum allowed distance
    // Input the maximum allowed distance
    cout << "Enter the maximum distance (D): ";
    cin >> D;
    srand(time(0));  // Seed for random number generation
    int x = rand() % (2 * D) - D;  // Random initial x within [-D, D]
    int y = rand() % (2 * D) - D;  // Random initial y within [-D, D]
    while (true) {
        double distance = sqrt(pow(x, 2) + pow(y, 2));
        // Check if the distance is less than or equal to D
        if (distance <= D) {
            cout << "The winner coordinates are: (" << x << ", " << y << ")" << endl;
            break;
        }
        // Randomly adjust coordinates
        x += rand() % (2 * D) - D;
        y += rand() % (2 * D) - D;
    }
    return 0;
}

输出

Enter the maximum distance (D): 6
The winner coordinates are: (-3, 5)

说明

用户输入

用户输入允许的最大距离(D)。

随机初始化

使用rand()函数在[-D, D]范围内选择随机初始坐标(x 和 y)。

srand(time(0))调用根据当前时间播种随机数生成器。

随机搜索迭代

在每次迭代中，程序计算从原点到当前坐标的欧几里得距离。

如果计算出的距离小于或等于 D，则当前坐标被视为获胜者，程序终止。

否则，它会随机调整坐标以探索二维平面的不同区域。

随机调整

在每次迭代中，都会对x和y进行随机调整。

调整范围在[-D, D]内，为搜索引入随机性。

收敛

随机调整会在坐标中产生变异。

经过多次迭代，随机性倾向于收敛到满足欧几里得距离条件的坐标。

输出

一旦找到获胜的坐标，程序就会输出它们。

复杂度分析

时间复杂度

由于其随机性质，该方法的时间复杂度很难精确确定。

平均而言，时间复杂度预计会相对较高，因为它取决于找到指定欧几里得距离内坐标所需的迭代次数。

平均时间复杂度可能近似为 O(N)，其中N是所需迭代次数的平均值。

空间复杂度

空间复杂度是恒定的，表示为O(1)，因为程序的内存使用量与输入值无关。

变量 D、x、y、distance 以及随机数生成变量在程序执行期间都占用恒定的内存量。

这些变量所需的空间不随输入的大小而增长。

下一个主题如何在 C++ 中从不同函数访问局部变量

通过增加坐标直到欧氏距离 <= D 来确定获胜者（C++）

引言

程序

方法 1：使用带步长增量的线性搜索

程序

方法 2：使用二次搜索进行对角线移动

程序

方法 3：带收敛的随机搜索

程序

联系信息

关注我们

教程

面试题

在线编译器

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++ 杂项

通过增加坐标直到欧氏距离 <= D 来确定获胜者（C++）

引言

程序

方法 1：使用带步长增量的线性搜索

程序

方法 2：使用二次搜索进行对角线移动

程序

方法 3：带收敛的随机搜索

程序

相关帖子

C++ STL 中的 match_results empty()

螺旋形式的层序遍历

C++ 预处理器

C++ Clamp

C++ 模板与 Java 泛型

C++ 中堆与树的比较

C++ 汉诺塔算法

虚函数与运行时多态

C++ 中 std::set::lower_bound 和 std::lower_bound 的区别

C++ 程序切换字符串的大小写

订阅 Tpoint Tech

联系信息