資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中計算排序陣列中乘積小於k的數對
給定一個排序的整型陣列和一個整型變數x，任務是從給定陣列中形成數對，計算數對中元素的乘積，並檢查計算出的乘積是否小於k。
輸入
int arr[] = {2, 7, 1, 0, 8}, int k = 10輸出
Count of pairs in a sorted array whose product is less than k are: 7
解釋
The pairs that can be formed from the given array are: (2, 7) = 14(greater than k), (2, 1) = 2(less than k), (2, 0) = 0(less than k), (2, 8) = 16(greater than k), (7, 1) = 7(less than k), (7, 0) = 0(less than k), (7, 8) = 56(greater than k), (1, 0) = 0(less than k), (1, 8) = 8(less than k), (0, 8) = 0(less than k). So, the count of pairs with sum less than k are 7.
輸入
int arr[] = {2, 4, 6, 8}, int k = 10輸出
Count of pairs in a sorted array whose product is less than k are: 1
解釋
The pairs that can be formed from the given array are: (2, 4) = 8(less than k), (2, 6) = 12(greater than k), (2, 8) = 16(greater than k), (4, 6) = 24(greater than x), (4, 8) = 32(greater than k), (6, 8) = 48(greater than k). So, the count of pairs with products less than k is 1.
下面程式中使用的演算法如下：
解決給定問題有多種方法，即樸素方法和高效方法。所以讓我們先看看樸素方法。
輸入一個整型陣列，計算陣列大小，並將資料傳遞給函式。
宣告一個臨時變數count來儲存乘積小於k的數對的數量。
從i=0開始迴圈到陣列大小。
在迴圈內，從j=i+1開始另一個迴圈到陣列大小。
在迴圈內計算乘積arr[i] * arr[j]，如果乘積< k，則將count加1。
返回count。
列印結果。
高效方法
輸入一個整型陣列，計算陣列大小，並將資料傳遞給函式。
宣告一個臨時變數count來儲存和數小於x的數對的數量。
設定arr_0為0，arr_1為size-1。
從arr_0迴圈到arr_1。
在迴圈內，如果arr[arr_0] * arr[arr_1] < x，則設定count為count + (arr_1 - arr_0)，並遞增arr_0++，否則將arr_1減1。
返回count。
列印結果。
示例（樸素方法）
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int count = 0;
int product = 1;
for(int i = 0 ; i<size ; i++){
for(int j = i+1; j<size; j++){
product = arr[i] * arr[j];
if(product < k){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {5, 8, 2, 1, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 10;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
}輸出
如果執行以上程式碼，將生成以下輸出：
Count of pairs in a sorted array whose product is less than k are: 5
示例（高效方法）
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
int product = 1;
while(arr_0 < arr_1){
product = arr[arr_0] * arr[arr_1];
if (product < k){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {1, 3, 4, 2, 1};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
}輸出
如果執行以上程式碼，將生成以下輸出：
Count of pairs in a sorted array whose product is less than k are: 10
更新於：2020年11月2日
212次瀏覽
廣告