robot.cpp

一个使用贪婪算法解决机器人收集硬币问题的小练习。

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

bool* g_pChessBoard;		//	棋盘
int g_nBase, g_nCoin;		//	棋盘的宽，硬币个数
/**
 *	@fn GenChessBoard
 *	@brief	生成棋盘
 *	@arg	nBase	棋盘的宽
 *	@arg	nCoin	硬币个数
 */
void GenChessBoard(int nBase, int nCoin)
{
	assert(nBase >= 2);
	assert(nCoin >= 1 && nCoin <= nBase*nBase);

	int nCBSize = nBase*nBase;
	g_pChessBoard = new bool[nBase*nBase];

	memset(g_pChessBoard, 0, sizeof(bool)*nCBSize);
	srand(time(NULL));	//取当前时钟初始化伪随机数发生器

	for(int i = 0 ; i < nCoin ; ++i)
	{
		//该算法有个缺陷，理论上说，可能会陷入死循环，实际上不大可能
		//万一你真碰到了,赶快去买张彩票吧
		for(;;)
		{
			int nPos = rand() % nCBSize;
			if (g_pChessBoard[nPos] == false){
				g_pChessBoard[nPos] = true;
				break;
			}
		}
	}
}
/**
 *	@fn	CalcRobot
 *	@brief	计算收集硬币所需要的机器人
 *	@return 所需机器人个数
 */
int CalcRobot()
{
	int nColRobot = 0, nRowRobot = 0;

	int nRow, nCol;

	//一列一列扫描,如果该列有一个硬币则意味着需要一个机器人
	for(nCol = 0 ; nCol < g_nBase ; ++nCol)
	{
		for(nRow = 0 ; nRow < g_nBase ; ++nRow)
		{
			if (g_pChessBoard[nRow*g_nBase+nCol]){
				++nColRobot;
				break;
			}
		}
	}
	//一行一行扫描,如果该行有一个硬币则意味着需要一个机器人
	for(nRow = 0 ; nRow < g_nBase ; ++nRow)
	{
		for(nCol = 0 ; nCol < g_nBase ; ++nCol)
		{
			if (g_pChessBoard[nRow*g_nBase+nCol]){
				++nRowRobot;
				break;
			}
		}
	}
	return nColRobot < nRowRobot ? nColRobot : nRowRobot;
}
/**
 *	@fn	ShowChessBoard
 *	@brief	显示棋盘
 */
void ShowChessBoard()
{
	system("cls");
	if (g_nBase >= 20){
		printf("too large\n");
		return;
	}
	for(int nRow = 0 ; nRow < g_nBase ; ++nRow)
	{
		for(int nCol = 0 ; nCol < g_nBase ; ++nCol)
		{
			printf("%c", g_pChessBoard[nRow*g_nBase+nCol] ? 'O' : '*');
		}
		printf("\n");
	}
}


int main(int argc, char* argv[])
{
	printf("please input chessboard width: ");
	scanf("%d", &g_nBase);
	printf("please input coin number: ");
	scanf("%d", &g_nCoin);

	if (g_nBase <= 2 || g_nCoin < 1 || g_nCoin > g_nBase*g_nBase){
		printf("invalid parameter\n");
		return -1;
	}
	
	GenChessBoard(g_nBase, g_nCoin);
	int nRobot = CalcRobot();
	ShowChessBoard();
	printf("robot number: %d\n", nRobot);

	delete[] g_pChessBoard;


	return 0;
}