欧几里德算法

参考2017蓝桥杯第8题

首先来一波欧几里德算法的核心

#include<stdio.h>
int gcd(int m,int n){//欧几里得算法(辗转相除法)
	int temp,rem;
	if(n>m){
		temp = n;
		n = m;
		m = temp;
	}
	while(n!=0){
		rem = m%n;
		m=n;
		n=rem;
	}
	return m;
}
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%d",gcd(m,n));
}

gcd(a,b)=gcd(b,a mod (b)),其中mod()表示模运算,a>b.比如gcd(18,12)=gcd(12,18%12)=gcd(6,12%6)=gcd(6,0)。

回到这个题中,

if(g != 1)
    {
        printf("INF\n");
    }else{
        bk[0] = true;
        for(int i = 0 ; i < n ; i ++)    //关键部分
        {
            for(int j = 0 ; j + arr[i] < N ; j ++)
                if(bk[j])bk[j+arr[i]]= true;
        }
        int count = 0;
        for(int i = N-1 ; i >= 0 ; i --){
            if(bk[i] == false) count++;
        }
        printf("%d\n",count);
    }

这个部分其实不难理解,目的就是将arr[0],arr[1]及其倍数都置为true,也将arr[0],arr[1]的倍数相加的值也置为true!

实际上这里用到了动态规划的思想。然而我还没有看懂,于是继续加油吧!


3月22日备忘录:memset(),freopen()函数。

memset()

int array[5] = {1,4,5,6,2};
memset(array,1,sizeof(array));
for(int i=0;i<5;i++)    printf("%d  ",array[i]);

此处将会输出:16843009 16843009 16843009 16843009 16843009,这是因为memset()是按照一个字节为单位赋值给array所占有的内存空间的,于是每个字节就是00000001,但是int类型是占四个字节的,所以每个array[i]为00000001000000010000000100000001,也就是16843009。我们一般用这个函数用于内存清空也就是memset(array,0,sizeof(array))。

freopen(“文件路径”,"r/w",stdin/stdout);官方称呼是输入输出重定,文件路径可以和程序同目录,这样直接如"DATA.txt"就可以访问了,比较方便。stdin和stdout指的是standard in,standard out,也就是键盘输入流和控制面板输出流。    重要的在于怎么使用,直接上代码:

#include <stdio.h>

int main()
{
    freopen("DATA.txt","r",stdin);
    double ans = 0,a,b;
    while(scanf("%lf%lf",&a,&b)!=EOF){
    	printf("%lf	%f\n",a,b);
        ans += a*b/100;
    }
    printf("%lf\n",ans);
    return 0;
}

DATA.txt的内容为

欧几里德算法(只是很少一部分)

所以使用这个函数的好处就是便于提取数据量巨大的文本。

;