杰哥私房题──大数相除

问题描述
求两个大的正整数相除的商
输入数据
第1 行是测试数据的组数n，每组测试数据占2 行，第1 行是被除数，第2 行是除数。
每组测试数据之间有一个空行，每行数据不超过100 个字符
输出要求
n 行，每组测试数据有一行输出是相应的整数商
输入样例
3
2405337312963373359009260457742057439230496493930355595797660791082739646
2987192585318701752584429931160870372907079248971095012509790550883793197894
10000000000000000000000000000000000000000
10000000000
5409656775097850895687056798068970934546546575676768678435435345
1
输出样例
0

1000000000000000000000000000000
5409656775097850895687056798068970934546546575676768678435435345

 

#include <stdio.h>
#include <string.h>
int iNum1[210];
int iNum2[210];

int minus(int* p1, int* p2, int length1, int length2){
	if(length1 < length2)	
		return -1;
	int i; 
	if(length1 ==  length2){
		for(i = length1 -1; i >= 0; i --){
			if(p1[i] < p2[i])
				return -1;
		}
	}
	for(i = 0; i < length1; i++){
		p1[i] -= p2[i];
		if(p1[i] < 0){
			p1[i] += 10;
			p1[i + 1] --;
		}
	}
	for(i = length1 -1; i >= 0; i--){
		if(p1[i])
			return i + 1;
	}
	return 0;
}
int main(){
	int nCases;
	char cNum1[210];
	char cNum2[210];
	int result[210];
	scanf("%d", &nCases);
	while(nCases--){
		scanf("%s", cNum1);
		scanf("%s", cNum2);
		memset(iNum1, 0, sizeof(iNum1));	
		memset(iNum2, 0, sizeof(iNum2));	
		memset(result, 0, sizeof(result));	
		int i, j = 0;
		int length1 = strlen(cNum1);
		for(i = length1 - 1; i >= 0; i--){
			iNum1[j] = cNum1[i] - '0';
			j++;
		}
		j = 0;
		int length2 = strlen(cNum2);
		for(i = length2 - 1; i >= 0; i--){
			iNum2[j] = cNum2[i] - '0';
			j++;
		}
		length1 = minus(iNum1, iNum2, length1, length2);	
		if(length1 < 0){
			printf("0\n");
			continue;
		}
		else if(length1 == 0){
			printf("1\n");
			continue;
		}
		result[0]++;
		int dis = length1 - length2;
		for(i = length1 -1; i >= 0; i--){
			if(i >= dis)
				iNum2[i] = iNum2[i - dis];
			else
				iNum2[i] = 0;
		}
		length2 = length1;
		for(i = 0; i <= dis;i ++){
			int disTmp;
			while((disTmp = minus(iNum1, iNum2 + i, length1, length2 - i)) >= 0){
				length1 = disTmp;	
				result[dis - i]++;
			}
		}
		for(i = 0; i < 210; i++){
			if(result[i] >= 10){
				result[i + 1] += result[i] / 10;
				result[i] %= 10;
			}
		}
		int flag = 0;
		for(i = 209; i >= 0;i --){
			if(flag)
				printf("%d", result[i]);
			else if(result[i]){
				flag = 1;
				printf("%d", result[i]);		
			}
		}
		printf("\n");
	}
	return 0;
}

 

评论

2 楼 kissyssong 2011-09-16  

kissyssong 写道

先顶再看！
除法是Division吧，怎么搞了个减法啊

仁兄麻烦写几句注释吧

1 楼 kissyssong 2011-09-16  

先顶再看！
除法是Division吧，怎么搞了个减法啊