A few basic python grammar topics have been posted earlier, which are mainly used to help test the mastery of basic knowledge. If you have carefully read or done them, I believe you should have a certain understanding of your mastery of knowledge. Next, you can relearn the part that is not very clear.

python basic syntax is OK? Do some tests

python basic syntax is OK? Do some tests (2)

python solution is OK? Do some tests (3)

Among the above three articles, the first and second articles are relatively simple. The content of the third article is indeed difficult if you have not specially studied the content related to data structure and algorithm. This is the opposite. Let's put the reference answers of the most difficult article first, and put the first and second articles in the next issue.

If you haven't read the third article, I suggest you think about it yourself first and try it according to your existing knowledge. Efficient learning or learning effect learning must produce a lot of effective thinking per unit time - that is, you have tried hard and tried various methods, but these thoughts are very helpful. You know your puzzles and problems to be solved; When you see the reference answer, it is completely different from those who have not thought. When these contents are successfully solved, your brain should make subtle changes in the game and make breakthroughs in technology.

Now officially enter the topic.

In order to make you better understand the following contents, let's talk about some larger concepts first.

Cycle of violence (exhaustive): most computer problems can be solved by exhaustive without considering time.

For example, we can find out all the schemes through exhaustive methods, and then find the one with the least quantity.

The same is true for Sudoku. There are four possibilities for each position. You can list all methods, and then judge the coincidence.

Similarly, the maze problem is the same.

The cycle of violence mentioned above is simple, but there are also some problems to face:

- How to ensure that all the information can be listed without omission?
- For example, how many non repeated 3 digits can be combined from 3, 4, 5, 6 and 4 numbers?
- 24 point game, random four numbers, 1, 3, 6, 9, plus, minus, multiplication and division (+ - * /), parentheses, how many situations can be combined?

- How to judge whether the current situation is inconsistent? Different problems lead to different difficulties. It's easy to judge the change. Maze and Sudoku are a little more troublesome.
- There is a large amount of data. It has been a long time without results. How can we speed up some speed?
- ......

To solve some of the above problems, we need to have some strategies, such as how to ensure that the poor cite all the cases, and the permutation and combination in mathematics is very popular.

There are many ways to realize permutation and combination. For example, I have used multiple loops before, and of course I can also use recursion.

Full Permutation and combination implementation method

This method ensures that there is no leakage. The tree structure and many decision trees are similar.

Question 2 specific analysis.

Problem 3: to reduce the data scale is to use recursion to calculate Fibonacci series. After 40 items are calculated, it is not increased once. The time is double. The computer card is stuck for a long time. The reason is repeated calculation. You can save the calculated values through a list and reduce repeated calculation, which will significantly improve the speed.

For example, if you find the target number in a range and judge it one by one from beginning to end, it must be slow. Two point search can cut half at a time. How large the range is, it becomes smaller after several times.

1. Find the smallest tuple value in the following list, and the maximum value is the same.

[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13, 14), (15, 16, 17), (18, 19, 20), (21, 22, 23), (24, 25, 26)]

result:

Minimum:(0, 1, 2) Maximum:(24, 25, 26)

2. Find the most frequent element in the following list and print the number.

l = [1,3,4,5,6,1,3,4,5,1,9,1,1,1]

result:

1 Up to 6 times.

Reference for questions 1 and 2: python mosaic pixel map , which gives the solution.

3. Change problem

Given the types of change that can be found and the total amount of change to be found, find the scheme of the least amount of change.

For example, change 6 yuan,

Scheme 1: 4 1;

Scheme 2: 3,3;

Scheme 3: 3,1,1,1;

Scheme 4: 1,1,1,1,1,1;

Obviously, scheme 2 has the least number, only 2.

values = [1, 3, 4] # Coin face value total = 6 # I need change

result:

[3,3]

Refer to answer 1 - local optimal solution:

# Target number of change total = 6 # Types of banknotes values = [4, 3, 1] # result number = [0,0,0] # Cycle, starting from the maximum face value for i in range(3): # Rounding to calculate the maximum number of sheets that can be found for the current face value number[i] = total // values[i] # Take the balance and calculate the amount of money left after the change of the current face value total = total % values[i] for i in range(3): print(values[i],'The number of sheets of yuan is:',number[i],'Zhang')

Reference answer 2 - global optimal solution (dynamic programming):

I'm too lazy to write. I found a number on the Internet and changed it. I feel it's still very clear

def rec_mc(coin_value_list, change, know_results): min_coins = change if change in coin_value_list: know_results[change] = 1 return 1 elif know_results[change] > 0: return know_results[change] else: for i in [c for c in coin_value_list if c <= change]: num_coins = 1 + rec_mc(coin_value_list, change-i, know_results) if num_coins < min_coins: min_coins = num_coins know_results[change] = min_coins return min_coins print("===========Recursive implementation========================") print(rec_mc([1, 3, 4], 6, [0]*7)) def dp_make_change(coin_value_list, change, min_coins, coins_used): for cents in range(change+1): coin_count = cents new_coin = 1 for j in [c for c in coin_value_list if c <= cents]: if min_coins[cents-j] + 1 < coin_count: coin_count = min_coins[cents-j]+1 new_coin = j min_coins[cents] = coin_count coins_used[cents] = new_coin return min_coins[change] def print_coins(coins_used, change): coin = change while coin > 0: this_coin = coins_used[coin] print(this_coin) coin = coin - this_coin a_mnt = 6 c_list = [1, 3, 4] c_used = [0] * (a_mnt+1) c_count = [0] * (a_mnt+1) print("===========Dynamic programming implementation========================") print('Making change for ', a_mnt, 'requires') print(dp_make_change(c_list, a_mnt, c_count, c_used), 'coins') print("They are: ") print_coins(c_used, a_mnt) print("The used list is as follows: ") print(c_used)

4. Sudoku 4

Using the program to automatically complete 4 * 4 Sudoku

[[0, 1, 0, 0], [0, 0, 0, 2], [3, 0, 0, 0], [0, 0, 4, 0]]

result:

answer:

# Print board def print_board(board): for row in board: print(row) def check_board(num,row,col): # Check the row and judge each grid of the row for i in range(cols): # If the number to be filled already exists if board[row][i] == num: return False # Check the column and judge each grid of the column for i in range(rows): # If the number to be filled already exists if board[i][col] == num: return False return True def backtrack(board, index): if index >= 16: print("----programme----") print_board(board) print("------------") else: for num in range(1, len(board)+1): row = index//len(board) col = index%len(board[0]) if board[row][col]==0: # Judge whether this number can be filled in if not check_board(num, row, col): continue # Select a number board[row][col] = num backtrack(board,index+1) # Number of unselected board[row][col] = 0 else: index = index +1 rows = 4 cols = 4 board = [[0 for i in range(rows)] for j in range(cols)] board[0][1] = 1 board[1][3] = 2 board[2][0] = 3 board[3][2] = 4 index = 0 backtrack(board,index)

Unpackaged visual Sudoku version:

from PIL import Image, ImageDraw import matplotlib.pyplot as plt #Title Setting Chinese plt.rc("font", family='MicroSoft YaHei', weight='bold') plt.ion() # Print board def print_board(board): for row in board: print(row) def show_board(board, x, y, num): img = Image.new("RGB", (100, 100), "white") draw = ImageDraw.Draw(img) for row in range(4): for col in range(4): pos = (0+30*col, 0+row*30) draw.text(pos, str(board[row][col]), fill=(0, 0, 255)) draw.text((0+30*y, 0+x*30), str(num), fill=(255, 0, 255)) return img def check_board(num, row, col): # Check the row and judge each grid of the row for i in range(cols): # If the number to be filled already exists if board[row][i] == num: return False # Check the column and judge each grid of the column for i in range(rows): # If the number to be filled already exists if board[i][col] == num: return False return True def backtrack(board, index): if index >= 16: print("----programme----") print_board(board) print("------------") img = show_board(board, 3, 3, board[3][3]) plt.title("Compliant scheme") # title plt.imshow(img) plt.pause(5) # Pause for 1 second else: for num in range(1, 4+1): row = index//4 col = index % 4 if board[row][col] == 0: # Judge whether this number can be filled in if not check_board(num, row, col): continue # Select a number board[row][col] = num plt.cla() # Clear the screen first img = show_board(board, row, col, num) plt.title("Fill in a number") # title plt.imshow(img) plt.pause(1) # Pause for 1 second backtrack(board, index+1) # Number of unselected board[row][col] = 0 plt.cla() # Clear the screen first img = show_board(board, row, col, num) plt.title("Cancel a number") # title plt.imshow(img) plt.pause(1) # Pause for 1 second else: index = index + 1 rows = 4 cols = 4 board = [[0 for i in range(rows)] for j in range(cols)] board[0][1] = 1 board[1][3] = 2 board[2][0] = 3 board[3][2] = 4 # plt.pause(5) img = show_board(board, 3, 3, board[3][3]) plt.title("4X4 Sudoku game") # title plt.imshow(img) plt.pause(5) plt.title("start") plt.pause(2) index = 0 backtrack(board, index) plt.pause(2) # Pause for 1 second plt.ioff() plt.show()

5. Sudoku 9

Increase the difficulty and use the program to automatically complete 9 * 9 Sudoku.

[[2, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [0, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 0, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [0, 9, 0, 0, 0, 0, 4, 0, 0]]

Results: there are many answers, and only some are listed below.

answer:

# Print board def print_board(board): for row in board: print(row) def check_board(num,row,col): # Check whether there are duplicate numbers in the row and column for i in range(9): if board[row][i] == num or board[i][col] == num: return False # Judge whether there is repetition in xiaojiugong sub_row = row // 3 sub_col = col // 3 for i in range(3): for j in range(3): if board[sub_row * 3 + i][sub_col * 3 + j] == num: return False return True def backtrack(board, index): # print(index) if index >= 81: print("-----------programme-----------") print_board(board) print("--------------------------") else: for num in range(1, 9+1): row = index//9 col = index%9 if board[row][col]==0: # Judge whether this number can be filled in if not check_board(num, row, col): continue # Select a number board[row][col] = num # Continue to select the next number backtrack(board,index+1) # Number of unselected board[row][col] = 0 else: # backtrack(board,index+1) index = index + 1 board = [[2, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [0, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 0, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [0, 9, 0, 0, 0, 0, 4, 0, 0]] index = 0 backtrack(board,index)

Unpackaged visual Sudoku version:

from PIL import Image,ImageDraw import matplotlib.pyplot as plt #Title Setting Chinese plt.rc("font", family='MicroSoft YaHei', weight='bold') plt.ion() # Print board def print_board(board): for row in board: print(row) def show_board(board,x,y,num): img = Image.new("RGB", (250, 250), "white") draw = ImageDraw.Draw(img) for row in range(9): for col in range(9): pos = (0+30*col, 0+row*30) draw.text(pos, str(board[row][col]), fill=(0, 0, 255)) draw.text((0+30*y, 0+x*30), str(num), fill=(255, 0, 255)) return img def check_board(num, row, col): # Check whether there are duplicate numbers in the row and column for i in range(9): if board[row][i] == num or board[i][col] == num: return False # Judge whether there is repetition in xiaojiugong sub_row = row // 3 sub_col = col // 3 for i in range(3): for j in range(3): if board[sub_row * 3 + i][sub_col * 3 + j] == num: return False return True def backtrack(board, index): global count # print(index) if index >= 81: count = count + 1 img = show_board(board, 8, 8, board[8][8]) plt.title("The first{}Suspension of 1 eligible scheme s".format(count)) # title plt.imshow(img) plt.pause(1) # Pause for 1 second plt.title("Next plan") # title plt.pause(1) # Pause for 1 second print("-----------------------") print_board(board) else: for num in range(1, 9+1): row = index//9 col = index % 9 if board[row][col] == 0: # Judge whether this number can be filled in if not check_board(num, row, col): continue # Select a number board[row][col] = num plt.cla() # Clear the screen first img = show_board(board,row,col,num) plt.title("Fill in a number") # title plt.imshow(img) plt.pause(0.1) # Pause for 1 second # Continue to select the next number backtrack(board, index+1) # Number of unselected board[row][col] = 0 plt.cla() # Clear the screen first img = show_board(board,row,col,num) plt.title("Cancel a number") # title plt.imshow(img) plt.pause(0.1) # Pause for 1 second else: # backtrack(board,index+1) index = index + 1 plt.cla() # Clear the screen first board = [[2, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [0, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 0, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [0, 9, 0, 0, 0, 0, 4, 0, 0]] img = show_board(board, 8, 8, board[8][8]) plt.title("9X9 Sudoku game") # title plt.imshow(img) plt.pause(2) plt.title("start") plt.pause(2) index = 0 global count count = 0 backtrack(board, index) # plt.ioff() plt.show()

6. Maze problem

A maze with a size of 5 * 6 is given, which is composed of channel (0) and wall (1), in which the upper left corner of the channel represents the starting point and the lower right corner of the channel represents the end point. Find the maze path.

maze = [[0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [1, 1, 1, 0, 0], [0, 1, 0, 0, 1], [0, 1, 0, 0, 0]]

result:

[[0, 0], [1, 0], [1, 1], [1, 2], [0, 2], [0, 3], [0, 4], [1, 4], [2, 4], [3, 4], [3, 3], [4, 3], [5, 3], [5, 4]]

Answer 1:

# Shortest distance shortest path maze =[[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 0]] n,m = len(maze),len(maze[0]) start = [0, 0] end = [4, 4] # List of data to be found search_queue = [] # List simulation queue # Add start point search_queue.append(start) visted = [] # Record visited points visted.append(start) def find_next_point(point): global search_queue,visted,n,m # px and py arrays are used to realize the moving order of bottom left and top right px = [-1, 0, 1, 0] py = [0, -1, 0, 1] # Move up, down, left and right for i in range(4): next_x = point[0] + px[i] next_y = point[1] + py[i] # How to add the next point to the queue to be searched and the access queue to meet the requirements if (0 <= next_x < n and 0 <= next_y < m and maze[next_x][next_y] == 0 and [next_x,next_y] not in visted): search_queue.append([next_x,next_y]) visted.append([next_x,next_y]) return True return False def dfs(): global search_queue,visted print(search_queue) while search_queue[-1] != end: # Get the last point of the queue and judge whether to reach the big end point point = search_queue[-1] # If there is a next point, continue if find_next_point(point): continue # Otherwise, delete the point you just added else: print("delete",search_queue.pop()) print(search_queue) dfs()

Answer 2:

The above is difficult to understand. You can see the following. I found a simple change on the Internet. It is easier to understand, but there are many codes

def up(point): # You have reached the top of the array. You can't go up if point[0] == 0: return False else: new_point = [point[0] - 1, point[1]] # The road we have traveled is no longer gone if new_point in visted: return False # Don't go against the wall elif maze[new_point[0]][new_point[1]] == 1: return False else: search_queue.append(new_point) visted.append(new_point) return True def down(point): # When you meet the bottom of the maze, you can't go further if point[0] == len(maze) - 1: # The number of two-dimensional array rows with 6 rows and 5 columns is calculated from 0, so it is 6-1 = 5 rows return False else: new_point = [point[0] + 1, point[1]] # The road we have traveled is no longer gone if new_point in visted: return False # Don't go against the wall elif maze[new_point[0]][new_point[1]] == 1: return False else: visted.append(new_point) search_queue.append(new_point) return True def left(point): # You can't continue to go left when you meet the leftmost part of the maze if point[1] == 0: return False else: new_point = [point[0], point[1] - 1] # The road we have traveled is no longer gone if new_point in visted: return False # Don't go against the wall elif maze[new_point[0]][new_point[1]] == 1: return False else: visted.append(new_point) search_queue.append(new_point) return True def right(point): # You cannot continue to move to the right when you encounter the rightmost side of the maze if point[1] == len(maze[0]) - 1: # The number of two-dimensional array columns with 6 rows and 5 columns is calculated from 0, so it is 5-1 = 4 rows return False else: new_point = [point[0], point[1] + 1] # The road we have traveled is no longer gone if new_point in visted: return False # Don't go against the wall elif maze[new_point[0]][new_point[1]] == 1: return False else: visted.append(new_point) search_queue.append(new_point) return True maze = [[0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [1, 1, 1, 0, 0], [0, 1, 0, 0, 1], [0, 1, 0, 0, 0]] start = [0, 0] end = [5, 4] search_queue = [] visted = [] search_queue.append(start) visted.append(start) print("start: %s --> end: %s\n" % (start, end)) while search_queue[-1] != end: now = search_queue[-1] if up(now) or down(now) or left(now) or right(now): continue print("delete",search_queue.pop()) print("final path: ", search_queue)

7. Maze problem 2 - shortest path.

Given a maze with a size of 5 * 5, it is composed of channel (0) and wall (1), in which the upper left corner of the channel represents the starting point and the lower right corner of the channel represents the end point, so as to find the shortest path of the maze.

maze = [[0, 1, 0, 0, 0,], [0, 1, 0, 1, 0,], [0, 0, 0, 0, 0,], [0, 1, 1, 1, 0,], [0, 0, 0, 1, 0,]]

There are two schemes, but scheme 2 is the shortest path.

answer:

# Shortest distance shortest path maze =[[0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 0]] n,m = len(maze),len(maze[0]) start = [0, 0] end = [4, 4] # Define the Breadth First Search algorithm def bfs(maze,n,m): # List of data to be found search_queue = [] # List simulation queue # Add start point search_queue.append(start) visted = [] # Record visited points visted.append(start) # Record parent node parent = {f"{start[0]}{start[1]}":None} px = [-1, 0, 1, 0] # px and py arrays are used to realize the moving order of bottom left and top right py = [0, -1, 0, 1] # Exit the loop until the lookup queue is empty while search_queue: # Take out the first point in the queue (search started recently) point = search_queue.pop(0) # Get all nearest points points = [] for i in range(4): next_x = point[0] + px[i] next_y = point[1] + py[i] if (0 <= next_x < n and 0 <= next_y < m and maze[next_x][next_y] == 0): points.append([next_x,next_y]) for i in points: # If i have not been visited if i not in visted: # Add I (nearest point) to the search queue search_queue.append(i) # Mark i as accessed visted.append(i) # Record the parent node of each point parent[f"{i[0]}{i[1]}"] = point return visted,parent visted,parent = bfs(maze,n,m) route_list = [] if end in visted: print(f"Existence from{start}reach{ end}Route") v = end # Currently accessed point # Until the start position None exits while v !=None: route_list.append(v) v=parent[f"{v[0]}{v[1]}"] else: print(f"Does not exist from{start}reach{ end}Route") route_list.reverse() print(route_list)

How to see the above methods is difficult. You can look at the concepts of DFS and BFS, backtracking, recursion and so on. You can also take a look at what I wrote before. I have time to update it later. What I wrote before is not very good. I can make do with it.

Full Permutation and combination implementation method

Thoughts on learning algorithms (end of full text)