08-初中作业辅导「美」

Homework 6: Searching

1. State for each question, whether the statements are True or False, and the reason why.

a. Linear searching does not need to usean ordered list, but abinary search does.

True

线性搜索不需要使用有序的列表，因为它从列表的第一个元素开始，逐一检查每个元素，直到找到所需的元素或检查完整个列表。而二分搜索确实需要一个有序的列表，因为它的搜索策略是基于每次将搜索范围缩小一半的原理。如果列表不是有序的，那么二分搜索就无法正常工作。

b. The maximum number of values examined in a binary search of 40.000 items is the same asthat for 60,000 items.

二分搜索的核心思想是每次查找都将当前的搜索范围缩小一半。所以要查找的最大次数是以2为基数的对数值。

对于40,000个项目，最大的查找次数是 log2(40000)。而对于60,000个项目，最大的查找次数是 log2(60000)。这两个值是不同的，所以对40,000和60,000个项目的二分搜索所需的最大查找次数并不相同。

c. Of the two searchc methods, linear and binary, a binary search is the fastest way to search a list of values.

d. Another name for a inear search is a sequential search

2. Suppose you have a list of names:

Andrew, Bob, Cathy, Debra, Kasim, Maisie, Noah, Paul, Sue, Tim, Verity

In a binary search of the list to find the name Kasim, which names would be examined? [4]

def binary_search(names, target):
    left = 0
    right = len(names) - 1
    examined_names = []

    while left <= right:
        mid = (left + right) // 2
        mid_name = names[mid]
        examined_names.append(mid_name)

        if mid_name == target:
            return examined_names
        elif mid_name < target:
            left = mid + 1
        else:
            right = mid - 1

    return None

names = ["Andrew", "Bob", "Cathy", "Debra", "Kasim", "Maisie", "Noah", "Paul", "Sue", "Tim", "Verity"]
target_name = "Kasim"
examined = binary_search(names, target_name)
print(examined)

6、Homework

3 Check the Access Records (40 Points)

3.1 Description

With the city’s streets now considerably less congested, there’s a sense of relief in the air. However, the calm is about to be interrupted as the mayor of Liberty City prepares to lead a delegation on a visit to the Los Santos area. Their accommodations? The prestigious Garden Bank Hotel.

To ensure their safety and maintain the security of the event, the LSPD has reached out for as- sistance in designing a robust license plate registration system. This system will serve as the gate- keeper, allowing only authorized vehicles to enter the premises while keeping uninvolved members of the community at bay.

It’s essential to understand that some criminal syndicates have been known to engage in the illegal practice of duplicating license plates for nefarious purposes. As a result, each license plate must be registered only once, granting a vehicle one entry into the hotel grounds. The goal is clear: to guarantee a safe and secure environment for the mayor and the visiting delegation during their stay.

3.2 Input Format

The first line, an integer n, represents the license plate of the vehicle registered in the system’s records. The next n lines, each line is a string indicating one license plate.
Line n + 2, an integer m, represents the number of license plates captured by surveillance.
The next m lines, one string per line, represent the license plate captured by the monitor.

3.3 Output Format

For each recorded license plate, output one line, which means you always have to output m lines.
Output OK if the license plate is correct (in the registered database) and is the first occurrence, WRONG if the license plate is incorrect, REPEAT if the license plate is correct but not the first occurrence, and INVALID if the license plate does not meet the federal requirement.

3.4 Sample Input 1

1 
AA−AAAAA−1 
1
AA−AAAAA−1

3.5 Sample Output 1

OK

3.6 Sample Input 2

3 
AA−AAAAA−A 
NY−QU0TE−0
NY−LRU0M−0 
4
NY−LRU0M−0 
NY−LRU0M−0 
AA−AAAAA−C
A&*

3.7 Sample Output 2

OK
REPEAT 
WRONG
INVALID

3.8 Data Constraints

This problem might need you to consider 3 parts: whether a plate is valid, whether it has registered, and, whether it has repeated in the monitor. However, some test cases don’t require you to finish all these functions. We promise that:

For the 1st test case, i.e. 1.inopen in new window,

• No invalid/repeated plates appeared;
• If you don’t assert whether a plate is valid or it has appeared more than once,you can still pass this case.

For the 2nd and 3rd test cases, i.e. 2.inopen in new window and 3.inopen in new window,

• No repeated plates appeared;
• If you don’t assert whether a plate has appeared more than once, you can still pass these two cases.

For all test cases, 1 ≤ n, m ≤ 10000.

3.9 Hint

One should note that all registered license plates are valid.

4 The Real GTA: Grand Theft Auto (Bonus, 20 Points)

4.1 Background

I can’t take anymore! You know what I am saying? This is bllsht! Those cops should write those dumb codes themselves.

Franklin said to himself. He attempted to break out of the LSPD holding cell the old-fashioned way - knocking out the guards and grabbing the keys. Just walking to the door, he was knocked down and sent back to the dim cell by the backup police officers who heard the sirens.

He suddenly remembers Leslie, the cripple he used to work with. He finds a way to get in touch with Leslie. Leslie says he can get Franklin out, but he needs Franklin to do what he says.

One day, Franklin finds a note in his lunch bread. The note tells him to rob the escort vehicle and escape on his way back to his cell from the office. Sure enough, in the afternoon Franklin got into the escort vehicle. On the way, the guard said he wanted a burger from McDonald’s, so he put a hook on Franklin’s head and cuffed his hands to the steering wheel.

To Franklin’s surprise, Leslie’s voice came over the radio. He told Franklin to drive the car right now.

I got mad respect for you man. But I can’t see anything, bro. I can’t even take off this dumb hood. Franklin said.

If you are still eager for freedom, do as I say! Stupid! Leslie roared.

4.2 Description

Franklin has to drive to the safe house within the time limit. Since Franklin’s head is covered by a hood and his hands are tied up, all he can do is step on the gas, hit the brakes and change the direction. Not only that, he doesn’t know the location of the safe house so he has to follow Leslie’s directions. Luckily, the main roads in Los Santos were basically straight, so with Franklin’s excellent driving skills he could estimate the distance of a block.

Leslie knows the size of the map, which is rectangular in shape, Leslie also creates a simple coordinate system. The point at the bottom left corner is the origin point (0, 0). He also knows Franklin’s initial location and the location of the safe house. Hearing the siren, Leslie tells Franklin there must be some obstacle on the road, Franklin should avoid hitting the obstacle if he does not want to be arrested again.

The following definitions are given for clarity.

4.2.1 Direction and Speed:

Franklin has an excellent sense of direction and can sense whether he is facing east or south or west or north. Note that speed is a non-negative integer. Note that before receiving the first instruction, Franklin’s speed is always 0.

• Facing north: (in the absence of obstacles) the next time step Franklin’s vertical coordinate increases by the current speed.
• Facing south: (in the absence of obstacles) the next time step Franklin’s vertical coordinate decreases by the current speed.
• Facing east: (in the absence of obstacles) the next time step Franklin’s horizontal coordinate increases by the current speed.
• Facing west: (in the absence of obstacles) the next time step Franklin’s horizontal coordinate decreases by the current speed.

4.2.2 Time and Instructions:

for a time limit t, the process has t time steps. Franklin always receives t instructions. Some instructions may lead to Franklin’s attributes (direction and speed) change. Instructions contain:

• North: May change the direction and the speed.

• South: May change the direction and the speed.

• East: May change the direction and the speed.

• West: May change the direction and the speed.

• Park: Keep the direction and reset the speed.

• Keep: Keep the direction and the speed.

4.2.3 Rules for the Game:

1. Rules for Franklin’s Actions:
   • Speed Adjustment Rules
     • When the command direction matches Franklin’s current direction, his speed increases by 1.
     • When the command direction and Franklin’s current direction are at 180-degree angles from each other, his speed decreases by 1 and his direction stays still.
   • Direction Adjustment Rule
     • When the command direction and Franklin’s current direction are at 90-degree angles from each other, his speed remains the same, but his direction changes to the command direction.
   • Zero Speed Rule
     • If Franklin’s speed reaches zero, his direction always changes to the command direction, and his speed is set to 1.
2. Attribute Precedence
   • Franklin’s attribute changes take precedence over coordinate changes. He first receives instruc- tions that may change his attributes (speed or direction), and then he moves according to the present direction and speed.
3. Obstacles and Border Rules:
   • When Franklin encounters police-imposed obstacles on the road, he cannot drive through them. These obstacles keep Franklin one block away from the obstacle and change his speed to 0.
   • Franklin cannot pass the borders of the map. If he reaches or attempts to pass the borders, his speed will change to 0.
4. End of Driving
   • Franklin’sdriveendseitherafteraspecifiednumberoftimesteps(ttimesteps)orwhenhiscoordi- nate is the same as the coordinate of the safe house. In the latter case, the safe house’s coordinates may either match Franklin’s new coordinates after following the instructions or be situated on the path between Franklin’s old and new coordinates.
   • If Franklin’s drive ends, he will disregard all subsequent instructions.

4.3 Input Format

The input contains 5 lines.

The first line contains three positive integers n, m and t representing the size of the mapping matrix and time limit, where n is the length in the horizontal direction and m is the length in the vertical direction. The integers are separated by one space. The origin point is (0, 0).

The second line is one coordinate of the form (x, y), which is the coordinate of the safe house.

The third line is one coordinate of the form (x, y), which is Franklin’s initial coordinate.

The fourth line is k coordinates of the form (x, y). These coordinates are the coordinates of the obstacle. If there is no obstacle, the input is (−1, −1).

The fifth line is a series of Franklin’s actions including t capital letters: N, E, S, W, P, and K for north, east, south, west, park and keep, respectively.

4.4 Output Format

The output contains only one integer, indicating the Manhattan Distance between Franklin’s final coordi- nates and the safe house.

4.5 Sample Input 1

3 1 8 
(0,2) 
(0,0)
(−1,−1) 
EEEEKKKK

4.6 Sample Output 1

0

4.7 Sample Input 2

3 3 4
(2,2) 
(0,0) 
(1,1)
ENEN

4.8 Sample Output 2

1

4.9 Sample Input 3

3 3 10 
(2,2)
(0,0) 
(1,1)
EKNKPKEEPP

4.10 Sample Output 3

0

4.11 Data Constraints

To solve this problem you have to consider a lot of constraints and read the problem thoroughly. However, it is promised that some test cases are easier to handle. The test cases are given as follows:

For the 1st and 2nd test cases, i.e. 1.inopen in new window and 2.inopen in new window:

• The game map is a single row, i.e. the car can’t move vertically.
• You may simply ignore all the instructions asking you to move N/S.
• Note that the car can still face North or South. This may affect it’s speed.

For the 1st-4th test cases, i.e. 1.inopen in new window, 2.inopen in new window, 3.inopen in new window and 4.inopen in new window,

• No obstacles are given;
• You can assume that the car won’t hit obstacles;
• But, be careful to handle it if the car hits the wall!

For another 20% data, i.e. 5.inopen in new window and 6.inopen in new window,

• They are corner cases;
• If you get the Wrong Answer on these two test cases, check your code carefully if it works correctly in special cases.

For all test cases, 1 ≤ n, m ≤ 64; 1 ≤ t ≤ 32; Let o be 12 (m + n), then 1 ≤ k ≤ o log o.

4.12 Hint

• MAKE SURE YOU UNDERSTAND EVERY SENTENCE ABOVE BEFORE YOU WRITE ANY CODE!
• PLEASE NOTE THAT THE ORIGIN POINT IS (0, 0).
• Note that there are some police-imposed obstacles on the road. When Franklin encounters these obstacles he cannot drive through them.
• Note that Franklin can not pass the borders of the map.
• You do NOT have to figure out why k is constrained as this.

公众号：AI悦创【二维码】