<jupyter_start><jupyter_text>基础**算法**：编写一段计算机程序，以实现一种已有的方法来解决某个问题。比如欧几里得算法>自然语言描述>>计算两个非负整数$p$和$q$的最大公约数：若$q$是$0$，则最大公约数为$p$。否则，将$p$除以$q$得到余数$r$，$p$和$q$的最大公约数即为$q$和$r$的最大公约数。>>Python语言描述<jupyter_code>%%writefile ./codes/1.01/gcd.py
def gcd(p, q):
    pTrue = isinstance(p,int)
    qTrue = isinstance(q,int)
    if pTrue and qTrue:
        if q == 0:
            return p
        r = p%q
        return gcd(q,r)
    else:
        print("Error!")
        return 0
%run ./codes/1.01/gcd.py
# sample
gcd(11*256,22*16)<jupyter_output><empty_output><jupyter_text>基础编程模型- 程序是对算法精确、优雅和完全的描述- 可以运行程序来学习算法的性质- 可以在程序中使用<jupyter_code>%%writefile ./codes/1.01/newtonRootFinder.py
def sqrt_Newton(c):
    cTrue = isinstance(c,(int,float))
    if cTrue:
        if c<0:
            return None
        err = 10**(-15)
        t = c
        while abs(t-c/t)>err*t:
            t = (c/t+t)/2
        
        return t
%run ./codes/1.01/newtonRootFinder
# sample
print('newtonRootFinder answer: {}'.format(sqrt_Newton(257)))
print('Python builtin ** method answer: {}'.format(257**0.5))
%%writefile ./codes/1.01/binarySearch.py

import sys

def rank(key, a):
    lo = 0
    hi = len(a)-1
    while lo<=hi:
        mid = int((hi+lo)/2)
        if key < a[mid]:
            hi = mid - 1
        elif key > a[mid]:
            lo = mid + 1
        else:
            return mid
    return -1

def main():
    whitelist = []
    with open(sys.argv[1],'r') as f:
        for line in f.readlines():
            whitelist.append(int(line.strip()))
    
    whitelist_unsorted = whitelist.copy()
    whitelist.sort()
    for line in whitelist_unsorted:
        if rank(line, whitelist) == -1:
            sys.stdout.write(line)

if __name__ == '__main__':
    main()
!python ./codes/1.01/binarySearch.py ./algs4-data/largeW.txt > ./codes/1.01/largeT.txt<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16163793103448276, 'fraction_numerical': 0.03017241379310345, 'mean_word_length': 2.4971751412429377, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '478797', 'license': 'MIT', 'n_tokens_mistral': 852, 'n_tokens_neox': 854, 'n_words': 129, 'path': 'Computational/Algorithms/Chap_01_Basics.ipynb', 'repo_name': 'XavierOwen/Notes', 'size': '1856'}