限制时空的循环左旋小节

一个基础的问题,常常会源于几点限制而上升到艰难解答的猜想,
比如:大数问题,经典的高精度算数。
大量问题,OI时代常常遇到的大量数据,算法不当常常导致超时.
内存限制问题,在很多极限内存限制的时候,算法截然不同,这个等下会提到.
时间限制问题,O(n^2)与O(nlogn)算法之间的区别,在于n为100万时,这两种算法的运行时间分别为3小时和1秒。

首先来个很简单的例子。实现单位字节(8 bits)内部循环左移。

要求:循环左移x位
基础:基本位操作

int leftmove(int x, unsigned char B)
{
    B = (B << x) | (B >> (8-x));
}

大部分时候我们会左移大得多的东西,例如字符串。
关于循环左移字符串,这里记录两个算法

要求:循环左移字符串
A: 
基础:迭代思想
旋转向量x其实就是交换ab的两段,得到向量ba。
假设a比b短,将b分成bl与br, 使 length(br) = length(a), 
交换 br与a, 得 br bl a 向量,则新任务是交换br与bl,与之前思想想通。

B:
基础:逆序思想(准确的说,近世代数)

一开始就分别对ab求逆序,ab-> ar b-> ar br 
然后对a‘b’整体求逆  (ar br)r->ba
例如对于”abcdefg“
i = 3;
reverse(0, i-1);  /* cbadefgh */
reverse(i, n-1);  /* cbahgfed */
reverse(0, n-1); /* defghabc */
此条目发表在C分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

邮箱地址不会被公开。 必填项已用*标注