郊游 ID：PICNIC
題目大意
仙女星幼兒園的快班小朋友們下周要到粟洞公園郊游。帶隊教師想在郊游時讓兩名學(xué)生組成一個小隊進行活動。不過讓兩名不是朋友的學(xué)生組成一隊會發(fā)生爭執(zhí)或者互不理睬。因此，必須由兩名朋友關(guān)系的學(xué)生組隊。
給定各學(xué)生的朋友關(guān)系詳情，編寫程序計算出所有可配對的不同方法。任何一個不相同的配對都將被視為一種不同的配對方法。例如，以下兩種配對方法就屬于不同的配對方法。
●(泰妍，杰西卡)(珊妮，蒂芬妮)(孝淵，俞利)
●(泰妍，杰西卡)(珊妮，俞利)(孝淵，蒂芬妮)
解題思路：
為了使用遞歸調(diào)用，首先將整個操作過程分解為幾個小的操作。這道題中，將整個問題分解為m/2個小操作，每個小操作等同于對兩名學(xué)生的組隊。此時問題將變?yōu)椤敖o定還未組隊的學(xué)生名單時，計算出兩名朋友間組成小隊的組合個數(shù)”。因為名單中找出兩名互為朋友關(guān)系的學(xué)生組隊后，對剩下學(xué)生的組隊又相當(dāng)于前一步驟的操作過程。
出現(xiàn)的問題：
計算組合個數(shù)時會經(jīng)常遇到重復(fù)相同答案的現(xiàn)象。為了解決這種錯誤，可采取只計算特定形態(tài)答案的方法。通常使用的方法是，在相同答案中以字典順序只選擇最先得到的答案。例如，忽略(2，3)、(0，1)或(1，0)、(2，3)，而選擇(0，1)、(2，3)。
為了強制這種屬性，在各操作階段只為序號最靠前的學(xué)生配上伙伴，即可解決前面提到的兩種問題。對序號最靠前的學(xué)生而言，其伙伴的序號肯定比其靠后，所以不可能得到像(1，0)這一類的答案。又因為總是從序號最靠前的學(xué)生開始配對，所以也不可能出現(xiàn)像(2，3)、(0，1)這一類答案。代碼6-5是按照這種思路編寫的代碼。
int n ; bool areFriend[10][10]; // 若第take[i] = i 個學(xué)生找到了伙伴，則返回true，否則為false int countPairings(bool take[10]){int firstFree = -1;for(int i =0;i<n;++i){if(!take[i]){firstFree = i;break;}}//所有的學(xué)生都匹配上了if(firstFree == -1)return 1;int ret = 0;//選擇與學(xué)生組隊的伙伴for(int pairWith = firstFree+1;pairWith<n;++i){if(!take[pairWith]&&areFriend[firstFree][pairWith]){take[firstFree] = take[pairWith] = true;ret += countPairings(take);take[firstFree] = take[pairWith] = false;}}return ret; }總結(jié)
以上是生活随笔為你收集整理的郊游 ID：PICNIC的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
