fibonacci数列

解法1(mine)

#include<iostream>
using namespace std;
long int fib(int n)
{
    int initial[2] = {0,1};
    long int r;
    if(n == 0)
    {
        return initial[0];
    }
    else if( n == 1)
    {
        return initial[1];
    }
    else if(n >= 2)
    {

    for(int i=2;i<=n;i++){
        if(i%2 == 0)
            initial[0] = initial[1]+initial[0];
        else
            initial[1] = initial[0]+initial[1];
    }
        return (n%2 == 0)?initial[0]:initial[1];
    }
    else
    {
        cout<<"输入的n必须为大于等于0的整数!"<<endl;
        return 0;
    }
}
int main()
{
    int n ;
    cout<<"输入n为:"<<endl;
    while(cin>>n)
    {
        cout<<"fibonacci("<<n<<"):"<<fib(n)<<endl;
    }
}

解法2(office)

#include<iostream>
using namespace std;
long int fib(unsigned int n)
{
    int result[2] = {0,1};
    if(n<2)
        return result[n];
    long long fibn_1 = 1;
    long long fibn_2 = 0;
    long long fibn = 0;
    for(unsigned int i=2;i<=n;i++){
        fibn = fibn_1+fibn_2;
        fibn_2 = fibn_1;
        fibn_1 = fibn; 
    }
    return fibn;
}
int main()
{
    unsigned int n;
    while(cin>>n){
        cout<<fib(n)<<endl;
    }
}

排序算法

shell排序

算法:

• 将待排序数列(n)以gap为间隔分为gap组元素，每组元素个数为n/gap，将每组进行插入排序，然后按照排序后的结果以每组第i组第一个元素排序，第i组第二个元素排序
• 将排序后的数组以n/4的gap排序，重复直到gap为1

对于下面的数组排序:

592,401,874,141,348,72,911,887,820,283

元素个数n=10，第一次排序gap=10/2=5.每组两个元素，5组。分组如下:

• 分组:(529,72)(401,911)(874,887),(141,820),(348,283)

• 对每组插入排序:(72,529)(401,911)(874,887),(141,820),(283,348)

取每组第一个元素，第二个元素排序:

72,401,874,141,283,529,911,887,820,348

• gap=10/4=2,2组，每组5个元素（72,874,283,911,820）(401,141,529,887,348),每组分别排序(72,283,820,874,911)(141,348,401,529,887),排序结果为(72,141,283,348,820,401,874,529,911,887)
• gap=10/8=1,1组10个元素，插入排序，(72,141,283,348,401,529,840,874,887)