目錄
問題陳述
範例範例2
Explanation
解釋
方法一:暴力破解方法
虛擬程式碼
範例:C 實作
輸出
方法二
結論
首頁 後端開發 C++ 兩兩乘積之和

兩兩乘積之和

Sep 11, 2023 pm 07:33 PM
計算 乘積

兩兩乘積之和

集合X = {a, b, c}的成對乘積可以定義為所有可能的集合對乘積的和。集合的成對為Y = {a * a, a * b, a *c, b * b, b * c, c * c},其中乘積是可交換的。因此,集合X的成對乘積是集合Y的元素總和,即aa ab ac bb bc cc。

在數學術語中,可能的配對乘積的總和可以表示為:

$$\mathrm{\displaystyle\sum\limits_{i=1,j=i}^{i\leq n,j\leq n}\:(i,j)=i\time j}$$

問題陳述

給定一個數字n。在範圍(1,n)內,包括n和1,找到成對乘積的總和。

範例範例1

Input: n = 4
登入後複製
Output: 65
登入後複製

Explanation

的中文翻譯為:

解釋

i的範圍從1到4,j的範圍從i到4。

1*1 1*2 1*3 1*4 2*2 2*3 2*4 3*3 3*4 4*4 = 1 2 3 4 4 6 8 9 12 16 = 65

範例範例2

Input: n = 10
登入後複製
Output: 1705
登入後複製

Explanation

的中文翻譯為:

解釋

i的範圍從1到10,j的範圍從i到10。

1*1 1*2 … 1*10 2*2 2*3 … 2*10 3*3 3*4 … 3*10 4*4 4 *5 … 4*10 5*5 5*6 … 5*10 6*6 6*7 … 6*10 7*7 7*8 … 7*10 8* 8 8*9 8*10 9*9 9*10 10*10 = 1705

方法一:暴力破解方法

解決這個問題的蠻力解法是使用兩個for循環迭代範圍內的所有可能的數對,其中第一個循環從1到n迭代,第二個循環從第一個數迭代到n。

虛擬程式碼

procedure pairwiseProduct (n)
   sum = 0
   for i = 1 to n
      for j = i to n
         sum = sum + (i * j)
end procedure
登入後複製

範例:C 實作

在以下程式中,我們找到所有可能的配對,然後找到乘積的和。

#include <bits/stdc++.h>
using namespace std;

// Function to find pairwise product over the range 1 to n, 1 and n inclusive
unsigned long long pairwiseProduct(unsigned int n){
   unsigned long long sum = 0;
   
   // First number: 1 <= i <= n
   for (unsigned int i = 1; i <= n; i++){
   
      // Second number: i <= j <= n
      for (unsigned int j = i; j <= n; j++){
         sum += i * j;
      }
   }
   return sum;
}
int main(){
   unsigned long long n = 9;
   cout << "Pairwise Product = " << pairwiseProduct(n);
   return 0;
}
登入後複製

輸出

Pairwise Product = 1155
登入後複製
登入後複製

時間複雜度 - O(n^2)

空間複雜度 - O(1)

方法二

以n = 4為例,

I = 1*1 1*2 1*3 1*4 2*2 2*3 2*4 3*3 3*4 4*4

在簡化上述內容時,

I = 1*1 (1 2)*2 (1 2 3)*3 (1 2 3 4)*4

取prefix_sum[1] = 1,

前綴總和[2] = 1 2,

前綴總和[3] = 1 2 3,

前綴總和[2] = 1 2,

虛擬程式碼

procedure pairwiseProduct (n)
   sum = 0
   prefixSum = 0
   for i = 1 to n
      prefixSum = prefixSum + 1
      sum = sum + i * prefixSum
end procedure
登入後複製

範例:C 實作

在下面的程式中,我們找到每次迭代的和,即前綴和,並乘以迭代次數,然後在每一步中加到最終和中。

#include <bits/stdc++.h>
using namespace std;

// Function to find pairwise product over the range 1 to n, 1 and n inclusive
unsigned long long pairwiseProduct(unsigned int n){
   unsigned long long sum = 0;
   unsigned long long prefixSum = 0;
   for (unsigned int i = 1; i <= n; i++){
      prefixSum += i;
      sum += i * prefixSum;
   }
   return sum;
}
int main(){
   unsigned long long n = 9;
   cout << "Pairwise Product = " << pairwiseProduct(n);
   return 0;
}
登入後複製

輸出

Pairwise Product = 1155
登入後複製
登入後複製

結論

總之,對於在範圍1到n內的數字的兩兩乘積之和的求解,我們可以採用上述兩種方法之一,其中第一種方法是暴力法,時間複雜度為O(n^ 2),第二種方法是使用前綴和來計算兩兩乘積總和的最佳化方法,時間複雜度為O(n)。

以上是兩兩乘積之和的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

<🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端:融合系統,解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

熱門話題

Java教學
1665
14
CakePHP 教程
1423
52
Laravel 教程
1321
25
PHP教程
1269
29
C# 教程
1249
24
CUDA之通用矩陣乘法:從入門到熟練! CUDA之通用矩陣乘法:從入門到熟練! Mar 25, 2024 pm 12:30 PM

通用矩陣乘法(GeneralMatrixMultiplication,GEMM)是許多應用程式和演算法中至關重要的一部分,也是評估電腦硬體效能的重要指標之一。透過深入研究和優化GEMM的實現,可以幫助我們更好地理解高效能運算以及軟硬體系統之間的關係。在電腦科學中,對GEMM進行有效的最佳化可以提高運算速度並節省資源,這對於提高電腦系統的整體效能至關重要。深入了解GEMM的工作原理和最佳化方法,有助於我們更好地利用現代計算硬體的潛力,並為各種複雜計算任務提供更有效率的解決方案。透過對GEMM性能的優

word文檔怎麼計算加減乘除 word文檔怎麼計算加減乘除 Mar 19, 2024 pm 08:13 PM

WORD是一個強大的文字處理器,我們可以利用word進行各種文字的編輯,在Excel表格當中,我們已經熟練了加減乘數的運算方法,那麼如果需要在Word表格裡,計算數值的加減乘數,該如何操作呢,難道只能用計算機計算嗎?答案當然是否定的,WORD也同樣可以完成。今天小編就來教大家如何在Word文件的表格當中,運用公式計算加減乘除等基本運算,一起來學習一下吧。那麼,今天就讓小編具體示範一下,WORD文件怎麼計算加減乘除?第一步:開啟一個WORD,點選工具列【插入】下的【表格】,在下拉式選單當中插入一

如何使用Python的count()函數計算清單中某個元素的數量 如何使用Python的count()函數計算清單中某個元素的數量 Nov 18, 2023 pm 02:53 PM

如何使用Python的count()函數計算清單中某個元素的數量,需要具體程式碼範例Python作為一種強大且易學的程式語言,提供了許多內建函數來處理不同的資料結構。其中之一就是count()函數,它可以用來計算清單中某個元素的數量。在本文中,我們將詳細介紹如何使用count()函數,並提供具體的程式碼範例。 count()函數是Python的內建函數,用來計算某

使用行列式計算三角形面積的Java程序 使用行列式計算三角形面積的Java程序 Aug 31, 2023 am 10:17 AM

簡介使用行列式計算三角形面積的Java程序是一個簡潔且有效率的程序,可以根據給定三個頂點的座標來計算三角形的面積。該程式對於學習或使用幾何的任何人都非常有用,因為它演示瞭如何在Java中使用基本算術和代數計算,以及如何使用Scanner類讀取使用者輸入。程式提示使用者輸入三角形三個點的座標,然後將其讀入並用於計算座標矩陣的行列式。使用行列式的絕對值來確保面積始終為正,然後使用公式計算三角形的面積並顯示給使用者。該程式可以輕鬆修改以接受不同格式的輸入或執行附加計算,使其成為幾何計算的多功能工具。決定因素行列

在Java中遞歸地計算子字串出現的次數 在Java中遞歸地計算子字串出現的次數 Sep 17, 2023 pm 07:49 PM

給定兩個字串str_1和str_2。目標是使用遞歸過程計算字串str1中子字串str2的出現次數。遞歸函數是在其定義中呼叫自身的函數。如果str1是"Iknowthatyouknowthatiknow",str2是"know"出現次數為-3讓我們透過範例來理解。例如輸入str1="TPisTPareTPamTP",str2="TP";輸出Countofoccurrencesofasubstringrecursi

如何使用C#中的Math.Pow函數計算指定數的冪次方 如何使用C#中的Math.Pow函數計算指定數的冪次方 Nov 18, 2023 am 11:32 AM

在C#中,有一個Math類別庫,其中包含許多數學函數。其中包括計算冪次方的函數Math.Pow,它可以幫助我們計算指定數的冪。 Math.Pow函數的用法非常簡單,只需要指定底數和指數就可以了。其語法如下:Math.Pow(base,exponent);其中base表示底數,exponent表示指數。此函數傳回double類型的結果,即冪次方的計算結果。下面讓

賽揚g4900與i36100相比哪個比較優? (賽揚g4900與i34170相比哪個比較優?) 賽揚g4900與i36100相比哪個比較優? (賽揚g4900與i34170相比哪個比較優?) Jan 01, 2024 pm 06:01 PM

賽揚g4900和i36100哪個好當涉及到賽揚G4900和I36100這兩款處理器時,毫無疑問,I36100的性能更勝一籌。賽揚處理器通常被視為低階處理器,主要用於廉價筆記型電腦。而I3處理器則主要用於高階處理器,其效能非常出色。不論是玩遊戲還是觀看視頻,使用I3處理器都不會出現任何卡頓情況。因此,如果你有可能,盡量選擇購買英特爾I系列處理器,特別是用於桌上型電腦,這樣你就能享受網路世界的樂趣了。賽揚G4900T性能怎麼樣從性能方面來看,奔騰G4900T在頻率方面表現出色,相比之前的版本,CPU性能

華碩主機板與R55600(包括R55600u和5600h)相容的選擇 華碩主機板與R55600(包括R55600u和5600h)相容的選擇 Jan 02, 2024 pm 05:32 PM

R55600搭配華碩哪個主機板華碩ROGStrixB550-FGaming主機板是個非常優秀的選擇。它與Ryzen55600X處理器完美兼容,並提供出色的性能和功能。此主機板具備可靠的供電系統,可支援超頻,並提供豐富的擴充插槽和連接埠,滿足日常使用和遊戲需求。 ROGStrixB550-FGaming還配備了高品質的音訊解決方案、快速的網路連接和可靠的散熱設計,確保系統保持高效穩定。此外,此主機板還採用了華麗的ROG風格,並配備了華麗的RGB照明效果,為您的電腦增添了視覺享受。總而言之,華碩ROGStri

See all articles