Problem : Find stone pair(s) There are N number of stones, labeled as [0, N-1]. We know the weight of each of those stones. We want to find ONE stone pair, i.e. 2 stones, whose weight difference is D. (20分) Question A Formally describe the problem to clearly define the problem without ambiguity. Something like: write a function F that … the inputs of the function are … the output of the function are …. This question might be harder than you thought. Please think carefully. Question B Write the function you described in your answer to question A.Using C language
时间: 2024-03-23 21:43:00 浏览: 93
Question A:
Write a C function that finds a pair of stones with a weight difference of D from an array of N stones. The function takes an array of integers and the size of the array as input, along with the weight difference D. The output of the function is a pair of integers representing the indices of the two stones in the array. If no such pair exists, the function returns a pair of -1.
Question B:
```
#include <stdio.h>
typedef struct Pair {
int first;
int second;
} Pair;
Pair findStonePair(int stones[], int n, int d) {
Pair pair = {-1, -1};
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (stones[i] - stones[j] == d || stones[j] - stones[i] == d) {
pair.first = i;
pair.second = j;
return pair;
}
}
}
return pair;
}
int main() {
int stones[] = {1, 5, 8, 12, 16, 19};
int n = sizeof(stones) / sizeof(stones[0]);
int d = 4;
Pair pair = findStonePair(stones, n, d);
if (pair.first == -1 && pair.second == -1) {
printf("No stone pair with a weight difference of %d found.\n", d);
} else {
printf("Stone pair with a weight difference of %d found: (%d, %d)\n", d, pair.first, pair.second);
}
return 0;
}
```
Note: This implementation has a time complexity of O(N^2), which may not be efficient enough for very large input sizes. There are more efficient algorithms for this problem, such as sorting the array and using two pointers to find the pair in O(N log N) time.
阅读全文