【$Educoder$作业】问题求解——while 循环

只要进入了循环，那么所有的算法也会慢慢走进我们的视野。从最简单的辗转相除，到暂时没提到的二分、排序，路很长，慢慢来。

$T1$辗转相除法

所谓的辗转相除法，其最本质的依据就是如果$c|a、c|b$就会有$c|a-b$。这是显然的。辗转相除就是利用的这个原理，通过不断地相减来得到$gcd$。

a = int(input())
b = int(input())
########## Begin ##########
c = a % b
while c :
    a = b
    b = c
    c = a % b
print(b)
########## End ##########

$T2$ 计算机如何进行复杂运算

这个题目本身的代码实现是容易的，但是其中的思想是牛顿斜线逼近，还是有点意思的。

x = eval(input())
########## Begin ##########
g = x / 2
while abs(x - g * g) >= 10**(-6) :
    g = (g + x / g) / 2
########## End ##########
print('%.5f' % g)

$T3$ 计算机如何进行复杂运算（续）

平方完了就搞三次方

x = eval(input())
########## Begin ##########
g1 = x / 3
g2 = 2 * g1 / 3 + x / (3 * g1 * g1)
while abs(g1 - g2) >= 10 ** -6 :
    g1 = g2
    g2 = 2 * g1 / 3 + x / (3 * g1 * g1)
########## End ##########
print('%.5f' % g2)

$T4$ 见证历史的数

$\pi$的意义是很大的，但是这个题是容易的。

n = int(input())
########## Begin ##########
pi = 0
i = 1
while i <= n :
    pi += ((-1) ** (i - 1)) / (2 * i - 1)
    i += 1
pi *= 4
########## End ##########
print('%.6f' % pi) #圆周率= 3.1415926…

$T5$ 见证历史的数（续）

利用马青公式的实现是简单的，这里我们聊一下那个注里的“一些技巧”。
他的本质思想可能很难理解，我们这里有两个前置知识点：第一个是$Python$的浮点数只能保留$14$位；第二个是$Python$支持高精度。也就是说$Python$的整数量并没有上限。也就是说，我们希望通过乘以$10$的多少次方来存储这个$\pi$。
当然，盲目的乘肯定有问题，因为取模运算本身就会损失精度，所以他给了一个缓冲量$k$，多乘$10^k$来避免这个取模误差。

n = int(input())
########## Begin ##########
cn = 239
i = 1
A, B = 0, 0
while i <= n :
    A += ((-1) ** (i - 1)) / ((2 * i - 1) * 5 ** (2 * i - 1))
    B += ((-1) ** (i - 1)) / ((2 * i - 1) * cn ** (2 * i - 1))
    i += 1
pi = 16 * A - 4 * B
########## End ##########
print('%.14f' % pi) #圆周率= 3.141592653589793…

$T6$ 三个数的最大公约数

无脑循环就行，下一个题也是一样的。
两个题一起说，原因就是三个数的最大公约数肯定不会小于$1$因为$1$是公约数；三个数的最小公倍数肯定不会大于$a\ast b\ast c$因为这个乘积是公倍数。如此来看，我们的循环是有保证的。

a = int(input())
b = int(input())
c = int(input())
########## Begin ##########
i = a
while True :
    if a % i == 0 and b % i == 0 and c % i == 0 :
        print(i)
        break
    i -= 1
########## End ##########

$T7$ 三个数的最小公倍数

a = int(input())
b = int(input())
c = int(input())
########## Begin ##########
i = a
while True :
    if i % a == 0 and i % b == 0 and i % c == 0 :
        print(i)
        break
    i += 1
########## End ##########

$T8$ 空瓶换酒

答案是$4\ast n-5$，通过归纳法证明是容易的。大概意思就是，一个空瓶子就可以喝一瓶酒，原因是两个空瓶子换回来的酒喝掉之后还剩一个空瓶子，也就相当于用一个空瓶子换了一瓶酒和一个盖子；同样，三个盖子就相当于喝了一次酒加一个空瓶子。
第二点，我们的交换顺序是没有关系的，就是说我们先用盖子换还是先用瓶子换是无所谓的，这个是显然的。
基于这两点，我们就可以先把盖子换空，然后开始换瓶子同时动态的保证盖子的总数目不多于$3$个即可。
以上是数学思路，用循环的话就非常简单。

n = int(input())
########## Begin ##########
a, b = n, n
ans = n
while a >= 4 or b >= 2 :
    if a >= 4 :
        a -= 3
        b += 1
        ans += 1
    if b >= 2 :
        b -= 1
        a += 1
        ans += 1
print(ans)
########## End ##########