2019-06-05 YTUOJ 算法/简单题

--------------------------------

Author ： ShawnDong

updateDate ：2019.6.6

Blog ： ShawnDong98.github.io

--------------------------------

题目：输入一个整数，把他转化成二进制。

int main(){
    int a;
    stack<int> S;
    cin >> a;
    while(a != 0){
        S.push(a % 2);
        a = a / 2;

    }
    while(!S.empty()){
        cout << S.top();
        S.pop();
    }
    return 0;
}

题目3333：Fibonacci数列，定义如下：
f(1)=f(2)=1
f(n)=f(n-1)+f(n-2) n>=3。
计算第n项Fibonacci数值，注意要求最后的结果要保留最后9位

输入	输出
11	89
12	144
3	2
2	1
6	8
45	134903170
99	555169026

unsigned long long  int Febonacci_one(unsigned long long int n){
    if(n <= 0)
        return 1;
    unsigned long long int current = 1;
    unsigned long long int last = 1;
    unsigned long long int beforelast = 0;
    for(unsigned long long int i=2; i<=n; i++){
        current = (last + beforelast) % 1000000000;
        beforelast = last;           //n-2
        last = current;              //n-1
    }

    return current;
}

int main(){
    unsigned long long int n;
    while(cin >> n){
        cout << Febonacci_one(n) << endl;
    }
    return 0;
}

3347: 菲波那契数:爱动脑的小西，学了菲薄数列以后，喜欢自己琢磨，然后他试着将菲薄数列进行求和，但他觉得手算太麻烦，想请你帮帮他。。。菲波那契(数定义为： f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2). n是>1的整数。
求f（1）+f（2）+...+f（n）

long long Febonacci_one(long long  n){
    if(n <= 0)
        return 1;
    long long current = 1;
    long long  last = 1;
    long long  beforelast = 0;
    for(long long i=2; i<=n; i++){
//        current = (last + beforelast) % 1000000000;
        current = (last + beforelast);
        beforelast = last;           //n-2
        last = current;              //n-1
    }

    return current;
}

long long Febonacci_two(long long n){
    long long sum = 0;
    for(long long i=1; i<=n; i++){
        sum += Febonacci_one(i);
    }
    return sum;
}


int main(){
    long long n;
    cin >> n;
    cout << Febonacci_two(n);
    return 0;
}

3364: 指针问题——求矩阵上三角之和：输入一个矩阵，求矩阵的上三角元素之和

#include<stdio.h>
const int N=100;
int main()
{
    int a[N][N],i,j,sum=0,*p;
    int n;
    scanf("%d",&n);
    for(i=0; i<n; i++)
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
    for(i=0;i<n;i++){
        p=&a[i][i];
        for(j=0;j<n-i;j++)
        {
            //sum += a[i][i+j];
            sum += *(p++);
        }
    }
    printf("%d\n",sum);
    return 0;
}

3374: H胖胖的健身计划：L老师布置了一道思考题，一个人一次可以上一个台阶，也可以上两个台阶，问上到n级台阶有多少种走法？H胖胖非常聪明，拿出胖胖的小手掐指算起来。登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种方法……所以，1，2，3，5，8，13，……。
H胖胖为了保持身体苗条，给自己制定了一个锻炼计划，决定用刚才计算的数列确定每天自己锻炼的步数，就是说第1天走1步，第2天走2步，第3天走5步，第4天走8步，第5天走13步，……。
H胖胖的同学LYQ正好在学习矩阵相乘，帮他想到了一个快递计算的方法如下公式所示。

快速幂——反复平方法:

该怎样去加速幂运算的过程呢？既然我们觉得将幂运算分为n步进行太慢，那我们就要想办法减少步骤，把其中的某一部分合成一步来进行。
比如，如果n能被2整除，那我们可以先计算一半，得到an/2的值，再把这个值平方得出结果。这样做虽然有优化，但优化的程度很小，仍是线性的复杂度。
再比如，如果我们能找到 $2^{k}=n$ ，那我们就能把原来的运算优化成 $((a^{2})^{2})^{2}...$ ，只需要k次运算就可以完成，效率大大提升。可惜的是，这种条件显然太苛刻了，适用范围很小。不过这给了我们一种思路，虽然我们很难找到 $2^{k}=n$ ，但我们能够找到 $2^{k1}+2^{k2}+2^{k3}+......+2^{km}=n$ 。这样，我们可以通过递推，在很短的时间内求出各个项的值。
我们都学习过进制与进制的转换，知道一个b进制数的值可以表示为各个数位的值与权值之积的总和。比如，2进制数1001，它的值可以表示为10进制的 $1×2^{3}+0×2^{2}+0×2^{1}+1×2^{0}$ ，即9。这完美地符合了上面的要求。可以通过2进制来把n转化成 $2^{km}$ 的序列之和，而2进制中第i位（从右边开始计数，值为1或是0）则标记了对应的 $2^{i−1}$ 是否存在于序列之中。譬如，13为二进制的1101，他可以表示为 $2^{3}+2^{2}+2^{0}$ ，其中由于第二位为0， $2^{1}$ 项被舍去。
如此一来，我们只需要计算a、 $a^{2}、a^{4}、a^{8}......a^{2km}$ 的值（这个序列中的项不一定都存在，由n的二进制决定）并把它们乘起来即可完成整个幂运算。借助位运算的操作，可以很方便地实现这一算法，其复杂度为O(logn)。

typedef long long ll;

typedef struct{
            ll a[2][2];
        }Mat;

Mat MatMul(Mat f, Mat b){
    Mat tmp;
    tmp.a[0][0] = (f.a[0][0] * b.a[0][0] + f.a[0][1] * b.a[1][0]) % 100007;
    tmp.a[0][1] = (f.a[0][0] * b.a[0][1] + f.a[0][1] * b.a[1][1]) % 100007;
    tmp.a[1][0] = (f.a[1][0] * b.a[0][0] + f.a[1][1] * b.a[1][0]) % 100007;
    tmp.a[1][1] = (f.a[1][0] * b.a[0][1] + f.a[1][1] * b.a[1][1]) % 100007;

    return tmp;
}

int main(){
    Mat f, b;
    f.a[0][0] =1,  f.a[1][1] = 1, f.a[0][1] = f.a[1][0] = 0;
    b.a[0][0] = b.a[0][1] = b.a[1][0] = 1, b.a[1][1] = 0;

    ll n;
    cin >> n;
    while(n)
    {
        if(n&1)
            f = MatMul(b,f);
        b = MatMul(b,b);
//        cout << "n : " << n << endl;
        n>>=1;
    }

    cout << f.a[0][0] ;
};