7-4 兔子回家

93 阅读 0 评论 62 点赞

我是靠谱客的博主友好小天鹅，这篇文章主要介绍7-4 兔子回家，现在分享给大家，希望可以做个参考。

n只兔子，n个房子，房子从左到右按1~n排列，标号为1~n，兔子标号也为1~n。标号为i的房子属于标号为i的兔子。现在每只兔子都在一个房子里面（可能不在自己的房子里面），每次相邻房子的兔子都可以交换房子，例如兔子a在房子x，兔子b在房子y。房子x与房子y相邻。a与b交换之后，兔子a在房子y，兔子b在房子x。计算至少要交换多少次能让所有的兔子在自己的家中。

输入格式:

第一行：n（1＜=n＜=1000）
第二行：输入一个数组a，ai表示房子i住着标号为ai的兔子。

输出格式:

输出一个数字表示答案。

输入样例:

复制代码

输出样例:

复制代码

1
2
7

Hint:

兔子1和兔子5交换：4 3 2 1 5
兔子2和兔子3交换：4 2 3 1 5
兔子4和兔子2交换：2 4 3 1 5
兔子4和兔子3交换：2 3 4 1 5
兔子1和兔子4交换：2 3 1 4 5
兔子1和兔子3交换：2 1 3 4 5
兔子1和兔子2交换：1 2 3 4 5
一共七步，这样兔子就都回家了

答案：冒泡排序裸题，记录下冒泡排序过程中交换的次数即可

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int bubble_sort(int arr[], int len) {
        int i, j, temp,sum;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                                sum++;
                        }
                        
}
int main() {
	int n,i,sum=0, j, temp;
	scanf("%d",&n);
	int a[n];
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
        for (i = 0; i < n - 1; i++)
                for (j = 0; j < n - 1 - i; j++){
                        if (a[j] > a[j + 1]) {
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                sum++;
                        }
						}
                printf("%d ",sum);
        return 0;
}