勾股四元數

---

四個正整數 (a, b, c, d) 滿足勾股定理的被稱為勾股四元數。

該方程可以寫成：a² + b² + c² = d²，其中 ‘d’ 是給定數字中最大的值。換句話說，第四個整數的平方應該等於前三個數字平方和。

(1, 2, 2, 3) 是一個勾股四元數，因為 (1² + 2² + 2²) = (1 + 4 + 4) = (9) = (3²)。由於需要滿足勾股定理，並非所有四個正整數集合都是勾股四元數。勾股四元數可以用來建立引人入勝的數學模式，並且在數論中也有應用。

問題陳述

這個問題的目的是檢查給定的4個整數是否構成勾股四元數。

示例

Input: {2, 3, 6, 7}
Output: True

說明 −

前三個數字的平方和可以寫成：

(2² + 3² + 6²) = (4 + 9 + 36) = 49

第四個數的平方是 7² = 49，等於前面的結果。因此，數字 {2, 3, 6, 7} 構成勾股四元數，所以我們返回 True。

Input: {1, 4, 8, 9}
Output: True

說明 −

前三個數字的平方和可以寫成：

(1² + 4² + 8²) = (1 + 16 + 64) = 81

第四個數的平方是 9² = 81，等於前面的結果。因此，數字 {1, 4, 8, 9} 構成勾股四元數，所以我們返回 True。

Input: {1, 2, 3, 4}
Output: False

說明 −

前三個數字的平方和可以寫成：

(1² + 2² + 3²) = (1 + 4 + 9) = 14

第四個數的平方是 4² = 16，不等於前面的結果。因此，數字 {1, 4, 8, 9} 不構成勾股四元數，所以我們返回 False。

解決方案方法

為了確定給定的4個數字是否構成勾股四元數，我們必須確定前3個數字的平方和是否等於第四個數字的平方，其中第四個數字的絕對值最大。

演算法

該方法包括以下步驟：

• 將數字向量按非遞減順序排序。

• 計算前三個數字的平方和。

• 計算第四個數的平方。

• 檢查步驟2和步驟3得到的結果是否相等。

• 顯示答案。

虛擬碼

函式 is_pythagorean_quadruplet()

• 初始化 squareSum。

• squareSum = a² + b² + c²

• 返回 (squareSum == d²)

函式 main()

• 初始化 vector<int>nums = {a, b, c, d}

• sort (nums.begin(), nums.end())

• 如果 (is_pythagorean_quadruplet())

• 返回 true

• 否則

• 返回 false

• 列印輸出

示例：C++程式

此程式程式碼使用is_pythagorean_quadruplet()布林函式檢查儲存在向量中的給定的4個數字是否構成勾股四元數。它最初使用C++標準模板庫sort()函式對向量進行排序。然後計算前三個數字的平方和並將它們儲存在squareSum變數中。如果squareSum的值等於第四個數的平方，則函式is_pythagorean_quadruplet()返回true，否則返回false。

// C++ code for to check if the 4 given numbers form a Pythagorean Quadruple
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

// this function is used to check out whether the 4 given numbers form a Pythagorean Quadruplet or not
bool is_pythagorean_quadruplet(vector<int> nums){
   int squareSum;
   squareSum = pow(nums[0], 2) + pow(nums[1], 2) + pow(nums[2], 2); // 9
   return (squareSum == pow(nums[3], 2)); // compares summation of square   of  first three numbers with square of fourth number (9 == 9)
}

int main(){
   vector<int> nums = {1, 2, 2, 3};
   sort(nums.begin(), nums.end()); // sorts the numbers in non-decreasing order
   if (is_pythagorean_quadruplet(nums)) {
      cout << "True" << endl; 
   } else {
      cout << "False" << endl;
   }
   return 0;
}

輸出

True

時間和空間複雜度分析

時間複雜度：O(1)

O(1)，因為它執行固定數量的操作。squareSum由函式is_pythagorean_quadruplet()使用三個常數時間操作計算，並測試其與第四個元素的平方是否相等。

在最壞的情況下，sort函式的時間複雜度為O(nlog(n))。因此，程式碼的整體時間複雜度應該為O(nlog(n))，其中n是向量中元素的數量。但是，由於在每種情況下向量的長度都設定為4，因此sort函式的時間複雜度保持不變。

空間複雜度：O(1)

這是因為儲存輸入向量所需的儲存空間始終為4。程式碼的實現不需要輔助空間；因此，空間複雜度可以認為是常數。

結論

總之，勾股四元數是整數a、b、c和d的元組，滿足

a² + b² + c² = d²。本文介紹的演算法提供了一種簡單有效的方法，可以在不使用輔助空間的情況下，以常數時間確定四個整數的元組是否構成勾股四元數。本文討論了勾股四元數的基本概念以及相應的示例。它還提供瞭解決方案方法、使用的演算法和C++程式解決方案，以及對其時間複雜度和空間複雜度的深入分析。