1. 2012校招-sonicWALL的两道编程笔试题

    求二叉树中两个结点的最近公共祖先

    比如:对于树

             A
           /
          B
        /   \
       C     D
     /   \
    E     F
    

    结点D,F的最近公共祖先为B

    实现:见源码

    求二进制整数部分bits求反后的值

    比如:对于整数0b1001101,将第2(begin)到第5(end)位(从右往左计数)上的bit求反,得到0b1110001。

    #include <stdio.h>
    
    int reverse_somebits(int a, int begin, int end)
    {
        return a^((1<<end)|((1<<end)-1))^((1<<begin)-1);
    }
    
    void ten_to_two(int a)
    {
        if ...
    Tagged as : 笔试 算法
  2. pi的一种并行算法

    我们都知道圆周率pi的值是3.141592653...,那么这个值是怎么算出来的呢?一种方式是通过某种方式算出圆的面积或者周长,然后根据公式$ S = pi \times r^2 $(或$ L = 2 \times pi \times r $)算出pi的值。但如何用计算机通过某种算法计算而得?有没有并行的算法?

    Introduction to Parallel Programming and MapReduce一文中介绍了一种基于概率的并行算法---假设有个正方形,里面有个內切圆。

    sample pic

    设内切圆的半径为$ r $,则

    正方形的面积为$ S_z = 4r^2 $

    内切圆的面积为$ S_y = pi \times r^2 $

    那么$ pi = \frac{ S_y }{ r^2 } = \frac{ S_y }{ S_z ...

    Tagged as : 算法 并行 Python

Page 1 / 1