数学问题

helloworldcode 2018-03-20 原文

这几天看看王道机试的书，觉得几种方法特别有意义，总结如下。

1、数位拆解

　　问题：特殊的乘法

　　采用字符数组去转化与分析

　　如：123 * 45 = 1*4+1*5+2*4+2*5+3*4+3*5

　　输入：

　　　　123 45

　　输出：

#include<stdio.h>
int main(){
	char buf1[20],buf2[20];
	while(scanf("%s %s",buf1,buf2)!=EOF){
		int sum=0;
		for(int i=0;buf1[i]!=0;i++)
			for(int j=0;buf2[j]!=0;j++)
				sum+=(buf1[i]-'0')*(buf2[j]-'0');
		printf("%d\n",sum);
	}
	return 0;
}

2、求最大公约数

　　其原理：若a，b全为0，则他们的最大公约数不存在；若a，b其中之一为0，则最大公约数为他们中最大的不为0的数；若a，b都不为0，则令a=b，而b=a%b(a为前置条件中的a，不是取等之后的数)，之后重复该过程。

#include<stdio.h>
#include<string.h>
int gcd(int a,int b){
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
int main()
{
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF){
		printf("%d\n",gcd(a,b));
	}
	return 0;
}

3、数制转换

　　问题：将一种进制数转化为另一种进制的数

　　用字符串接受输入的a进制数str，先将其转化为十进制，后转化为b进制，这个过程中要巧用字符数组

#include<stdio.h>
#include<string.h>
int main(){
	int a,b;
	char str[40];
	while(scanf("%d%s%d",&a,str,&b)!=EOF){
		int tmp=0,len=strlen(str);
		int x,c=1;
		for(int i=len-1 ; i>=0 ; i--){
			if(str[i]>='0' && str[i]<='9')
				x=str[i]-'0';
			else if(str[i]>='a' && str[i]<='z')
				x=str[i]-'a'+10;
			else
				x=str[i]-'A'+10;
			tmp+=x*c;
			c*=a;
		}
		char ans[40],size=0;
		while(tmp!=0){
			int x=tmp%b;
			ans[size++]=(x<10) ? x+'0':x+'A'-10;
			tmp/=b;
		}
		for(i=size-1;i>=0;i--)
			printf("%c",ans[i]);
		printf("\n");

	}
	return 0;
}

4、最小公倍数

　　a，b的最小公倍数的值即为a*b与a，b的最大约数相除

#include<stdio.h>
int gcd(int a,int b){
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}

int main(){
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF){
		printf("%d\n",a*b/gcd(a,b));
	}
	return 0;
}