每周一课:L12 Euclidean algorithm(12.

作者: AiFany | 来源:发表于2019-02-17 21:47 被阅读3次
    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

    相关文章

      网友评论

        本文标题:每周一课:L12 Euclidean algorithm(12.

        本文链接:https://www.haomeiwen.com/subject/fbpneqtx.html