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。
假定:
- 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))
- 结果
点击获得更多编程练习题。欢迎Follow,感谢Star!!! 扫描关注微信公众号pythonfan,获取更多。
image image
网友评论