学习python3的野路子——GCD、冒泡排序、约瑟夫环
2019-03-05 本文已影响0人
HerdingCat
GCD
关于最大公约数的求解，先前的文章[1]并不是很好，此处直接引用相关资料[2]。
以下是编程题
# PAT中的基础编程题目集函数题7-24
def GCD(a, b):
r = a % b
while r:
a = b
b = r
r = a % b
return b
a, b = input().split('/')
r = GCD(int(a), int(b))
print('%d/%d' %(int(a)/r, int(b)/r))
# PAT中的基础编程题目集函数题7-33
def GCD(a, b):
r = a % b
while r:
a = b
b = r
r = a % b
return b
a, b = input().split()
a1, a2 = a.split('/')
b1, b2 = b.split('/')
a = int(a1) * int(b2) + int(b1) * int(a2)
b = int(a2) * int(b2)
r = GCD(a, b)
if b/r == 1:
print(int(a/r))
else :
print('%d/%d' %(a/r, b/r))
# PAT中的基础编程题目集函数题7-35
def GCD(a, b):
r = a % b
while r:
a = b
b = r
r = a % b
return b
def addition(a, b):
a1, a2 = a.split('/')
b1, b2 = b.split('/')
a = int(a1) * int(b2) + int(b1) * int(a2)
b = int(a2) * int(b2)
r = GCD(a, b)
return str(a//r) + '/' + str(b//r)
n = eval(input())
fracs = input().split()
sum = '0/1'
for frac in fracs:
sum = addition(sum, frac)
a, b = sum.split('/')
a = int(a)
b = int(b) * n
r = GCD(a, b)
if b/r == 1:
print(int(a/r))
else :
print('%d/%d' %(a/r, b/r))
冒泡排序
顾名思义水中有一连串气泡，由于水压的不同导致气泡的大小也不同；显然水深处有大气泡是不合理的，因此要和附近水较浅处的小气泡对换。可以简单的理解该过程，同样可参考需要优质的网上资源[3]。
以下是编程题。
# PAT中的基础编程题目集函数题7-27
N, K = input().split()
elems = input().split()
for i in range(0, int(N)):
elems[i] = int(elems[i])
for k in range(1, int(K) + 1): # 此循环用于冒泡排序
for i in range(1, int(N)):
if elems[i - 1] > elems[i]:
tmp = elems[i - 1]
elems[i - 1] = elems[i]
elems[i] = tmp
pattern = ''
ans = ''
for i in range(0, int(N)):
if i:
pattern += ' '
pattern += '%d'
ans += str(elems[i]) + ','
print(pattern %(eval(ans)))
# PAT中的基础编程题目集函数题7-30
N, K = input().split()
elems = []
for i in range(0, int(N)):
elems.append(input())
for k in range(1, int(K) + 1):
for i in range(1, int(N)):
if elems[i - 1] > elems[i]:
tmp = elems[i - 1]
elems[i - 1] = elems[i]
elems[i] = tmp
for i in range(0, int(N)):
print(elems[i])
约瑟夫环
作为竞赛的经典题型，同样网络上有许多优质的解答。对两种解法做说明的资料[4]；以及本文作者认为是参考了《Concrete Mathematics》的推导过程[5]。
# PAT中的基础编程题目集函数题7-28
n = eval(input())
monkeys = [] # 一群猴子，初始时，每只猴子各拿一个编号；当退出时，赋值为0表示退出
for monkey in range(1, n + 1):
monkeys.append(monkey)
i = 0 # 保证猴子围成一个圈
cnt = 0 # 计数有多少猴子退出
next = 0 # 报号的传递
ans = 0
while cnt != n:
if monkeys[i]:
next += 1
if next == 3:
ans = monkeys[i]
monkeys[i] = 0
next = 0
cnt += 1
i += 1
if i == n:
i = 0
print(ans)
本文作为PAT编程题系列最后一篇，之后可能会着眼于相关包的功能。
万分感谢各位。
