算法基元（to be continued)

74 阅读 0 评论 49 点赞

我是靠谱客的博主感动电脑，最近开发中收集的这篇文章主要介绍算法基元（to be continued)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

个人觉得，算法是输入->输出的一种解决方法。这意味算法问题本身需要先建模为有输入，有输出的样子。另外，无论什么算法，都是基元算法的组合或变形。

1. 电梯调度

二级排序。一级为方向，二级为楼层。

2. 最大数字子串：摒弃负数的贪婪扩展

3. 树的变相遍历，递归

4. 穷举法，需要保证穷举是朝不断靠近结果的方向

5. 关键字的互相替换

for,while可以用递归，if,else可以用switch case，三目?:。另外，循环是让相同代码执行N遍，所以用new object+全局变量的方式可以达到

6. 广度优先搜索，利用队列

7. 计算机模拟逻辑

穷举法的变种。例如下题：

“有4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任
意两张牌，
A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，
A 说不知道，B 说不知道，C 说不知道，然后A 说知道了。
请教如何推理，A 是怎么知道的。
如果用程序，又怎么实现呢？”

首先第一步，建立一个可以列出所有情况的循环

第二步，在每种情况下判断是否满足逻辑，以本题为例，需要满足如下逻辑：

1. A,B,C第一轮大家都不知道。这意味着，不能出现类似1,1;1,1;或2,2;2,2（即，同时两个人都是1或2.因为这种情况下，有一种牌已经用完，那么毫无疑问，自己头上是另一种牌）

2. A根据B,C说不知道后，就可以推断出自己头上的牌。这种逻辑仍然用穷举法解决。也就是说，当B,C固定时，A只能有一种解法（否则A没有办法确认自己头上的牌）。

综上所述，代码如下。

#include <iostream>
using namespace std;
r:1,b:2
int a[2]={0};
int b[2]={0};
int c[2]={0};

void count(int *a, int *b, int *c, int *r, int *bl)
{
    if(a[0] ==1)
        (*r)++;
    else
        (*bl)++;

    if(a[1] ==1)
        (*r)++;
    else
        (*bl)++;

    if(b[0] ==1)
        (*r)++;
    else
        (*bl)++;

    if(b[1] ==1)
        (*r)++;
    else
        (*bl)++;

    if(c[0] ==1)
        (*r)++;
    else
        (*bl)++;

    if(c[1] ==1)
        (*r)++;
    else
        (*bl)++;
}

bool verify()
{
    in the case of B,C, try to figure out the A
    if there is only one solution for A, that is it
    int sCount=0;//solution count;
    int ta[2]={0};//tmp a

    for(int i=0;i<3;i++)
    {
        switch(i)
        {
        case 0:
            ta[0]=1;
            ta[1]=1;
            break;

        case 1:
            ta[0]=2;
            ta[1]=2;
            break;

        case 2:
            ta[0]=1;
            ta[1]=2;
            break;
        default:
            break;
        }

        first check the existence of such ta
        int r=0,bl=0;
        count(ta,b,c,&r,&bl);
        if(r>4 || bl>4)
            continue;

        check the first round of "i don't know"
        int nAllRed=0;
        int nAllBlue=0;
        if(ta[0]==1&&ta[1]==1)
            nAllRed++;
        else if(ta[0]==2&&ta[1]==2)
            nAllBlue++;

        if(b[0]==1&&b[1]==1)
            nAllRed++;
        else if(b[0]==2&&b[1]==2)
            nAllBlue++;

        if(c[0]==1&&c[1]==1)
            nAllRed++;
        else if(c[0]==2&&c[1]==2)
            nAllBlue++;

if(nAllRed==2 || nAllBlue==2)
continue;

        /pass all the verify,solution++
        sCount++;
    }

    if(sCount==1 && a[0]==ta[0] && a[1]==ta[1])
        return true;
    else
        return false;
}

void card()
{
    for(int i=0;i<3;i++) //3*a, rb,rr,bb
    {
        for(int j=0;j<3;j++) //b
        {
            for(int k=0;k<3;k++) //c
            {
                if(i==0)
                {
                    a[0]=1;
                    a[1]=1;
                }
                else if(i==1)
                {
                    a[0]=2;
                    a[1]=2;
                }
                else if(i==2)
                {
                    a[0]=1;
                    a[1]=2;
                }

                if(j==0)
                {
                    b[0]=1;
                    b[1]=1;
                }
                else if(j==1)
                {
                    b[0]=2;
                    b[1]=2;
                }
                else if(j==2)
                {
                    b[0]=1;
                    b[1]=2;
                }
                if(k==0)
                {
                    c[0]=1;
                    c[1]=1;
                }
                else if(k==1)
                {
                    c[0]=2;
                    c[1]=2;
                }
                else if(k==2)
                {
                    c[0]=1;
                    c[1]=2;
                }
                int r=0,bl=0;
                count(a,b,c, &r,&bl);
                if(r>4 || bl>4)
                    continue;

                if(verify() == true)
                {
                    cout<<"found:"<<endl;
                    cout<<"A:"<<a[0]<<" "<<a[1]<<endl;
                    cout<<"B:"<<b[0]<<" "<<b[1]<<endl;
                    cout<<"C:"<<c[0]<<" "<<c[1]<<endl;
                };
            }
        }
    }

}

void main()
{
card();
}

8. 以时间换空间。例：

“

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。

”

如果不考虑内存，我们可以分配一个大空间来完成。在限制空间的情况下，就可以通过多次部分反转实现

9. 最优算法（大概意思，不知用得对不对）

递归，将问题不断化解为小问题，所以每次只要处理当前问题，而当前问题和下一个小问题只是在量上有差异，处理本质是一样的。

10. 进程同步互斥

多线程产生的，对于客观事实（前提是共享资源）的不符。比如一个线程读了一个数，另一线程改变了这个数，从而产生了第一个线程不符。

所以实质是如何克服这种共享资源的不符。

互斥：个人认为，是一种自己使用，自己释放的竞争方式。进程间关系只是使用共享资源而已

同步：是两个之间互相协同使用，释放的过程。进程间除了使用同种共享资源，还有其它依赖。或者，也可能它们并不是直接在相同资源上产生共享，而是在两种资源上（但同时这两种资源又产生了依赖）。

我觉得有两种方法来解决，

其一，是通过将对临界区的相关操作全部做成原语，不可打断。

其二，用信号量和P/V。

sem: 正数时表示当前资源可用数，负数表示正在等待的进程数

P: 原语

(1) sem减1；

(2) 若sem减1后仍大于或等于

零，则进程继续执行；

(3) 若sem减l后小于零，

则该进程被阻塞在与该信

号相对应的队列中，然后

转进程调度。

V：原语

(1) sem加1；

(2) 若相加结果大于零，

进程继续执行；

(3) 若相加结果小于或等于

零，则从该信号的等待

队列中唤醒一等待进程，

然后再返回原进程继续

执行或转进程调度。

11. 动态规划，贪心算法，分治法，最优解

个人认为，动态规划和分治法一样，都是通过将问题不断细化得出最优解。而分治法细化出的小问题，彼此间是没有关联的;相反，动态规划则处理细化问题有关联的情况。换句话讲，动态规划能解的，分治也能解。但效率上，因为动态规划考虑到了冗繁（小问题间的解结果可以互相借鉴），所以比分治法在解类似问题时高效。

贪心算法：以下定义引用自网络“在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解”。

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解。

我并不太理解上面所说“最优”是什么概念。不过在我看来，贪心算法是一直朝一个逐渐接近目标的方向发展，直至证明这个方向确实已经无法行通，再另辟蹊径。

也就是说，最优解它是把问题不断细化为N步（递归，问题越来越细，有点像子集的意思），而解决时每个细化都得到一个最佳方案，整个合成起来就是解法。而贪心算法则是把问题平均切割，得到切割后的局部解，再将局部解合成，得到最佳解。这样子说来，有点一个横向，一个纵向的感觉。

12. 概率相关

概率：分为古典概率、试验概率和主观概率

某一事件的概率=出现含有此事件的结果的数量/总共出现的结果数

古典：有两个性质。其一，等概率性。其二，结果有限可知。所有可能出现的结果，它们的概率是一样的。比如掷骰子，有6种结果，每种都是1/6。

试验概率：以下定义引自百科---“在许多实际问题中，要将全部观察或试验结果列举出来往往是不可能的，同时，试验结果的等可能性假定也是很难成立的，难以按古典概率计算概率，而只能利用实际频数数据来估计概率。因此，根据大量的、重复的统计试验结果计算随机事种各种可能发生结果的概率，称为试验概率或频率概率”。

主观概率：以下引自百科---“主观概率定义：合理的信念的测度。某人对特定事件会发生的可能的度量。即他相信(认为)事件将会发生的可能性大小的程度。这种相信的程度是一种信念，是主观的，但又是根据经验、各方而后知识，对客观情况的了解进行分析、推理、综合判断而设定(Assignment)的，与主观臆测不同。例：考博士生、掷硬币、抛图钉”，这些事件本身很难用试验概率来验证。

排列组合（这两个都是无放回的）：总的来讲，它们都是从n个元素中取m个（无放回，m<n）的取法数量。

排列是讲顺序的，组合则不需要顺序。举例： ⑴．站成一排拍照。(这个需要顺序的，是排列)； ⑵．选出5个人去开会。(这个不需要顺序，是组合)。

排列 P(n,m)= n！/(n-m)！，组合 C(n,m) = n！/(m！*(n-m)！)

对于排列公式的理解：有m个坑，需要从n个元素中取来填满。步骤是：填第一个坑时，n个元素取一个的取法有 n种;剩下n-1取第二个的取法有n-1,所以总共有n*(n-1)*… = n!/(n-m)!

对于组合公式的理解：除了上述情况外，因为固定的m个球的不同排列，对于组合来讲是一样的（比如你拿出了3个球，对于组合来讲，是一种情况，对于排列来讲，这3个球还能有3!种排法），所以我们要在排列的种数上，扣除这种情况，即得以上公式。

13. 大文件处理

排序：用归并。其它见另一篇博文 http://blog.csdn.net/uiop78uiop78/archive/2011/03/22/6268918.aspx