3.cpp

7道ACM题

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


/* 
 * 主要是大数相乘相加的算法,还有就是数字和字符串之间的转化,要注意小数点
 */

int main()
{
	// 大数相加和大数相乘函数,实现接口,前 4 个参数分别为要计算的两个数组的数组名和长度,第 5, 6 个参数为要得到结果的数组名
	// 和长度,在这里长度用指针变量,因为这个长度要返回来使用
	void bigPlus( int *v1, int v1Size, int *v2, int v2Size, int *v, int *vSize );
	void bigMultiply( int *v1, int v1Size, int *v2, int v2Size, int *v, int *vSize );

	int i, j;
	int pos;
	int v1Size, v2Size, vSize = 0;

	// 用字符串来装两个要输入的数字
	char s1[ 7 ], s2[ 3 ];
	while ( scanf( "%s%s", s1, s2 ) != EOF )
	{
		v1Size = strlen( s1 ) - 1, v2Size = strlen( s2 );

		int *v1 = ( int* )malloc( v1Size * sizeof( int ) );
		int *v2 = ( int* )malloc( v1Size * sizeof( int ) );
		
		// 把第一个输入的字符串变成一个整数数组,代表要乘幂的数,当读入不是数字时则代表是一个小数点,记录下小数点的位置,这个
		// 在后面去掉小数点时有用
		for ( i = 0, j = v1Size; i < v1Size; j-- )
		{
			if ( s1[ j ] >= 48 && s1[ j ] <= 57 )
			{
				v1[ i ] = s1[ j ] - 48;
				i++;
			}
			else
				pos = i;
		}
	
		// 把第二个字符串直接变成一个整数,代表要相乘的次数
		int temp = 1, mi = 0;
		for ( i = v2Size - 1; i >= 0; i-- )
		{
			mi += temp * ( s2[ i ] - 48 );
			temp *= 10;
		}
	
		// 把两个整数数组都初始化一样,接下来为了把两个相乘
		v2Size = v1Size;
		for ( int i = 0; i < v1Size; i++ )
			v2[ i ] = v1[ i ];

		// 在这里调用大数相乘,把得到的结果再变成被乘数,循环至输入要求的次数
		for ( int i = 1; i <= mi - 1; i++ )
		{
			int temp;		// temp 表示得到的结果的位数,我们知道两个数相乘后的位数不会大于原来两个数的位数之和
			temp = v1Size + v2Size;
			int *v = ( int* )malloc( temp * sizeof( int ) );
			for ( int j = 0; j < temp; j++ )
				v[ j ] = 0;
			bigMultiply( v1, v1Size, v2, v2Size, v, &vSize );		
			
			v1 = ( int* )malloc( vSize * sizeof( int ) );		// 把结果赋给被乘数
			for ( int j = 0; j < vSize; j++ )
				v1[ j ] = v[ j ];
			v1Size = vSize;
		}

		// 下面是为了确定小数点的位置
		int flag1 = 0;
		j = 0;
		while ( v1[ j ] == 0 )		// 确定最后面有多少个 0, 因为在小数点之后的最后面的那些 0 是不用打印的
			j++;
			
		pos *= mi;			// 小数部分相乘后得到的小数点位数是原来的两倍
		int flag = 0;
		for ( int i = v1Size - 1; i >= 0; i-- )
		{
			if ( v1[ v1Size - 1 ] != 0 )
				flag = 1;
			if ( i + 1 == pos )		// 如果小数点后面出现的数字都是 0 的话也不用打印
			{
				int k = i;
				while ( v1[ k ] == 0 )
					k--;
				if ( k == -1 )
					break;

				printf( "." );
				flag = 1;
				flag1 = 1;
			}
			
			if ( flag1 == 1 && i + 1 == j )		// 小数点之后的最后面的那些 0 是不用打印的
				break;
			if ( v1[ i ] != 0 || flag == 1 )	// 题目要求当结果小于 1 时小数点前面的 0 不用打印
				printf( "%d", v1[ i ] );
		}
		printf( "\n" );
	}

	return 0;
}


// 大数相加
void bigPlus( int *v1, int v1Size, int *v2, int v2Size, int *v, int *vSize )
{
	int i;
	int temp;

	// 用那个大的作被加数比较好实现
	if ( v1Size < v2Size )
		temp = v2Size;
	else
		temp = v1Size;
	
	// 再建立丙个新的数组,一个跟被加数一样,另一个跟加数一样,不过在加数前面补 0,
	int *v3 = ( int* )malloc( temp * sizeof( int ) );
	for ( i = 0; i < temp; i++ )
		v3[ i ] = 0;
	int *v4 = ( int* )malloc( temp * sizeof( int ) );
	for ( i = 0; i < temp; i++ )
		v4[ i ] = 0;
	for ( i = 0; i < v1Size; i++ )
		v3[ i ] = v1[ i ];
	for ( i = 0; i < v2Size; i++ )
		v4[ i ] = v2[ i ];

	// 跟作笔算一样,对每一位进行最简单的 1 位数相加,并控制进位
	int carry = 0; int a = 0;
	for ( i = 0; i < temp; i++ )
	{
		a = v3[ i ] + v4[ i ];
		v[ *vSize ] =  ( a  + carry ) % 10 ;	// 加上上次的进位,如果大于 10, 取个位数
		(*vSize)++;
		carry = ( a + carry ) / 10;
	}
	if ( carry )		// 如果最后还有进位的话应该在结果前面再加一个 1
	{
		v[ *vSize ] = 1;
		(*vSize)++;
	}
}

// 大数相乘
void bigMultiply( int *v1, int v1Size, int *v2, int v2Size, int *v, int *vSize )
{
	int i, j, k;

	// 用那个大的作被乘数比较好实现
	int *v0, temp;
	if ( v1Size < v2Size )
	{
		v0 = v1;
		v1 = v2;
		v2 = v0;
		temp = v1Size;
		v1Size = v2Size;
		v2Size = temp;
	}

	// 把被乘数跟乘数的每一位相乘,然后再相加,跟做笔算一样
	temp = v1Size + v2Size;
	int *v3 = ( int* )malloc( temp * sizeof( int ) );
	for ( i = 0; i < temp; i++ )
		v3[ i ] = 0;
	int *v4 = ( int* )malloc( temp * sizeof( int ) );
	for ( i = 0; i < temp; i++ )
		v4[ i ] = 0;

	int a, carry = 0;
	for ( i = 0; i < v2Size; i++ )		// 处理乘数的每一位
	{
		int v3Size = 0, v4Size = 0;
		carry = 0;	
		for ( j = 0; j < v1Size; j++ )		// 把被乘数的每一位跟当前乘数的那一样相乘,得到一个结果,放在 v3 里面
		{
			a = v1[ j ] * v2[ i ];
			v3[ v3Size ] = ( a + carry) % 10;
			v3Size++;
			carry = ( a + carry ) / 10;
		}
		if ( carry )
		{
			v3[ v3Size ] = carry;
			v3Size++;
		}

		//  把 v3 里面的数字向左移位,因为每一次乘数的那一位数都会是比前一次的 10 倍
		v3Size += i;
		for ( j = v3Size - 1; j >= 0; j-- )
			v3[ j ] = v3 [ j - i ];
		for ( j = 0; j < i; j++ )
			v3[ j ] = 0;

		// 下面把相乘得到的数相加,放在 v 里面
		if ( i == 0 )		// 第一次的话直接赋给 v
		{
			*vSize = v3Size;
			for ( j = 0; j < v3Size; j++ )
				v[ j ] = v3[ j ];
		}
		else		// 先把 v 赋给 v4, 拿 v3 跟 v4 相加后再把结果放在 v 里面
		{
			v4Size = *vSize;
			for ( j = 0; j < *vSize; j++ )
				v4[ j ] = v[ j ];
			
			*vSize = 0;
			bigPlus( v3, v3Size, v4, v4Size, v, vSize );
		}
	}
}