Chinaunix

标题: 求一最大公约数算法 [打印本页]

作者: djyos 时间: 2008-12-02 13:02
标题: 求一最大公约数算法
有一队列，队列中每个节点有一个整数成员，队列长度是动态的，最初只有一个结点，每次添加结点或者删除结点时重新计算最大公约数。

作者: alexhappy 时间: 2008-12-02 13:03

原帖由 djyos 于 2008-12-2 13:02 发表
有一队列，队列中每个节点有一个整数成员，队列长度是动态的，最初只有一个结点，每次添加结点或者删除结点时重新计算最大公约数。

那就算喽

作者: 5毛党党员 时间: 2008-12-02 13:08
lz的意思是不是找个位置保存现在队列的最大公约数，下次插入就可以减少计算量了？

作者: 5毛党党员 时间: 2008-12-02 13:10
不过我没有想到删除节点时有什么好方法，似乎只能重新计算？

作者: cugb_cat 时间: 2008-12-02 13:19
添加的时候，添加一个算一个就ok，删除的话，重算可能更简单一点。

作者: cjaizss 时间: 2008-12-02 13:42
一起做相除法,先找最小的数,然后其他的都对它做除法,过程中记录最小的余数......
如此循环,直到每个都除尽
当然,这是对一堆事先没有作任何处理的数的算法.
如果数是一个个进的,每进一个就和之前的最大公约数来作辗转相除求得最大公约数,就是最新的最大公约数

[ 本帖最后由 cjaizss 于 2008-12-2 14:49 编辑 ]

作者: cjaizss 时间: 2008-12-02 13:49
标题: 回复 #6 cjaizss 的帖子
另外,余数为0(除尽)不算最小的余数,而算最大的余数

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)