慧庄－by 朱涛: 算法

显示标签为“算法”的博文。显示所有博文

2009-04-13

UVa 3n+1 问题

UVa 3n+1 问题

1. 问题描述

编号 :100.

简单描述 : 就是对一个整数 ( 大于等于 1), 不断按照这样的规律进行运算 , 即如果当前数是偶数 , 则下一个数为当前数除以 2, 如果当前数为奇数 , 则下一个数为当前数乘 3 加 1, 整个过程直到计算到 1 为止 . 那么形成的数列的长度称为 cycle-length.

问题的输入是 : 给定一个区间 [a,b]

问题的输出为 : 输出给定区间 ( 含端点 ) 所以数的 cycle-length 的最大的 cycle-length.

详细描述可参见这里 .

2. 问题分析

2.1 直观分析

最直观的方法当然是采用蛮力法 ( 即 brute-force), 将给定区间的每个数求出其 cycle-length, 然后在所以的 cycle-length 中找出最大的即可 .

2.2 优化

优化是建立在分析的基础之上 .

我们先对一个简单例子进行实验 .

例如给定区间为 B[1,10], 即 1,2,3,4,5,6,7,8,9,10

通过简单分析我们可以知道 , 通常较大的数具有较大的 cycle-length, 所以我们可以首先取 A=9( 为什么不取 10, 是因为 9 在一次处理后可变为 28, 大于 10) 按照给定的规律来进行如下 :

9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

可以看出 , 上面红色标记的部分 , 处于给定的区间内 , 而且它们的 cycle-length 显然是小于当前的数 9 的 cycle-length, 所以这些数可以从给定的区间内剔除掉 , 记住当前的 cycle-length, 于是

经过一次的操作后 , 给定的区间变为 3,6

继续按照这个方法进行 , 直至这个区间为空 , 停止 , 其中最大的 cycle-length 即为所求 .

2.3 得出算法

算法的描述同 2.2 处优化部分的分析 , 具体的算法描述可见 3.

3. 算法描述

算法伪代码 ( 类 C) 描述如下 :

function getMCL

B[left, right]; // 为给定的区间

mcl = 0; //mcl 指 max-cycle-length

while !B.empty()

{

A = getCandidate(B);// 这个函数是用来找出 B 区间内当前最适合处理的元素 ,

// 一般是最大的奇数 , 即预计可能具有较大 cycle-length 的元素

ccl = 1; //ccl 是指 current-cycle-length

while (A!=1)

{

ccl++;

A = (A%2)?(3*A+1):(A/2);

if find(B,A) // 这个函数是用来判断 B 区间内是否存在中间结果 A

pop(B,A); // 有则剔除

}

mcl = (mcl<ccl)?ccl:mcl;

}

return mcl;

4. 具体实现

Cpp代码
#include "iostream"

using namespace std;



int getCandidate(int B[], int base, int n)

{

    int i;

    for (i = n-1; i>=0; i--)

    {

        if (((base+i) % 2)&&(B[i]==0))

            return i;

    }

    for (i = n-1; i>=0; i--)

    {

        if (!B[i])

            return i;

    }

    return -1;

}

int nadd2(int left, int right)

{

    int Blength = right - left + 1;

    int length = Blength;

    int *B = new int[length];

    for (int i=0; i<length; i++)

        B[i] = 0;

    int mcl = 0;

    while (length > 0)

    {

        int ccl = 1;

        int pos = getCandidate(B, left, Blength);

        if (pos==-1)

            break;

        B[pos] = 1;

        length--;

        int A = pos+left;

        while (A!=1)

        {

            ccl ++;

            A = (A%2)?(3*A+1):(A/2);

            int Apos;

            if ((A-left>Blength)||(B[A-left])||(A<left))

                Apos = -1;

            else

                Apos = A-left;



            //B[Apos] = 1;

            if (Apos!=-1)

            {

                B[Apos] = 1;

                length --;

            }

        }

        mcl = (mcl<ccl)?ccl:mcl;

    }

    delete[] B;

    return mcl;

}

int main()

{

    int left, right;

    while(cin>>left>>right)

        cout<<left<<" "<<right<<" "<<nadd2(left,right)<<endl;

    return 0;

}

#include "iostream" using namespace std;  int getCandidate(int B[], int base, int n) {  int i;  for (i = n-1; i>=0; i--)  {   if (((base+i) % 2)&&(B[i]==0))    return i;  }  for (i = n-1; i>=0; i--)  {   if (!B[i])    return i;  }  return -1; } int nadd2(int left, int right) {  int Blength = right - left + 1;  int length = Blength;  int *B = new int[length];  for (int i=0; i<length; i++)   B[i] = 0;  int mcl = 0;  while (length > 0)  {   int ccl = 1;   int pos = getCandidate(B, left, Blength);   if (pos==-1)    break;   B[pos] = 1;   length--;   int A = pos+left;   while (A!=1)   {    ccl ++;    A = (A%2)?(3*A+1):(A/2);    int Apos;    if ((A-left>Blength)||(B[A-left])||(A<left))     Apos = -1;    else     Apos = A-left;         //B[Apos] = 1;    if (Apos!=-1)    {     B[Apos] = 1;     length --;    }   }   mcl = (mcl<ccl)?ccl:mcl;  }  delete[] B;  return mcl; } int main() {  int left, right;  while(cin>>left>>right)   cout<<left<<" "<<right<<" "<<nadd2(left,right)<<endl;  return 0; }

5. 复杂性分析

主要的耗时部分是二层循环部分 , 而外层循环的次数主要取决于内层循环在区间内的命中率 . 没有进行过统计学的分析 , 但只要 candidate 选取合适 , 每次内层循环会有大于 50% 的命中率 .

假设区间内数 A 的内层循环次数 ( 即由 A 按照规则变为 1 的 cycle-length) 为 X, 平均命中率为 p, 那么时间复杂度为 :

T(n) = X*T(n*(1-p)) // 其中 X 为平均的 cycle-length

6. 备注

在实现过程中 , 最初使用的是 C++ 中的 vector, 但运行时的实际耗时比使用数组的蛮力法还要长 , 经过分析 , 这是因为编译器在维护 vector 这个数据结构时所耗时长是比较大的 , 特别是当使用 vector 的 earse 方法来删除某个特定元素时 . 所以最后还是使用最基本的数组来实现 , 用标记来指示删除状态 .

所以在实际的算法实现中 , 数据结构的选取也是非常重要的 , 所谓的程序 = 算法 + 数据结构是也 .

可以改进的地方包括有 :getCandidate 函数的算法 , 即如何预估一个具有较长 cycle-length 的元素 ; 还有当内层循环出现在区间内已标记为删除状态的元素中时 , 这时内层循环可终止 .

字符匹配问题（1）――Rabin-Karp算法

字符串匹配问题（ 1 ）—— Rabin-Karp 算法

1. 问题描述

给定目标字符串 T[0..n-1] （基于 0 的数组，数组长度为 n ），和模式串 P[0..m-1] ，问 P 可否匹配 T 中的任意子串，如果可以，返回匹配位置。

2. 问题分析

直观分析

brute-force 的蛮力法，适用于较小规模的字符串匹配。

优化

主要介绍 3 种优化办法，分别具体为： Rabin-Karp 算法，有限自动机和 KMP 算法。将分为 3 篇博文分别讨论。本小节主要介绍 Rabin-Karp 算法。

得出算法

Rabin-Karp 算法（以下简称为 RK 算法），是基于这样的思路：即把串看作是字符集长度进制的数，由数的比较得出字符串的比较结果。例如，给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ，∑长度为 d=10 ，那么任何以∑为字符集的串都可看作 d （此处为 10 ）进制的数。

记模式串 P[0..n-1] 对应的数值为 P ， T[0..n-1] 所有长度为 m 的子串对应的数值为 t_s ，设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。

那么， t_s 即为 T[s..s+m] 对应的数值，这里 0<=s<=n-m-1 。

P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))

同样 t₀ 也可类似求得。

最重要的是如何从 t_s 求出 t_s+1 。

t_s+1 =T[s+m]+d*(t_s +d^m-1 *T[s])

注：此处是该算法的关键，即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象，举个例子就比较明白了，设 x=12345 ，现在是已知长度为 3 的数值 234 ，现在要求 345 对应的数值，可以这样来得到： 345 = 5 + 10*(234-10² *2)

3. 算法描述

求出所有 m 长度子串所对应的数值，对数值进行比较，继而得出子串是否匹配。当模式串长度很大时，这时对应的数值会很大，比较起来比较麻烦，可使用对一个大奇数取模后进行比较。

4. 具体实现

这里实现的只是m值较小时的情形，大整数需要特定的类的支持（如可自定义大整数类），选取10进制的数是为了方便起见，当然字母也是OK的。

Cpp代码
#include "iostream"

#include "string"

#include "cmath"

using namespace std;



// get the value of the character in the set

int getV(char p, string set)

{

    for(int i=0; i<set.length(); i++)

    {

        if (p==set[i])

            return i;

    }

    return -1;

}

// d is the size of the character set

int RK(string T, string P,string set)

{

    int d = int(set.length());

    int n = T.length();

    int m = P.length();

    int h = pow(double(d), m-1);

    int p=0;

    int t = 0;

    for(int i=0; i<m; i++)

    {

        p = d*p + getV(P[i],set);

        t = d*t + getV(T[i], set);

    }

    for (int s=0; s<=n-m; s++)

    {

        cout<<"p,t is "<<p<<","<<t<<endl;

        if (p==t)

            return s;

        if (s<n-m)

            t = getV(T[s+m],set)+d*(t-h*getV(T[s],set));

    }

    return -1;

}

int main()

{

    // set is the character set

    string set= "0123456789";

    // pattern P

    string P = "2365";

    // T is the string to match

    string T = "258569236589780";

    int i = RK(T, P, set);

    cout<<"the postition is:"<<i<<endl;

    return 0;

}

#include "iostream" #include "string" #include "cmath" using namespace std;  // get the value of the character in the set  int getV(char p, string set) {  for(int i=0; i<set.length(); i++)  {   if (p==set[i])    return i;  }  return -1; } // d is the size of the character set int RK(string T, string P,string set) {  int d = int(set.length());  int n = T.length();  int m = P.length();  int h = pow(double(d), m-1);  int p=0;  int t = 0;  for(int i=0; i<m; i++)  {   p = d*p + getV(P[i],set);   t = d*t + getV(T[i], set);  }  for (int s=0; s<=n-m; s++)  {   cout<<"p,t is "<<p<<","<<t<<endl;   if (p==t)    return s;   if (s<n-m)    t = getV(T[s+m],set)+d*(t-h*getV(T[s],set));  }  return -1; } int main() {  // set is the character set  string set= "0123456789";  // pattern P  string P = "2365";  // T is the string to match  string T = "258569236589780";  int i = RK(T, P, set);  cout<<"the postition is:"<<i<<endl;  return 0; }

5. 参考资料

[1] Thomas H. Cormen Introduction to Algorithms