算法交作业(一)

首先解释下标题的含义:在网上看了一位大牛写的基础算法相关的博文,感觉自己不是天赋异禀,所以决定自己实现一遍当作交作业。
开篇:
今天这篇博文是关于数组查找的,很简单。
算法是计算机的生命。没有算法,就没有软件,计算机也就成了一个冰冷的机器,没有什么实用价值。很多人认为,算法是数学的内容,学起来特别麻烦。我们不能认为这种观点是错误的。但是我们也知道,软件是一种复合的技术,如果一个人只知道算法,但是不能用编程语言很好地实现,那么再优秀的算法也不能发挥作用。一个人只有有了很好的计算机知识和数学知识,才能在算法的学习上不断进步。不管算法都么简单,都要自己亲手实践,只有不断认识错误、不断发现错误,才能不断提高自己的编程能力,不断提高自己的业务水平。
这里取名一步一步写算法的目的主要有两个:第一,保证我们的算法都是大家可以学得会,看的懂的;第二,保证我们的算法是健壮的、可以测试的。所以在编写的过程中,我们的算法开发过程是伴随着测试用例增加的,没有测试用例保证的代码只是一段无序的字符而已,没有什么价值。
其实任何算法都有自己的应用环境和应用场景,没有算法可以适用于所有的场景。这一点希望大家明白。同时,我们也要清楚复杂的算法都是由普通的算法构成的,没有普通的算法就没有复杂的算法可言,所以复杂变简单,由大化小,这就是算法分治递归的基本思想。
原文地址

上面的内容我感觉写的比较好,所以搬运了。下面正式实现自己的版本。
1.数组查找函数1.0版本:

int Find_Array(int arr[], unsigned length, const int& value){
    int index = 0;
    return index;
}
测试:
#include <iostream>
#include <assert.h>
//存在返回下标,否则返回-1表示查找失败。
int Find_Array(int arr[], unsigned length, const int& value){
    int index = 0;
    return index;
}
static void test1(){
    int arr[10] = { 0 };
    assert(Find_Array(nullptr, 10, 1)==-1);
    assert(Find_Array(arr, 0, 1) == -1);
}
int main(){
    test1();
}
通过测试可以看错程序的不健壮,需要对入口进行修改。

2.0版本:

int Find_Array(int arr[], unsigned length, const int& value){
    if (arr == nullptr || length == 0)
        return -1;
    int index = 0;
    return index;
}
//可以看到我们对入口进了测试。

3.0版本:

int Find_Array(int arr[], std::size_t length, const int& value){
    if (arr == nullptr || length == 0)
        return -1;
    for (std::size_t index = 0; index < length; ++index){
        if (arr[index] == value)
            return index;
        continue;
    }
    return -1;
}
static void test1(){
    int arr[10] = { 1,2};
    assert(Find_Array(nullptr, 10, 1)==-1);
    assert(Find_Array(arr, 10, 1) == 0);
}

4.0优化版本:

1)用指针进行优化:
int Find_Array(int arr[], std::size_t length, const int& value){
    if (arr == nullptr || length == 0)
        return -1;
    for (std::size_t index = 0; index < length; ++index){
        if (*(arr+index)== value)
            return index;
        continue;
    }
    return -1;
}

2)对形参进行优化:

using array = int(&)[10];//数组类型的引用。
int Find_Array(array arr, const int& value){
    if (arr == nullptr)
        return -1;
    for (std::size_t index = 0; index < 10; ++index){
        if (arr[index] == value)
            return index;
        continue;
    }



----------


C++ 11:
using array = int(&)[10];//数组类型的引用。
int Find_Array(array arr, const int& value){
    int index = 0;
    for (const auto& x : arr){
        if (x == value)
            return index;
        ++index;
        continue;
    }
    return -1;
}
void test(){
    int arr[10] = { 1, 2 };
    assert(Find_Array(arr, 10) == -1);
    assert(Find_Array(arr, 2) == 1);
}
//我们省略了数组大小的参数,不过上面的写法存在一定的局限性。


----------


3)模版函数版本:
template<class T>
int Find_Array(const T* const &arr, const std::size_t length, const T& value){
    if (arr == nullptr || length == 0)
        return -1;
    auto beg = arr, end = beg + length;
    while (beg != end)
        if (*beg++ == value)
            return beg - arr-1;
    return -1;
}
void test(){
    int arr[10] = { 1, 2 };
    assert(Find_Array(arr, 10,1) ==0);
    assert(Find_Array(arr, 10,3) == -1);
}

相关说明:
1.为什么用size_t?避免数组长度小于0.
2.参数的优化:尽量用const引用进行优化,锱铢必较。
3.测试平台:VS 2013+Win 7.

二次优化版本:

最近学了点标准库的内容,所以用向量和标准版定义的array 类型实现下。

#include <iostream>
#include <assert.h>
#include <vector>
#include <array>
//存在返回下标,否则返回-1表示查找失败。
//vector 版本。
int Find_Array(const std::vector<int>& ivec, const int& value){
    //不使用下标版本,直接使用迭代器。
    auto beg = ivec.begin(), end = ivec.end();
    if (beg == end)
        return -1;
    int index = 0;
    while (beg != end)
        if (*beg++==value)
            return beg - ivec.begin() - 1;
    return -1;
}

void test1(){
    std::vector<int> ivec = { 1, 2, 3 };
    assert(Find_Array(ivec,2)== 1);
    assert(Find_Array(ivec, 10) == -1);
    assert(Find_Array(std::vector<int>(), 10) == -1);

}
//标准库的数组版本。
int Find_Array(const std::array<int,10>& arr, const int& value){
    if (arr.empty())
        return -1;
    int index = 0;
    for (const auto& x : arr){
        if (x == value)
            return index;
        ++index;
        continue;
    }
    return -1;
}
void test2(){
    std::array < int, 10 > arr= {1, 2, 3};
    assert(Find_Array(arr, 2) == 1);
    assert(Find_Array(arr, 10) == -1);
    assert(Find_Array(std::array<int,10>(), 10) == -1);
}
int main(){
    test1();
    test2();
    system("pause");
    return 0;
}
----------
//来个可变参数列表试试。
int Find_Array(const std::initializer_list<int>& i1, const int& value){
    auto beg = i1.begin(), end = i1.end();
    if (beg == end)
        return -1;
    int index = 0;
    while (beg != end)
        if (*beg++ == value)
            return beg - i1.begin() - 1;
    return -1;
}
void test3(){
    assert(Find_Array(std::initializer_list<int>{1, 2, 3}, 1) == 0);
    assert(Find_Array(std::initializer_list<int>(), 10) == -1);
}

Summary:

1.算法的思路非常简单,我只不过闲的无聊重写了一遍。查找涉及到基本操作应该是遍历,计数等操作。
2.学会一步步优化算法。
3.拓宽算法的可用性。
4.保证健壮性。
5.博文参考:原文地址,戳我进去

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。