2019-06-07YTUOJ 算法/递归

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

Author ： ShawnDong

updateDate ：2019.6.8

Blog ： ShawnDong98.github.io

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

3178: 少校吃小炒：少校学长是一个喜欢吃小炒的人，每次他都会叫上几个同学走向七餐的4楼，尝遍各式各样的小炒。而且少校学长还有大长腿呢。他每次都不坐电梯，在他上楼的时候每次可以走1级或2级台阶。现在请你输入台阶的数目，求出他能走到的不同走法数。

typedef  long long ll;

ll HaveLunch(ll steps){
    ll current = 1;
    ll last = 1;
    ll beforelast = 1;
    for(int i=2; i<=steps; i++){
        current = last + beforelast;
        beforelast = last;
        last = current;
    }
    return current;

}

int main(){
    int n;
    while(cin >> n && n!=0){
        ll sum = HaveLunch(n);
        cout << sum << endl;
    }
    return 0;
}

3198: C 递归函数--进制转换（十进制转二进制）：

void conversion(int n); //将n转换为二进制输出的递归函数声明
int main()
{
    int a;
    scanf("%d",&a);
    conversion(a) ; //将n转换为二进制输出
    return 0;
}

void conversion(int n){
    stack<int> SS;
    if(n == 0) cout << 0;
    while(n!=0) {
        SS.push(n % 2);
        n /= 2;
    }

    while(!SS.empty()){
        cout << SS.top();
        SS.pop();
    }
}

3240: 第39级台阶：小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。

typedef long long ll;

int count=0;

void Fun(int stair_S,int step_S)
{   //stari用于表示剩余的楼梯的层数，当等于0时停止递归
    //step是走过的步数，用来判断是否是偶数，是否符合要求
    if(stair_S<0)return;
    if(stair_S==0)  //39节楼梯全部走完
    {
        if(step_S%2 == 0)count++;
        return;
    }
    Fun(stair_S-1,step_S+1);    //这一步走了一个台阶
    Fun(stair_S-2,step_S+1);    //这一步走了两个台阶
}


int main() {

    Fun(39,0);
    cout<<count<<endl;
    return 0;
}

3241: 奇怪的比赛：某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：

每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。

每位选手都有一个起步的分数为10分。

某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？

如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011 就是可能的情况。

你的任务是算出所有可能情况。每个答案占一行。(将每一个答案看成二进制数，答案由大到小排列)

typedef long long ll;

int a[11] = {0};

int Compete(int n, int Score){

    if(n==11){
        if(Score == 100){
            for(int i=1; i<11; i++){
                cout << a[i];
            }
            cout << "\n";
        }
        return 0;
    }
    a[n] = 1;
    Compete(n+1, Score * 2);
    a[n] = 0;
    Compete(n+1, Score - n);

}

int main(){

    Compete(1, 10);

    return 0;
}