goal00001111

     摘要: 快速排序是在實踐中最快的已知排序算法，它的平均運行時間是O（NlogN）。該算法之所以特別快，主要是由于非常精練和高度優化的內部循環。在隊列中尋找合適的樞點元素，并按樞點元素劃分序列，是快速排序算法的關鍵。
為簡單起見，我這里數組的第一個元素作為樞點元素，重新排列數組，使得樞點元素之前的元素都小于樞點元素，而樞點元素之后的元素都大于或等于樞點元素。  閱讀全文

     摘要: 排序在最壞的情況下，其時間復雜度也能達到O（nlogn）。相對于快速排序來說，這是它最大的優點，此外，堆排序僅需要一個記錄大小供交換用的輔助存儲空間。
堆排序的數據結構是二叉堆，二叉堆的特點有兩個，一個是它是一棵完全二叉樹，另一個是它的根結點小于孩子結點，所以我們很容易找到它的最小結點----根結點；當然如果你想找到最大結點的話，那就要掃描所有的葉子結點，這是很費時間的，如果你想找的是最大結點的話，你最好把它弄成一個大頂堆，即一棵根結點大于孩子結點的完全二叉樹。
二叉堆通常用數組來實現，它舍棄下標0，從下標1開始置數，則很容易滿足，對于數組中任意位置i上的元素，其左兒子的位置在2i上，右兒子的位置在2i+1上，雙親的位置則在i/2上。
堆排序的算法之一是把數組構建成二叉堆----這只要增添一個長度為n+1的輔助空間，然后把原數組的元素依次插入到二叉堆即可。然后刪除二叉堆的根，把它作為排序后的數組的第一個元素,然后使二叉堆的長度減1，并通過上移使得新得到的序列仍為二叉堆，再提取新二叉堆的第一個元素到新數組。依此類推，直到提取最后  閱讀全文

/*
問題描述：有三個柱子A, B, C. A柱子上疊放有n個盤子，每個盤子都比它下面的盤子要小一點，
可以從上到下用1, 2, ..., n編號。要求借助柱子B，把柱子A上的所有的盤子移動到柱子C上。
移動條件為：1、一次只能移一個盤子；
2、移動過程中大盤子不能放在小盤子上，只能小盤子放在大盤子上。
*/
/*
遞歸的算法相信大多數人都知道，非遞歸算法也有出現過。
如：摘自http://www.programfan.com/club/old_showbbs.asp?id=96548
作者：qq590240
#include <iostream>
#include <stdlib.h>

#ifdef _WIN32
using namespace std;
#endif

static void hanoi(int height)
{
??? int fromPole, toPole, Disk;
??? int *BitStr = new int[height],
??????? *Hold?? = new int[height];
??? char Place[]? = {'A', 'B', 'C'};
??? int i, j, temp;

??? for (i=0; i < height; i++)
??? {
??????? BitStr[i] = 0;
??????? Hold[i] = 1;
??? }
??? temp = 3 - (height % 2);
??? int TotalMoves = (1 << height) - 1;
??? for (i=1; i <= TotalMoves; i++)
??? {
??????? for (j=0 ; BitStr[j] != 0; j++)
??????? {
??????????? BitStr[j] = 0;
??????? }
??????? BitStr[j] = 1;
??????? Disk = j+1;
??????? if (Disk == 1)
??????? {
??????????? fromPole = Hold[0];
??????????? toPole = 6 - fromPole - temp;
??????????? temp = fromPole;
??????? }
??????? else
??????? {
??????????? fromPole = Hold[Disk-1];
??????????? toPole = 6 - Hold[0] - Hold[Disk-1];
??????? }
??????? cout << "Move disk " << Disk << " from " << Place[fromPole-1]
???????????? << " to " << Place[toPole-1] << endl;
??????? Hold[Disk-1] = toPole;
??? }
}

?

int main(int argc, char *argv[])
{
??? cout << "Towers of Hanoi: " << endl
???????? << "moving a tower of n disks from pole A to pole B by using pole C" << endl;
??? cout << "Input the height of the original tower: ";
??? int height;
??? cin >> height;
??? hanoi(height);

??? system("PAUSE");
??? return EXIT_SUCCESS;
}
?////////////////////////////////////////////////////////////
?我在這里根據《數學營養菜》（談祥柏 著）提供的一種方法，編了一個程序來實現。
*/
/*
算法介紹：
首先容易證明，當盤子的個數為n時，移動的次數應等于2^n - 1。
一位美國學者發現一種出人意料的方法，只要輪流進行兩步操作就可以了。
首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上。
根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；
若n為奇數，按順時針方向依次擺放 A C B。
（1）按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；
若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。
（2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。
即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤
這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。
（3）反復進行（1）（2）操作，最后就能按規定完成漢諾塔的移動。
*/
#include <iostream>
using namespace std;

const int MAX = 64; //圓盤的個數最多為64

struct st{? //用來表示每根柱子的信息
????? int s[MAX]; //柱子上的圓盤存儲情況
????? int top; //棧頂，用來最上面的圓盤
????? char name; //柱子的名字，可以是A，B，C中的一個
?????
????? int Top()//取棧頂元素
????? {
??????????? return s[top];
????? }
????? int Pop()//出棧
????? {
??????????? return s[top--];
????? }
????? void Push(int x)//入棧
????? {
??????????? s[++top] = x;
????? }
} ;

long Pow(int x, int y); //計算x^y
void Creat(st ta[], int n); //給結構數組設置初值
void Hannuota(st ta[], long max); //移動漢諾塔的主要函數

int main(void)
{
????? int n;
????? cin >> n; //輸入圓盤的個數
?????
????? st ta[3]; //三根柱子的信息用結構數組存儲
????? Creat(ta, n); //給結構數組設置初值

????? long max = Pow(2, n) - 1;//動的次數應等于2^n - 1
????? Hannuota(ta, max);//移動漢諾塔的主要函數

????? system("pause");
????? return 0;
}

void Creat(st ta[], int n)
{
????? ta[0].name = 'A';
????? ta[0].top = n-1;
????? for (int i=0; i<n; i++) //把所有的圓盤按從大到小的順序放在柱子A上
??????????? ta[0].s[i] = n - i;
???????????
????? ta[1].top = ta[2].top = 0;//柱子B，C上開始沒有沒有圓盤
????? for (int i=0; i<n; i++)
??????????? ta[1].s[i] = ta[2].s[i] = 0;
???????????
????? if (n%2 == 0) //若n為偶數，按順時針方向依次擺放 A B C
????? {
??????????? ta[1].name = 'B';
??????????? ta[2].name = 'C';
????? }
????? else? //若n為奇數，按順時針方向依次擺放 A C B
????? {
??????????? ta[1].name = 'C';
??????????? ta[2].name = 'B';
????? }
}

long Pow(int x, int y)
{
????? long sum = 1;
????? for (int i=0; i<y; i++)
??????????? sum *= x;

????? return sum;
}

void Hannuota(st ta[], long max)
{
????? int k = 0; //累計移動的次數
????? int i = 0;
????? int ch;
????? while (k < max)
????? {
??????????? //按順時針方向把圓盤1從現在的柱子移動到下一根柱子
??????????? ch = ta[i%3].Pop();
??????????? ta[(i+1)%3].Push(ch);
??????????? cout << ++k << ": " << "Move disk " << ch << " from " << ta[i%3].name << " to " << ta[(i+1)%3].name << endl;
??????????? i++;
??????????? //把另外兩根柱子上可以移動的圓盤移動到新的柱子上
??????????? if (k < max)
??????????? {???? //把非空柱子上的圓盤移動到空柱子上，當兩根柱子都為空時，移動較小的圓盤
????????????????? if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
????????????????? {
??????????????????????? ch =? ta[(i-1)%3].Pop();
??????????????????????? ta[(i+1)%3].Push(ch);
??????????????????????? cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl;
????????????????? }
????????????????? else
????????????????? {
??????????????????????? ch =? ta[(i+1)%3].Pop();
??????????????????????? ta[(i-1)%3].Push(ch);
??????????????????????? cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i+1)%3].name << " to " << ta[(i-1)%3].name << endl;
????????????????? }
??????????? }
????? }
}

?

也許二杈樹是很好用的，在插入和查找的時候時間復雜度一般為O（logN），但如果左右子樹失去平衡，也可能達到O（N）。為了防止這種現象發生，一種解決辦法是是左右子樹盡量保持平衡，即建立一種平衡有序樹AVL樹。?????
????一棵AVL樹是其每個結點的左子樹和右子樹的高度最多相差1的二杈有序樹。空樹的高度定義為-1。
????AVL樹的結點聲明；
typedef?struct?avlnode
{
????int?height;//比普通二杈有序樹多了一個高度信息?
????ElemType?data;
????struct?bnode?*lchild,?*rchild;
}?*AvlTree,?*Position;????
//----------AVL樹基本操作------------?------------------------------
AvlTree?MakeEmpty(AvlTree?T);
Position?Find(ElemType?x,?AvlTree?T);
Position?FindMin(AvlTree?T);
Position?FindMax(AvlTree?T);
static?int?Height(Position?P);
AvlTree?Insert(ElemType?x,?AvlTree?T);
AvlTree?Delete(ElemType?x,?AvlTree?T);
ElemType?Retrieve(Position?P);

//----------AVL樹基本操作的算法實現--------------------
遞歸算法：?
Position?FindMin(AvlTree?T)
{
????if(T==NULL)
????????return?NULL;
????else?if(T->lchild?==?NULL)
????????return?T;
????else
????????return?FindMin(T->lchild);
}

Position?FindMax(AvlTree?T)
{
????if(T==NULL)
????????return?NULL;
????else?if(T->rchild?==?NULL)
????????return?T;
????else
????????return?FindMax(T->rchild);
}
非遞歸算法：
Position?FindMin(AvlTree?T)
{
????if(T!=NULL)
????{
????????while(T->lchild?!=?NULL)
????????????T?=?T->lchild;
????}
????
????return?T;
}

Position?FindMax(AvlTree?T)
{
????if(T!=NULL)
????{
????????while(T->rchild?!=?NULL)
????????????T?=?T->rchild;
????}
????
????return?T;
}
//返回P點的高度?
static?int?Height(Position?P)
{
????if(P==NULL)
????????return?-1;
????else
????????return?P->height;
}
//在對一棵AVL樹進行插入操作后，可能會破壞它的平衡條件，因此必須對新的AVL樹進行調整，
這里用到了“單旋轉”或“雙旋轉”的算法，分別適用于：
單左旋轉（SingleRotateWithLeft）；對結點p的左孩子的左子樹進行一次插入?
單右旋轉（SingleRotateWithRight）；對結點p的右孩子的右子樹進行一次插入??
雙左旋轉（DoubleRotateWithLeft）；對結點p的左孩子的右子樹進行一次插入?
雙右旋轉（DoubleRotateWithRight）；對結點p的右孩子的左子樹進行一次插入??
static?Position?SingleRotateWithLeft(Position?K2)
{
????Position?K1;
????
????K1?=?K2->lchild;??//在K2和K1之間進行一次單左旋轉?
????K2->lchild?=?K1->rchild;
????K1->rchild?=?K2;
????
????K2->height?=?Max(Height(K2->lchild),?Height(K2->rchild))?+?1;
????K1->height?=?Max(Height(K1->lchild),?Height(K1->rchild))?+?1;
????
????return?K1;
}

static?Position?SingleRotateWithRight(Position?K2)
{
????Position?K1;
????
????K1?=?K2->rchild;????//在K2和K1之間進行一次單右旋轉?
????K2->rchild?=?K1->lchild;
????K1->lchild?=?K2;
????
????K2->height?=?Max(Height(K2->lchild),?Height(K2->rchild))?+?1;
????K1->height?=?Max(Height(K1->lchild),?Height(K1->rchild))?+?1;
????
????return?K1;
}

static?Position?DoubleRotateWithLeft(Position?K3)
{
????K3->lchild?=?SingleRotateWithRight(K3->lchild);?//在K2和K1之間進行一次單右旋轉?
????
????return?SingleRotateWithLeft(K3);?//在K3和K2之間進行一次單左旋轉?
}

static?Position?DoubleRotateWithRight(Position?K3)
{
????K3->rchild?=?SingleRotateWithLeft(K3->rchild);?//在K2和K1之間進行一次單左旋轉?
????
????return?SingleRotateWithRight(K3);//在K3和K2之間進行一次單右旋轉?
}

//向AVL樹插入結點的操作?
AvlTree?Insert(float?x,?AvlTree?T)
{
????if(T?==?NULL)
????{
????????T?=?(Position)malloc(sizeof(struct?avlnode));
????????if(T?==?NULL)
????????{
????????????puts("wrong");?
????????????exit(1);
????????}
????????T->data?=?x;??
????????T->height?=?0;
????????T->lchild?=?T->rchild?=?NULL;
????}
????else?if(T->data?==?x)//不做任何插入操作?
????????;
????else?if(T->data?>?x)//把s所指結點插入到左子樹中
????{
??????????T->lchild?=?Insert(x,?T->lchild);
??????????if(Height(T->lchild)?-?Height(T->rchild)?==?2)?//若平衡被破壞
??????????{
????????????if(x?<?T->lchild->data)?????//若x比T的左孩子小，對T單左旋轉??
????????????????T?=?SingleRotateWithLeft(T);
????????????else?????????????????????????//否則，對T雙左旋轉???
????????????????T?=?DoubleRotateWithLeft(T);
????????}
????}
????else??????//把s所指結點插入到右子樹中
????{
??????????T->rchild?=?Insert(x,?T->rchild);
??????????if(Height(T->rchild)?-?Height(T->lchild)?==?2)
??????????{
????????????if(x?>?T->rchild->data)????//若x比T的右孩子大，對T單右旋轉??
????????????????T?=?SingleRotateWithRight(T);
????????????else????????????????????????//否則，對T雙右旋轉???
????????????????T?=?DoubleRotateWithRight(T);
????????}
????}
????T->height?=?Max(Height(T->lchild),?Height(T->rchild))?+?1;
????
????return?T;???
}
int?Max(int?a,?int?b)
{
????if(a?>?b)
????????return?a;
????else
????????return?b;
}
還有一種AVL樹，它的結構中不包含高度特征，但包含一個平衡因子bf，用來判斷結點的平衡性，若左孩子比右孩子高，則bf==1；否則，bf==-1；若左右相等則bf==0。
????AVL樹的結點聲明；
enum??BALANCE{LH?=?1,?EH?=?0,?RH?=?-1};
typedef?struct?avlnode
{
????BALANCE?bf;//比普通二杈有序樹多了一個平衡因子信息
????ElemType?data;
????struct?avlnode?*lchild,?*rchild;
}?*AvlTree,?*Position;
//----------AVL樹基本操作------------?------------------------------
AvlTree?MakeEmpty(AvlTree?T);
Position?Find(ElemType?x,?AvlTree?T);
Position?FindMin(AvlTree?T);
Position?FindMax(AvlTree?T);
AvlTree?Insert(ElemType?x,?AvlTree?T);
AvlTree?Delete(ElemType?x,?AvlTree?T);
ElemType?Retrieve(Position?P);

//----------AVL樹基本操作的算法實現--------------------

//在對一棵AVL樹進行插入操作后，可能會破壞它的平衡條件，因此必須對新的AVL樹進行調整，
這里用到了“單旋轉”或“雙旋轉”的算法，分別適用于：
單左旋轉（SingleRotateWithLeft）；對結點p的左孩子的左子樹進行一次插入
單右旋轉（SingleRotateWithRight）；對結點p的右孩子的右子樹進行一次插入
雙左旋轉（DoubleRotateWithLeft）；對結點p的左孩子的右子樹進行一次插入
雙右旋轉（DoubleRotateWithRight）；對結點p的右孩子的左子樹進行一次插入
Position?SingleRotateWithLeft(Position?K2)
{
????Position?K1;

????K1?=?K2->lchild;??//在K2和K1之間進行一次單左旋轉
????K2->lchild?=?K1->rchild;
????K1->rchild?=?K2;

????return?K1;
}

Position?SingleRotateWithRight(Position?K2)
{
????Position?K1;

????K1?=?K2->rchild;????//在K2和K1之間進行一次單右旋轉
????K2->rchild?=?K1->lchild;
????K1->lchild?=?K2;

????return?K1;
}

Position?DoubleRotateWithLeft(Position?K3)
{
????K3->lchild?=?SingleRotateWithRight(K3->lchild);?//在K2和K1之間進行一次單右旋轉

????return?SingleRotateWithLeft(K3);?//在K3和K2之間進行一次單左旋轉
}

Position?DoubleRotateWithRight(Position?K3)
{
????K3->rchild?=?SingleRotateWithLeft(K3->rchild);?//在K2和K1之間進行一次單左旋轉

????return?SingleRotateWithRight(K3);//在K3和K2之間進行一次單右旋轉
}

AvlTree?LeftBalance(AvlTree?T)?//左平衡處理
{
??????AvlTree?lT?=?T->lchild;
??????switch?(lT->bf)?//檢查左樹的平衡度，并做相應處理
??????{
????????????case?LH?:???T?=?SingleRotateWithLeft(T);?//若新結點插入在T的左孩子的左子樹上，對T單左旋轉
????????????????????????T->bf?=?lT->bf?=?EH;???//重新設置平衡度
????????????????????????break;
????????????case?RH?:???AvlTree?rT?=?lT->rchild;//若新結點插入在T的左孩子的右子樹上，對T雙左旋轉，并重新設置平衡度
????????????????????????switch?(rT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?RH;
??????????????????????????????????????????lT->bf?=?EH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?lT->bf?=?EH;?//我感覺這種情況應該不會出現
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?EH;
??????????????????????????????????????????lT->bf?=?LH;
??????????????????????????????????????????break
????????????????????????}
????????????????????????rT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithLeft(T);
????????????????????????break;
??????}
??????return?T;
}

AvlTree?RightBalance(AvlTree?T)?//右平衡處理
{
??????AvlTree?rT?=?T->rchild;
??????switch?(rT->bf)?//檢查右樹的平衡度，并做相應處理
??????{
????????????case?LH?:???T?=?SingleRotateWithRight(T);?//若新結點插入在T的右孩子的右子樹上，對T單右旋轉
????????????????????????T->bf?=?rT->bf?=?EH;???//重新設置平衡度
????????????????????????break;
????????????case?RH?:???AvlTree?lT?=?rT->lchild;//若新結點插入在T的右孩子的左子樹上，對T雙右旋轉，并重新設置平衡度
????????????????????????switch?(lT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?EH;
??????????????????????????????????????????rT->bf?=?RH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?rT->bf?=?EH;?//我感覺這種情況應該不會出現
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?LH;
??????????????????????????????????????????rT->bf?=?EH;
??????????????????????????????????????????break
????????????????????????}
????????????????????????lT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithRight(T);
????????????????????????break;
??????}
??????return?T;
}

//向AVL樹插入結點的操作
AvlTree?Insert(ElemType?x,?AvlTree?T,?bool?&?taller)
{
????if(T?==?NULL)
????{
????????T?=?(Position)malloc(sizeof(struct?avlnode));
????????if(T?==?NULL)
????????{
????????????puts("wrong");
????????????exit(1);
????????}
????????T->data?=?x;
????????T->lchild?=?T->rchild?=?NULL;
????????T->bf?=?EH;
????????taller?=?true;?//插入新結點，樹“長高”，置taller為真值
????}
????else?if(T->data?==?x)//不做任何插入操作
????????taller?=?false;?//樹未長高，置taller為假值
????else?if(T->data?>?x)//把x插入到左子樹中
????{
??????????T->lchild?=?Insert(x,?T->lchild,?taller);
??????????if?(taller)//已經插入左子樹，且樹“長高”，需要檢查平衡度，并做相應處理
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T?=?LeftBalance(T);//原本左樹高于右樹，需做左平衡處理，樹高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?LH;//原本左右等高，現在左高于右，且樹“長高”
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T->bf?=?EH;?//原本右樹高于左樹，現在左右等高，樹高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}
????else??????//把x插入到右子樹中，仿照處理左樹的方法處理
????{
????????????T->rchild?=?Insert(x,?T->rchild,?taller);
??????????if?(taller)
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T->bf?=?EH;
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?RH;
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T?=?RightBalance(T);
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}

????return?T;
}
AVL樹應用示例:
?/*輸入一組數,存儲到AVL樹中,并進行輸出*/
#include?<iostream>
using?namespace?std;

#define?MAX?100
enum??BALANCE{LH?=?1,?EH?=?0,?RH?=?-1};
typedef?struct?avlnode
{
????BALANCE?bf;//比普通二杈有序樹多了一個平衡因子信息
????int?data;
????struct?avlnode?*lchild,?*rchild;
}?*AvlTree,?*Position;

int?Input(int?a[]);//輸入數據到數組,未排序
void?Print(const?int?a[],?int?len);?//輸入未排序的原始數據
AvlTree?Sort(AvlTree?A,?const?int?a[],?int?len);?//對數據進行排序
AvlTree?Insert(int?x,?AvlTree?T,?bool?&?taller);?//把數據存儲到AVL樹中
Position?SingleRotateWithLeft(Position?K2);?//單左旋轉
Position?SingleRotateWithRight(Position?K2);?//單右旋轉
Position?DoubleRotateWithLeft(Position?K3);//雙左旋轉
Position?DoubleRotateWithRight(Position?K3);//雙右旋轉
AvlTree?LeftBalance(AvlTree?T);//?左平衡處理
AvlTree?RightBalance(AvlTree?T);?//右平衡處理
void?inorder(const?AvlTree?bt);?//中序遍歷AVL樹
void?PrintBT(AvlTree?bt);?//輸出二杈樹

int?main(void)
{
????int?a[MAX]={0};
????int?len;
????AvlTree?A=NULL;

????len?=?Input(a);
????Print(a,?len);
????printf("\n");
????A?=?Sort(A,?a,?len);
????PrintBT(A);
????printf("\n");
????inorder(A);
????system("pause");
??????return?0;
}
int?Input(int?a[])
{
????int?i=0;

????do{
????????a[i++]?=?rand()%1000;//輸入隨機數
????}?while(i<MAX);
????return?i;
}
void?Print(const?int?a[],?int?len)
{
????int?i;

????for(i=0;?i<len;?i++)
????????printf("%d\t",?a[i]);
}
AvlTree?Sort(AvlTree?A,?const?int?a[],?int?len)
{
????int?i;
????bool?taller?=?false;

????for(i=0;?i<len;?i++)
?????????A?=?Insert(a[i],?A,?taller);
????return?A;
}
void?inorder(const?AvlTree?bt)
{
????AvlTree?p=bt,?stack[MAX];//p表示當前結點，棧stack[]用來存儲結點
????int?top=-1;

????do
????{
????????while(p?!=?NULL)//先處理結點的左孩子結點，把所有左孩子依次入棧
????????{
????????????stack[++top]?=?p;
????????????p?=?p->lchild;
????????}
????????if(top?>=?0)?//所有左孩子處理完畢后
????????{
????????????p?=?stack[top--];//棧頂元素出棧
????????????printf("%d\t",?p->data);?//輸出該結點
????????????p?=?p->rchild;?//處理其右孩子結點
????????}
????}?while((p?!=?NULL)||(top?>=?0));
}

//向AVL樹插入結點的操作
AvlTree?Insert(int?x,?AvlTree?T,?bool?&?taller)
{
????if(T?==?NULL)
????{
????????T?=?(Position)malloc(sizeof(struct?avlnode));
????????if(T?==?NULL)
????????{
????????????puts("wrong");
????????????exit(1);
????????}
????????T->data?=?x;
????????T->lchild?=?T->rchild?=?NULL;
????????T->bf?=?EH;
????????taller?=?true;?//插入新結點，樹“長高”，置taller為真值
????}
????else?if(T->data?==?x)//不做任何插入操作
????????taller?=?false;?//樹未長高，置taller為假值
????else?if(T->data?>?x)//把x插入到左子樹中
????{
??????????T->lchild?=?Insert(x,?T->lchild,?taller);
??????????if?(taller)//已經插入左子樹，且樹“長高”，需要檢查平衡度，并做相應處理
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T?=?LeftBalance(T);//原本左樹高于右樹，需做左平衡處理，樹高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?LH;//原本左右等高，現在左高于右，且樹“長高”
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T->bf?=?EH;?//原本右樹高于左樹，現在左右等高，樹高不變
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}
????else??????//把x插入到右子樹中，仿照處理左樹的方法處理
????{
????????????T->rchild?=?Insert(x,?T->rchild,?taller);
??????????if?(taller)
??????????{
??????????????????switch(T->bf)
??????????????????{
????????????????????????case?LH?:???T->bf?=?EH;
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
????????????????????????case?EH?:???T->bf?=?RH;
????????????????????????????????????taller?=?true;
????????????????????????????????????break;
????????????????????????case?RH?:???T?=?RightBalance(T);
????????????????????????????????????taller?=?false;
????????????????????????????????????break;
??????????????????}
????????????}
????}

????return?T;
}

Position?SingleRotateWithLeft(Position?K2)
{
????Position?K1;

????K1?=?K2->lchild;??//在K2和K1之間進行一次單左旋轉
????K2->lchild?=?K1->rchild;
????K1->rchild?=?K2;

????return?K1;
}

Position?SingleRotateWithRight(Position?K2)
{
????Position?K1;

????K1?=?K2->rchild;????//在K2和K1之間進行一次單右旋轉
????K2->rchild?=?K1->lchild;
????K1->lchild?=?K2;

????return?K1;
}

Position?DoubleRotateWithLeft(Position?K3)
{
????K3->lchild?=?SingleRotateWithRight(K3->lchild);?//在K2和K1之間進行一次單右旋轉

????return?SingleRotateWithLeft(K3);?//在K3和K2之間進行一次單左旋轉
}

Position?DoubleRotateWithRight(Position?K3)
{
????K3->rchild?=?SingleRotateWithLeft(K3->rchild);?//在K2和K1之間進行一次單左旋轉

????return?SingleRotateWithRight(K3);//在K3和K2之間進行一次單右旋轉
}

AvlTree?LeftBalance(AvlTree?T)?//左平衡處理
{
??????AvlTree?lT?=?T->lchild;
??????switch?(lT->bf)?//檢查左樹的平衡度，并做相應處理
??????{
????????????case?LH?:???T?=?SingleRotateWithLeft(T);?//若新結點插入在T的左孩子的左子樹上，對T單左旋轉
????????????????????????T->bf?=?lT->bf?=?EH;???//重新設置平衡度
????????????????????????break;
????????????case?RH?:???AvlTree?rT?=?lT->rchild;//若新結點插入在T的左孩子的右子樹上，對T雙左旋轉，并重新設置平衡度
????????????????????????switch?(rT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?RH;
??????????????????????????????????????????lT->bf?=?EH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?lT->bf?=?EH;?//我感覺這種情況應該不會出現
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?EH;
??????????????????????????????????????????lT->bf?=?LH;
??????????????????????????????????????????break;
????????????????????????}
????????????????????????rT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithLeft(T);
????????????????????????break;
??????}
??????return?T;
}

AvlTree?RightBalance(AvlTree?T)?//右平衡處理
{
??????AvlTree?rT?=?T->rchild;
??????switch?(rT->bf)?//檢查右樹的平衡度，并做相應處理
??????{
????????????case?RH?:???T?=?SingleRotateWithRight(T);?//若新結點插入在T的右孩子的右子樹上，對T單右旋轉
????????????????????????T->bf?=?rT->bf?=?EH;???//重新設置平衡度
????????????????????????break;
????????????case?LH?:???AvlTree?lT?=?rT->lchild;//若新結點插入在T的右孩子的左子樹上，對T雙右旋轉，并重新設置平衡度
????????????????????????switch?(lT->bf)
????????????????????????{
??????????????????????????????case?LH?:???T->bf?=?EH;
??????????????????????????????????????????rT->bf?=?RH;
??????????????????????????????????????????break;
??????????????????????????????case?EH?:???T->bf?=?rT->bf?=?EH;?//我感覺這種情況應該不會出現
??????????????????????????????????????????break;
??????????????????????????????case?RH?:???T->bf?=?LH;
??????????????????????????????????????????rT->bf?=?EH;
??????????????????????????????????????????break;
????????????????????????}
????????????????????????lT->bf?=?EH;
????????????????????????T?=?DoubleRotateWithRight(T);
????????????????????????break;
??????}
??????return?T;
}

void?PrintBT(AvlTree?bt)
{
????if(bt?!=?NULL)
????{
????????printf("%d",?bt->data);
????????if(bt->lchild!=NULL?||?bt->rchild!=NULL)
????????{
????????????printf("(");
????????????PrintBT(bt->lchild);
????????????if(bt->rchild!=NULL)
????????????????printf(",");
????????????PrintBT(bt->rchild);
????????????printf(")");
????????}
????}
}

對于一般的二叉樹來說，刪去樹中的一個結點是沒有意義的，因為它將使以被刪除的結點為根的子樹變成森林，破壞了整棵樹的結構
但是，對于二叉排序樹，刪去樹上的一個結點相當于刪去有序序列中的一個記錄，只要在刪除某個結點后不改變二叉排序樹的特性即可。
??????在二叉排序樹上刪除一個結點的算法如下：
btree?*?DeleteBST(btree?*b,?ElemType?x)
{
??????if?(b)
??????{
????????????if?(b->data?==?x)
??????????????????b?=?DelNode(b);
????????????else?if?(b->data?>?x)
??????????????????b->lchild?=?DeleteBST(b->lchild,?x);
????????????else
??????????????????b->rchild?=?DeleteBST(b->rchild,?x);
??????}
??????return?b;
}
其中刪除過程有兩種方法。
第一種過程如下：
1。若p有左子樹，找到其左子樹的最右邊的葉子結點r，用該葉子結點r來替代p，把r的左孩子
作為r的父親的右孩子。
2。若p沒有左子樹，直接用p的右孩子取代它。

第二種過程如下：
1。若p有左子樹，用p的左孩子取代它；找到其左子樹的最右邊的葉子結點r，把p的右子樹作為r
的右子樹。
2。若p沒有左子樹，直接用p的右孩子取代它。
????兩種方法各有優劣，第一種操作簡單一點點，但均衡性不如第二種，因為它將結點p的右子樹
全部移到左邊來了。下面將分別以兩種種思路編寫代碼。


第一種：
btree?*?DelNode(btree?*p)
{
??????if?(p->lchild)
??????{
????????????btree?*r?=?p->lchild;???//r指向其左子樹;
????????while(r->rchild?!=?NULL)//搜索左子樹的最右邊的葉子結點r
????????{
????????????r?=?r->rchild;
????????}
????????????r->rchild?=?p->rchild;

????????????btree?*q?=?p->lchild;???//q指向其左子樹;
????????????free(p);
????????????return?q;
??????}
??????else
??????{
????????????btree?*q?=?p->rchild;???//q指向其右子樹;
????????????free(p);
????????????return?q;
??????}
}

第二種：
btree?*?DelNode(btree?*p)
{
??????if?(p->lchild)
??????{
????????????btree?*r?=?p->lchild;???//r指向其左子樹;
????????????btree?*prer?=?p->lchild;???//prer指向其左子樹;
????????while(r->rchild?!=?NULL)//搜索左子樹的最右邊的葉子結點r
????????{
??????????????????prer?=?r;
????????????r?=?r->rchild;
????????}

????????if(prer?!=?r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
????????{
??????????????????prer->rchild?=?r->lchild;
??????????????????r->lchild?=?p->lchild;?//被刪結點p的左子樹作為r的左子樹
????????????}
????????r->rchild?=?p->rchild;?//被刪結點p的右子樹作為r的右子樹

????????????free(p);
????????????return?r;
??????}
??????else
??????{
????????????btree?*q?=?p->rchild;???//q指向其右子樹;
????????????free(p);
????????????return?q;
??????}
}
????但是上面這種方法，把r移來移去，很容易出錯，其實在這里我們刪除的只是p的元素值，而不是它的地址，所以完全沒有必要移動指針。仔細觀察，發現我們刪除的地址實際上是p的左子樹的最右邊的葉子結點r的地址，所以我們只要把r的數據填到p中，然后把r刪除即可。
算法如下：
btree?*?DelNode(btree?*p)
{
??????if?(p->lchild)
??????{
????????????btree?*r?=?p->lchild;???//r指向其左子樹;
????????????btree?*prer?=?p->lchild;???//prer指向其左子樹;
????????while(r->rchild?!=?NULL)//搜索左子樹的最右邊的葉子結點r
????????{
??????????????????prer?=?r;
????????????r?=?r->rchild;
????????}
????????????p->data?=?r->data;

????????if(prer?!=?r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
??????????????????prer->rchild?=?r->lchild;
????????????else
????????????p->lchild?=?r->lchild;?//否則結點p的左子樹指向r的左子樹

????????????free(r);
????????????return?p;
??????}
??????else
??????{
????????????btree?*q?=?p->rchild;???//q指向其右子樹;
????????????free(p);
????????????return?q;
??????}
}

二、任給 1<=n<=20 個不同的非零正整數，每個正整數最多使用1次，請問這n個正整數能夠加和的結果共有多少種(不考慮和超出long的最大值的可以),
程序中請實現如下函數。用于計算數組data,中ncount的加和的數量。
long getsumcount(long data[], long count);
程序中可以出現別的輔助函數。或輔助結構等。

例如，
data[] = {1,2,3,4};
ncount = 4;
函數返回 10

分解如下。（0不算）

1??= 1
2??= 2
3??= 3 = 1+2
4??= 4 = 1+3

5??= 2+3 = 1+4
6??= 2+4 = 1+2+3
7??= 3+4 = 1+2+4
8??= 1+3+4
9??= 2+3+4
10 = 1+2+3+4
如上。所以結果是10種可能。
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>
#define libsize (1<<16)
#define hashsize (1<<16)
#define hashmask (0xffff)

using namespace std;

typedef struct node{
??? long data;
??? struct node *next;
}NODE;
NODE hashtab[hashsize];

const long MAX = 20;

bool IsNew(long array[], long len, long data);
void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num);
long _getsumcount(const long data[], long count);
long Sum(const long a[], int len);
long getsumcount(const long data[], long count);

int main(void)
{
????? time_t startTime;
?time_t endTime;
?time(&startTime);
????? long data[MAX]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

????? for (long i=0; i<MAX; i++) //給數組賦值為1-100的隨機數
????? {
??????????? long temp = rand()%100 + 1;
??????????? if (IsNew(data, i, temp))
????????????????? data[i] = temp;
????? }

????? for (long i=0; i<MAX; i++)
??????????? cout << data[i] << ' ';
????? cout << endl;

????? int sum = 0;
????? for (long i=1; i<=MAX; i++)
????? {
??????????? long s1 = getsumcount(data, i);
??????????? long s2 = _getsumcount(data, i);
???????????
??????????? cout << i << ": s1=" << s1 <<"? s2=" << s2 << endl;
??????????? if (s1 == s2)
????????????????? sum++;
????? }
????? cout << sum << endl;

????? time(&endTime);
?cout << "time:" << difftime(endTime, startTime) << endl;

?getchar();
?return 0;
}
//////////////////////////////////////////////////////////////////////////
/*
? Author: goal00001111
*/
bool IsNew(long array[], long len, long data)
{
????? for(int i=0; i<=len; i++)
??????????? if (array[i] == data)
????????????????? return false;
????? return true;
}

long _getsumcount(const long data[], long count)
{
????? bool lib[libsize];
????? for (long i=0; i<libsize; i++)
??????????? lib[i] = false;
????? long *a = new long[count];

????? for (int k=0; k<count; k++)
??????????? solve(data, lib, a, count, 0, k, 0);

????? delete []a;
????? long sum = 1;
????? for (long i=0; i<libsize; i++)
????? {
??????????? if (lib[i])
??????????? {
????????????????? sum++;
??????????????? // cout << i << ' ';
??????????? }
????? }
????? return sum;
}

void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num)
{
????? if (num == max)
????? {
??????????? for (int i=pos; i<len; i++)
??????????? {
????????????????? a[num] = data[i];
????????????????? lib[Sum(a, num)] = true;
??????????? }
????? }
????? else? //如果不是最后一個數字
????? {
??????????? for (int i=pos; i<len; i++)
??????????? {
????????????????? a[num] = data[i];
???solve(data, lib, a, len, i+1, max, num+1);?//分析下一個數
??????????? }
????? }
}

long Sum(const long a[], int len)
{
????? long sum = 0;
????? for (int i=0; i<=len; i++)
??????????? sum += a[i];
????? return sum;
}
///////////////////////////////////////////////////////////////////////
/*
? Author: eastcowboy
*/

/*尋找并插入，找到而未插入返回0，未找到而插入返回1*/
static int hashinsert(long sum)
{
??? NODE *p,*q;
??? p = hashtab+ (sum & hashmask);
??? while( p && (p->data!=sum) )
??? {?? q = p;
??????? p = p->next;
??? }
??? if( p )
??????? return 0;
??? q->next = p = (NODE*)malloc(sizeof(NODE));
??? p ->next = NULL;
??? p ->data = sum;
??? return 1;
}
/*刪除hash表的第index條目*/
static void hashdelete(long index)
{?? NODE *p,*q;
??? p = hashtab[index].next;
??? while(p)
??? {?? q = p;
??????? p = p->next;
??????? free(q);
??? }
}
/*這才是正主^^*/
long getsumcount(const long data[],long count)
{
??? long i;
??? int state[MAX] = {0};
??? long sum = 0,sp = 0;
??? int ret = 1; /*由于0已經先放入表中，所以首先就有一個*/

??? /*hash表初始化*/
??? for(i=0;i<hashsize;++i)
??? {?? hashtab[i].data = 0;
??????? hashtab[i].next = NULL;
??? }
??? /*回溯求解*/
??? while(sp>=0)
??? {?? if(sp==count)
??????? {?? ret += hashinsert(sum);
??????????? --sp;
??????? }
??????? switch( state[sp] )
??????? {?? case 0:
??????????????? state[sp] = 1;
??????????????? sum += data[sp];
??????????????? ++sp;
??????????????? break;
??????????? case 1:
??????????????? state[sp] = 2;
??????????????? sum -= data[sp];
??????????????? ++sp;
??????????????? break;
??????????? case 2:
??????????????? state[sp] = 0;
??????????????? --sp;
??????????????? break;
??????? }
??? }
??? /*hash表銷毀*/
??? for(i=0;i<hashsize;++i)
??? {?? hashdelete(i);
??? }
??? return ret;
}

/*
? Name:6.剪刀石頭布
? Copyright:
? Author:
? Date: 28-05-06 08:51
? Description:
N個小孩正在和你玩一種剪刀石頭布游戲（剪刀贏布，布贏石頭，石頭贏剪刀）。N個小孩中有一個是裁判，其余小孩分成三組（不排除某些組沒有任何成員的可能性），但是你不知道誰是裁判，也不知道小孩們的分組情況。然后，小孩們開始玩剪刀石頭布游戲，一共玩M次，每次任意選擇兩個小孩進行一輪，你會被告知結果，即兩個小孩的勝負情況，然而你不會得知小孩具體出的是剪刀、石頭還是布。已知各組的小孩分別只會出一種手勢（因而同一組的兩個小孩總會是和局），而裁判則每次都會隨便選擇出一種手勢，因此沒有人會知道裁判到底會出什么。請你在M次剪刀石頭布游戲結束后，猜猜誰是裁判。如果你能猜出誰是裁判，請說明最早在第幾次游戲結束后你就能夠確定誰是裁判。

輸入要求：
輸入文件包含多組測試數據，每組測試數據第一行為兩個整數N和M(1<=N<=500，0<M<=2000)，分別為小孩的個數和剪刀石頭布游戲進行的次數。接下來M行，每行兩個整數且中間以一個符號隔開。兩個整數分別為進行游戲的兩個小孩各自的編號（為小于N的非負整數）。符號的可能值為“=”、“>”和“<”，分別表示和局、第一個小孩勝和第二個小孩勝三種情況。例：
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0

?

輸出要求：
1．每組測試數據輸出一行，若能猜出誰是裁判，則輸出裁判的編號，并輸出在第幾次游戲結束后就能夠確定誰是裁判，小孩的編號和游戲次數以一個空格隔開；
2．如果無法確定誰是裁判，輸出-2；如果發現剪刀石頭布游戲的勝負情況不合理（即無論誰是裁判都會出現矛盾），則輸出-1。例：
-2
1 4
-1
0 0

?

評分規則：
1．程序將運行在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運行不能超過10秒，否則該用例不得分；
2．要求程序能按照輸入樣例的格式讀取數據文件，按照輸出樣例的格式將運行結果輸出到標準輸出上。如果不能正確讀入數據和輸出數據，該題將不得分；
3．該題目共有5個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比例分別為5%、10%、15%、30%和40%；
4．該題目20分。
*/

/*
算法介紹：
1。如果只有1個人，參加比賽，那么他就是裁判，即輸出：0 0 。
2。建立數組 players[MAX][MAX] 記錄比賽結果（數組賦初值0），若選手a輸給b，則players[a][b]=1，players[b][a]=3；若打平，則players[a][b]=players[b][a]=2；
注意：在記錄成績之前，先判斷選手a，b 是否已經比賽過，如果已經比賽過，則判斷先前的比賽結果是否與當前結果相同，若不相同，在數組judger[]中做標記（數組賦初值0），若judger[a]=0，使judger[a]=1，表示a有可能為裁判；若judger[a]=1，則使judger[a]=2，表示a肯定為裁判，因為他和兩個人出現不同結果。
同理處理b。
3。遍歷數組judger[]，用temp1記錄judger[i]=1出現的次數，用temp2記錄judger[i]=2出現的次數，如果2個或以下的人可能為裁判，且沒有人肯定為裁判，即if (temp1 <= 2 && temp2 == 0)，則無法確定誰是裁判；
如果2個或以下的人可能為裁判，且有1人肯定為裁判，即if (temp1 <= 2 && temp2 == 1)，則確定裁判i；
如果2個以上的人可能為裁判，即if (temp1 > 2)，則勝負情況不合理。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 500;
void Readata(const char *filename);

int main()
{
?time_t startTime;
?time_t endTime;
?time(&startTime);

?Readata("in.txt");

?time(&endTime);
?cout << difftime(endTime, startTime) << endl;

?getchar();
?return 0;
}

void Readata(const char *filename)
{
????? fstream in(filename);
????? if (!in)
??????????? return ;?? //結束程序執行

????? while (!in.eof())
????? {
??????????? int N, M;
??????????? in >> N;
??????????? in >> M;
???????????
??????????? if (N == 1) //如果只有1個人，參加比賽，那么他就是裁判
????????????????? cout << 0 << ' ' << 0 << endl;
?????????????????
??????????? int players[MAX][MAX] = {0};//記錄比賽結果
??????????? int *judger = new int[N];//記錄是否可能為裁判，0表示不可能，1表示可能，2表示確定
??????????? for (int i=0; i<N; i++)
????????????????? judger[i] = 0;
?????????????????
??????????? int n = 0;//累計比賽場數
??????????? int min = n;//存儲能夠確定誰是裁判的最少場數
??????????? while (!in.eof() && n < M)//讀入比賽結果信息
??????????? {
????????????????? char data[3]; //存儲比賽選手編號和結果

????????????????? in >> data[0];
????????????????? in >> data[1];
????????????????? in >> data[2];
???????????????? // cout << data[0] << ' ' << data[1] << ' ' << data[2] << endl;
????????????????? n++;
????????????????? int flag = (data[1]=='<')? 1 :((data[1]=='=')? 2 : 3);//分別用1，2，3表示負，平，勝
?????????????????
????????????????? if (players[data[0]-'0'][data[2]-'0'] == 0)//若a,b未對局過，存儲比賽結果
????????????????? {
??????????????????????? players[data[0]-'0'][data[2]-'0'] = flag;
??????????????????????? players[data[2]-'0'][data[0]-'0'] = 4 - flag;
????????????????? }
????????????????? else if (players[data[0]-'0'][data[2]-'0'] != flag)//若a,b已對局過，且比賽結果不同
????????????????? {
??????????????????????? if (judger[data[0]-'0'] == 0) //a有可能為裁判
????????????????????????????? judger[data[0]-'0'] = 1;
??????????????????????? else if (judger[data[0]-'0'] == 1)//a就是裁判
??????????????????????? {
????????????????????????????? judger[data[0]-'0'] = 2;
????????????????????????????? min = n;
??????????????????????? }
???????????????????????
??????????????????????? if (judger[data[2]-'0'] == 0) //b有可能為裁判
????????????????????????????? judger[data[2]-'0'] = 1;
??????????????????????? else if (judger[data[2]-'0'] == 1) //a就b是裁判
??????????????????????? {
????????????????????????????? judger[data[2]-'0'] = 2;
????????????????????????????? min = n;
??????????????????????? }
????????????????? }
???????????????? // cout << "players["<<data[0]-'0'<<"]["<<data[2]-'0'<<"]="<<players[data[0]-'0'][data[2]-'0']<<endl;
??????????? }
??????????? int temp1 = 0; //記錄judger[i]=1出現的次數
??????????? int temp2 = 0; //記錄judger[i]=2出現的次數
??????????? int answer;
??????????? for (int i=0; i<N; i++)
??????????? {
????????????????? //cout << judger[i] << ' ';
????????????????? if (judger[i] == 1)
?????????????????????? temp1++;

????????????????? if (judger[i] == 2)
????????????????? {
?????????????????????? temp2++;
?????????????????????? answer = i;
????????????????? }
??????????? }
??????????? cout << endl;
??????????? if (temp1 <= 2 && temp2 == 0)
????????????????? cout << -2 << endl;
??????????? else? if (temp1 <= 2 && temp2 == 1)
????????????????? cout << answer << ' ' << min << endl;
??????????? else? if (temp1 > 2)
????????????????? cout << -1 << endl;
?????????????????
??????????? delete []judger;
????? }

??? in.close(); //關閉文件
}

?

/*
? Name:
? Copyright:
? Author:
? Date: 28-05-06 15:26
? Description: 5.座位調整
百度辦公區里到處擺放著各種各樣的零食。百度人力資源部的調研發現，員工如果可以在自己喜歡的美食旁邊工作，效率會大大提高。因此，百度決定進行一次員工座位的大調整。

調整的方法如下：
1．首先將辦公區按照各種零食的擺放分成N個不同的區域（例如：可樂區，餅干區，牛奶區等等）；
2．每個員工對不同的零食區域有不同的喜好程度（喜好程度是1~100的整數， 喜好程度越大表示該員工越希望被調整到相應的零食區域）；
3．由于每個零食區域可以容納的員工數量有限，人力資源部希望找到一個最優的調整方案使得總的喜好程度最大。

輸入要求：
文件第一行包含兩個整數N，M(N>=1，M<=300)。分別表示N個區域和M個員工；
第二行是N個整數構成的數列a，其中a[i]表示第i個區域可以容納的員工數(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)；
緊接著是一個M*N的矩陣P，P(i,j)表示第i個員工對第j個區域的喜好程度。例：
3 3
1 1 1
100 50 25
100 50 25
100 50 25

輸出要求：
對于每個測試數據，輸出可以達到的最大的喜好程度。例：
175

?

數據解釋：
此數據只存在一種安排方法，三個員工分別安置在三個區域。最終的喜好程度為100+50+25=175

評分規則：
1．程序將運行在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運行不能超過10秒，否則該用例不得分；
2．要求程序能按照輸入樣例的格式讀取數據文件，按照輸出樣例的格式將運行結果輸出到標準輸出上。如果不能正確讀入數據和輸出數據，該題將不得分；
3．該題目共有4個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比例分別為25%，25%，25%，25%；
4．該題目20分。

*/
/*
算法介紹：
1。讀入數據N，M，a[]和p[][]。
2。以員工為主序，采用回溯的方法依次處理每一個員工在每個位置的喜好程度，返回總的最大的喜好程度。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 301;
void Readata(const char *filename, int a[], int p[][MAX], int & N, int & M);
int GetPlace(int N, int maxMen, int man, const int p[][MAX], int a[]);

int main()
{
?time_t startTime;
?time_t endTime;
?time(&startTime);

????? int N, M;
????? int a[MAX] = {0};
????? int p[MAX][MAX] = {0};

?Readata("in5.txt", a, p, N, M);//讀入數據

//?cout << M << ' ' << N << endl;
//?for (int i=1; i<=N; i++)
//??????????? cout << a[i] << ' ';
//????? cout << endl;
//????? for (int i=1; i<=M; i++)
//????? {
//??????????? for (int j=1; j<=N; j++)
//????????????????? cout << p[i][j] << ' ';
//??????????? cout << endl;
//????? }

????? int sum = GetPlace(N, M, 1, p, a);//返回總的最大的喜好程度。
????? cout << sum << endl;

?time(&endTime);
?cout << difftime(endTime, startTime) << endl;

?getchar();
?return 0;
}

void Readata(const char *filename, int a[], int p[][MAX], int & N, int & M)
{
????? fstream in(filename);
????? if (!in)
??????????? return ;?? //結束程序執行

????? while (!in.eof())
????? {
??????????? in >> N;
??????????? in >> M;
??????????? for (int i=1; i<=N; i++)
????????????????? in >> a[i];
??????????? for (int i=1; i<=M; i++)
????????????????? for (int j=1; j<=N; j++)
??????????????????????? in >> p[i][j];
????? }

??? in.close(); //關閉文件
}

int GetPlace(int N, int maxMen, int man, const int p[][MAX], int a[])
{
????? int max = 0;
????? int sum = 0;

????? if (man == maxMen)//處理最后一個員工
????? {
??????????? for (int i=1; i<=N; i++)
??????????? {
????????????????? if (a[i] > 0)//如果該位置還可以容納此員工，用sum記錄其在該處的喜好度
??????????????????????? sum = p[man][i];
????????????????? if (sum > max)
??????????????????????? max = sum;//用max記錄該員工可以獲得的最大喜好度
??????????? }
????? }
????? else //如果處理的不是最后一個員工，應采用回溯方法以取得最優解
????? {
??????????? for (int i=1; i<=N; i++)
??????????? {
????????????????? if (a[i] > 0)//如果該位置還可以容納此員工，用sum記錄其在該處的喜好度
????????????????? {
??????????????????????? a[i]--;//該位置可容納員工數減1
??????????????????????? sum = p[man][i] + GetPlace(N, maxMen, man+1, p, a);
??????????????????????? a[i]++;
????????????????? }
????????????????? if (sum > max)
??????????????????????? max = sum;
??????????? }
????? }
????? return max; //返回第man到M個員工總的最大喜好度
}

?

/*3.變態比賽規則
為了促進各部門員工的交流，百度舉辦了一場全公司范圍內的“拳皇”（百度內部最流行的格斗游戲）友誼賽，負責組織這場比賽的是百度的超級“拳皇”迷W.Z。W.Z不想用傳統的淘汰賽或者循環賽的方式，而是自己制定了一個比賽規則。

由于一些員工（比如同部門或者相鄰部門員工）平時接觸的機會比較多，為了促進不同部門之間的交流，
W.Z希望員工自由分組。不同組之間的每兩個人都會進行一場友誼賽而同一組內的人之間不會打任何比賽。

比如4個人，編號為1~4,如果分為兩個組并且1，2一個組，3，4一個組，那么一共需要打四場比賽：
1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如果是1，2，3一組，4單獨一組，那么一共需要打三場比賽:
????? 1 vs 4，2 vs 4，3 vs 4。

很快W.Z意識到，這樣的比賽規則可能會讓比賽的場數非常多。W.Z想知道如果有N個人，
通過上面這種比賽規則，總比賽場數有可能為K場嗎？比如3個人，如果只分到一組則不需要比賽，
如果分到兩組則需要2場比賽，如果分為三組則需要3場比賽。但是無論怎么分都不可能恰需要1場比賽。

相信作為編程高手的你一定知道該怎么回答這個問題了吧？ 那么現在請你幫助W.Z吧。

輸入要求：
每行為一組數據，包含兩個數字 N, K(0<N<=500, K>=0)。例：
2 0
2 1
3 1
3 2

?

輸出要求：
對輸入的N,K 如果N個員工通過一定的分組方式可以使比賽場數恰好為K，則輸出"YES"，否則輸出"NO"
（請全部使用大寫字母），每組數據占一行。例：
YES
YES
NO
YES

*/
/*
算法分析：采用遞歸的方法，原理較簡單，大家看源碼即可。
*/

/*
? Name:
? Copyright:
? Author:
? Date: 27-05-06 15:37
? Description:
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 100;
void Readata(const char *filename);
bool check(long n, long k);

int main()
{
?time_t startTime;
?time_t endTime;
?time(&startTime);

?Readata("in.txt");

?time(&endTime);
?cout << difftime(endTime, startTime) << endl;

?getchar();
?return 0;
}

void Readata(const char *filename)
{
????? fstream in(filename);
????? if (!in)
??????????? return ;?? //結束程序執行

????? while (!in.eof())
????? {
??????????? long data[2];

??????????? in >> data[0];
??????????? in >> data[1];
??????????? //cout << data[0] << ' ' << data[1] << endl;

??????????? if (check(data[0], data[1]))
????????????????? cout << "YES" << endl;
??????????? else
????????????????? cout << "NO" << endl;
????? }

??? in.close(); //關閉文件
}
bool check(long n, long k)
{
??? bool flag = false;
??? int i;
??? if(k == 0) //可能? 。。。1
??????? return true;
??? if(n==0 && k || k<0)? //不可能 。。。2
??????? return false;
??? for(i=1; i<n && !flag; i++) //i表示將被減掉的小組的人數，每少一個由i個人組成的組就會少(n-i) * i場比賽
??????? flag = check(n-i,k - (n-i) * i);? //不斷的減少小組數和對應減少的比賽次數，直到出現1或2的情況 （出現可能的情況也會終止分析）
??? return flag;
}

?/*
? Name:
? Copyright:
? Author:
? Date: 28-05-07 15:26
? Description: 2.飯團的煩惱
“午餐飯團”是百度內部參與人數最多的民間組織。
同一個部門的、同一所大學的、同一年出生的、使用同一種型號電腦的員工們總是以各種理由組織各種長期的、臨時的飯團。

參加飯團，不僅可以以優惠的價格嘗到更加豐富的菜式，還可以在吃飯的時候和同事們增進感情。
但是，隨著百度的員工越來越多，各個飯團的管理變得繁雜起來。特別是為了照顧員工們越來越挑剔的胃，飯團的點菜負責人的壓力也越來越大。現在，這個任務就交給“百度之星”了，因為，你將要為所有的百度飯團設計一個自動點菜的算法。

飯團點菜的需求如下：
1．經濟是我們要考慮的一個因素，既要充分利用百度員工的午餐補助，又不能鋪張浪費。因此，我們希望最后的人均費用越接近12元越好。
2．菜式豐富是我們要考慮的另一個因素。為簡單起見，我們將各種菜肴的屬性歸結為葷菜，素菜，辛辣，清淡，并且每個菜只能點一次。
3．請謹記，百度飯團在各大餐館享受8折優惠。

輸入要求：
1．輸入數據第一行包含三個整數N，M，K(0<N<=16，0<M<=N，0<K<=12)，分別表示菜單上菜的數目，飯團需要點的菜的數目，就餐的人數；
2．緊接著N行，每行的格式如下：
菜名（長度不超過20個字符） 價格（原價，整數） 是否葷菜（1表示是，0表示否） 是否辛辣（1表示是，0表示否）；
3．第N+2行是 a b c d 四個整數，分別表示需要點的葷菜，素菜，辛辣，清淡菜的數目。例：
3 2 2
水煮魚 30 1 1
口水雞 18 1 1
清燉豆腐 12 0 0
1 1 1 1

?

輸出要求：
對于每組測試數據，輸出數據包含M+1行，前M行每行包含一個菜名（按菜名在原菜單的順序排序）。第M+1行是人均消費，結果保留兩位小數。例：
口水雞
清燉豆腐
12.00

評分規則：
1．程序將運行在一臺Linux機器上（內存使用不作嚴格限制），在每一測試用例上運行不能超過10秒，否則該用例不得分；
2．要求程序能按照輸入樣例的格式讀取數據文件，按照輸出樣例的格式將運行結果輸出到標準輸出上。如果不能正確讀入數據和輸出數據，該題將不得分；
3．該題目共有5個測試用例，每個測試用例為一個輸入文件。各測試用例占該題目分數的比例分別為20%，20%，20%，20%，20%；
4．該題目10分。
*/
/*
算法介紹：
1。讀入數據。
2。以菜的個數為主序，采用回溯的方法依次處理每個菜的可能性，返回最好的點菜方法:
????? 即將問題轉化為：從N個不同的數中選出滿足要求的M個數。
????? 解決辦法為先從N個不同的數中選出M個數，再判斷這M個數是否滿足要求，滿足要求則存儲到數組bestdish[]，并根據當前實際最佳金額與理論最佳金額的差值，實時更換數組bestdish[]的值，最后得到的數組bestdish[]就是最佳數組bestdish[]。
3。根據數組bestdish[]，輸出結果。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 21;
double Min = 1000000;//存儲當前實際最佳金額與理論最佳金額的差值
double pay; //存儲當前實際最佳金額
double bestPay; //存儲所需的理論最佳金額，恰好每人12元
int N, M, K;
int hunCai;
int suCai;
int xinLa;
int qingDan;

class Dish{
public:
????? char name[MAX];
????? double price;
????? bool isMeat;
????? bool isAcridity;

????? void PutData(const char *na, double p, bool m, bool acr) //輸入數據
????? {
??????????? strcpy(name, na);
??????????? price = p;
??????????? isMeat = m;
??????????? isAcridity = acr;
????? }

????? void PrintData()
????? {
??????????? cout << name << ' ' << price << ' ' << isMeat << ' ' << isAcridity << endl;
????? }
};

void ReadData(const char *filename, Dish **obj);
double Abs(double a);
bool IsPass(const int pass[], const Dish *obj, double & sum);
void GetDishes(int num, int pos, const Dish *obj, int pass[], int bestDish[]);

int main()
{
?time_t startTime;
?time_t endTime;
?time(&startTime);

????? Dish *obj;

?ReadData("in3.txt", &obj);//讀入數據

?//cout << N << ' ' << M << ' ' << K << endl;
//?for (int i=0; i<N; i++)
//??????????? obj[i].PrintData();
//????? cout << hunCai << ' ' << suCai << ' ' << xinLa << ' ' << qingDan << endl;

????? bestPay = K * 12; //存儲所需的理論最佳金額，恰好每人12元
????? int *pass = new int[N+1]; //存儲已經被點了的菜
????? int *bestDish = new int[N+1]; //存儲最佳被點了的菜

????? GetDishes(1, 0, obj, pass, bestDish); //以菜的個數用回溯的方法求最佳點菜方案
?????
????? for (int i=1; i<=M; i++)
????? {
??????????? cout << obj[bestDish[i]].name << endl;
????? }
????? printf("%.2f\n", pay / K);
?????
????? delete []pass;
????? delete []bestDish;
?????
?time(&endTime);
//?cout << difftime(endTime, startTime) << endl;

?getchar();
?return 0;
}

void GetDishes(int num, int pos, const Dish *obj, int pass[], int bestDish[])
{
????? if (num == M)//處理最后一個菜
????? {
??????????? for (int i=pos; i<N; i++)
??????????? {
????????????????? pass[num] = i;
????????????????? double sum = 0;
????????????????? if (IsPass(pass, obj, sum) && Abs(sum-bestPay)<Min) //若該道菜滿足口味要求，并最接近理論最佳金額
????????????????? {
??????????????????????? pay = sum;? //存儲當前實際最佳金額
??????????????????????? Min = Abs(sum-bestPay);//存儲當前最小差別
??????????????????????? for (int i=1; i<=M; i++)
????????????????????????????? bestDish[i] = pass[i];
????????????????? }
??????????? }
????? }
????? else //如果處理的不是最后一個菜，應采用回溯方法以取得最優解
????? {
??????????? for (int i=pos; i<N-M+num; i++)
??????????? {
???????????????? pass[num] = i;
???????????????? GetDishes(num+1, i+1, obj, pass, bestDish);
??????????? }
????? }
}

bool IsPass(const int pass[], const Dish *obj, double & sum)
{
????? int h = 0; //存儲實際已經點了的葷菜
????? int s = 0; //存儲實際已經點了的素菜
????? int x = 0; //存儲實際已經點了的辛辣菜
????? int q = 0; //存儲實際已經點了的清淡菜
????? for (int j=1; j<=M; j++)
????? {
??????????? sum += obj[pass[j]].price * 0.8;
??????????? if (obj[pass[j]].isMeat && h < hunCai)//分析該道菜的各種屬性
????????????????? h++;
??????????? else if (!obj[pass[j]].isMeat && s < suCai)
????????????????? s++;
??????????? else
????????????????? return false;
??????????? if (obj[pass[j]].isAcridity && x < xinLa)
????????????????? x++;
??????????? else if (!obj[pass[j]].isAcridity && q < qingDan)
????????????????? q++;
??????????? else
????????????????? return false;
????? }
????? return true;
}

double Abs(double a)
{
????? return (a > 0) ? a : -a;
}

void ReadData(const char *filename, Dish **obj)
{
????? fstream in(filename);
????? if (!in)
??????????? return ;?? //結束程序執行

????? in >> N;
????? in >> M;
????? in >> K;

????? *obj = new Dish[N];
????? int n = 0;
????? while (!in.eof() && n < N)
????? {
??????????? char name[MAX];
??????????? double price;
??????????? bool isMeat;
??????????? bool isAcridity;

??????????? in >> name;
??????????? in >> price;
??????????? in >> isMeat;
??????????? in >> isAcridity;

??????????? (*obj)[n++].PutData(name, price, isMeat, isAcridity);
????? }
????? in >> hunCai;
????? in >> suCai;
????? in >> xinLa;
????? in >> qingDan;

????? in.close(); //關閉文件
}