python写出欧几里得算法

欧几里得算法，又称辗转相除法，用于计算两个整数的最大公约数（GCD）。在Python中，可以使用递归或迭代的方式来实现欧几里得算法。以下是使用递归方式实现欧几里得算法的Python代码：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

以上代码通过不断用较小数除以较大数的余数来进行递归，直到余数为0时，返回较大数即为最大公约数。

以下是使用迭代方式实现欧几里得算法的Python代码：

def gcd(a, b):
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

以上代码通过不断求余数并更新两个数的值，直到余数为0时，返回较大数即为最大公约数。

相关问题

Python代码写出c均值算法误差平方和准则函数

以下是Python代码实现c均值算法误差平方和准则函数：

import numpy as np

def cmeans_error(data, centers, m, p):
    """
    计算c均值算法误差平方和准则函数
    data: 数据集，每一行代表一个样本
    centers: 聚类中心，每一行代表一个聚类中心
    m: 模糊指数，取值范围为 [1, ∞)
    p: 范数，取值范围为 [1, ∞)。当 p=2 时，表示欧几里得距离
    """
    n_samples = data.shape[0]
    n_centers = centers.shape[0]
    distances = np.zeros((n_samples, n_centers))
    # 计算每个样本与每个聚类中心的距离
    for i in range(n_centers):
        distances[:, i] = np.linalg.norm(data - centers[i], ord=p, axis=1)
    # 计算隶属度矩阵
    u = np.power(distances, -2/(m-1))
    u /= np.sum(u, axis=1, keepdims=True)
    # 计算误差平方和准则函数
    J = np.sum(np.power(u, m) * np.power(distances, 2))
    return J

其中，`data`是数据集，每一行代表一个样本；`centers`是聚类中心，每一行代表一个聚类中心；`m`是模糊指数，取值范围为 [1, ∞)，一般取值为2；`p`是范数，取值范围为 [1, ∞)，当 p=2 时，表示欧几里得距离。函数的返回值为误差平方和准则函数的值。

用python写出分治法求解最近点对问题并出图

好的，这个问题是关于算法的，我可以回答。以下是用Python实现分治法求解最近点对问题的代码，并附带着出图功能：

import math
import matplotlib.pyplot as plt
import random

def dist(p1, p2):
    # 计算两点之间的欧几里得距离
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

def brute_force(points, n):
    # brute-force算法求最近点对
    min_d = float('inf')
    for i in range(n):
        for j in range(i+1, n):
            d = dist(points[i], points[j])
            if d < min_d:
                min_d = d
                pair = (points[i], points[j])
    return pair, min_d

def closest_pair(points_x, points_y, n):
    if n <= 3:
        # 点数小于等于3直接使用暴力算法求解最近点对
        return brute_force(points_x, n)

    # 分治求解最近点对问题
    mid = n // 2
    mid_point = points_x[mid]
    # 分治左侧点集合
    points_y_left = [p for p in points_y if p[0] <= mid_point[0]]
    left_pair, left_min = closest_pair(points_x[:mid], points_y_left, mid)
    # 分治右侧点集合
    points_y_right = [p for p in points_y if p[0] > mid_point[0]]
    right_pair, right_min = closest_pair(points_x[mid:], points_y_right, n-mid)

    # 取最小距离
    min_d = min(left_min, right_min)
    if min_d == 0:
        return (points_x[0], points_x[0]), 0

    # 跨越左右集合，且分别在其中一个集合上、距离不大于 min_d 的点对
    strip_points = [p for p in points_y if abs(p[0]-mid_point[0]) < min_d]
    strip_len = len(strip_points)
    # 在纵坐标方向上排序
    strip_points.sort(key = lambda x:x[1])
    for i in range(strip_len):
        for j in range(i+1, strip_len):
            if strip_points[j][1] - strip_points[i][1] >= min_d:
                break
            d = dist(strip_points[i], strip_points[j])
            if d < min_d:
                min_d = d
                pair = (strip_points[i], strip_points[j])
    return pair, min_d

def generate_points(num):
    # 生成 num 个二元组坐标
    return [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(num)]

def plot(points, pair):
    # 画图显示点集和最近点对
    plt.plot([p[0] for p in points], [p[1] for p in points], 'ro')
    plt.plot([pair[0][0], pair[1][0]], [pair[0][1], pair[1][1]], 'b-')
    plt.show()

if __name__ == '__main__':
    points = generate_points(10)
    # 按横坐标排序
    points_x = sorted(points, key = lambda x:x[0])
    # 按纵坐标排序
    points_y = sorted(points, key = lambda x:x[1])
    pair, min_dist = closest_pair(points_x, points_y, len(points))
    plot(points, pair)
    print("The closest pair is {} with distance {:.3f}".format(pair, min_dist))

代码说明：首先定义了一个点之间的距离计算函数`dist`，以及一个暴力算法求最近点对问题的函数`brute_force`。然后是核心函数`closest_pair`，该函数使用分治算法求最近点对问题，首先将点集按横坐标排序，然后将点集按纵坐标排序，之后按照分治思想，将点集分成左右两个部分，并递归求得左右两个部分的最近点对。接着，通过“方法2”的技巧，将整个点集按横坐标在 x=mid 附近分为两半，则从两半的点集中寻找最近点对。最后，将两部分结果中的最小距离与经过两部分的距离计算，得到整个点集中的最近点对。最后是画图函数`plot`，该函数将点集和最近点对画出来。

你可以将`generate_points(10)`中的 10 改为任意正整数，生成不同数量的随机点进行测试。此外，如果采用了“方法2”，还需注意输入点集的按横坐标升序排序。