# Python Algorithm1
###### tags: `python2021`
* 要求 (request)：
* 格式請依照ex1的標準 (檔名:ex9-1.py, ex9-2.py...，最後將所有檔案壓縮至學號.zip or 學號.7z上傳e3)
* 輸出檔案內容以TA截圖為標準

# Question 1: Write a function named Decimal_to_Hexadecimal for 十進位轉十六進位

0123456789ABCDEF (0~15)

Decimal_to_Hexadecimal(1033)
-> 0x00000409
Decimal_to_Hexadecimal(15)
-> 0x0000000F

def Decimal_to_Hexadecimal(num):
    dict1 = {}
    for i in range(10):
        dict1[i] = str(i)
    dict1[10] = 'A'
    dict1[11] = 'B'
    dict1[12] = 'C'
    dict1[13] = 'D'
    dict1[14] = 'E'
    dict1[15] = 'F'

    hexa = ""
    while num>=16:
        hexa = dict1[num%16] + hexa
        num = int(num/16)
    hexa = dict1[num] + hexa

    if len(hexa) < 8:
        for j in range(8-len(hexa)):
            hexa = "0" + hexa
    hexa = "0x" + hexa

    return hexa
    
    
list_num=[15,192,16,160,200,8888888];
for ele in list_num:
         print (str(ele) +"\tis\t"+ Decimal_to_Hexadecimal(ele))


# Question 2: Binary search algorithm

You have two methods when you want to find whether a certain element exit in a "sorted" list.

* Simple one:
Check every element until you match the element.
* Binary search:
Source: https://www.youtube.com/watch?v=j5uXyPJ0Pew

def normal_search(input_list,target): #Simple one
        find=0
        search_time=0
        for i in range(len(input_list)):
                search_time+=1

                if input_list[i] == target:
                        print ("in index: ",i)
                        print("search time: ",search_time)
                        find=1
                        return i
                        break

        if find==0:
                print ("not found!")
                return False



def binary_search(input_list,target): #Binary search
        #write something
        print("")


        
list1 = []
for i in range(101):
    list1.append(i)

print("use normal search:")
normal_search(list1,78) #Slow 
print("\nuse binary search:")
binary_search(list1,78) #Quick one you need to finish   

# Question 3: GCD and LCM (最大公因數 最小公倍數)
Given 2 integers, please write 2 functions to print out the GCD (greatest common divisor) and LCM (least common multiple) of them.
:::info
hint: 輾轉相除法 https://www.youtube.com/watch?v=8PPQc16kK-c
:::

def gcd(m,n):
        #write something
        print("")

def lcm(m,n):
        #write something
        print("")



print("GCD: ")
print(gcd(36,60))
print("LCM: ")
print(lcm(36,60))

# Question 4: Leap year
Write a program to input an A.D. year (e.g. 2019) and to determine whether the year is a leap year or not. If yes, then print "Yes", otherwise print "No".
:::info
Hint: Rules of Gregorian calendar leap year:
1. 如果年份能被 4 整除，請移至步驟 2。否則請移至步驟 5。
3. 如果年份能被 100 整除，請移至步驟 3。否則請移至步驟 4。
4. 如果年份能被 400 整除，請移至步驟 4。否則請移至步驟 5。
5. 該年份為閏年 (有 366 天)。
6. 該年份不是閏年 (有 365 天)。
:::

year = input("year: ")
    #write something