bigint.c

大整数运算用与解决3人传球问题 希望会对你有用

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void simple(int n);
void chu();
void power2(int n);
void print();
int mod10000();
#define MAX 500
struct bigint
{
	int * bint;
	int end;
	

}bigint;
struct bigint theone;
int main()
{
	

	int n,p,ans;
	int x;

	for(; ;)
	{
		theone.bint=malloc(sizeof(int)*MAX);
		memset(theone.bint,-1,sizeof(int)*MAX);
		scanf("%d",&n);
		x=1;
		if(n==0)
			break;
		power2(n);
		if(n%2==0)
			p=2;
		else p=-2;
		simple(p);
		chu();
		ans=mod10000();
		printf("%d\n",ans);
	}	getchar();

}
void simple(int n)
{
	int i=0;

	int give=0;
	int borrow=0;
	switch(n)
	{
	case 2:
		theone.bint[0]+=2;
		for(i=0;theone.bint[i]!=-1;i++)
		{
			if(give)theone.bint[i]+=1;
			if(theone.bint[i]>=10)
			{
				give=1;
				theone.bint[i]-=10;
			}
				else
				give=0;
			if(theone.bint[i+1]==-1)
			{
				if(give)theone.bint[i+1]=1;
				break;
			}
			//print();
		
		}
		break;
	case -2:
		if(theone.bint[0]>=2)
		{
			theone.bint[0]-=2;
			return;
		}
		else
		{

				for(i=1;theone.bint[i]!=-1;i++)
				{
					
					if(theone.bint[i]>=1)
					{
						theone.bint[i]-=1;
						break;
					}
				
				//	print();
				}	
				for(i--;i>=0;i--)
				{
					if(i>0)
						theone.bint[i]+=9;
					else
						theone.bint[i]+=8;
				}
		}
		break;
	}
}
void chu()
{
	int i=0;
	
	int givehowmuch=0;
	int churesult;
	for(i=0;theone.bint[i]!=-1;i++);
	i--;
	for(;i>=0;i--)
	{
		theone.bint[i]+=givehowmuch;
		givehowmuch=(theone.bint[i]%3)*10;
		churesult=theone.bint[i]/3;
		if(churesult==0)
		{
			theone.bint[i]=-1;
			
		}
		else
			theone.bint[i]=churesult;
		
	}
}

void power2(int n)
{
	int i=0;
	int j=0;
	int give=0;
	
	
	
	theone.bint[0]=1;
	theone.end=0;
	for(i=0;i<n;i++)
	{	
		give=0;
		for(j=0;theone.bint[j]!=-1;j++)
		{
			theone.bint[j]*=2;
		}
		for(j=0;theone.bint[j]!=-1;j++)
		{
			if(give)theone.bint[j]+=1;
			if(theone.bint[j]>=10)
			{
				theone.bint[j]-=10;
				if(theone.bint[j+1]==-1)
				{	
					theone.bint[j+1]=1;
					break;
				}
				else
					give=1;
			}
			else
				give=0;

			
		}
	//	print();
	}
}
void print()
{
	int i=0;
	while(theone.bint[i]!=-1)
	{
	
		i++;
	}
	i--;
	while(i>=0)
	{
		printf("%d ",theone.bint[i]);
		i--;
	}
	printf("\n");
}
int mod10000()
{
	int fina;
	int i=0;
	int j=0;
	for(;theone.bint[i]!=-1;i++);
	i--;
	if(i>=3)
	{
		fina=theone.bint[0]+theone.bint[1]*10+theone.bint[2]*100+theone.bint[3]*1000;
	}
	else
		if(i==2)
		{
			fina=theone.bint[0]+theone.bint[1]*10+theone.bint[2]*100;
		}
		else
			if(i==1)
			{
				fina=theone.bint[0]+theone.bint[1]*10;
			}
			else
				if(i==0)
				{
					fina=theone.bint[0];
				}
	
	return fina;
}