- 2020-08-19 02:41
*views 8*- python algorithm
- Python

What is recursion

Recursion is a way to solve problems , Decompose the problem into smaller subproblems , Until you get a small enough problem that can be easily solved . Recursion usually involves the function call itself

. Recursion allows us to write elegant solutions , Solve problems that can be difficult to program .

Three laws of recursion

* 1. Recursive algorithms must have a basic case .

* 2. Recursive algorithm must change its state and approach the basic situation .

* 3. Recursive algorithms must call themselves recursively .

Recurrence Examples

def listsum(numList): if len(numList) == 1: return numList.pop() # Basic information else:

# Change the situation and get closer to the basic situation return numList.pop() + listsum(numList) # Call itself

print(listsum([1,3,5,7,9]))

dynamic programming

The essence of dynamic programming is to divide and rule and solve redundancy , Therefore, dynamic programming is a kind of decomposition of problem instances into smaller ones , Similar subproblems , A subproblem with the solution of storage subproblem to avoid repeated calculation

, Algorithmic strategies for solving optimization problems .

Minimum change

Suppose you are a programmer for a vending machine manufacturer . Your company wants to simplify work by giving a minimum of coins per transaction . Suppose the customer puts in 1 Dollar bills and purchases 37 beautiful

Divided goods . What is the minimum number of coins you can change ? The answer is six coins ： Two 25 cent , One 10 cent and

One cent for three . How do we get the answer for six coins ? We start with the largest coin （25 cent ） open beginning , And as much as possible , Then we go to the next smaller coin , And use them as much as possible . This first method

It's called the greedy method , Because we're trying to solve the biggest problem as soon as possible . def recDC(coinValueList,change,knownResults):

minCoins = change if change in coinValueList: # First, judge whether the current amount can be changed exactly

knownResults[change] = 1 return 1 elif knownResults[change] > 0:

# Second, look at the calculated list , Can the results be found return knownResults[change] else: for i in [c for c in

coinValueList if c <= change]: # Choose the money whose face value is less than the change amount and use it for change numCoins = 1 +

recDC(coinValueList, change-i,knownResults) if numCoins < minCoins: minCoins =

numCoins knownResults[change] = minCoins # Update the list of stored calculation results return minCoins

knownResults = [0]*64 #0 Because I didn't use it print(recDC([1,5,10,25],63,knownResults))

print(knownResults) def dpMakeChange(coinValueList,change,minCoins,coinsUsed):

for cents in range(change+1): newCoin = 1 # The initial conditions are all used 1 Change in denomination coinCount = cents

# Initial situation amount even quantity for j in [c for c in coinValueList if c <= cents]:

# The coins with denomination less than the change amount are selected from the coins for change if minCoins[cents-j] + 1 < coinCount: # Use a coin first , Change, so +

1, Then check the number of coins required for the remaining amount . This is the previous calculation , Dynamic programming . coinCount = minCoins[cents-j]+1

# If the total quantity is less than the current planned quantity , Update dynamic planning results newCoin = j # The updated results are used for the next calculation minCoins[cents] = coinCount

# to update coinsUsed[cents] = newCoin # to update return minCoins[change] def

printCoins(coinsUsed,change): coin = change while coin > 0: thisCoin =

coinsUsed[coin] print(thisCoin) coin = coin - thisCoin def main(): amnt = 63

clist = [1,5,10,25] coinsUsed = [0]*(amnt+1) # Number of coins coinCount = [0]*(amnt+1)

# Denomination of coins print("Making change for",amnt,"requires")

print(dpMakeChange(clist,amnt,coinCount,coinsUsed),"coins") print("They are:")

printCoins(coinsUsed,amnt) print("The used list is as follows:")

print(coinsUsed) print(coinCount) main()

Technology

- Python104 blogs
- Java97 blogs
- Flow Chart79 blogs
- Vue51 blogs
- MySQL32 blogs
- programing language31 blogs
- javascript28 blogs
- Linux27 blogs
- more...

Daily Recommendation

©2020 ioDraw All rights reserved

JavaScript study （ Scope ）R Language group summation , Group average , Group count antd table sort 2021 Front end high frequency interview questions （ You have to watch it !!!）Android end Firefox Testing credit card and address auto fill function Sql What is the order of execution of ?vue+element-ui Realize the input limit of price 2021 Front end interview questions and written questions ——Vuejavascript Adding and deleting form information FastAPI to write get,post Interface , adopt json Interface for parameter transfer