algorithm - meetbill/op_practice_book GitHub Wiki

• 1 求值
  • 1.1 最大公约数
  • 1.2 最小公倍数
  • 1.3 中位数
• 2 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
• 3 排序
  • 3.1 冒泡排序
• 4 多线程

1 求值

1.1 最大公约数

两个正整数a和b（a>b），它们的最大公约数等于(b)和(a除以b的余数c)之间的最大公约数。

while b: 
    a,b=b,a%b

最后的a 就是最大公约数

1.2 最小公倍数

先用辗转相除法求出最大公约数，然后再利用（最小公倍数=两数乘积/最大公约数）求得最小公倍数。

def min(a, b):
    c = a*b
    while b: a,b = b, a%b
    return c//a

1.3 中位数

def median(data):
    data.sort()
    half = len(data) // 2
    return (data[half] + data[~half])/2

2 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

def getOneCount(num):
    if num > 0:
        b_num=bin(b_num)
        count = b_num.count('1')
        print(b_num)
        return count
    elif num < 0:
        b_num = bin(~num)
        count = 8 - b_num.count('1')
        return count
    else:
        return 0

3 排序

3.1 冒泡排序

# 冒泡排序将小数字在上面
nums=[3,5,1,8,9]
def w_sort(nums):
    # 冒泡的排序次数
    for i in range(len(nums)-1):
        # 每次冒泡时需要比较的次数
        for j in range(len(nums)-i-1):
            if  nums[j] > nums[j+1]:
                nums[j],nums[j+1] = nums[j+1] ,nums[j]
    return nums


print w_sort(nums)

4 多线程

多线程输出数组中的内容

import threading

w=[1,2,3,4,5,6]

def wang():
    global w_flag
    while w_flag != len(w):
        print w[w_flag]
        w_flag = w_flag +1


if __name__ == "__main__":
    global w_flag
    w_flag=0
    a=threading.Thread(target=wang)
    a.start()
    a1=threading.Thread(target=wang)
    a1.start()
    a2=threading.Thread(target=wang)
    a2.start()