題意：

給出一個大天平，大天平中還有許多小天平，求出所有的天平是否平衡；平衡條件為wldl = wrdr；

題目

Before being an ubiquous communications gadget, a mobile
was just a structure made of strings and wires suspending
colourfull things. This kind of mobile is usually found hanging
over cradles of small babies.
The figure illustrates a simple mobile. It is just a wire,
suspended by a string, with an object on each side. It can
also be seen as a kind of lever with the fulcrum on the point where the string ties the wire. From the
lever principle we know that to balance a simple mobile the product of the weight of the objects by
their distance to the fulcrum must be equal. That is Wl × Dl = Wr × Dr where Dl
is the left distance,
Dr is the right distance, Wl
is the left weight and Wr is the right weight.
In a more complex mobile the object may be replaced by a sub-mobile, as shown in the next figure.
In this case it is not so straightforward to check if the mobile is balanced so we need you to write a
program that, given a description of a mobile as input, checks whether the mobile is in equilibrium or
not.

Input

The input begins with a single positive integer on a line by itself indicating the number
of the cases following, each of them as described below. This line is followed by a blank
line, and there is also a blank line between two consecutive inputs.
The input is composed of several lines, each containing 4 integers separated by a single space.
The 4 integers represent the distances of each object to the fulcrum and their weights, in the format:
Wl Dl Wr Dr
If Wl or Wr is zero then there is a sub-mobile hanging from that end and the following lines define
the the sub-mobile. In this case we compute the weight of the sub-mobile as the sum of weights of
all its objects, disregarding the weight of the wires and strings. If both Wl and Wr are zero then the
following lines define two sub-mobiles: first the left then the right one.

Output

For each test case, the output must follow the description below. The outputs of two
consecutive cases will be separated by a blank line.
Write ‘YES’ if the mobile is in equilibrium, write ‘NO’ otherwise.

Sample Input

1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2

Sample Output

YES
方案一：思維：可以構(gòu)造一個二叉樹，遞歸求出每個子樹是否平衡，傳遞判斷天平是否平衡1,0；
錯誤出現(xiàn)：1，若在調(diào)用函數(shù)bfs中了.l,r定義為全局變量（且在調(diào)用中對r,l賦值），則錯誤。
因為賦值時會覆蓋掉上一次獲取的r,l的值。
解決方案1，將其定義為局部變量，每一次調(diào)用，r,l不為同一值，利用遞歸，對r,l的值進行傳遞。
2，定義全局變量，但在主函數(shù)中賦初值，用遞歸傳遞值
（2） 參數(shù)傳遞的方式是引用傳遞
對形參的任何操作都能改變相應(yīng)的數(shù)據(jù)

#include<iostream> #include<string.h> using namespace std; int t; int bfs(int &p)//p 相當于此分支目前的重量 {/*遞歸傳遞判斷天平是否平衡1,0*/int a,u,b,v;cin>>a>>u>>b>>v;///輸入數(shù)據(jù)的時候正好可以構(gòu)建樹，當輸入數(shù)完成后就構(gòu)建成了一顆完整的樹int l=1,r=1;/**care 可能l和r最后也沒能賦值，為了到達葉節(jié)點可以比較，故賦初值*/if(a==0)l=bfs(a);/**判斷左子樹上，葉節(jié)點是否平衡*/if(b==0)r=bfs(b);/**判斷右子樹上，葉節(jié)點是否平衡*/p=a+b;///當輸入結(jié)束，回溯過程時，左右子樹重量相加,獲得判斷節(jié)點的重量和if(l&&r&&(a*u==b*v)) return 1;///左邊，右邊子樹重量相等，再比較此時它的重量else return 0; } int main() {cin>>t;while(t--){int x;int flag=bfs(x);///x 相當于此分支目前的重量if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;if(t)cout<<endl;}return 0; } /** 在C++中，參數(shù)傳遞的方式是“實虛結(jié)合”。 A按值傳遞(pass by value) int x B地址傳遞(pass by pointer) int *x C引用傳遞(pass by reference) int &x A調(diào)用函數(shù)本身不對實參進行操作，也就是說，即使形參的值在函數(shù)中發(fā)生了變化，實參的值也完全不會受 到影響，仍為調(diào)用前的值。 B地址傳遞與按值傳遞的不同在于，它把實參的存儲地址傳送給對應(yīng)的形參，從而使得形參指針和實參指針 指向同一個地址。因此，被調(diào)用函數(shù)中對形參指針所指向的地址中內(nèi)容的任何改變都會影響到實參。 C如果以引用為參數(shù)，可以使得對形參的任何操作都能改變相應(yīng)的數(shù)據(jù)，引用傳遞方式是在函數(shù)定義時在形參前面加上引用運算符“&”。 */

方案二
可以構(gòu)造一個二叉樹，遞歸求出每個子樹是否平衡，并返回wl+wr作為父親節(jié)點的w；

#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int t,flag; int dfs() {int a=0,u,b=0,v;scanf("%d%d%d%d",&a,&u,&b,&v);if(a==0)a=dfs();if(b==0)b=dfs();if(a*u!=b*v)flag=1;return a+b; } int main() {scanf("%d",&t);while(t--){flag=0;dfs();if(!flag)printf("YES\n");elseprintf("NO\n");if(t)printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Not so Mobile（二叉树递归输入同时建树）{天平}的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。