求最大公约数的解法

求最大公约数的解法

---

# 解法描述
计算两个数的最大公约数的不同解法，包括：
a. 欧几里得算法 gcd1，更详细描述可以参见维基欧几里得算法。

b. 计算gcd(m, n)的连续整数检测算法gcd2。

c. 中学里的计算方法gcd3, 相对最复杂的解法，不过计算结果当然是有效的，正确。算法逻辑描述如下：

1 找到m的所有质数prime1；
2 找到n的所有质数prime2；
3 从prime1和prime2中找出所有的公因数com_prime。
注意：如果p是其中一个公因数，而且在prime1和prime2中分别出现Pm，Pn次那么应该将p重复min{Pm, Pn}次；
4 将com_prime的所有质因数相乘，结果即m, n最大公约数。

……（gcd3解法O_o 够折腾的求解过程吧。） ……


以上三者不同解法的效率也不同，比较情况为：gcd1 > gcd2 > gcd3 。

# 代码示例


int gcd1(int m, int n)
{
    assert (m>0 && n>0);
    if (m < n)
std::swap(m, n);
    while (0 !=n) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

int gcd2(int m, int n)

{

    assert (m>0 && n>0);

    int min = (m > n ? n : m);

    for (; ; --min) {

        if (0 == m % min && 0 == n % min)

            break;

    }

    return min;

}

int gcd3(int m, int n)

{ 

... 代码繁多，在此略 ...

}

# 附
> 完整代码示例，参见github。

（完）

十八晚离深回家，准备过年啊。

腊月十八晚离深回家，准备过年啊。标记一篇。

这次假期，安排十五天的时间，希望自己可以轻轻松松，珍惜。

哦，放假期间，回家过年就尽量不与电脑，网络打交道了，让自己放放松，体验下除了这两样东西，其他生活元素的美好，尤其在家和家人，亲朋好友一起聊天，交流甚是开心啊，颇难得需好好珍惜哈。
所以，在此的博客就会休息一段时间了，但愿年后回深工作了，我会继续花花时间经营。不管好坏，慢慢写起吧，呵呵。

2012迅雷会员卡，需要的童鞋们可找我，先到先得。

过完年就是龙年了，话说我的本命年啊，祝我好运祝我勇敢。同时，顺祝大家龙年吉祥如意！

凸包问题

凸包问题

---

# 故事

这些天想到了某某编程问题，联想到了凸包问题……犹记得当年，我还在大学时，学习《算法分析与设计》课程过程，参与ACM程序设计过程，均面对过凸包问题，回忆那时光还是比较清晰的，毕竟日子还未曾久远……但是，尝试想起具体的凸包问题及其解决方案（算法），却真的有些模糊了啊。不行…我需找时间回头学习之，所以，自己需要花时间去查查书，翻翻曾经的测试代码……再回过头来整理了下，这样才再次清晰了，温故而知新啊，知新啊……

那就稍微梳理，博客一篇吧。

在此介绍凸包问题的两种解决算法包括, 蛮力法与分治法。

# 蛮力法
 > 蛮力法使用到几何知识:
P1，P2{(x1, y1), (x2, y2)} => ax + by = c
=> {a = y2-y1, b = x1 - x2, c = x1y2 - y1x2}

使用公式ax + by = c可判断点P3(x3, y3)落在{(x1, y1), (x2, y2)}哪边.

蛮力解法步骤：


1. 循环遍历所有的点，找出所有像P1，P2的点，需满足条件：
其他所有的点均分布在直线P1P2同一边，借助以上几何知识。
2. 找出了所有这样的点，那么就完成凸包问题。

蛮力解决方案时间复杂度O(n^3).

# 分治法
 > 分治法使用到几何知识:
{(x1, y1), (x2, y2), (x3, y3)} P1, P2, P3.面积S(P1P2P3)为以下行列式绝对值的一半，
|x1 y1 1|
|x2 y2 1| = x1y2 + x3y1 + x2y3 - x3y2 - x2y1 - x1y3
|x3 y3 1|


P3位于直线P1P2的左侧时，该表达式为正值。
P3位于直线P1P2的右侧时，该表达式为负值。
 该绝对值越大，即P3就与直线P1P2距离越大。

分治解法步骤：


1. 按照X轴（或Y轴）排序点集合S0，得到最小大值P1，Pn，并划分上包，下包不同点集合。
2. 以上包为例，根据以上几何知识，找出上包顶点Pmax即距离P1Pn最远的点，找不到即结束。
3. 继续以P1Pmax和PmaxPn构造上包，递归下去直至找不到上包顶点。得到点集合S1.
4. 下包操作同。得到点集合S2.
5. 合并集合S1, S2, 得到S3即凸包结果.


分治法解决方案时间复杂度O(n^2).

# 附
BTW，详细的算法可以参见《算法分析与设计》3.蛮力法3.3.2凸包问题 & 4.分治法4.6.2凸包问题.

文章描述的两种解法，完整的示例代码可以参见 github I II。

预祝兄弟们各奔前程顺利

预祝兄弟们各奔前程顺利
  -- 20120628夜，修改文章标题，加更新博文！

---

本文的主题很简单，简单一句话，感谢王二（WY）和路子（LSH）从帝都寄过来的明信片！明信片拍图如下：

微博文：“奇怪了，今天才有HR-MM给我送来这张贺卡。延迟了半个月了都……难道一直卡在路上或落在前台没人知晓？？。虽然小小东西，但在这电子信息时代稀罕这纸质东西哈，感谢王二，路子。”

===

王二（sqrabs），路子（pigsoldier）乃之前在珠海KS老同事两枚，美名曰兄弟，恶名曰基友。其实，当时在那里好友很多，还有其他诸位啊LGT，ZW，GRS，QCJ，PBW，PZF，DJ,XLJ……（那群的武汉帮啊见后面附图）等。虽然那时候在珠海呆过的时间说长不长，就五六月的时候吧，但是在这些的时间里，那时候大家相处时间比较长，工作一起，聊天一起，玩一起；上班一起，吃饭也一起，下班还是一起。因为：
那时候，基友们都是即将大学毕业，到司实习锻炼，基本除了公司，就是（公司）宿舍。
（后来）那时候，基友们都是刚刚大学毕业，初步入社会开始工作，都是比较单调单纯的苦逼程序猿，在公司一起的时间最多了，连周末都是大家一起叫外卖，一起出去聚餐。
那时候，基友们都是围着一起吃饭，一起聊天，一起吐槽。


所以，那时候大家的感情都是特别真，特别纯。相比外面一些‘险恶’的职场生活。
唉，不再多回忆了，回忆总是美好的，但是难免有些伤感伤情的。待有来日，希望大家再聚吧，把酒言欢言愁言苦，畅其所谈。

===
再后来，基友们就慢慢的离开珠海KS，一个，两个，三个 ……


（插播一段故事：我是离开者的其中之一，回忆当时我离开的情况比较悲催（窘迫），公司于尴尬处境，有着变相裁员的趋向，（相信那段日子很多的基友们都不好过，天天焦心焦虑的感觉吧，）于我于司均勉为其难，只有离开了，虽那是对刚毕业生的难，但求痛快明了，后来自己心里亦得以安慰了。该不该怨恨或记仇那些没有在那时候不与给予支持的Leader？ 其实，后来这样的问题慢慢地已然无所谓了，想通了即宽心了！以“天下谁人不识君”的心态，愤然投奔深圳，最后安定于XL至今。在XL工作，我的表现可总结为愿意付出，敢作敢为，与团队协作融洽，同事关系十分可观。荣幸的是在今年年初已升级高级工程师，同时得到Leader的看好得以多方面的培养。感谢很多人，包括基友们！）


当然，王二和路子也包含在这些离开者之中，他俩，是在我的离开的后后来才陆续离开的啦，其离开的处境与情况就不一样的啦，乐观的状态也。

往事不堪回首啊，确实，过去已快两年的时间了。
不堪回首，不堪回首 ……

===

小小博文一篇,在此致谢两位好（基）友，同时祝福友情日久醇厚!

好吧，不早了，洗洗睡觉，晚安。

最后，预祝兄弟们各奔前程顺利，似锦！

KS-WPS 2012毕业生“武汉帮”（部分），某次聚会附图如下：

（完）

代码重构（优化）笔记

代码重构（优化）笔记

总结如下：

1. 代码风格格式化，最简单的，也是很重要的第一步。整体上，需要做到的几点：

     a 该对齐的对齐，换行的换行。（具体规则不必多说，同时也根据个人具体情况稍微不同）

     b 针对模糊或是不合理的命名，重新给予良好的命名。

     c 去掉冗余的代码，包括测试性的代码，多余的变量和注释。

2. 理清程序大体的运行结构。

     就C/C++代码而已，可以从*.h文件入手，因为你暂时无需关心实现细节，只要清楚那些主要函数的功能说明。

3. 选择重构的关键点。同时，也是你的重构工作的切入点。

     否则，面对那一坨坨量大又繁杂的代码，难免显得无从入手。放心吧，只要你有了切入点，很多优化工作会慢慢清晰，水到渠成就是这样的道理。

     当然，很可能你选择的关键点会发生变化。变化时允许的但不得过于频繁，因为你对于重构逻辑的了解也是一个循序渐进的进步过程。若过于频繁变化重构的关键点，那么就属于你的问题了，要么你没冷静想清楚过于冲动地重构工作，要么你过于贪心盲目追求重构的效果。

4. 具体分析，优化代码逻辑。比如：

     a 是否可以省略其中某些变量。利于结构清晰，避免变量（标志值）太多容易导致代码烦乱。

     b 减少耗时的操作次数，如排序，查找，精度值计算。

     c 调整循环结构，尽可能清晰明了。如选择for或while循环。

简要介绍一本关于重构书籍《重构--改善既有代码的设计》，讲解具体一条一条的重构规则，同时也是一种技巧吧。

想必大家都已有所了解这本重构书籍。

重构

 

更新描述或封面

副标题: 改善既有代码的设计
作者: Martin Fowler
出版社: 中国电力
出版年: 2003-8-1
页数: 464
定价: 68.00元
装帧: 平装(无盘)
ISBN: 9787508315546

9.0

(1394人评价)

57.8%
34.0%
7.2%
0.6%
0.3%

我读过这本书    修改   删除
我的评价: 推荐
标签: 设计模式 C/C++ 软件开发 编程
站在代码艺术风格角度，以Java语言在描述，讲的很清晰明了，再说Java的语言很好理解（我懂java就更无碍了），该书很值得推荐。真正掌握了书中的精髓那么你一定是一位称职而干练的工程师了 。

2011-11-10 / huangjunkun/

微博传闻的”雷娘“（迅雷）

显然，没有前段时间到处流传的“度娘”那么拉轰，所谓的事业线足够长。但是“雷娘”还是有些给力的吧。哈哈。MARK！图贴一张，见上。

拷贝带有随机指针的链表

拷贝带有随机指针的链表

---

# 算法描述


问题描述：拷贝“随机链表”，即节点带有一个指针可能指向链表随机另一个节点的链表。

解法1：一般的简单蛮力算法，可完成该功能，但时间复杂度为 O(n*m)。步骤：

 a 遍历链表一遍，完成拷贝链表与初始化next指针。遍历链表一遍M，M为节点个数。
 b 查找原链表的每一random指针对应节点，需要遍历旧链表直至找到匹配并记录偏移位置pos。遍历链表一遍M'，M' <= M且可变。
 c 根据偏移位置pos，在新链表对应节点的random指针赋值。遍历链表一遍M'，M' <= M可可变。
 d 重复b c操作，直至链表节点的random指针均赋值。该重复操作M次。
btw. 显然以上做法为最最低效。


解法2：较高效的算法，相比时间复杂度为O(m)。具体操作，需要遍历源链表三遍。包括拷贝链表+复制随机指针+回复源链表NEXT指针。算法步骤，复制完链表，遍历两遍即完成拷贝操作。详细步骤见下：

a. ABCD是原来的链表，A’B’C’D’是复制的链表，第一遍扫描顺序复制next指针，
b. 把ABCD的next分别指向A’B’C’D’，将A’的next指针指向B，B’的next指针指向C，依次类推。
c. 复制random指针： A’->random=A->random->next
d. 恢复:A->next=A’->next; A’->next=A’->next->next;



# 算法实现（C源码）

struct random_list_node
{
random_list_node()
: value(0), next_ptr(NULL), random_ptr(NULL)
{}
random_list_node(int v)
: value(v), next_ptr(NULL), random_ptr(NULL)
{}
~random_list_node() {}


int value;
random_list_node* next_ptr;
random_list_node* random_ptr;
};


typedef random_list_node* random_list;




random_list_node* copy_random_list(random_list_node* head_ptr)
{
if (NULL == head_ptr) return NULL;


random_list_node* new_head_ptr = new random_list_node;
new_head_ptr->value = head_ptr->value;
new_head_ptr->next_ptr = head_ptr->next_ptr;
head_ptr->next_ptr = new_head_ptr;
// copy random_list
random_list_node* move_ptr = new_head_ptr->next_ptr;
while (move_ptr)
{
random_list_node* new_node = new random_list_node;
new_node->value = move_ptr->value;
new_node->next_ptr = move_ptr->next_ptr;
move_ptr->next_ptr = new_node;
move_ptr = new_node->next_ptr;
}


// scan random_list twice, for random_ptr and next_ptr.
move_ptr = head_ptr;
while (move_ptr)
{
random_list_node* new_move_ptr = move_ptr->next_ptr;
if (move_ptr->random_ptr)
new_move_ptr->random_ptr = move_ptr->random_ptr->next_ptr;


assert(NULL != new_move_ptr);
move_ptr = new_move_ptr->next_ptr;
//new_move_ptr = move_ptr->next_ptr;
}


move_ptr = head_ptr;
random_list_node* new_move_ptr = move_ptr->next_ptr;
while (new_move_ptr)
{
move_ptr->next_ptr = new_move_ptr->next_ptr;
if (new_move_ptr->next_ptr)
new_move_ptr->next_ptr = new_move_ptr->next_ptr->next_ptr;
move_ptr = move_ptr->next_ptr;
new_move_ptr = new_move_ptr->next_ptr;
}


return new_head_ptr;
}

# 附
该算法完整的C程序示例代码放在Github，可参见。
可参考其他网友同仁的博文，包括其图示说明，在这里。

（完）

STL稳定排序源码分析

STL稳定排序源码分析

 -- std::stable_sort源码学习笔记

---

发表于 2011年11月07日 10:41

# 背景说明
先贴一张图吧:

前几天，一个新同事前来询问算法stl-stable_sort的情况。由于离上次研读stl源码时间久已（两三年前的事儿了），有些细节笔记模糊了。所以就找了sgi-stl和ms-stl俩版本，重新复习一遍其中的stl-stable_sort算法。稍微简单整理了阅读笔记，主要裁剪sgi-stl源码的“伪代码”，顺便加些注释还可看懂一二！sgi-stl 可读性笔记强。

    事后，和新同事们讲解，分享该算法的内在，主要想说明区别于通用型的std::sort。 

    希望贴出来，对于一些新学者有点用处！ 

===
# 源码分析

Title: [ std::stable_sort源码学习笔记 ]

===== begin =====

 STL算法 （稳定）在位排序

 stable_sort(__first,  __last) {

 // 关键点1：申请排序缓冲区

  _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);

  if (buf.begin() == 0)

    __inplace_stable_sort(__first, __last);//若缓冲区为空则内部排序。

  else 

    __stable_sort_adaptive(__first, __last, buf.begin(),

                           _Distance(buf.size()));//转调 

}

=====>>>>>

转调的在位排序，实则归并排序。

__stable_sort_adaptive(__first, __last, __buffer,__buffer_size) {

// 关键点2：递归，归并排序！

  __len = (__last - __first + 1) / 2;

  __middle = __first + __len;

  if (__len > __buffer_size) {

    __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);

    __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);

  }

  else {

    __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);

    __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);

  }

  __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 

                   _Distance(__last - __middle), __buffer, __buffer_size);

}

=====>>>>>

借助缓冲区进行归并排序

__merge_sort_with_buffer(__first, __last, __buffer) {

  __len = __last - __first;

  __buffer_last = __buffer + __len;

  __step_size = __stl_chunk_size;// sgi stl 7

  // 关键点3：在整个集合分片地进行插入排序，保证每分片均有序。

  __chunk_insertion_sort(__first, __last, __step_size);

  // 关键点4：合并不同分片（有序的）元素。

  while (__step_size < __len) {

    __merge_sort_loop(__first, __last, __buffer, __step_size);

    __step_size *= 2;

    __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);

    __step_size *= 2;

  }

}

=====>>>>> 

__merge_sort_loop(__first,  __last, __result, __step_size) {

  __two_step = 2 * __step_size;

  while (__last - __first >= __two_step) {

    __result = merge(__first, __first + __step_size,

                     __first + __step_size, __first + __two_step,

                     __result);

    __first += __two_step;

  }

  __step_size = min((__last - __first), __step_size);

  merge(__first, __first + __step_size, __first + __step_size, __last,

        __result);

}

=====>>>>>

将集合切分若干分片，排序每分片元素。

__chunk_insertion_sort(__first, __last, __chunk_size)

{

  while (__last - __first >= __chunk_size) {

    __insertion_sort(__first, __first + __chunk_size);

    __first += __chunk_size;

  }

  __insertion_sort(__first, __last);

}

=====>>>>>

插入排序

__insertion_sort(__first, __last) { 

  for (__i = __first + 1; __i != __last; ++__i)

    __linear_insert(__first, __i, __VALUE_TYPE(__first));

}

=====>>>>>

__linear_insert( __first, __last, _Tp*) {

  if (__val < *__first) {

    copy_backward(__first, __last, __last + 1);

    *__first = __val;

  }

  else

    __unguarded_linear_insert(__last, __val);

}

=====>>>>>

__unguarded_linear_insert(__last, __val) {

  __next = __last;

  --__next;

  while (__val < *__next) {

    *__last = *__next;

    __last = __next;

    --__next;

  }

  *__last = __val;

}

===== end =====

@huangjunkun/2011-11-01/

# 附说明

转：http://my.oschina.net/junkunhuang/blog/34726

在线流程图简洁工具:http://www.websequencediagrams.com/

code:

stable_sort -> __stable_sort_adaptive :申请排序缓冲区
__stable_sort_adaptive -> __merge_sort_with_buffer:借助缓冲区，\n递归地归并排序！
__merge_sort_with_buffer -> __merge_sort_loop:集合切分分片，\n插入排序各分片，\n保证分片均有序；\n合并不同有序分片。
__merge_sort_loop  -> merge :以分治法切分\n进行合并排序
merge -> __chunk_insertion_sort :将集合切分若干分片，\n排序每分片元素。
__chunk_insertion_sort -> __insertion_sort:插入排序
__insertion_sort -> __linear_insert: 
__linear_insert -> __unguarded_linear_insert: 
__unguarded_linear_insert -> end: 

人月神话浅谈

人月神话浅谈
  -- 阅读《人月神话》的小小感想

---

《Agile project management with scrum》

几年前，我还在大学，大二学习数据结构这门课程时候，任课老师推荐同学们去看看《人月神话》，尝试感悟学习其中的软件工程学的一些东西。记得当时我粗读一遍，浑浑噩噩般感觉到一些东西了，但算不上感悟。毕竟当时从未有过真实的工程项目开发经验，真的比较难感悟到那些项目管理那些东西，勉强只能算达到理解的感觉吧。

……

而之后好多年，至今参加工作快两年时间了（从开始实习算起），对于这些东西慢慢的有颇多的感悟了。只要日后还继续从事软件开发，估计这种类似的感悟会更多。

……

恰巧，前几天在网上“不小心”看到一篇文章，记载着一位博友亦是粗读《人月神话》的感觉，正如我当时感觉，哈哈，可惜我以前喜欢用手写笔记，若那时候我也喜欢在网上写博客记录自己的学习笔记，那么今天我一定可以翻出来（可惜木有）……而不必我今天再次燃起冲动整理这篇笔记（博客）。

没事儿，那就重新花点时间，归结几点吧，见下：

1.

一条Brooks提出的诡异定律：给推迟的软件项目增加人手将使得项目更加推迟。但是根据其书中描述的不无道理，很有道理。

如何将一份繁多复杂的工作分配给许多人，相关的培训和程序员之间的交流都需要额外的工作。而这些（工作量）代价很多时候比你想象还要巨大。

（个人认为，该点可排除有个别情况--增加人手即真的加快项目进度，尤其小型团队于中型项目。）

2.

在从事系统设计时候，需明确关键的一点是，也是最重要的，概念的完整性。

概念已统一的系统更容易建造和测试，很大程度缩减了培训与交流的代价。要保证概念上的完整性，其概念的设计应该由一个人或者观念一致的小规模小组完成，需要具有足够权威性和统一设计能力。

3.

巴别塔项目失败的原因是缺乏组织和交流。良好的组织与高效的交流是相辅相成的。

良好的组织促进交流的高效，而高效的交流影响下一次良好的组织。

4.

若想要尽量保证项目的进度不被大幅度地推迟，制订进度表很重要。

进度表由里程碑和完成的时间组成，里程碑必须具体、明确、可界定，不允许存在模糊概念如差不多，50%（不好判断百分比情况），基本完成等。

引用链接在这里。

附图：

慎用C++异常

慎用C++异常
  --慎用try-throw-catch结构（C++代码）

---

# 背景描述
“The disadvantage of the __try{}__catch(Expression){} construction is that you may forget to guard a potentially incorrect code that may cause an exception that won't be handled by your program”

先分析上面这句说明吧，引用于这里。

该句引发讨论，思考，回忆，整理……最后导致写了篇该Blog。
具体原因与情况无解：）

# 示例剖析 
开始先举个简单示例吧，如下：
try
{
...
}
catch(int e1)
{


     if (1 ==e1)
          ...
     else  if (2 ==e1)
     ...
}
catch(char e2)
{


     if ('1' ==e2)
          ...
     else  if ('2' ==e2)
     ...
}

但当try语句块里面抛出异常，为以下情况之一：

1.  (3==e)，捕获到异常，但无设计对应异常处理操作；

2. 或('3'==e)，捕获到异常，同样无处理 ；

3. 或throw "error" (e为char*类型没做catch捕获处理)，无法捕获。

若出现该情况，亦可以算是代码分析与设计的不足，对于错误情况认知不够。
所以，选择下面的做法：

1. 要么就一概不用try-throw-catch结构处理异常情况；

2. 要么保证可以捕获并处理所有异常，但强烈不推荐catch(...)这样的捕获（虽然可捕获所有异常）！

当然，对于所有的异常情况做到完全的认知，很多情况都是很难的。So大多数的工程性代码鉴于安全可靠性，均不推荐或禁止代码使用try-throw-catch结构。

# 建议分享

还有一点值得说明，try-throw-catch结构的实现机制，在不同的操作系统都会有区别，同时不同系统对于该结构的支持程度也不一样。在程序的运行效率方面也是有影响的，当然比起纯粹的函数返回错误码再根据错误码处理异常的机制相差一些的（更多的详情细节找谷歌求解吧）。

针对异常情况，其他处理方案取代 :

step1. 返回错误码 .
step2. 根据不同错误码再做不同处理 .

btw.
 异常会降低程序效率 ,当程序需要编译器做优化时 ,会因为过多使用异常 ,而失效 .
 尽量少用使用异常 ,异常开销可能会比较大 ,而且不同编译器对于支持异常 ,其实现的效率也不一样 .

OK，总结至此。欢迎交流。

/个人总结 /junkun huang /2012-01-11/

（完）

总结，分享，交流与学习。

总结，分享，交流与学习。

---

总结，分享，交流与学习，就在这里开始吧，Mark！
我想在此开始写些技术博客,用于总结，分享，交流与学习。
希望多抽些时间，坚持下去。

加油！

2012下载库兄弟们合照

2012最新下载库兄弟们合照（突然今天又少了位同事 o o...）.jpg

祝大家2012新年快乐，工作顺利或事业发展！

【Hello】2011清远漂流游玩拍图一张

Hi ，阿杜Blogger！