資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 C++ 中最大化樹中任意兩個頂點之間度數乘積之和
給定任務是用給定的整數 N 構造一棵樹，使得所有有序對 (x,y) 的 degree(x) * degree(y) 之和最大，且 x 不等於 y。
輸入 −N=5
輸出 −50
解釋
1 \ 2 \ 3 \ 4 \ 5 Degree of 1st node = 1 Degree of 2nd node = 2 Degree of 3rd node = 2 Degree of 4th node = 2 Degree of 5th node = 1
所有有序對 (x, y) 的所有度數的乘積 −
1st node = 1*2 + 1*2 + 1*2 + 1*1 = 7 2nd node = 2*1 + 2*2 + 2*2 + 2*1 = 12 3rd node = 2*1 + 2*2 + 2*2 + 2*1 = 12 4th node = 2*1 + 2*2 + 2*2 + 2*1 = 12 5th node = 1*2 + 1*2 + 1*2 + 1*1 = 7 Total sum = 50
輸入 −N=7
輸出 −122
下面程式中使用的演算法如下
樹中所有節點的度數之和為 − (2 * N) – 2。這裡 N=樹中節點數。為了最大化總和，必須最小化葉節點數。
在 Max() 函式內，初始化 int sum=0 並建立巢狀迴圈，初始化 x=1 和 y=1，條件為 x<N 和 y<N。
在巢狀迴圈內，首先檢查 if(x==y)，如果是，則新增 continue; 語句
否則，初始化 int degree=2，並使用 if 語句檢查 if(x==1 || x==n)。如果是，則將 degreeX=1。然後初始化 int degree=2，對變數 y 執行相同的操作
最後，在關閉迴圈之前，透過編寫 sum = (degreeX + degreeY) 來更新 sum 變數
示例
#include <bits/stdc++.h>
using namespace std;
int Max(int N){
int sum = 0;
for (int x = 1; x <= N; x++){
for (int y = 1; y <= N; y++){
if (x == y)
continue;
//Initializing degree for node x to 2
int degreeX = 2;
//If x is the leaf node or the root node
if (x == 1 || x == N)
degreeX = 1;
//Initializing degree for node y to 2
int degreeY = 2;
//If y is the leaf node or the root node
if (y == 1 || y == N)
degreeY = 1;
//Updating sum
sum += (degreeX * degreeY);
}
}
return sum;
}
//Main function
int main(){
int N = 5;
cout << Max(N);
}輸出
如果我們執行上述程式碼，我們將得到以下輸出：
50
更新於：2020年8月17日
254 次瀏覽
廣告