有N個瓶子,編號 1 ~ N,放在架子上。
比如有5個瓶子:
2 1 3 5 4
要求每次拿起2個瓶子,交換它們的位置。
經過若干次后,使得瓶子的序號為:
1 2 3 4 5
對于這么簡單的情況,顯然,至少需要交換2次就可以復位。
如果瓶子更多呢?你可以通過編程來解決。
輸入格式為兩行:
第一行: 一個正整數N(N<10000), 表示瓶子的數目
第二行:N個正整數,用空格分開,表示瓶子目前的排列情況。
輸出數據為一行一個正整數,表示至少交換多少次,才能完成排序。
例如,輸入:
5
3 1 2 5 4
程序應該輸出:
3
再例如,輸入:
5
5 4 3 2 1
程序應該輸出:
2
思路分析:
拿案例來說: 輸入 5 表示5個瓶子,分別標號1~5;
輸入 3 1 2 5 4(表示不同標號的瓶子排放位置的先后次序)
3 1 2 5 4 首先第一個位置的瓶子標號為3 ,然后,找位置為3的瓶子,進行交換
2 1 3 5 4(此時,第一個位置的瓶子標號為2,然后,找位置為2的瓶子,進行交換)
1 2 3 5 4(由于第一個位置的瓶子標號跟位置一致,進行下一個位置查找,直到發現第4個位置的瓶子標號為5,進行交換)
1 2 3 4 5(結束)
代碼如下:
#include <iostream>
#include<stdio.h>
using namespace std;int main(){int a[10001];//用來存放各個瓶子的標號int i,j,sum=0;//sum代表 計數,最后一共交換多少次int x,t;//x代表 一共有幾個瓶子 t為一個交換的中間變量scanf("%d",&x);//輸入一個幾個瓶子for(i=1;i<=x;i++){scanf("%d",&a[i]);//按從1~x的位置以次輸入不同標號的瓶子}for(j=1;j<=x;j++){//按位置進行查找交換while(a[j] != j){//如果位置與瓶子的標號不一致,進交換位置t=a[a[j]];//找到第j個位置上的瓶子標號(1<=j<=x),然后找到該標號對應的位置上的那個瓶子標號a[a[j]]=a[j];//將第j個位置上的瓶子(1<=j<=x),與該瓶子標號相同的位置上的那個瓶子進行交換a[j]=t;//將第j個位置上的瓶子,找到與給瓶子的標號相同的位置上的瓶子,進行交換sum++;//交換一下,計數加一}}printf("%d",sum);return 0;
}