每周一课：L12 Euclidean algorithm(12.

12.png

P12.1 ChocolatesByNumbers

There are N chocolates in a circle. Count the number of chocolates you will eat.

P12.1 巧克力数
N块巧克力围成一个圈，你能吃到几颗

N和M为两个正整数。整数N表示一圈中摆放的巧克力数量，编号从0到N-1。

吃了巧克力，这位置只剩下一个空的包装纸。下面开始说明如何吃巧克力。如果吃的是X号巧克力，那么接下来你将吃的是(X+M)modN号巧克力。当遇到空包装时，就停止进食。

例如，给定整数N=10，M=4。可以吃到的巧克力编号为：0，4，8，2，6。

按照上述规则计算可以吃到的巧克力的数量。

编写函数：

def solution(N, M)

给定两个正整数N和M，则返回可以吃到的巧克力的数量。

例如，给定整数N=10，M=4。函数应该返回5。

假定：

1. N和M均是区间[1，100000000]中的整数；

• 解题思路

可以吃到的巧克力的数量就是总的巧克力的颗数N除以N和M的最大公约数。并且需要利用欧几里得算法，也就是辗转相除法计算N和M的最大公约数。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 12：Euclidean algorithm
# P 12.1 ChocolatesByNumbers


def solution_base(N, M):
    """
    N块巧克力排成一圈，从0号开始吃，每次间隔M-1个位置，可以吃到的巧克力的数量, 常规方法
    :param N: 巧克力数量
    :param M: 间隔的个数
    :return: 返回可以吃到的巧克力的数量
    """
    eat_dict = {}
    eat_count = 0
    if M == 1 or N == 1:
        return N
    while 1:
        sum_num = eat_count * M
        start_num = sum_num % N
        if start_num not in eat_dict:
            eat_count += 1
            eat_dict[start_num] = 1
        else:
            break
    return eat_count


def gcd(N, M):
    """
    计算N和M的最大公约数，利用欧几里得算法——辗转相除法
    :param N: 整数
    :param M: 整数
    :return: N和M的最大公约数
    """
    if N % M == 0:
        return M
    else:
        return gcd(M, N % M)


def solution(N, M):
    """
    N块巧克力排成一圈，从0号开始吃，每次间隔M-1个位置，可以吃到的巧克力的数量,时间复杂度O(log(N + M))
    首先计算N和M的最大公约数P, N除以P得到的商即为所求
    :param N: 巧克力数量
    :param M: 间隔的个数
    :return: 返回可以吃到的巧克力的数量
    """
    return int(N / gcd(N, M))

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image