菜鸟学算法--简单的交换和最大公约数算法入门篇

工作之后我们大部分的时间实在研究如何如何学习一门语言 如何如何掌握一门技术,但是作为编程的本质 数据结构和算法 我们慢慢的忽略了 。

工作后的很多程序员真的没有大学生一样的时间 去静下心来去增加自己的底蕴,这是我深有体会的事情当然我这里指的是和我有累死感觉的人。

学习是一个过程,从简入繁 一贯如此,记录下来只为 记录自己的点点滴滴。

算法的本质并不是我们程序员去创造算法 而是我们 按照先人创造的算法思想 用代码来实现算法。

下面开始介绍两个 简单的例子 一个是交换 一个是最大公约数算法。

简单的交换

#include "stdafx.h"
#include <stdio.h>
/*
  我们的目标是  
  交换abcd的值为bcda     函数 M1   M2
  此处代码相信都是再小儿科不过的代码了,但是小儿科的代码实际上也是有小儿科的写法。
  我们在写代码的时候要保证的两点  高效 快速 最小的损耗 完成功能即可 。
*/
int a = 1, b = 2, c = 3, d = 4;
int arr[4] = { 1, 2, 3, 4 };

//abcd的值变成 bcda
#define  M1(ta,tb,tc,td)  \
       int tem;  tem=td ; td=ta;ta=tb;tb=tc;tc=tem
//abcd的值变成 bcda
#define M2(ta,tb,tc,td)      \
            ta+=td;td=ta-td;ta-=td; \
            ta+=tc;tc=ta-tc;ta-=tc;  \
			ta+=tb;tb=ta-tb;ta-=tb;
#define  RESET(ta,tb,tc,td)   \
        ta = 1; tb = 2; tc = 3; td = 4; 

       
int _tmain(int argc, _TCHAR* argv[])
{ 
	//首先对abcd进行值替换成bcda 一说到替换 很多新手就想到了  t=a  a=b b=t~  
	//这里中间多一步 空间的 浪费 即  t中间变量  实际上我们可以  a=a+b; b=a-b; a=a-b;     
	//我们可以这样去写这个代码 

	printf("M2----abcd的值:%d,%d,%d,%d\n", a, b, c, d);
	M2(a, b, c, d);
	printf("M2----abcd的值:%d,%d,%d,%d\n", a, b, c, d);
	printf("\n");
	RESET(a, b, c, d);
	//不同的情况下我们使用不同的方式 来解决 ,对于两个变量的交换我们可以用上述的  无中间变量的方式来交换看似减少了空间占用 ,但是四个变量呢 ？四个变量的交换 貌似情况变了 
	//实现如M1 尽管我实现的不好 但是的确是减少了 传统意义上的交换步骤  这种代码其实只有在大家 刚接触程序的时候才会写道~~~~哈哈 
	//这也印证了一点  情况复杂多变  代码实现方式也很多   我们要做到  最少的代码 最少的计算次数 完成目的即可。
	printf("M1----abcd的值:%d,%d,%d,%d\n", a, b, c, d);
	M1(a, b, c, d);
	printf("M1----abcd的值:%d,%d,%d,%d\n", a, b, c, d);  
	return 0;
}

下面一个是 求最大公约数的算法 欧几里得算法

#include "stdafx.h"
//求最大公约数
//算法欧几里得算法的应用
//获得最大公约数 
//现在求ab的最大公约数 既能被a又能被b整除的数字 
//如果你不了解 欧几里得算法 那么可能会 循环来解决问题 ...那么很糟糕的 
//我们程序员的算法本质 是 拿来数学算法 思想转换成代码 这就是我们大部分使用算法的本质  除非你是算法研究者 那么 另当别论
//看看这端程序如果你不知道 欧几里得算法  衍生的 求最大公约数算法 你该如何去写程序?或许是多个循环吧，~
int   GreatestCommonDivision(int a, int b)
{  
	//不能为负数
	if (a < 0 || b < 0)
		return -1;
	///保证a一定大于等于b
	if (a < b)
	{
		a = a + b;
		b = a - b;
		a = a - b;
	}
	int r = 0;
	//取余数 如果余数等于0 那么 最大公约数既为 当前a 
	while ((r = a%b) != 0)
	{  
		//否则 a<-b   b<-r    这里的余数r 一定是小于b的
		a = b;
		b = r;
	}
	//等于0就退出了 
	return  b;
}

int _tmain(int argc, char**argv)
{
	int a = 15, b = 220;
	printf("%d和%d的最大公约数是:%d\n", a, b, GreatestCommonDivision(a, b));
	return 0;
}