华为编程题-1

发表于 | 阅读次数:

题目描述

1
2

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

输出描述:

1
输入两个正整数A和B。

输出描述:

1
输出A和B的最小公倍数。

实例:

1
2
3
4
5
输入:
5
7
输出:
35

最大公倍数的解法:

  1. 质因数分解法
  2. 短除法
  3. 辗转相除法
  4. 更相减损法
    无论是短除法，还是分解质因数法，在质因数较大时，都会觉得困难。这时就需要用新的方法。
    辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    例如，求（319，377）：
    ∵ 319÷377=0（余319）
    ∴（319，377）=（377，319）；
    ∵ 377÷319=1（余58）
    ∴（377，319）=（319，58）；
    ∵ 319÷58=5（余29）
    ∴ （319，58）=（58，29）；
    ∵ 58÷29=2（余0）
    ∴ （58，29）= 29；
    ∴ （319，377）=29。

更相减损法:

1
2
3
4
5

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

1
2
3
4
5
6
7
8
9
10
11
例1．用更相减损术求98与63的最大公约数。
解：由于63不是偶数，把98和63以大数减小数，并辗转相减：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公约数等于7。
这个过程可以简单的写为：
（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.

利用质因数分解法做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import sys
import math
import copy
def iSPrime(num):
    limit=int(math.ceil(math.sqrt(num)))
    flag=1
    for i in range(2,limit+1):
        if num%i==0 and i!=num:
            flag=0
            break
    return flag

def FindPrime(num):
    r_list=list()
    if iSPrime(num):
        r_list.append(num)
        return r_list
    else:
        limit=int(num/2)
        for i in range(2,limit+1):
            if iSPrime(i):
                r_list.append(i)
        return  r_list

def  PrimeFen(num):
    t=copy.deepcopy(num)
    r_list=list()
    t_list=FindPrime(num)
    i=0
    while t>1 and i<len(t_list):
        if t%t_list[i]==0:
            t=t/t_list[i]
            r_list.append(t_list[i])
        else:
            i+=1
    return r_list

def Stat(L):
    d={}
    for i in L:
        if d.has_key(i):
            d[i]+=1
        else:
            d[i]=1
    return d

def FindMax(d1,d2):
    r={}
    for k,v in d1.items():
        if d2.has_key(k) and d2[k]>d1[k]:
            r[k]=d2[k]
            del d2[k]
        else:
            r[k]=d1[k]
    for k,v in d2.items():
        r[k]=v
    result=1
    for k,v in r.items():
        result=result*(k**v)
    return result

try:
    A,B=map(int,raw_input().split())
    Min=min(A,B)
    Max=max(A,B)
    if Max%Min==0:
        print Max
    else:
        Max_list=PrimeFen(Max)
        Min_list=PrimeFen(Min)
        d1=Stat(Max_list)
        d2=Stat(Min_list)
        r=FindMax(d1,d2)
        print r
except:
    pass

这种解法是最笨的,采用辗转相除最大公约数.再用两者的乘积进行相除,简单清新,但是容易造成最大数越界的问题:
辗转相除法

1
2
3
4
5
6
7
8
9
def func2(num1,num2):
    m=num1%num2;
    a=num2
    b=m
    while a%b>0:
        m=a%b
        a=b
        b=m
    return b

更相减损法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def func1(num1,num2):
    r_list=list()
    while num1%2==0 and num2%2==0:
        num1=num1/2
        num2=num2/2
        r_list.append(2)
    Max=max(num1,num2)
    Min=min(num1,num2)
    t=Max-Min
    while t!=Max:
        t=Max-Min
        Max=max(Min,t)
        Min=min(Min,t)
    for i in r_list:
        Min=Min*i

热评文章