学步园

【回到豆瓣】http://site.douban.com/196781/widget/notes/12161495/note/258843932/

【题目】2.给定一个整数X和整数序列A1,A2,......,An,后者已经预先排序，求X是否在序列中，并返回下标，若不在序列中返回-1.

【思路】这道题除了2分还真不知道有啥更好的，关于多分，比如3分4分，一般不常用，我搜到这样一篇文章 仅供参考，http://blog.csdn.net/aaajj/article/details/5601687

【代码】包含2分的递归解和非递归解

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

#define N 100

//递归解
template <typename Comparable>
int binarySearch2(const vector<Comparable> & arr,Comparable k, int low,int high){
    int mid = (low + high)/2;
    if(low > high){
        return -1;
    }
    if(k > arr[mid]){
        return binarySearch2(arr,k,mid+1,high); 
    }else if(k < arr[mid]){
        return binarySearch2(arr,k,low,mid-1);
    }else{
        return mid;
    }
    return -1;
}

//非递归解
template <typename Comparable>
int binarySearch1(const vector<Comparable> & arr,Comparable k){
    int low = 0,high = arr.size()-1;
    while(low <= high){
        int mid = (low + high)/2;
        if(k > arr[mid]){
            low = mid + 1;
        }else if(k < arr[mid]){
            high = mid - 1;
        }else{
            return mid;
        }
    }
    return -1;
}

int main()
{
    srand(time(0));
    vector<int> arr;
    for(int i = 0;i < N;++i){
        arr.push_back(rand());
    }
    sort(arr.begin(),arr.end());
    for(int i = 0;i < N;++i){
        cout<<i<<":"<<arr[i]<<endl;
    }
    int k = 0;
    cin>>k;
    cout<<binarySearch1(arr,k)<<endl;
//    cout<<binarySearch2(arr,k,0,arr.size()-1)<<endl;
    system("pause");
    return 0;
}

【题目】3.给定正整数A和B,求二者的最大公约数。

【思路】最常见的算法就是欧几里德算法了，其利用了这样的事实，gcd(a,b) = gcd(b,a mod b)（a >= b） (a mod b是指a取余b)，之前我写了一种证明，详细讨论请见本帖http://site.douban.com/196781/widget/forum/12161503/discussion/51264526/

【代码】

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

//递归解
int gcd1(int a,int b){
    if(b > a){
        int t = a;
        a = b;
        b = t;
    }
    if(b == 0){
        return a;
    }else{
        return gcd1(b,a%b);
    }
}
//非递归解
int gcd2(int a,int b){
    if(b > a){
        int t = a;
        a = b;
        b = t;
    }
    int temp = 0;
    while(b){
        temp = a;
        a = b;
        b = temp % b;
    }
    return temp;
}

int main3()
{
    int a = 0;
    int b = 0;
    cin>>a>>b;
    cout<<gcd1(a,b)<<endl;
    system("pause");
    return 0;
}

【题目】4.给定正整数N，求解其是否为素数。

【思路1】从2开始逐个数除，能整除的话说明不是素数，如果除到sqrt（N），还没有整除的情况，就说明该数是素数，这里番茄酱同学给出了两个改进点：

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

(1).过分追求时间，可以将一定范围内的所有素数放入Static const的数组中，做二分法查找。

(2).标准做法，for循环，n=3开始n+=2.

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

这里为何可以n+=2呢？理解这句话很关键，如果一个数不能被2整除，那么它就一定不能被2以上的其他偶数整除。所以大于2的偶数可以被忽略了。

【思路2】筛法，筛法是求一定范围内所有素数的算法。

具体做法：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。

【思路3】关于判断素数还有一些高效的不确定性算法，具体请移步至http://wenku.baidu.com/view/ab5139697e21af45b307a812.html

【代码】

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool isPrime(int x) {
    if (x < 3)
        return x == 2 ? true : false;

    if (x % 2 == 0)
        return false;

    int sqrt_root = (int)sqrt(x);
    for (int i=3; i<=sqrt_root; i += 2)
        if (x % i == 0)
            return false;

    return true;
}

int main() {
    int x;
    while (cin >> x) {
        string str = isPrime(x) ? "Yes" : "No";
        cout << "Is " << x << " a prime? " << str << endl;
    }

    return 0;
}