主题:一个小方法
有时候可能需要用到循环队列,通常我们会这样遍历队列:
如果需要一个N个元素的循环队列,用sub做下标,f表示队列的头,t表示尾部
for ( sub=f; sub != t ; )
{
...
sub = ++sub>=N ? 0 : sub;
}
其实原理是一样的,只不过是用查表法来实现这一功能,下面我拿斐波那契数列来举例。
f(n) = f(n-1) + f(n-2);
下面的 b1,b2就是分别表示f(n-1),f(n-2)这两项的下标,cur表示的就是f(n)这一项的下标;
ret[cur]保存的是f(n),ret[b1],ret[b2]分别表示的是f(n-1),f(n-2);
最开始ret放的是f(0),f(1),f(2);
计算f(3)的时候,b2,b1,cur按着顺时针的方向旋转一次;以后每次计算f(n)都会旋转一次。
下面是代码: [code=c]
#include <limits.h>
#include <errno.h>
#if LONG_LONG_MAX != 9223372036854775807LL
#error sizeof(unsigned long long) must be 4
#endif
unsigned long long
( fun )(unsigned long long number)
{
const char sub[]={1,2,0}; /* 就是这个表 */
char b2=0, b1=1, cur=2;
unsigned long long ret[]={0,1,1}, mask=(1ULL<<63);
if (number<3) return ret[number];
while(--number>1)
{
ret[ cur=sub[cur] ] = ret[ b1=sub[b1] ] + ret[ b2=sub[b2] ];
//ret[ cur=(cur+1)%3 ] = ret[ b1=(b1+1)%3 ] + ret[ b2=(b2+1)%3 ];/* %如果不能用&代替,建议不要用这个方案 */
if (ret[cur] & mask) /* 溢出 */
{
errno = ERANGE;
return ((unsigned long long)-1);
}
}
return ret[cur];
}
[/code]
如果需要一个N个元素的循环队列,用sub做下标,f表示队列的头,t表示尾部
for ( sub=f; sub != t ; )
{
...
sub = ++sub>=N ? 0 : sub;
}
其实原理是一样的,只不过是用查表法来实现这一功能,下面我拿斐波那契数列来举例。
f(n) = f(n-1) + f(n-2);
下面的 b1,b2就是分别表示f(n-1),f(n-2)这两项的下标,cur表示的就是f(n)这一项的下标;
ret[cur]保存的是f(n),ret[b1],ret[b2]分别表示的是f(n-1),f(n-2);
最开始ret放的是f(0),f(1),f(2);
计算f(3)的时候,b2,b1,cur按着顺时针的方向旋转一次;以后每次计算f(n)都会旋转一次。
下面是代码: [code=c]
#include <limits.h>
#include <errno.h>
#if LONG_LONG_MAX != 9223372036854775807LL
#error sizeof(unsigned long long) must be 4
#endif
unsigned long long
( fun )(unsigned long long number)
{
const char sub[]={1,2,0}; /* 就是这个表 */
char b2=0, b1=1, cur=2;
unsigned long long ret[]={0,1,1}, mask=(1ULL<<63);
if (number<3) return ret[number];
while(--number>1)
{
ret[ cur=sub[cur] ] = ret[ b1=sub[b1] ] + ret[ b2=sub[b2] ];
//ret[ cur=(cur+1)%3 ] = ret[ b1=(b1+1)%3 ] + ret[ b2=(b2+1)%3 ];/* %如果不能用&代替,建议不要用这个方案 */
if (ret[cur] & mask) /* 溢出 */
{
errno = ERANGE;
return ((unsigned long long)-1);
}
}
return ret[cur];
}
[/code]