本文共 1613 字，大约阅读时间需要 5 分钟。

  今天早上做了算法题，其中一道如下所示:

#include 
   
    	#include
    
      	using namespace std;	int main()	{		DWORD dwStart = GetTickCount(); 		int n;		cin >> n;		int flag = 0;		int max = 0;		for (int a = 1; a <= n; a+=2)	//因为两个偶数的最大公约数一定不是1，所以这里每次循环后a+=2, b+=1。		{			for (int b = 1; b <= n; ++b)			{				for (int k = 2; k <= min(a, b); ++k)		//求最大公约数				{					if (a % k == 0 && b % k == 0)					{						flag = 1;						break;					}				}				if (flag == 0 && max < a+b)				{					max = a+b;				}			}		}		cout << max << endl;		DWORD dwTime = GetTickCount() - dwStart; 		cout << dwTime << endl;		return 0;	}
    
   

  先不考虑代码，梳理一下知识点：

  一、求最大公约数、最小公倍数

  1、最小公倍数

  如有两个数x、y，则x * y = 最大公约数 * 最小公倍数

  2、最大公约数

  ①辗转相除法：

/*非递归解法*/int gcd(int x, int y)			//最大公约数：greatest common divisor{	int z = y;	while (x % y != 0)	{		z = x%y;		x = y;		y = z;	}		return z;}/*递归解法*/int gcd(int a, int b){	return b ? gcd(b, a%b) : a;}

  ②辗转相减法：

int gcd(int a, int b){	while (a != b)	{		if (a > b)		{			a = a-b;		}		else		{			b = b-a;		}	}		return a;}

  ③穷举法：

int gcd(int x, int y){	int temp = min(x, y);	while (!(x%temp == 0 && y%temp == 0))	{		--temp;	}		return temp;}

  二、测试时间

  这大概是我一直不明白的问题，每次查来查去，每次也理不清什么。自测的结果总是让人感觉怪怪的(感觉时间数字和单位不一致)。这次也贴一个今天早上找的一篇博客的链接：

  三、大整数

  具体会有大整数的加减乘除各种运算，今天早上的练习很多都是这方面的，要梳理强化！大整数应该是一个考点的方向的，先把加减乘除最基本的弄好！

  Ps：这次做题，关于图、网的还是就那样空了，也没思考。要先把书上的图这一章的好好消化一下，之后重点练习！

  And，纪念一下第一次用Markdown写博客，哈哈哈太好玩了,确实很方便！~

转载地址：http://zvtai.baihongyu.com/