HASH算法介绍

• Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一地确定输入值。
• 数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值。

struct linka {
int data;
linka next;
};
void reverse(linka& head) {
if(head ==NULL) return;
linka pre, cur, *ne;
pre=head;
cur=head->next;
while(cur) {
ne = cur->next; //将下一个节点保存
cur->next = pre; //将当前节点的下一个节点置为当前节点
pre = cur; //将当前节点保存为前一节点
cur = ne; //将当前节点置为下一节点
}
head->next = NULL;
head = pre;
}

linka reverse(linka p,linka& head) {
if(p == NULL || p->next == NULL) { //判断跳出条件
head=p; return p;//将链表切断，否则会形成回环
} else {
linka tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}

《编程珠玑》第1版是对我职业生涯早期影响最大的书之一，其中的许多真知灼见多年之后仍然使我受益匪浅。Jon在第2版中对素材进行了大量更新，许多新内容让我耳目一新。

在段式虚拟存储器中，虚存空间中能容纳的程序段数要比主存空间中能存放的相同长度的程序段数多得多。因此，必然会出现当主存中所有页面都已经被占用，或者所有主存空间都已经被占用，而又要从磁盘存储器中调入新页的情况。这时，必须从主存储器中淘汰掉一个不常用的页面，以便腾出主存空间来存放新调入的页面。下面介绍几种常用的替换算法：RAND算法,FIFO算法,LFU算法,LRU算法,OPT算法。

一群猴子排成一圈，按1,2,...,n依次编号。

然后从第1只开始数，数到第m只,把它踢出圈，

从它后面再开始数， 再数到第m只，在把它踢出去...，

如此不停的进行下去， 直到最后只剩下一只猴子为止，那只猴子就叫做大王。

要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。

目录
• 方法一 按逻辑依次去除
• 方法二 递归的算法
• 方法三:线性表应用
 方法一 按逻辑依次去除编辑本段回目录
<?php
/*
* filename: kingmonkey.php
* author: luochuan wang
* date: April 2nd, 2009
* descript: an arithmetic to a program
* program: 
   一群猴子排成一圈，按1,2,...,n依次编号。 
   然后从第1只开始数，数到第m只,把它踢出圈，
   从它后面再开始数，  再数到第m只，在把它踢出去...，
   如此不停的进行下去，  直到最后只剩下一只猴子为止，那只猴子就叫做大王。 
   要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。
*/

function getKingMokey($n, $m)
{
        $monkey[0] = 0;

        //将1-n只猴子顺序编号 入数组中[break]
        for($i= 1; $i<= $n; $i++)
        {
               $monkey[$i] = $i;
        }

        $len = count($monkey);

        //循环遍历数组元素(猴子编号)
        for($i= 0; $i< $len; $i= $i)
        {
              $num = 0;

             /*
              * 遍历$monkey数组，计算数组中值不为0的元素个数（剩余猴子的个数）
              * 赋值为$num，并获取值不为0的元素的元素值
             */
             foreach($monkey as $key => $value)
             {
                if($value == 0) continue;
                $num++;
                $values = $value;
             }

             //若只剩一只猴子 则输出该猴子编号(数组元素值) 并退出循环
             if($num == 1)
             {
                    echo $values;
                    exit;
             }

             /*
              * 若剩余猴子数大于1（$num > 1）
              * 继续程序
             */

             //将第$i只猴子踢出队伍(相应数组位置元素值设为0)
             $monkey[$i] = 0;

             //打印该猴子位置
             echo $i."";

            /*
             * 获取下一只需要踢出队伍的猴子编号
             * 在$m值范围内遍历猴子 并设置$m的计数器
             * 依次取下一猴子编号
             * 若元素值为0，则该位置的猴子已被踢出队伍
             * 若不为0，继续获取下一猴子编号，且计数器加1
             * 若取得的猴子编号大于数组个数
             * 则从第0只猴子开始遍历(数组指针归零) 步骤同上
             * 直到计数器到达$m值 * 最后获取的$i值即为下一只需要踢出队伍的猴子编号
             */

             //设置计数器
             for($j= 1; $j<= $m; $j++)
             {
                   //猴子编号加一，遍历下一只猴子
                   $i++;

                   //若该猴子未被踢出队伍,获取下一只猴子编号
                   if($monkey[$i] > 0) continue;

                   //若元素值为0，则猴子已被踢出队伍，进而循环取下一只猴子编号
                   if($monkey[$i] == 0)
                   {
                           //取下一只猴子编号
                           for($k= $i; $k< $len; $k++)
                           {
                                   //值为0，编号加1
                                   if($monkey[$k] == 0) $i++;

                                   //否则，编号已取得，退出
                                   if($monkey[$k] > 0) break;
                           }
                    }

                   //若编号大于猴子个数，则从第0只猴子开始遍历(数组指针归零) 步骤同上
                   if($i == $len) $i = 0;

                   //同上步骤，获取下一只猴子编号
                   if($monkey[$i] == 0)
                   {
                          for($k= $i; $k< $len; $k++)
                          {
                                   if($monkey[$k] == 0) $i++;

                                  if($monkey[$k] > 0) break;
                          }
                   }
            }
      }
}

//猴子个数
$n = 10;

//踢出队伍的编号间隔值
$m = 3;

//调用猴王获取函数

getKingMokey($n, $m);

?>

方法二 递归的算法编辑本段回目录$monkeys = array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10);  //monkey的编号
$m = 4;  //数到第几只的那只猴子被踢出去
/* 猴王算法*/
/*面向过程的实现 */
function killMonkey($monkeys , $m , $current = 0){
    $number = count($monkeys);
        $num = 1;
        if(count($monkeys) == 1){
            echo $monkeys[0]."成为猴王了";
            return;
        }
        else{
            while($num++ < $m){
                    $current++ ;
                    $current = $current%$number;
                }
                echo $monkeys[$current]."的猴子被踢掉了<br/>";
                array_splice($monkeys , $current , 1);
                killMonkey($monkeys , $m , $current);
        }
}
killMonkey($monkeys , $m);

最后这个算法最牛有网友给了解释：

居伽爱牛 

哦，是这样的，每个猴子出列后，剩下的猴子又组成了另一个子问题。只是他们的编号变化了。第一个出列的猴子肯定是a[1]=m(mod)n(m/n的余数)，他除去后剩下的猴子是a[1]+1,a[1]+2,…,n,1,2,…a[1]-2,a[1]-1，对应的新编号是1,2,3…n-1。设此时某个猴子的新编号是i，他原来的编号就是(i+a[1])%n。于是，这便形成了一个递归问题。假如知道了这个子问题(n-1个猴子)的解是x，那么原问题(n个猴子)的解便是：(x+m%n)%n=(x+m)%n。问题的起始条件：如果n=1,那么结果就是1。

方法三:线性表应用编辑本段回目录 /**
* 线性表应用（选首领问题）
*
* @param  $n  总数
* @param  $m  当报数到 m 时，m出列
* @return 最后剩下的数字
*/
function yuesefu($n,$m) { 
    $r=0; 
    for($i=2; $i<=$n; $i++) {
            $r=($r+$m)%$i; 
    }
    return $r+1; 
} 
print_r(yuesefu(3,3));
?>
 

哈希算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

【基本思想】

将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

二分搜索法的应用极其广泛，而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。

 使用PHP描述顺序查找和二分查找（也叫做折半查找）算法，顺序查找必须考虑效率，对象可以是一个有序数组
//二分查找（数组里查找某个元素）
function bin_sch($array, $low, $high, $k){
    if ($low <= $high){
        $mid = intval(($low+$high)/2);
        if ($array[$mid] == $k){
            return $mid;
        }elseif ($k < $array[$mid]){
            return bin_sch($array, $low, $mid-1, $k);
        }else{
            return bin_sch($array, $mid+1, $high, $k);
        }
    }
    return -1;
} [break]

1、顺序查找的基本思想
     基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。

2、顺序查找的存储结构要求
  顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。

3、基于顺序结构的顺序查找算法
（1）类型说明
  typedef struct{
    KeyType key；
    InfoType otherinfo； //此类型依赖于应用
   }NodeType；
  typedef NodeType SeqList[n+1]； //0号单元用作哨兵

（2）具体算法
  int SeqSearch(Seqlist R，KeyType K)
    { //在顺序表R[1..n]中顺序查找关键字为K的结点，
      //成功时返回找到的结点位置，失败时返回0
      int i；
      R[0].key=K； //设置哨兵
      for(i=n；R[i].key!=K;i--)； //从表后往前找
      return i； //若i为0，表示查找失败，否则R[i]是要找的结点
    } //SeqSearch
④顺序查找的优点
     算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。

⑤顺序查找的缺点
  查找效率低，因此，当n较大时不宜采用顺序查找

//顺序查找（数组里查找某个元素）
function seq_sch($array, $n, $k){
    $array[$n] = $k;
    for($i=0; $i<$n; $i++){ 
        if($array[$i]==$k){
            break;
        }
    }
    if ($i<$n){
        return $i;
    }else{
        return -1;
    }
}

算法思想：
　　将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
　　折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
　　算法步骤描述：
　　step1 首先确定整个查找区间的中间位置
　　mid = （ left + right ）/ 2
　　step2 用待查关键字值与中间位置的关键字值进行比较；
　　若相等，则查找成功
　　若大于，则在后（右）半个区域继续进行折半查找
　　若小于，则在前（左）半个区域继续进行折半查找
　　Step3 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。
　　折半查找的存储结构采用一维数组存放。
　　折半查找算法举例
　　对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。
　　折半查找的算法讨论：
　　优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
　　缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。
　　考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？
　　可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。