算法很美--递归

题目1 : Exam10_TheKthStep
时间限制:2000ms
单点时限:1000ms
内存限制:256MB

描述

小明刚刚看完电影《第K级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是K级!

站在台阶前，他突然又想着一个问题：

如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，

也就是说一共要走偶数步。那么，上完K级台阶，有多少种不同的上法呢？

请你利用计算机的优势，帮助小明寻找答案。
输入

一个整数K（10<=K<=20）
输出

整数，走法的种数
样例输入

10

样例输出

44

AC代码

#include<iostream>
using namespace std;
int count=0;
void fun(int stair,int step)
{   //stari用于表示剩余的楼梯的层数，当等于0时停止递归
    //step是走过的步数，用来判断是否是偶数，是否符合要求
     if(stair<0)return; 
     if(stair==0)   //k节楼梯全部走完 
     {
        if(step%2 == 0)count++;
        return;
     } 
     fun(stair-1,step+1);   //这一步走了一个台阶 
     fun(stair-2,step+1);   //这一步走了两个台阶 
}
int main()
{
    int i;
    cin >> i;
    fun(i,0);
    cout<<count<<endl;
    return 0; 
}

题目2 : Exam11_FindInRotaryArr
时间限制:4000ms
单点时限:1000ms
内存限制:256MB

描述

输入一个递增排序的数组（元素不重复）的一个旋转（次数不详），找出某个元素.
输入

第一行：N，数组的长度
第二行：N个整数，作为数组的元素，空格分开
第三行：要查找的关键字K
输出

关键字K的下标，如果没有找到，输出-1
样例输入

5
6 1 2 3 4
1

样例输出

1

AC代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
//二分查找法，主要要确定好左右边界
class Solution {
public:
    int removeDuplicates(int *a, int len, int target)
    {
        int start = 0;
        int end = len - 1;
        while (start != end)
        {
            int mid = (start + end) / 2;
            if (a[mid] == target)
            {
                return mid;
            }
            if (a[start] <= a[mid])
            {
                if (a[start] < target&&target < a[mid])
                    end = mid;
                else
                    start = mid + 1;
            }
            else
            {
                if (a[start] > target&&target < a[mid])
                    end = mid;
                else
                    start = mid + 1;
            }
        }
    }
};
int main()
{
    int x,y;
    cin>>x;
    int a[x];
    for(int i = 0; i < x; i++) 
        cin>>a[i];
        //scanf("%d", &a[i]);
    cin>>y;
    Solution b;
    int length = b.removeDuplicates(a, x ,y);
    printf("%d \n",length);
    return 0;
}

题目3 : Exam12_TwoSum
时间限制:4000ms
单点时限:1000ms
内存限制:256MB

描述

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要输出这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

你可以假设数组递增有序。

请在O(N)时间内完成。
输入

第一行：N个整数，作为数组的元素，空格分开
第二行：target
输出

两个下标，空格隔开。如有多组满足要求，输出靠前的一组。
样例输入

4
2 7 11 15
9

样例输出

0 1

#include <iostream>
using namespace std;

int getSumNum(int *arr, int n ,int Sum)   //arr为数组，Sum为和 
{
    int i,j;

    for(i = 0, j = n-1; i < j; )
    {
        if(arr[i] + arr[j] == Sum){
            cout<<i<<" "<<j;
            return 0;
        }
        else if(arr[i] + arr[j] < Sum)
            i++;
        else
            j--;
    }
    return 0;
}
int main(){
    int n,m;
    cin>>n;
    int a[n];
    for (int i = 0;i<n;i++){
        cin>>a[i];
    }
    cin>>m;
    getSumNum(a,n,m);
    return 0;
}