少年游

欲买桂花同载酒，终不似，少年游。

0%

最近校招算法题整理

发表于 更新于 分类于
算法

幂次

判断一个数的幂次

个位数是2的n次方的尾数循环为：2486 2486 2486 2486….
个位数是3的n次方的尾数循环为：3971 3971 3971 3971….
[公式] : n&(n-1)判断n中有多少个1;

  • 判断一个数是2的幂次
    [code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//
// Created by Paul on 2016/4/20.
//
    #include "iostream"
    int is2sN(int n);

    int main(){
        for(int i = 1;i < 1000;i ++){
            int flag = is2sN(i);
            if(flag == 0){
                printf("%d \n",i);
            }
        }
    }

    int is2sN(int n){
        return n & (n - 1);
    }
  • 判断一个数是3的幂次
    [code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
// Created by Paul on 2016/4/20.
//
    #include "iostream"
    #include "math.h"

    int is3sN(int n);

    int main(){
        for(int i = 1;i < 1000;i ++){
            int flag = is3sN(i);
            if(flag == 1)printf("%d  %d \n",i,flag);
        }
    }

    int is3sN(int n){
        double a = log(n)/log(3);
        if(floor(a) == ceil(a))return 1;
    }

[完全数]梅森素数

大数学家欧几里德曾推算出完全数的获得公式：如果2^p-1质数,那么(2^p-1)2^(p-1)便是一个完全数.

1
2
3
4
example:
         p=2,2^p-1=3是质数,(2^p-1)*2^(p-1)=3*2=6
         p=3,2^p-1=7是质数,(2^p-1)*2^(p-1)=7X4=28
         p=5,2^p-1=31是质数,(2^p-1)*2^(p-1)=31X16=496

但是2^p-1什么条件下才是质数呢?当2^p-1是质数的时候,称其为梅森素数!顾名思义,就是梅森第一个系统地研究这种形式的素数的!事实上,至今(2006.9.4)为止,人类只发现了44个梅森素数,也就是只发现了44个完全数!

[算法]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//
// Created by Paul on 2016/4/20.
//
    #include "iostream"
    int isPerfectNumber(int n);

    int main(){
        for(int i = 1;i < 10000;i ++){
            int flag = isPerfectNumber(i);
            if(flag == 1){
                printf("%d \n",i);
            }
        }
    }

    int isPerfectNumber(int n)
    {
        if(n < 6)return 0;
        int i = 2;
        int sum = 1;
        while(i < n/2 + 1){
            if(n % i == 0)sum += i;
            i ++;
        }
        if(sum == n)return 1;
        else return 0;
    }