时光博客

算法设计

DIV7的位运算实现

题目如下

一个数除以7,不能用除法,乘法以及模运算,写出算法并实现

解题思路

既然不能用常规的函数,那么我们就像想别的办法,最容易想到的,当然还是位运算,关于位运算,leetcode上有一道题,属于经典的位运算题目,我博客之前也做过分析,猛击这里阅读「 Single Number II 

首先假设这个数为N,这个数可以表示为 N = 8 * A + B,为什么要用8,是因为8是最靠近7的,且可以通过二级制位移来产生的数字,例如:A >> 3 = A * 2 ^ 3 = A * 8

有了上面的结论后,那么就有了下面的递归

equation.png - 大小: 1.75 KB - 尺寸: 282 x 18 - 点击打开新窗口浏览全图

从上面的公式中很容易看出来递归,那么A、B究竟该怎么表示呢?回到公式 N = 8 * A + B,不难看出,

A = N / 8  且 B = N & 7

A = N / 8 很好理解,可以看做8是被除数,N是商

B = N & 7 这个又回到了,我们的位运算的与运算上,因为B < 8,所以要获得B 只需要获取 N 的二级制最小位开始的后三位即可,所以这里是 & 0111,直接返回后3位的值

上面的理解了,程序就很容易写出来了

代码如下

#include <stdio.h>
int div7(int n) {
    if(n < 8)
    {
        return (n + 1) >> 3; //此处+1是为了处理n为7的情况
    }
    else
    {
        return (n >> 3) + div7((n >> 3) + n & 7);
    }
}
int main(){
    int n = 14;
    int x;
    x = div7(n);
    printf("%d div 7 is : %d\n", n, x);
} 

编译之后运行 14 div 7 is : 2

这里留一道地考题,如何求 任意数正整数对7求余,同样不利用乘法、除法、取模

妙用PHP数组函数实现笛卡尔积

之前我写过一篇关于笛卡尔积的2个版本的PHP实现,在网上看到一篇结合PHP数组函数和递归实现的版本。代码如下:

<?php

$arr = array(
    array(1),
    array(2,3),
    array(4,5,6)
);

fun($arr);
print_r($res);

function fun($arr, $tmp = array())
{
    foreach(array_shift($arr) as $v)
    {
        $tmp[]  = $v;
        if($arr)
        {
            fun($arr, $tmp);
        }
        else
        {
            $GLOBALS["res"][]   = implode("", $tmp);
        }
        array_pop($tmp);
    }
}

?>

下图是我对该版本算法运行的简易流程图:

flow.png - 大小: 10.42 KB - 尺寸:  x  - 点击打开新窗口浏览全图

说妙用是因为,利用array_shift实现数组的剔除,来实现遍历,另一个妙用array_pop实现数组的弹出,避免在递归中出现的重复值。

笛卡尔积算法,二维数组矩阵算法

给定一个数组: 

$list ['a'] = array (1,2,3); 
$list ['b'] = array (1,2); 
$list ['c'] = array (1,2,3,4);
...

要求输出这样:111,112,113,114,121,122,123.....

以上结果其实就是笛卡尔积下面为我实现的2个版本

继续阅读

©2008-2017 - 时光博客 Ucloud

京ICP备15052479号返回顶部