Mark He

算法

枚举法

如果a+b+c=1000,且a^2+b^2=c^2（a,b,c为自然数)，如何求出所有a，b，c可能的组合？

import time

start_time = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a+b+c == 1000 and a**2 + b**2 == c**2:
                print("a, b, c: %d, %d, %d " % (a,b,c))

end_time = time.time()
print("times: %d" % (end_time - start_time))
print("finished")

import time

start_time = time.time()
for a in range(0, 1001):
    for b in range(0, 1001):
      c = 1000 - a - b
      if a**2 + b**2 == c**2:
        print("a, b, c: %d, %d, %d " % (a,b,c))

end_time = time.time()
print("times: %d" % (end_time - start_time))
print("finished")

Bubble Sort

def bubbleSort(arr):
    n = len(arr)

    for i in range(n):
 
        for j in range(0, n-i-1):
 
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

Insertion Sort

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
        arr[j+1] = key

Selection Sort

for i in range(len(A)): 
      
   
    min_idx = i 
    for j in range(i+1, len(A)): 
        if A[min_idx] > A[j]: 
            min_idx = j 
                
    A[i], A[min_idx] = A[min_idx], A[i] 

def binarySearch(arr, l, r, x):
    if r >= l:
        mid = int(l + (r - l) / 2)

        if arr[mid] == x:
        return mid

        elif arr[mid] > x:
            return binarySearch(arr, l, mid - 1, x)
        
        else:
            return binarySearch(arr, mid+1, x)
    else:
        return -1

← 操作MongoDB →