标签 数据结构、算法与应用 下的文章

数据结构、算法与应用 第一张练习 19，20

阶乘 n! Factorial

阶乘是非常常见的数学计算以及算法入门问题。 其中 0,1,2,6,24,120... fn = n ( n<=1 ) fn = n * fn(n-1) (n>1) 使用递归实现是非常直观和简单的：

递归版本
int factorial( int n ){
    return n>1 ? n*factorial(n-1) : n;
}
迭代版本
int factorial( int n ){
    int res = n;
    while( n>1 ){
        res *= --n;
    }
    return res;
}

斐波那契 Fibonacci

1.斐波那契数

斐波那契数列是算法里最基础的概念了。

其中 0，1，1，2，3，5，8... fn = n ( n<=1 ) fn = fn(n-2) + fn(n-1) ( n>1 )

同样递归版本是简单而直观的：

递归版：
int fabonacci( int n ){
    return n>1 ? fabonacci( n-1 ) + fabonacci( n-2 ) : n;
}

递归版的Fibonacci效率是有严重缺陷的，主要是由于在合并两次之和时，两边进行了重复的计算，而每次重复计算也都是包含了更多迭代版本中更多的重复。这里由于递归而造成的重复计算复杂度为 O( 2∧n )

迭代版：
/*
 * n>0 当n<=0时，默认不考虑
 * 使用双指针缓存本次和上次结果，并进一步迭代
 */
int fabonacci( int n ){
    int l = 1;
    int r = 1;
    for( int i = 2; i <= n; i ++ ){
        r = l + r;
        l = r - l;
    }
    return r;
}

迭代版的斐波那契数的复杂度仅为O(n)

2.Fibonacci数列

/*
 * 返回数组首元素，数组长度为n n>0
 */
#include <iostream>
#include <cstdlib>
int * fabonacci( int n ){
    int * a = new int[n];
    a[0] = 1;
    if( n<2 ) return a;
    a[1] = 1;
    for( int i = 2; i < n; i++ ){
        a[i] = a[i-1] + a[i-2];
        a[i-1] = a[i] - a[i-2];
    }
    return a;
}

int main()
{
    int n   = 8;
    int * b = fabonacci(n);
    for( int i = 0; i<n; i++ ){
        std::cout << b[i] << std::endl;
    }
}

这段代码会输出:

1
1
2
3
5
8
13
21

最长公共子序列是一个经典的基础算法问题 在两个序列中 如果序列1中的元素a也存在于序列2，则认为a是1，2的公共元素。 当序列3中的每一个元素都能够满足在不改变次序的情况下依次属于1，2，那么则认为3是1，2的公共子序列。多个公共子序列中，元素最多的即为最长公共子序列。

在学堂在线的算法课程中，有比较详细的课程讲述这个算法的构思。但是没有给出具体的实现，这里来自己实现一下。

首先使用表格模拟排列组合的所有情况: 以{a,b,c,d,e},{a,b,q,c,b}为例:

A\B a b q c b
a 1 1 1 1 1
b 1 2 2 2 2
c 1 2 2 3 3
d 1 2 2 3 3
e 1 2 2 3 3

实际上看到这样的填充，直觉上就应该反应出来，使用二维数组来解决。 其中当 A[i]!=B[j]时，取左方或者上方更大的，而A[i]==B[j]的时候，取T[i-1][j-1] + 1。这里i=0或j=0的时候就不方便了，所以给矩阵默认增加一行 0 行。即

A\B 0 a b q c b
0 0 0 0 0 0 0
a 0 1 1 1 1 1
b 0 1 2 2 2 2
c 0 1 2 2 3 3
d 0 1 2 2 3 3
e 0 1 2 2 3 3

- 阅读剩余部分 -

数据结构、算法与应用 C++语言描述

第一章 习题25

子集生成法（Subset Generation）

三元素集{a,b,c}的子集是：{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。 这些子集又可以使用01序列来表示，分别是000,100,010,001,110,101,011,111。 0/1分别代表着 含有/不含 原集合中的对应元素。

输出n个元素的所有子集（以01序列的形式）。

在网上看了一下基本上最终输出的都是数组，但并没有按照题目输出01序列。所以我这里严格按照题目来解。

分析

子集生成是一个完全排列组合问题，包括退化情况空集，以及极限情况自身。 其他的情况分别是[1,n)个元素的任意组合。 所以如果递归的话，也就是每一次元素数量+1 或者是-1，如果不是输出01序列，那么输出的元素个数就刚好等于递归中的n。输出序列的时候，只需要在其他位置补0即可。而补0逻辑也可以反过来考虑，即默认是n个0 e.g. 0000，随着循环的i改变，在不同的位置上填1e.g. 0001,0010,0100,1000，这样更加便捷。

至此，已经有了算法的模型了：

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void subsetGeneration( T* const A, int len, string code = "", int focus = 0 ){

    if( focus > len ) return;
    if( focus == len ){ cout << string(len,'1') << endl; return; }
    if( focus == 0 ){ cout << string(len,'0') << endl; }

    if( code == "" ){ code = string(len,'0'); }

    code[focus] = '1';
    for( int i = focus; i<len; i++ ){
        code[i] = '1';
        cout << code << endl;
        code[i] = '0';
    }

    subsetGeneration( A, len, code, focus + 1 );
}
int main(){

    subsetGeneration( "abcd", 4 );
    return 0;
}

思考1 上述算法已经成功解题，但是思维略显复杂，直觉上就感觉不是一个优质解。

- 阅读剩余部分 -

  1. 1
  2. 2