请帮我写个逆反序数的程序用c语言
时间: 2023-04-08 15:04:51 浏览: 93
好的,我可以回答这个问题。以下是一个简单的逆反序数的程序,使用C语言编写:
```
#include <stdio.h>
int main() {
int n, i, j, count = 0;
printf("请输入一个整数n:");
scanf("%d", &n);
int a[n];
printf("请输入%d个整数:", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
count++;
}
}
}
printf("逆反序数的个数为:%d\n", count);
return 0;
}
```
这个程序会先让用户输入一个整数n,表示接下来要输入n个整数。然后用户输入n个整数,程序会计算这些整数中逆反序数的个数,并输出结果。逆反序数指的是在一个数组中,如果i < j 且 a[i] > a[j],那么(i, j)就是一个逆反序数。
相关问题
c语言编写两个程序分别用来求逆序数和判定序数
1. 求逆序数的程序:
```c
#include <stdio.h>
int merge(int arr[], int temp[], int left, int mid, int right) {
int i, j, k;
int count = 0;
i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i);
}
}
while (i <= mid - 1) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
return count;
}
int mergeSort(int arr[], int temp[], int left, int right) {
int mid, count = 0;
if (right > left) {
mid = (right + left) / 2;
count = mergeSort(arr, temp, left, mid);
count += mergeSort(arr, temp, mid + 1, right);
count += merge(arr, temp, left, mid + 1, right);
}
return count;
}
int getInvCount(int arr[], int n) {
int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main() {
int arr[] = {1, 20, 6, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("逆序数为 %d", getInvCount(arr, n));
return 0;
}
```
2. 判断序列是否有序的程序:
```c
#include <stdio.h>
int isSorted(int arr[], int n) {
int i;
for (i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
return 0;
}
}
return 1;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
if (isSorted(arr, n)) {
printf("该序列有序\n");
} else {
printf("该序列无序\n");
}
return 0;
}
```
编写两个程序分别用来求逆序数和判定序数
求逆序数的程序:
```python
def merge_sort(arr):
if len(arr) == 1:
return arr, 0
mid = len(arr) // 2
left, inv_left = merge_sort(arr[:mid])
right, inv_right = merge_sort(arr[mid:])
merged, count = merge(left, right)
return merged, inv_left + inv_right + count
def merge(left, right):
result = []
count = 0
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
count += len(left) - i
result += left[i:]
result += right[j:]
return result, count
arr = [2, 4, 1, 3, 5]
result, inv_count = merge_sort(arr)
print(inv_count)
```
判定序数的程序:
```python
def is_sorted(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
arr = [1, 2, 3, 4, 5]
print(is_sorted(arr)) # True
arr = [2, 1, 3, 4, 5]
print(is_sorted(arr)) # False
```
第一个程序使用归并排序算法来求逆序数,它的基本思想是将数组分成两部分进行排序,然后将两部分合并。在合并的过程中,如果左半部分的元素大于右半部分的元素,那么就要计算逆序数,具体的计算方法是左半部分剩余的元素个数。最终,逆序数等于左半部分的逆序数加上右半部分的逆序数加上合并时计算得到的逆序数。
第二个程序很简单,只需要遍历整个数组,判断相邻的两个元素是否有逆序即可。如果有逆序,就说明数组是无序的。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)