利用python编程语言实现sstf算法 输入格式: Each input file only contains one test case. The first line contains two integer n, m (1 ≤ n ≤ 106, 1 ≤ m ≤ 109), indicating the length of the track sequence and the number of the current magnetic head. The second line contains n integers a1​,a2​,...,an​ (1 ≤ ai​ ≤ 109), indicating the track sequence. 输出格式： For each test case output an integer indicating the sum of the magnetic head's moving distance. 输入样例： 9 100 55 58 39 18 90 160 150 38 184 输出样例： 248

以下是一个实现上述功能的Python程序：

n, m = map(int, input().split())
a = list(map(int, input().split()))

total_dist = 0
while len(a) > 0:
    min_dist = float('inf')
    min_idx = -1
    for i in range(len(a)):
        dist = abs(a[i] - m)
        if dist < min_dist:
            min_dist = dist
            min_idx = i
    total_dist += min_dist
    m = a[min_idx]
    a.pop(min_idx)

print(total_dist)

首先，我们使用`map()`函数将输入的字符串转换为整数类型，并将它们存储在变量`n`和`m`中。接下来，我们使用`list()`和`map()`函数将输入的磁道序列转换为整数列表`a`。然后，我们使用一个循环来迭代所有磁道，直到序列为空为止。在每次循环中，我们找到距离当前位置最近的磁道，计算移动距离并更新当前位置。最后，我们输出移动距离的总和。

需要注意的是，在实际应用中，可能需要使用更高效的算法来解决这个问题。该实现的时间复杂度为$O(n^2)$，对于大型数据集可能会导致超时。

相关问题

利用python编程语言实现sstf算法

下面是一个利用Python实现SSTF算法的示例代码：

def sstf(current, requests):
    # 计算距离最近的请求
    shortest_distance = abs(current - requests[0])
    shortest_index = 0
    for i in range(1, len(requests)):
        distance = abs(current - requests[i])
        if distance < shortest_distance:
            shortest_distance = distance
            shortest_index = i

    # 返回结果
    return (requests[shortest_index], shortest_index)

# 测试
if __name__ == '__main__':
    current = 50
    requests = [82, 170, 43, 140, 24, 16, 190]
    total_distance = 0
    while requests:
        next_request, index = sstf(current, requests)
        total_distance += abs(current - next_request)
        current = next_request
        del requests[index]
    print('SSTF Algorithm Total Movement:', total_distance)

在这个示例代码中，我们定义了一个`sstf`函数来计算当前位置和所有请求之间的距离，并选择距离最近的请求作为下一个访问的请求。然后我们使用一个`while`循环来迭代所有请求，直到没有请求剩余为止。在每次循环中，我们使用`sstf`函数计算下一个请求，更新总距离，并从请求列表中删除已经处理过的请求。最后，我们输出总距离，即SSTF算法的结果。

需要注意的是，这只是一个简单的SSTF算法的实现，实际应用中可能需要考虑更多的因素，比如请求的优先级、IO设备的性能等等。

Write a C program that implements the following disk-scheduling algorithms: a. FCFS b. SSTF c. SCAN d. C-SCAN e. LOOK f. C-LOOK Your program will service a disk with 5,000 cylinders numbered 0 to 4,999. The program will generate a random series of 1,000 cylinder requests and service them according to each of the algorithms listed above. The program will be passed the initial position of the disk head (as a parameter on the command line) and report the total amount of head movement required by each algorithm.

Sure, here's a sample C program that implements the disk-scheduling algorithms you mentioned:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define CYLINDERS 5000
#define REQUESTS 1000

// Struct to represent a disk request
typedef struct {
    int cylinder;
    bool visited;
} request;

// Function to generate random cylinder requests
void generateRequests(request* queue) {
    for (int i = 0; i < REQUESTS; i++) {
        queue[i].cylinder = rand() % CYLINDERS;
        queue[i].visited = false;
    }
}

// FCFS algorithm
int fcfs(request* queue, int head) {
    int totalMovement = 0;
    for (int i = 0; i < REQUESTS; i++) {
        totalMovement += abs(head - queue[i].cylinder);
        head = queue[i].cylinder;
    }
    return totalMovement;
}

// SSTF algorithm
int sstf(request* queue, int head) {
    int totalMovement = 0;
    for (int i = 0; i < REQUESTS; i++) {
        int minDistance = CYLINDERS;
        int minIndex = -1;
        for (int j = 0; j < REQUESTS; j++) {
            if (!queue[j].visited) {
                int distance = abs(head - queue[j].cylinder);
                if (distance < minDistance) {
                    minDistance = distance;
                    minIndex = j;
                }
            }
        }
        if (minIndex != -1) {
            totalMovement += minDistance;
            head = queue[minIndex].cylinder;
            queue[minIndex].visited = true;
        }
    }
    return totalMovement;
}

// SCAN algorithm
int scan(request* queue, int head) {
    int totalMovement = 0;
    int direction = 1; // 1 for up, -1 for down
    int currentIndex = -1;
    for (int i = 0; i < REQUESTS; i++) {
        if (queue[i].cylinder == head) {
            currentIndex = i;
            break;
        }
    }
    if (currentIndex == -1) {
        // Insert head into queue
        for (int i = 0; i < REQUESTS; i++) {
            if (head < queue[i].cylinder) {
                for (int j = REQUESTS - 1; j > i; j--) {
                    queue[j] = queue[j-1];
                }
                queue[i].cylinder = head;
                queue[i].visited = true;
                currentIndex = i;
                break;
            }
        }
    }
    for (int i = currentIndex; i >= 0 && i < REQUESTS; i += direction) {
        if (!queue[i].visited) {
            totalMovement += abs(head - queue[i].cylinder);
            head = queue[i].cylinder;
            queue[i].visited = true;
        }
        if (i == 0 || i == REQUESTS - 1) {
            direction = -direction;
        }
    }
    return totalMovement;
}

// C-SCAN algorithm
int cscan(request* queue, int head) {
    int totalMovement = 0;
    int currentIndex = -1;
    for (int i = 0; i < REQUESTS; i++) {
        if (queue[i].cylinder == head) {
            currentIndex = i;
            break;
        }
    }
    if (currentIndex == -1) {
        // Insert head into queue
        for (int i = 0; i < REQUESTS; i++) {
            if (head < queue[i].cylinder) {
                for (int j = REQUESTS - 1; j > i; j--) {
                    queue[j] = queue[j-1];
                }
                queue[i].cylinder = head;
                queue[i].visited = true;
                currentIndex = i;
                break;
            }
        }
    }
    // Service requests in one direction
    for (int i = currentIndex; i >= 0; i--) {
        if (!queue[i].visited) {
            totalMovement += abs(head - queue[i].cylinder);
            head = queue[i].cylinder;
            queue[i].visited = true;
        }
    }
    totalMovement += head; // Head movement to go to the end
    head = 0;
    // Service requests in the other direction
    for (int i = REQUESTS - 1; i > currentIndex; i--) {
        if (!queue[i].visited) {
            totalMovement += abs(head - queue[i].cylinder);
            head = queue[i].cylinder;
            queue[i].visited = true;
        }
    }
    return totalMovement;
}

// LOOK algorithm
int look(request* queue, int head) {
    int totalMovement = 0;
    int direction = 1; // 1 for up, -1 for down
    int currentIndex = -1;
    for (int i = 0; i < REQUESTS; i++) {
        if (queue[i].cylinder == head) {
            currentIndex = i;
            break;
        }
    }
    if (currentIndex == -1) {
        // Insert head into queue
        for (int i = 0; i < REQUESTS; i++) {
            if (head < queue[i].cylinder) {
                for (int j = REQUESTS - 1; j > i; j--) {
                    queue[j] = queue[j-1];
                }
                queue[i].cylinder = head;
                queue[i].visited = true;
                currentIndex = i;
                break;
            }
        }
    }
    for (int i = currentIndex; i >= 0 && i < REQUESTS; i += direction) {
        if (!queue[i].visited) {
            totalMovement += abs(head - queue[i].cylinder);
            head = queue[i].cylinder;
            queue[i].visited = true;
        }
        if (i == 0 || i == REQUESTS - 1) {
            direction = -direction;
        }
    }
    return totalMovement;
}

// C-LOOK algorithm
int clook(request* queue, int head) {
    int totalMovement = 0;
    int currentIndex = -1;
    for (int i = 0; i < REQUESTS; i++) {
        if (queue[i].cylinder == head) {
            currentIndex = i;
            break;
        }
    }
    if (currentIndex == -1) {
        // Insert head into queue
        for (int i = 0; i < REQUESTS; i++) {
            if (head < queue[i].cylinder) {
                for (int j = REQUESTS - 1; j > i; j--) {
                    queue[j] = queue[j-1];
                }
                queue[i].cylinder = head;
                queue[i].visited = true;
                currentIndex = i;
                break;
            }
        }
    }
    // Service requests in one direction
    for (int i = currentIndex; i >= 0; i--) {
        if (!queue[i].visited) {
            totalMovement += abs(head - queue[i].cylinder);
            head = queue[i].cylinder;
            queue[i].visited = true;
        }
    }
    // Service requests in the other direction
    for (int i = REQUESTS - 1; i > currentIndex; i--) {
        if (!queue[i].visited) {
            totalMovement += abs(head - queue[i].cylinder);
            head = queue[i].cylinder;
            queue[i].visited = true;
        }
    }
    return totalMovement;
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        printf("Usage: %s <initial position>\n", argv[0]);
        return 1;
    }
    int initial = atoi(argv[1]);
    if (initial < 0 || initial >= CYLINDERS) {
        printf("Initial position must be between 0 and %d\n", CYLINDERS - 1);
        return 1;
    }

    request queue[REQUESTS];
    generateRequests(queue);

    printf("FCFS: %d\n", fcfs(queue, initial));
    for (int i = 0; i < REQUESTS; i++) {
        queue[i].visited = false;
    }
    printf("SSTF: %d\n", sstf(queue, initial));
    for (int i = 0; i < REQUESTS; i++) {
        queue[i].visited = false;
    }
    printf("SCAN: %d\n", scan(queue, initial));
    for (int i = 0; i < REQUESTS; i++) {
        queue[i].visited = false;
    }
    printf("C-SCAN: %d\n", cscan(queue, initial));
    for (int i = 0; i < REQUESTS; i++) {
        queue[i].visited = false;
    }
    printf("LOOK: %d\n", look(queue, initial));
    for (int i = 0; i < REQUESTS; i++) {
        queue[i].visited = false;
    }
    printf("C-LOOK: %d\n", clook(queue, initial));

    return 0;
}

To compile and run the program, you can use the following commands:

$ gcc disk-scheduling.c -o disk-scheduling
$ ./disk-scheduling <initial position>

Replace `<initial position>` with the desired starting position of the disk head. The program will generate a random series of 1,000 cylinder requests and service them according to each of the algorithms listed above, reporting the total amount of head movement required by each algorithm.