题目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;
}
