資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中兩點之間整數點的個數
在本教程中，我們將編寫一個程式來查詢給定兩點之間整數點的個數。
給定兩點之間的點數將為 gcd(abs(x2), abs(y1-y2)) - 1。
如果連線線平行於x軸，則整數點的個數為 abs(y1 - y2) - 1。
如果連線線平行於y軸，則整數點的個數為 abs(x1 - x2) - 1
如果兩點的x座標相等，則它們平行於x軸。如果兩點的y座標相等，則它們平行於y軸。
讓我們來看一個例子。
輸入
pointOne = [1, 5] pointTwo = [1, 3]
輸出
1
演算法
- 初始化兩點。
- 檢查它們是否平行於x軸。
- 如果它們平行於x軸，則使用公式 abs(y1 - y2) - 1。
- 檢查它們是否平行於y軸。
- 如果它們平行於y軸，則使用公式 abs(x1 - x2) - 1。
- 如果它們不平行於任何軸，則使用公式 gcd(abs(x1-x2), abs(y1- y2)) - 1。
- 計算結果並列印。
實現
以下是上述演算法在C++中的實現
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int getCount(int pointOne[], int pointTwo[]) {
if (pointOne[0] == pointTwo[0]) {
return abs(pointOne[1] - pointTwo[1]) - 1;
}
if (pointOne[1] == pointTwo[1]) {
return abs(pointOne[0] - pointTwo[0]) - 1;
}
return gcd(abs(pointOne[0] - pointTwo[0]), abs(pointOne[1] - pointTwo[1])) - 1;
}
int main() {
int pointOne[] = {1, 3}, pointTwo[] = {10, 12};
cout << getCount(pointOne, pointTwo) << endl;
return 0;
}輸出
如果執行以上程式碼，則將得到以下結果。
8
更新於：2021年10月26日
483 次瀏覽
廣告