求N个数的最大公约数和最小公倍数以及Hankson"逆问题"（python）

求N个数的最大公约数和最小公倍数以及Hankson"逆问题"（python）

一、题目要求
1.基本要求：
求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题
2.提高要求：
已知正整数a0,a1,b0,b1，设某未知正整数x满足：
（1）x和a0的最大公约数是a1；
（2）x和b0的最小公倍数是b1。
输入数据保证a0能被a1整除，b1能被b0整除。
对于每组数据：若不存在这样的x，请输出0；
若存在这样的x，请输出满足条件的x的个数；
二、算法设计
1.题目分析
基本要求:
n个数的最大公约数的求解，首先要输入n个数，并将数字进行保存。求解时求两个的最大公约数gcd(x1,x2),再将所得的数与第三个求解最大公约数gcd( gcd(x1,x2) , x3 )……如此递归调用即可求出n个数的最大公约数。
n个数的最小公倍数的求解，首先求两个的最小公倍数(x1x2)/gcd(x1,x2),再将所得的最小公倍数与第三个求最小公倍数，……，如此递归调用即可求出n个数的最小公倍数。
提高要求:
对题意进行分析，是将一次最大公约数求解和一次最小公倍数求解作为判断条件并求解，得出以下等式：
a1 = gcd( x , a0)
b1 = x * b0 / gcd( x , b0)
在输入时的判断条件：
a1 % a0 == 0
b1 % a1 == 0
2.算法设计
基于Python3.7
2.1对于求n个数的最大公约数和最小公倍数
（1）输入n个数，将输入的n个数保存至列表，利用append()函数添加至列表尾端，利用列表解决了存在数组里面，数组大小过小或者过大的问题
（2）求解最大公约数时，利用列表中的pop()函数从列表尾端连续删除两个数并返回这两个数的值，对两个数进行最大公约数函数调用得出一个结果，将结果利用append()添加至列表尾端
（3）重复（2）中的操作，直到列表中只剩下一个值时结束，仅剩的一个值就是n个数的最大公约数。
（4）求解最小公倍数时，利用列表中的pop()函数从列表尾端连续删除两个数并返回这两个数的值，对两个数进行最小公倍数的求解，将结果利用append()添加至列表尾端
（5）重复（4）中的操作，直到列表中只剩下一个值时结束，仅剩的一个值就是n个数的最小公倍数。
2.2 Hankson’逆问题’的求解
（1）输入n组数，每组数要求4个正整数，利用while(n 4 != count)进行判断输入的数的个数。
（2）将输入的数利用append()函数全部添加至列表中，再利用range()将长列表变成n个包含四个数的子列表。
（3）利用for语句将每个子列表取出，对子列表中的数利用a1 % a0 == 0 和b1 % a1 == 0进行正确性判断，符合输入要求则进行求解，否则输出数据有误。
（4）求解过程，定义一个计数器，将x从a1开始自增，利用a1 = gcd( x , a0)，b1 = x * b0 / gcd( x , b0)进行判断，符合要求计数器+1，直到x增加到b1.
然后输出计数器中的值。

三、算法示意图
1.求最大公约数：

2.求最小公倍数：

3.Hankson“逆问题”：

四、源代码

"""
功能：1.求N个数的最大公约数和最小公倍数.
      2.已知正整数a0,a1,b0,b1，设某未知正整数x满足：
         (1)x和a0的最大公约数是a1
         (2)x和b0的最小公倍数是b1
        输入数据保证a0能被a1整除，b1能被b0整除。
        对于每组数据：若不存在这样的x，请输出0；
        若存在这样的x，请输出满足条件的x的个数；
作者：Elf.苏洛曦

修改历史：
        1.  2019-03-20      创建，完成功能1
        2.  2019-03-21      完善功能1，完成功能2
"""

def gcd(a , b):
    """求最大公约数函数"""
    if a < b:
        a , b = b , a

    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a

def setNumber():
    n = int( input('您想输入数的个数：'))
    global list1
    list1 = []
    count = 0
    while (count < n):
        c = int(input('请输入:'))
        while (c <= 0):
            print("您输入的数有误，请重新输入：")
            c = int(input('请输入:'))
        list1.append(c)
        count += 1
    print(list1)

def compare():
    list2 = list(set(list1))
    list3 = list2[::]    #列表复制

    #求N个数最大公约数
    while len(list2) != 1:
        a1 = list2.pop()
        b1 = list2.pop()
        c = gcd(a1,b1)
        list2.append(c)

    #求最小公倍数
    while len(list3) != 1:
        a2 = list3.pop()
        b2 = list3.pop()
        c2 = gcd(a2,b2)
        d = ((a2 * b2) // c2)
        list3.append(d)

    print("你输入所有数的最大公约数为：",end="")
    print(list2[0])
    print("你输入所有数的最小公倍数为：", end="")
    print(list3[0])

def getX():
    global list4
    list4 = []
    count = 0
    want = 0
    n1 = int(input("请您输入组数："))
    print("每四个数为一组，请保证第一个能被第二个数整除，第四个数能被第三个数整除")
    while (n1 * 4 != count):
        c = int(input('请输入:'))
        while (c <= 0):
            print("您输入的数有误，请重新输入：")
            c = int(input('请输入:'))
        list4.append(c)              #将输入的数加入列表
        count += 1

    list5 = [list4[i:i+4] for i in range(0 ,len(list4),4)]   #将长列表的数，分为每组4个的子列表
    global count1   # x的计数器

    #遍历子列表，对每个字列表中的四个数进行操作
    for i in list5:
        list5=i           #取出子列表
        count1 = 0

        #判断是否满足输入要求
        if (list5[0] % list5[1] != 0 or list5[3] % list5[2] !=0):
            print(i,end="")
            print("这组数据不符合输入要求")
        else:
            for x in range(list5[1],list5[3]+1):
                if((gcd(x ,list5[0]==list5[1]))  and ((x *list5[2] / gcd(x , list5[2])))==list5[3] ):
                    count1 += 1
            print(i)
            print(count1)


print("1.求N个数的最大公约数和最小公倍数")
print("2.Hankson'逆问题'的求解")
n=int (input("请输入你想执行的操作的序号："))
while(n != 1 and n!= 2):
    print("您输入的序号不在范围内")
    n = int(input("请输入你想执行的操作的序号："))
if(n ==1):
    setNumber()
    compare()
if(n==2):
    getX()

五、调试和测试
1.出现错误及解决方法
（1）出现错误：
在没有错误提示的情况下，测试求n个数最大公约数和最小公倍数函数时出现如下错误：

在pop()删除数据时列表已经为空，提示错误在33行

解决方法：通过逻辑思考，发现列表中的数不用全部弹出进行运算，最后会剩余一个数在列表中，剩余数就是所求结果，将判断语句改为：

程序执行正确。

（2）出现错误：在没有提示错误的情况下测试Hankson’逆问题’，结果如下：


输入正确的测试数据后，多次输出了0~5
解决方法：通过调试发现是print(count1)函数执行的结果，所有可以确定print()函数在嵌套的层次上出现了问题，经过分析将print()缩进到到正确位置输出结果如下：

发现计数器的值与正确答案不相符，检查所在语句，考虑x的取值范围，因此在for下加入如下代码：

输出结果如下：

X的值仅到287，并未到288，才意识到切片函数range()包括左端数，而不包括右端的数，为右端的数+1，将其包括进去

再次测试，结果正确。
2．运行结果图
2.1.求最大公约数和最小公倍数：
输入四个数12,32,5,6 运行结果如下：

输入三个数，当输入为负整数和0时，提示错误并进行重新输入：

2.Hankson’逆问题’：
求解1组数，在输入数之前给出四个数的要求，输入完成后，给出四个数以及求解结果：

求解3组数，在输入数之前给出四个数的要求，输入负整数和0 提示错误，并重新输入，结果如下：


若不按提示要求输入，不符合输入的规定，则会输出错误。若不存在符合要求的x，则输出其数量为0。

六、总结
通过本次编程，我对求最小公倍数和最大公约数更加熟悉，同时对递归调用有了更深入的了解，也对python有了进一步了解，体会到了python语言的强大之处，但找到了自己在学习python中存在一些不足。在本次编码中对变量名的使用不够规范，没有达到见名知意。在同时函数中的功能比较混杂，没有做到将功能模块化。学习到了关于列表更多的操作，列如将长列表变成多个子列表的和，列表的拷贝和浅复制，含有子列表的列表的遍历。更重要的是学习到了对问题的思考方法和处理方法，可以将问题中的重要信息就行数学公式化，更容易看出解决问题的关键所在。