SoRoMan

今天看到一個網友在談論一個關于The Tower of Babylon的, 見http://www.shnenglu.com/sicheng/archive/2006/08/09/11024.html，感覺其實就是個按關鍵字面積插入排序的問題。于是用插入排序算法實現如下。

簡單測試了下，應該沒問題。
We have 4 kinds of blocks, they are:
(1,1,1)
(1,2,3)
(2,3,4)
(2,3,2)
Building the tower of babylon...
The max height of tower is: 18.
Totally 7 blocks are used, they are:
(1) block (1,1,1), area = 1
(2) block (1,2,3), area = 2
(3) block (1,2,3), area = 3
(4) block (2,3,2), area = 4
(5) block (2,3,4), area = 6
(6) block (2,3,4), area = 8
(7) block (2,3,4), area = 12

------------------------------------
TowerOfBabylon.cpp:
------------------------------------
//
// File: [TowerOfBabylon.cpp]
// Description:[This program illustrates how to get the Tower Of Babylon. the Tower Of Babylon: Given N kinds of blocks,
// you need to buid the tower under the condition that every upper block's area should less than the lower one.]
// Author:[SoRoMan]
// Date:[2006-08-08]
// Version:[2.0]
// History: [1.0: initial draft.
// 2.0: add a new type TOWER
// 3.0: chnage the sequence data structure to list structure to avoid memory access violation.]
//

// INCLUDES //////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "malloc.h"

// DEFINES //////////////////////////////////////////////////////////////////////////
#define N 4

// TYPES //////////////////////////////////////////////////////////////////////////
typedef struct BLOCK_TYP
{
?int x,y,z;
?int area;
?int height;
?
?BLOCK_TYP *pNext;
} BLOCK, *BLOCK_PTR;

typedef struct TOWER_TYP
{
?int height;
?int num_block;

?BLOCK_PTR pTowerTop;
} TOWER, *TOWER_PTR;

// PROTOTYPES //////////////////////////////////////////////////////////////////////////
TOWER_PTR BuildTower(BLOCK_PTR pBlock, int n);

// FUNCTIONS //////////////////////////////////////////////////////////////////////////
int main(int argc, wchar_t* argv[])
{
?BLOCK blocks[N] = {{1,1,1},{2,2,2},{3,3,3},{4,4,4}};

?printf("We have %d kinds of blocks, they are:\n", N);
?int i;
?for(i = 0; i < N; i++)
?{
? printf("(%d,%d,%d)\n", blocks[i].x, blocks[i].y, blocks[i].z);
?}
?printf("Building the tower of babylon...\n");

?TOWER_PTR pT = BuildTower(blocks, N);
?printf("The max height of tower is: %d.\nTotally %d blocks are used, they are:\n", pT->height, pT->num_block );

?BLOCK_PTR pBlock = pT->pTowerTop;
?for(i = 0; i < pT->num_block; i++)
?{
??????? printf("(%d) block (%d,%d,%d), area = %d, height = %d\n", i+1, pBlock->x, pBlock->y, pBlock->z, pBlock->area, pBlock->height);?
??pBlock = pBlock->pNext;
?}

?getchar();

?return 0;
}

////////////////////////////////////////////////////////////////////////////////
// Algorithm of building the Tower Of Babylon.
// Input Parameters: pBlock: pointer variable that identifies blocks sequence.
// n: int variable that identifies how many kinds of blocks.
// Output Parameters: None.
// Return: pointer variable that identifies the built tower.
////////////////////////////////////////////////////////////////////////////////
TOWER_PTR BuildTower(BLOCK_PTR pBlock, int n)
{
?int index_block = 0;
?TOWER_PTR pTower = new TOWER();
?BLOCK_PTR pTop = new BLOCK();?
?pTower->pTowerTop = pTop;

?// initialize tower
?pTower->pTowerTop->x = pBlock->x;
?pTower->pTowerTop->y = pBlock->y;
?pTower->pTowerTop->z = pBlock->z;

?pTower->pTowerTop->area = (pBlock->x)*(pBlock->y);
?pTower->pTowerTop->height = pBlock->z;
?pTower->height = pTower->pTowerTop->height;
?pTower->num_block = 1;
???
?for(int i = 1; i < 3*n; i++)
?{
? index_block = i/3;
? if (i%3 == 0) // condition 1, area = x*y, height = z.
? {
?? (pBlock+index_block)->area = ((pBlock+index_block)->x)*((pBlock+index_block)->y);
?? (pBlock+index_block)->height = (pBlock+index_block)->z;
? }
? else if (i%3 == 1) // condition 2, area = x*z, height = y.
? {
?? (pBlock+index_block)->area = ((pBlock+index_block)->x)*((pBlock+index_block)->z);
?? (pBlock+index_block)->height = (pBlock+index_block)->y;
? }
? else // condition 3, area = y*z, height = z.
? {
?? (pBlock+index_block)->area = ((pBlock+index_block)->y)*((pBlock+index_block)->z);
?? (pBlock+index_block)->height = (pBlock+index_block)->x;
? }
?
? bool bNeedToBeAdded = true;?

? BLOCK_PTR pB = pTower->pTowerTop;
? BLOCK_PTR pPrev = pTower->pTowerTop;
? while(pB != NULL)
? {
?? if ((pBlock+index_block)->area < (pB->area))
?? {
?// insert new block
?BLOCK_PTR pNewBlock = new BLOCK();?
??? *pNewBlock = *(pBlock+index_block);

?if(pB == pPrev)
?{
??pNewBlock->pNext = pB;
??pTower->pTowerTop = pNewBlock;
?}
?else
?{
??pNewBlock->pNext = pPrev->pNext;
??pPrev->pNext = pNewBlock;
?}
?
??? // increase number of blocks
??? pTower->num_block++;
??? // increase height of tower
??? pTower->height += (pBlock+index_block)->height;
???
??? bNeedToBeAdded = false;
??? break;
?? }
?? else if ((pBlock+index_block)->area == (pB->area))
?? {
??? if (pB->height < ((pBlock+index_block)->height))
??? {
???? // increase height of tower
???? pTower->height += (pBlock+index_block)->height - pB->height;
???? // replace blocks
? BLOCK_PTR pNewBlock = new BLOCK();?
? *pNewBlock = *(pBlock+index_block);

? if (pB == pPrev)
? {
??pNewBlock->pNext = pB->pNext;
??pTower->pTowerTop = pNewBlock;
? }
? else
? {
?? pNewBlock->pNext = pB->pNext;
?? pPrev->pNext = pNewBlock;
? }
??? }

??? bNeedToBeAdded = false;
??? break;
?? }

?? pPrev = pB;
?? pB = pB->pNext;
? }
?
? if(bNeedToBeAdded)
? {
?? // add new block at the end
?? BLOCK_PTR pNewBlock = new BLOCK();?
?? *pNewBlock = *(pBlock+index_block);
??
?? pPrev->pNext = pNewBlock;
?? pNewBlock->pNext = NULL;

?? // increase number of blocks
?? pTower->num_block++;
?? // increase height of tower
?? pTower->height += (pBlock+index_block)->height;
? }
?}

?return pTower;
}

?

?

?

?