棋盘覆盖

棋盘覆盖

思路：

自己学个数组模拟一下数的乘除法即可，至于课本上的分治法求两个大数的积，如果用在这里有点大才小用，简单模拟即可。

下面的代码是求用多少块格子，递归覆盖棋盘的代码和用队列模拟的递归覆盖棋盘的代码。仅供参考

再说点，大数乘除法以后可能会经常用到，感兴趣的可以上网搜一下大数的C++模板，JAVA有个大数包，据说只要内存够，数就能存下，可以看一下。

//棋盘覆盖问题
//自己模拟数的乘除法
//NYOJ 45 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

int a[105];

int main(){
	int T;
	scanf("%d",&T);
	int num;
	int _count = 1;
	int jin_wei;
	int tmp;
	while(T--){
		a[0] = 1;
		_count = 1;
		scanf("%d",&num);
		for(int i=1; i<=num; i++){
			jin_wei = 0;
			for(int j=0; j<_count; j++){
				tmp = a[j]*4+jin_wei;
				a[j] = tmp%10;
				jin_wei = tmp/10;
			}
			if(jin_wei)
				a[_count++] = jin_wei;
		}
		//模拟除法 
		a[0] -= 1;
		tmp = 0;
		for(int i=_count-1; i>=0; i--){
			tmp = (10*tmp+a[i]);
			a[i] = tmp/3;
			tmp = tmp%3;
		}
		int i;
		if(a[_count-1]==0)
			i = _count-2;
		else
			i = _count-1; 
		for( ; i>=0; i--)
			printf("%d",a[i]);
		cout << endl;
	}
	
	return 0;
} 


//方法一：用递归的分治 
/*
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long int ll;

int Count = 1;
int board[1050][1050];

void print(int size){
	
	for(int i=0; i<size; i++){
		for(int j=0; j<size; j++)
			printf("%-3d",board[i][j]);
		printf("n");
	} 
}

void chess_board(int posx,int posy,int x,int y,int size){
	
	if( size==1 )
		return ;
	size /= 2;
	int num = Count++;
	//左上角
	if( posx+size>x && posy+size>y )
		chess_board(posx,posy,x,y,size);
	else{
		board[posx+size-1][posy+size-1] = num;
		chess_board(posx,posx+size-1,posy+size-1,size);
	}
	
	//右上角
	if( y>=posy+size && x<posx+size )
		chess_board(posx,posy+size,size);
	else{
		board[posx+size-1][posy+size] = num;
		chess_board(posx,size);
	} 
	
	//左下角
	if( x>=posx+size && y<posy+size )
		chess_board(posx+size,size);
	else{
		board[posx+size][posy+size-1] = num;
		chess_board(posx+size,posx+size,size);
	} 
	
	//右下角
	if( x>=posx+size && y>=posy+size )
		chess_board(posx+size,size);
	else{
		board[posx+size][posy+size] = num;
		chess_board(posx+size,size);
	}
}

int main(){
	
	int E;
	scanf("%d",&E);
	int x,y;
	scanf("%d %d",&x,&y);
	board[x][y] = -1;
	chess_board(0,E);
	print(E);
	return 0;
	
}
*/

/*
//用队列实现的分治
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

int Count = 1;
int board[1050][1050];

struct Node{
	int posx;
	int posy;
	int x;
	int y;
	int size;
	Node(){
		posx = posy = x = y = size = 0;
	}
	Node(int a1,int a2,int a3,int a4,int a5){
		posx = a1;
		posy = a2;
		x = a3;
		y = a4;
		size = a5;
	}
};
queue<Node> Q;

void print(int size){
	
	for(int i=0; i<size; i++){
		for(int j=0; j<size; j++)
			printf("%-5d",board[i][j]);
		printf("n");
	} 
}

int main(){
	
	int E;
	scanf("%d",&y);
	board[x][y] = -1;
	Node node,tmp;
	node.posx = 0;
	node.posy = 0;
	node.x = x;
	node.y = y;
	node.size = E;
	Q.push(node);
	while( !Q.empty() ){
		tmp = Q.front();
		Q.pop();
		if( tmp.size==1 )
			continue;
		int size = tmp.size/2;
		int posx = tmp.posx;
		int posy = tmp.posy;
		int x = tmp.x;
		int y = tmp.y;
		int num = Count++;
		//左上角 
		if( posx+size>x && posy+size>y ){
			Node node(posx,size);
			Q.push(node);
		}
		else{
			board[posx+size-1][posy+size-1] = num;
			Node node(posx,size);
			Q.push(node);
		}
		
		//右上角
		if( y>=posy+size && x<posx+size ){
			Node node(posx,size);
			Q.push(node);
		} 
		else{
			board[posx+size-1][posy+size] = num;
			Node node(posx,size);
			Q.push(node);
		}
	
		//左下角
		if( x>=posx+size && y<posy+size ){
			Node node(posx+size,size);
			Q.push(node);
		}
		else{
			board[posx+size][posy+size-1] = num;
			Node node(posx+size,size);
			Q.push(node);
		} 
	
		//右下角
		if( x>=posx+size && y>=posy+size ){
			Node node(posx+size,size);
			Q.push(node);
		}
		else{
			board[posx+size][posy+size] = num;
			Node node(posx+size,size);
			Q.push(node);
		}
	}
	print(E);	
	return 0;
} 

*/