題目1 : Exam10_TheKthStep
時(shí)間限制:2000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
描述
小明剛剛看完電影《第K級(jí)臺(tái)階》，離開電影院的時(shí)候食店，他數(shù)了數(shù)禮堂前的臺(tái)階數(shù)渣淤，恰好是K級(jí)!
站在臺(tái)階前，他突然又想著一個(gè)問題：
如果我每一步只能邁上1個(gè)或2個(gè)臺(tái)階吉嫩。先邁左腳价认，然后左右交替，最后一步是邁右腳自娩，
也就是說一共要走偶數(shù)步用踩。那么，上完K級(jí)臺(tái)階忙迁，有多少種不同的上法呢脐彩？
請(qǐng)你利用計(jì)算機(jī)的優(yōu)勢(shì)，幫助小明尋找答案姊扔。
輸入
一個(gè)整數(shù)K（10<=K<=20）
輸出
整數(shù)惠奸，走法的種數(shù)
樣例輸入
10
樣例輸出
44
AC代碼
#include<iostream>
using namespace std;
int count=0;
void fun(int stair,int step)
{ //stari用于表示剩余的樓梯的層數(shù)，當(dāng)?shù)扔?時(shí)停止遞歸
//step是走過的步數(shù)恰梢，用來判斷是否是偶數(shù)佛南，是否符合要求
if(stair<0)return;
if(stair==0) //k節(jié)樓梯全部走完
{
if(step%2 == 0)count++;
return;
}
fun(stair-1,step+1); //這一步走了一個(gè)臺(tái)階
fun(stair-2,step+1); //這一步走了兩個(gè)臺(tái)階
}
int main()
{
int i;
cin >> i;
fun(i,0);
cout<<count<<endl;
return 0;
}
題目2 : Exam11_FindInRotaryArr
時(shí)間限制:4000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
描述
輸入一個(gè)遞增排序的數(shù)組（元素不重復(fù)）的一個(gè)旋轉(zhuǎn)（次數(shù)不詳），找出某個(gè)元素.
輸入
第一行：N嵌言，數(shù)組的長(zhǎng)度
第二行：N個(gè)整數(shù)嗅回，作為數(shù)組的元素，空格分開
第三行：要查找的關(guān)鍵字K
輸出
關(guān)鍵字K的下標(biāo)摧茴，如果沒有找到绵载，輸出-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
時(shí)間限制:4000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
描述
給一個(gè)整數(shù)數(shù)組苛白，找到兩個(gè)數(shù)使得他們的和等于一個(gè)給定的數(shù) target娃豹。你需要輸出這兩個(gè)數(shù)的下標(biāo), 并且第一個(gè)下標(biāo)小于第二個(gè)下標(biāo)。注意這里下標(biāo)的范圍是 0 到 n-1购裙。
你可以假設(shè)數(shù)組遞增有序培愁。
請(qǐng)?jiān)贠(N)時(shí)間內(nèi)完成。
輸入
第一行：N個(gè)整數(shù)缓窜，作為數(shù)組的元素定续，空格分開
第二行：target
輸出
兩個(gè)下標(biāo)，空格隔開禾锤。如有多組滿足要求私股，輸出靠前的一組。
樣例輸入
4
2 7 11 15
9
樣例輸出
0 1
#include <iostream>
using namespace std;
int getSumNum(int *arr, int n ,int Sum) //arr為數(shù)組恩掷，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;
}
