資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++陣列中交叉線的計數
給定一個包含不同元素的未排序陣列。目標是在陣列排序後找到交叉線。交叉線的計數如下所示：
Arr[]={ 1,2,4,3,5 } 如圖所示，共有3條交叉線。
Arr[]= { 1,2,3,4,5 }。因為陣列已排序，所以沒有交叉線。
我們將使用插入排序來計算交叉線，其中從右邊取一個元素新增到其左邊的已排序元素中。每次元素新增到已排序部分時，都將計數器遞增，因為它移動到其正確的位置。它將透過穿過所有大於它的元素來進行。
讓我們透過例子來理解。
輸入 − arr[]= {4,3,1,2 }
輸出− 陣列中交叉線的數量 − 5
解釋 − 4-4 和 3-3 交叉 1-1 和 2-2。共有 4 條交叉線。
4-4 和 3-3 互相交叉一次。共有 4+1=5 條交叉線。
輸入 − arr[]= { 0,1,5,3 }
輸出 − 陣列中交叉線的數量 − 1
解釋 − 5-5 和 3-3 互相交叉一次。共有 1 條交叉線。
下面程式中使用的演算法如下：
我們使用一個用不同數字初始化的整數陣列 arr[]。
函式 insertionSort(int arr[], int n) 以陣列及其長度作為輸入，排序後返回交叉線的數量作為結果。
將交叉線的初始數量設為 0。使用計數變數。
第一個元素已經排序，所以從第二個元素到結尾 (i=1 到 i<n)，取每個元素作為 item。(item=arr[i]) 並令 j=i-1。
如果元素 > item 且 j>0，則將所有元素向右移動。對於每次移動，計數器遞增，因為這些元素都被 item 交叉。
在 while 迴圈結束時，將 item 放置到其正確的位置，即 arr[j+1]。
對所有元素執行此操作，並計算它們交叉的元素數。
將計數器值遞增為可能的交叉線數。
示例
#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
int count=0;
int item;
int j;
for (int i = 1; i < n; i++){
item = arr[i];
j = i - 1;
//insert element at correct position in sorted part, no. of elements it passes
//from right till correct position is count of cross lines.
while (j >= 0 && arr[j] > item){
arr[j + 1] = arr[j];
j = j - 1;
count++;
}
arr[j + 1] = item;
}
return count;
}
int main(){
int arr[] = { 4,5,3,1,2};
int n = 5;
cout<<"Number of cross lines: "<<insertionSort(arr, n);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Number of cross lines: 8
更新於：2020年8月29日
163 次瀏覽
廣告