蓝桥杯比赛算法总结

发表于 | 分类于
本文字数： 1.6k | 阅读时长 ≈ 4 分钟

今天突然想把我自己在蓝桥杯比赛时准备的一些算法记录下来，以便翻阅。

蓝桥杯官网

  1. 斐波那契（记忆化搜索） 

    1
    2
    3
    4
    5
    6
    int memo[MAX_N + 1];  
    int fib(int n) {  
    	if (n <= 1) return n;  
    	if (memo[n] != 0) return memo[n];  
    	else return memo[n] = fib(n-1) + fib(n-2);  
    }

  2. 全排列n个元素(非常好用) 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //k：当前交换位置与其后元素交换  
    public static void f(char[] data, int k){  
    	if (k == data.length) {  
    		for (int i = 0; i < data.length; i++)  
    			system.out.print(data[i] + " ");  
    		system.out.println();  
    	}  
    	for (int i = k; i < data.length; i++) {  
    		char t = data[k]; data[k] = data[i]; data[i] = t;//试探  
    		f(data, k + 1);  
    		char t = data[k]; data[k] = data[i]; data[i] = t;//回溯  
    	}  
    }

  3. 辗转相除法求最大公约数 

    1
    2
    3
    4
    int gcd(int a, int b) {  
    	if (b == 0) return a;  
    	else return gcd(b, a % b);  
    }

  4. 埃氏筛法（搜索n以内的所有素数） 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int prime[MAX_N];//第i个素数  
    bool is_prime[MAX_N + 1];  

    //返回n以内素数的个数  
    int sieve(int n) {  
    	int p = 0;
    	for (int i = 0; i <= n; i++)  
    		is_prime[i] = true;  
    	is_prime[0] = is_prime[1] = false;  
    	for (int i = 2; i <= n; i++) {  
    		if (is_prime[i]){  
    			prime[p++] = i;  
    			for (int j = 2*i; j <= n; j += i)  
    				is_prime[j] = false;  
    		}  
    	}  
    	return p;  
    }

  5. 快速幂运算（反复平方法） 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //计算：x^n % mod  
    int mod_pow(int x, int n, int mod) {
    	int res = 1;  
    	while (n > 0) {  
    		if (n & 1)  
    			res = res * x % mod;  
    		x = x * x % mod;  
    		n >> = 1;
    	}  
    	return res;  
    }

我总觉得要把静态博客玩成动态博客才有意思，所以我又无耻的从Dribbble拖了张动图，哈哈o(∩_∩)o。

注：图片来自于Dribbble。

————————原创文章，未经许可，请勿转载！！！————————