输入一串n个正整数的数组以及一个正整数 C,要求计算出所有满足 A−B=C 的数对的个数 (AB均为数组内的数,AB不能同时取同一位置的数) (不同位置的数字一样的数对算不同的数对) (1<n<15) (先输入n个正整数用空格隔开,换行后再输入正整数C,输出一个正整数) C语言做
时间: 2024-10-03 13:00:40 浏览: 41
这是一个经典的数组问题,通常需要使用哈希表(或者称为字典)的数据结构来解决。你可以按照以下步骤编写C语言代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 14 // 假设n的最大值是14
// 创建一个辅助函数用于检查是否存在目标差值
bool checkDiff(int diff, int arr[], int n) {
for (int i = 0; i < n; i++) {
if (arr[i] - diff >= 0 && arr[i] - diff != arr[i]) { // 检查是否有另一个元素等于当前元素减去diff
return true;
}
}
return false;
}
// 主函数
int countPairs(int arr[], int n, int target) {
int count = 0;
bool visited[MAX_N + 1]; // 初始化一个哈希表
memset(visited, false, sizeof(visited));
for (int i = 0; i < n; i++) {
if (!visited[arr[i]]) { // 如果当前元素未访问过
for (int j = i + 1; j < n; j++) { // 遍历剩余元素
if (!visited[arr[j]]) { // 同理,第二个元素也未访问过
if (arr[i] - arr[j] == target) { // 找到满足条件的数对
count++;
visited[arr[i]] = true; // 标记第一个元素已处理
visited[arr[j]] = true; // 标记第二个元素已处理
} else if (checkDiff(arr[i], arr + j, n - j)) { // 如果差值存在其他数,更新计数
count += visited[arr[i] - arr[j]];
}
}
}
}
}
return count;
}
int main() {
int n;
scanf("%d", &n);
int arr[MAX_N];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int target;
scanf("%d", &target);
int result = countPairs(arr, n, target);
printf("满足条件的数对个数: %d\n", result);
return 0;
}
```
这个程序首先通过`countPairs`函数遍历数组,对于每个元素,它都会尝试找到所有满足差值`target`的数对,并利用哈希表`visited`来避免重复计算。注意,`checkDiff`函数用于检查是否存在其他位置的数可以构成所需的差值。
阅读全文