# Python data structure and mathematical algorithm examples (continuously updating)

2022-05-15 05:55:37

# 1.1 Find the least common factor

## Basic Edition ：

``````x=1# Calculate the initial value , Because it's finding the least common factor
while True:
if x % 12 == 0 and x %15 == 0:# According to the meaning of the least common factor , This judgment condition can be obtained
break
x+=1
print('12 and 15 The least common factor of is {}'.format(x))
``````

The output effect is as follows ：

``````12 and 15 The least common factor of is 60！
``````

``````a=int(input(' Please enter the first number ( Press enter to enter the next command )：'))
b=int(input(' Please enter the second number ：( Press enter to enter the next command )：'))
x=1# Calculate the initial value , Because it's finding the least common factor
while True:
if x % a == 0 and x % b == 0:# According to the meaning of the least common factor , This judgment condition can be obtained
break
x+=1
print('{} and {} The least common factor of is {}！'.format(a,b,x))
``````

The output effect is as follows ：

`````` Please enter the first number ( Press enter to enter the next command )：14
Please enter the second number ：( Press enter to enter the next command )：28
14 and 28 The least common factor of is 28！
``````

# 1.2 The equivalent of square calculation is transformed into addition principle operation

## Basic Edition ：

``````x=4# Multiply the square value
counts=0
times=x
while times!=0:
counts+=x
times=times-1
print(str(x)+'*'+str(x)+'='+str(counts))
``````

``````x=int(input(' Please enter the square to be calculated ( Press enter to enter the next command )：'))# Multiply the square value
counts=0
times=x
while times!=0:
counts+=x
times=times-1
print(str(x)+'*'+str(x)+'='+str(counts))
``````

Output effect ：

`````` Please enter the square to be calculated ( Press enter to enter the next command )：6
6*6=36
``````

# 1.3 Find the integer cube root of a number by exhaustive method while loop

The algorithm technology used in this program is called Exhaustive method , It is a variant of guess and test algorithm . Let's enumerate all the possibilities , Until you get the right answer or try all the values . At first glance , This is an extremely stupid solution . But the amazing thing is , Exhaustive method is often the most practical way to solve problems . It's particularly easy to implement , And easy to understand . also , In many cases , It also runs fast enough .
Exhaustive search is a search technique , Valid only if the searched set contains answers .

## Code ：

``````x=int(input(' Please enter a number ( Press enter to enter the next command )：'))
counts=0
while counts**3 <abs(x):#x Is its absolute value , It can be used as positive integer and negative integer algorithms
counts+=1# The result is an integer cube root
if counts **3 != abs(x):# When there is no integer cube root
print('x There is no cube root ！')
else:
if x<0:#
counts=-counts
print('x The cube root of is {}!'.format(counts))
``````

Output effect ：

`````` Please enter a number ( Press enter to enter the next command )：-27
x The cube root of is -3

``````

Even if the number itself is large, the operation will be completed quickly , Almost no difference , Because modern computers are so fast , It executes an instruction only by 1 nanosecond ——10 Parts per billion 1 second ：

`````` Please enter a number ( Press enter to enter the next command )：1957816251
x The cube root of is 1251!
``````

# 1.4for in range The problem of circulation ：

range The parameters of the function have been evaluated by the interpreter before the first iteration of the loop , It will not be evaluated again in subsequent iterations , in other words for in range Use the corresponding value before the loop starts , It won't affect in the middle .

``````x = 4
for j in range(x):
for i in range(x):
print(i)
x = 2
``````

Output effect ：

``````0
1
2
3
0
1
0
1
0
1

Process ended , Exit code  0

``````

# 1.5 Find the cube root of a complete cubic number for loop ：

``````x=int(input(' Please enter a number ( Press enter to enter the next command )：'))
for i in range(0,abs(x)+1):#x Is its absolute value , It can be used as positive integer and negative integer algorithms
if i **3 >= abs(x):
break
if i **3 != abs(x):
print('x There is no cube root ！')# When there is no integer cube root
else:
if x < 0:
i=-i
print('x The cube root of is {}!'.format(i))
``````

Output effect ：

`````` Please enter a number ( Press enter to enter the next command )：-8
x The cube root of is -2!
``````

# 1.5 Use the exhaustive method to find the approximate square root

## Basic Edition ：

``````x = 25
epsilon = 0.01# Accuracy error
step = epsilon**2
ans = 0.0
while abs(ans**2 - x) >= epsilon and ans <= x:
ans += step
if abs(ans**2 - x) >= epsilon:
print(' Nonnegative number {} There is no approximate square root !'.format(x))
else:
print(' Nonnegative number {0} There is an approximate square root of {1}'.format(x,ans))
``````

``````x = int(input(' Please enter a non negative number ( Press enter to enter the next command )：'))
epsilon = eval(input(' Please enter a non negative precision number ( Press enter to enter the next command )：'))# Accuracy error , The suggestion is 0.01
step = epsilon**2
ans = 0.0
while abs(ans**2 - x) >= epsilon and ans <= x:
ans += step
if abs(ans**2 - x) >= epsilon:
print(' Nonnegative number {} There is no approximate square root !'.format(x))
else:
print(' Nonnegative number {0} There is an approximate square root of {1}'.format(x,ans))
``````

Output effect ：

`````` Please enter a non negative number ( Press enter to enter the next command )：49
Please enter a non negative precision number ( Press enter to enter the next command )：0.01
Nonnegative number 49 There is an approximate square root of 6.999299999997026

``````

# 1.6 Use binary search to find the approximate square root

``````x = 25
epsilon = 0.01# Accuracy error
low=0.0# Left end point of interval
high=max(0.0,x)# The right end of the interval
ans = (low+high)/2.0# Average.

while abs(ans**2 - x) >= epsilon :
print('low =', low, 'high =', high, 'ans =', ans)# Print binary process
if ans**2  < x:
low=ans
else:
high=ans
ans = (low + high) / 2
print(' Nonnegative number {0} There is an approximate square root of {1}'.format(x,ans))
``````

Output effect ：

``````low = 0.0 high = 25 ans = 12.5
low = 0.0 high = 12.5 ans = 6.25
low = 0.0 high = 6.25 ans = 3.125
low = 3.125 high = 6.25 ans = 4.6875
low = 4.6875 high = 6.25 ans = 5.46875
low = 4.6875 high = 5.46875 ans = 5.078125
low = 4.6875 high = 5.078125 ans = 4.8828125
low = 4.8828125 high = 5.078125 ans = 4.98046875
low = 4.98046875 high = 5.078125 ans = 5.029296875
low = 4.98046875 high = 5.029296875 ans = 5.0048828125
low = 4.98046875 high = 5.0048828125 ans = 4.99267578125
low = 4.99267578125 high = 5.0048828125 ans = 4.998779296875
low = 4.998779296875 high = 5.0048828125 ans = 5.0018310546875
Nonnegative number 25 There is an approximate square root of 5.00030517578125
``````

# 1.7 Using Newton - Lafferson method to find the approximate square root

Newton proved a Theorem ： If there is a value guess Is a polynomial p The approximate value of the root of , that guess -p(guess)/p’(guess) Is a better approximation , among p’ yes p The first derivative of .
Tips ： Compare Newton - The efficiency of lafferson method and binary search method , You'll find Newton - The lafferson method is more efficient .

``````epsilon = 0.01# precision
x = 24.0
guess = x/2.0# Initial value
while abs(guess**2 - x) >= epsilon:
guess = guess - (((guess**2) - x)/(2*guess))# Newton － Lafferson's law theorem uses the expression
print(' Nonnegative number {0} There is an approximate square root of {1}'.format(x,guess))
``````

Output effect ：

`````` Nonnegative number 24.0 There is an approximate square root of 4.8989887432139305
``````

# 1.8 Multiplication factorial

## (1) Iteration

``````def facts(n):# A recursive algorithm , hypothesis n It's a positive integer.
result=1
while n >1:
result=result*n
n-=1
return result
# The following is the calling function
n=int(input(' Please enter order multiplier ：( Press enter to enter the next command )：'))
counts=facts(n)
print(counts)

``````

## (2) Recursive version

``````def facts(n):# A recursive algorithm , hypothesis n It's a positive integer.
if n == 1:# Recursive base case
return n
else:
return n*facts(n-1)# Recursive chain
# The following is the calling function
n=int(input(' Please enter order multiplier ：( Press enter to enter the next command )：'))
counts=facts(n)
print(counts)
``````

Output effect ：

`````` Please enter order multiplier ：( Press enter to enter the next command )：4
24
``````

# 1.9 Recursive implementation of Fibonacci sequence

Fibonacci sequence is another commonly used mathematical function that is often defined recursively .1202 year , Italian mathematician Leonardo of Pisa （ Also known as Fibonacci ） Come up with a formula , Used to calculate the reproduction of Rabbits .
Questions as follows ：
Suppose a pair of newborn rabbits are put in the rabbit pen （ Worse, put it in the wild ）, A male rabbit , A female rabbit . Suppose that rabbits can mate when they are one month old （ it is a wonder that , Some varieties do ）, And one month of pregnancy （ it is a wonder that , Some varieties do ）. Last , Suppose these mythical rabbits never die , And the female rabbit can give birth to a pair of rabbits every month after the second month （ One male and one female ）. that 6 After a month , How many female rabbits will there be ？

It would be better to use a simple iterative implementation .

``````def facts(n):# A recursive algorithm , hypothesis n It's a positive integer.
if n == 0 or n == 1:# Adjust the base case condition according to the algorithm
return 1
else:
return facts(n-1) + facts(n-2)
# The following is the calling function
n=int(input(' Please enter the number of months ：( Press enter to enter the next command )：'))
counts=facts(n)
print(' after {0} In a few months, the number will become {1} individual '.format(n,counts))
``````

Output effect ：

`````` Please enter the number of months ：( Press enter to enter the next command )：5
after 5 In a few months, the number will become 8 individual
``````

# 2.0 Palindrome detection

## Basic Edition （ Recursion uses ）：

``````def doPalindrome(s):# Palindrome processing main function
def dochars(s):# Auxiliary function , Used to process filter strings
words=''
s=s.lower()
for i in s:
if i in 'abcdefghijklmnopqrstuvwxyz':
words = words + i
return  words
def checkPalindrome(s):# Auxiliary function , Used to judge whether it is palindrome
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and checkPalindrome(s[1:-1])
return checkPalindrome(dochars(s))
s=input(' Please enter the string to be detected ( Press enter to enter the next command )：')
results=doPalindrome(s)
if results == True:
print(' The string is palindrome ！')
else:
print(' The string is not a palindrome ！')

``````

Output effect ：

`````` Please enter the string to be detected ( Press enter to enter the next command )：ABBA
The string is palindrome ！

``````

``````def doPalindrome(s):# Palindrome processing main function
def dochars(s):# Auxiliary function , Used to process filter strings
words=''
s=s.lower()
for i in s:
if i in 'abcdefghijklmnopqrstuvwxyz':
words = words + i
return  words
def checkPalindrome(s):# Auxiliary function , Used to judge whether it is palindrome
return s[::1] == s[::-1]
return checkPalindrome(dochars(s))
s=input(' Please enter the string to be detected ( Press enter to enter the next command )：')
results=doPalindrome(s)
if results == True:
print(' The string is palindrome ！')
else:
print(' The string is not a palindrome ！')
``````

Output effect ：

`````` Please enter the string to be detected ( Press enter to enter the next command )：ABCBA
The string is palindrome ！
``````

# 2.1 Clone list

Be careful ： stay for In circulation ,Python Use a built-in counter to track the location of the program in the list , The internal counter is incremented at the end of each iteration 1. When the value of the counter is equal to the current length of the list , Cycle termination . If the list does not change during the cycle , So this mechanism is effective , But if the list changes , Will produce unexpected results .

## （1） No clone ：

``````L1 = [1,2,3,4]
L2 = [1,2,5,6]
A=L1
for i in A:
if i in L2:
L1.remove(i)
print(L1)
``````

Output effect ：

``````[2, 3, 4]
``````

## （2） Cloned ：

``````L1 = [1,2,3,4]
L2 = [1,2,5,6]
for i in L1[:]:# Slice the list
if i in L2:
L1.remove(i)
print(L1)
``````

Output effect ：

``````[3, 4]
``````

# 2.2 Using dictionary to realize simple English and French - French English translation program

``````Ewords= {
'eat':'mange', 'drink':'bois', 'John':'Jean',
'friends':'amis', 'and': 'et', 'of':'du','red':'rouge'}# English French data dictionary
Fwords= {
'mange':'eat', 'bois':'drink', 'Jean':'John',
'amis':'friends', 'et':'and', 'du':'of', 'rouge':'red'}# French English data dictionary
dicts = {
'English to French':Ewords, 'French to English':Fwords}# A dictionary of alternative translation , for translateword Parameter selection translation
def translateword(words, dictionary):# Function of translating a single word
if words in dictionary.keys():# Translated words
return dictionary[words]
return words# If it is a sentence symbol or a word beyond the ability of the program , Keep and return

def translate(sentences,dicts,languages):# The main function
Big='ABCDEFGHIJKLMNOPQRSTUVWXYZ'
Small= 'abcdefghijklmnopqrstuvwxyz'
strs=Big+Small# Both English and French are composed of letters , It can be used as a condition to judge whether it is a single word
words=''
dictionary=dicts[languages]
translations=''
for i in sentences:
if i in strs:
words=words+i# Returns a single word
else:
translations=translations+translateword(words,dictionary)+i# Return the translated content
words=''# Empty the contents of the object , Save characters for the next word
return translations
a=translate('I drink good red wine, and eat bread.', dicts,'English to French')
b=translate('Je bois du vin rouge.', dicts, 'French to English')
print(a)
print(b)
``````

Output effect ：

``````Je bois good rouge vin, et mange pain.
I drink of wine red.
``````

# 2.3 Input content type check

## （1） Basic Edition ：

``````while True:
vals=input(' Please enter an integer ：')
try:
vals=int(vals)
print(' The number you enter is :{}'.format(vals))
break# If the integer condition is satisfied, jump out of the loop
except ValueError:# Type error response
print(' You're not entering numbers ！ Please re-enter ！')
``````

Output effect ：

`````` Please enter an integer ：abc
You're not entering numbers ！ Please re-enter ！
The number you enter is :9
``````

## （2） Multiple repeated inputs are used ：

``````def inputInt():
while True:
vals = input(' Please enter an integer ：')
try:
return int(vals)
except ValueError:  #  Type error response
print(' You're not entering numbers ！ Please re-enter ！')
inputInt()
``````

## （3） Multiple repeated inputs and types , Prompt message: select ：

``````def intVal(valType, reMsg, errorMsg):# Corresponding data type , Input content prompt , Error prompt parameter
while True:
vals = input(reMsg)
try:
return valType(vals)
except ValueError:  #  Type error response
print(errorMsg)
intVal(int,' Please enter integer type content ：',' The type you entered is not an integer , Please re-enter ！')
``````

Output effect ：

`````` Please enter integer type content ：a
The type you entered is not an integer , Please re-enter ！
Please enter integer type content ：7
``````