SoRoMan

今天看到一个网友在谈论一个关于The Tower of Babylon的, 见http://www.cppblog.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;
}