| 例2.9 | 找x | （九度教程第17題） |
|---|---|---|
| 時間限制：1秒 | **內(nèi)存限制：32兆 ** | 特殊判題：否 |
題目描述：
輸入一個數(shù)n，然后輸入n個數(shù)值各不相同，再輸入一個值x工坊，輸出這個值在這個數(shù)組中的下標(biāo)（從0開始，若不在數(shù)組中則輸出-1）敢订。
輸入：
測試數(shù)據(jù)有多組王污，輸入n(1<=n<=200)，接著輸入n個數(shù)楚午，然后輸入x昭齐。
輸出：
對于每組輸入,請輸出結(jié)果。
樣例輸入：
2
1 3
0
樣例輸出：
-1
來源：
2010年哈爾濱工業(yè)大學(xué)計算機研究生機試真題
#include <stdio.h>
int main () {
int buf[200];
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
} //輸入數(shù)據(jù)
int x , ans = -1; //初始化答案為-1矾柜，以期在找不到答案時能正確的輸出-1
scanf ("%d",&x);
for (int i = 0;i < n;i ++) { //依次遍歷數(shù)組元素
if (x == buf[i]) {//目標(biāo)數(shù)字與數(shù)組元素依次比較
ans = i;
break; //找到答案后跳出循環(huán)
}
}
printf("%d\n",ans);
}
return 0;
}
| 例2.10 | 查找學(xué)生信息 | （九度教程第18題） |
|---|---|---|
| 時間限制：1秒 | **內(nèi)存限制：32兆 ** | 特殊判題：否 |
題目描述：
輸入N個學(xué)生的信息阱驾，然后進行查詢就谜。
輸入：
輸入的第一行為N，即學(xué)生的個數(shù)(N<=1000)
接下來的N行包括N個學(xué)生的信息里覆，信息格式如下：
01 李江 男 21
02 劉唐 男 23
03 張軍 男 19
04 王娜 女 19
然后輸入一個M(M<=10000),接下來會有M行丧荐，代表M次查詢，每行輸入一個學(xué)號喧枷，格式如下：
02
03
01
04
輸出：
輸出M行虹统，每行包括一個對應(yīng)于查詢的學(xué)生的信息。
如果沒有對應(yīng)的學(xué)生信息隧甚，則輸出“No Answer!”
樣例輸入：
4
01 李江 男 21
02 劉唐 男 23
03 張軍 男 19
04 王娜 女 19
5
02
03
01
04
03
樣例輸出：
02 劉唐 男 23
03 張軍 男 19
01 李江 男 21
04 王娜 女 19
03 張軍 男 19
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Student{ //用于表示學(xué)生個體的結(jié)構(gòu)體
char no[100]; //學(xué)號
char name[100]; //姓名
int age; //年齡
char sex[5]; //性別
bool operator < (const Student & A) const { //重載小于運算符使其能使用sort函數(shù)排序
return strcmp(no,A.no) < 0;
}
}buf[1000];
int main () {
int n;
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
} //輸入
sort(buf,buf + n); //對數(shù)組排序使其按照學(xué)號升序排列
int t;
scanf ("%d",&t); //有t組詢問
while (t -- != 0) { //while循環(huán)保證查詢次數(shù)為t
int ans = -1; //目標(biāo)元素下標(biāo),初始化為-1
char x[30];
scanf ("%s",x); //待查找學(xué)號
int top = n - 1,base = 0; //初試時窟却，開始下標(biāo)0,結(jié)束下標(biāo)n-1,查找子集為整個數(shù)組
while(top >= base) { //當(dāng)查找子集不為空集時重復(fù)二分查找
int mid = (top + base) / 2; //計算中間點下標(biāo)
int tmp = strcmp(buf[mid].no,x); //比較中間點學(xué)號與目標(biāo)學(xué)號
if (tmp == 0) {
ans = mid;
break; //若相等,則查找完成跳出二分查找
}
else if (tmp > 0) top = mid - 1; // 若大于,則結(jié)束下標(biāo)變?yōu)橹虚g點 前一個點下標(biāo)
else base = mid + 1; //若小于,則開始點下標(biāo)變?yōu)橹虚g點后一個點坐標(biāo)
}
if (ans == -1) { //若查找失敗
printf("No Answer!\n");
}
else printf("%s %s %s %d\n",buf[ans].no,buf[ans].name,buf[ans].sex,buf[ans].age); //若查找成功
}
}
return 0;
}
| 題目1126 | 打印極值點下標(biāo) | （九度教程第19題） |
|---|---|---|
| 時間限制：1秒 | **內(nèi)存限制：32兆 ** | 特殊判題：否 |
來源：
2008年北京大學(xué)方正實驗室計算機研究生機試真題
#include <stdio.h>
int main(){
int n;
while(scanf("%d",&n) != EOF){
while(n--){
int k, flag = 0;
scanf("%d",&k);
int a[k];
for(int i=0; i<k; i++)scanf("%d",&a[i]);
if(a[0]!=a[1]){flag=1;printf("0");}
for(int i=1; i<k-1; i++){
if((a[i]<a[i-1]&&a[i]<a[i+1])||(a[i]>a[i-1]&&a[i]>a[i+1])){
if(flag==1){printf(" %d",i);}
else {printf("%d",i);flag=1;}
}
}
if(a[k-1]!=a[k-2]){if(flag=1)printf(" %d",k-1);else printf("%d",k-1);}
printf("\n");
}
}
}
//最后一個極值之后不需要輸出空格
| 題目1173 | 查找 | （九度教程第20題） |
|---|---|---|
| 時間限制：1秒 | **內(nèi)存限制：32兆 ** | 特殊判題：否 |
題目描述：
輸入數(shù)組長度 n 輸入數(shù)組 a[1...n] 輸入查找個數(shù)m 輸入查找數(shù)字b[1...m] 輸出 YES or NO 查找有則YES 否則NO 。
輸入：
輸入有多組數(shù)據(jù)呻逆。每組輸入n夸赫，然后輸入n個整數(shù)，再輸入m咖城，然后再輸入m個整數(shù)（1<=m<=n<=100）茬腿。
輸出：
如果在n個數(shù)組中輸出YES否則輸出NO。
樣例輸入：
5
1 5 2 4 3
3
2 5 6
樣例輸出：
YES
YES
NO
來源：
2010年北京郵電大學(xué)網(wǎng)院研究生機試真題
#include <iostream>
#include <algorithm>
using namespace std;
int N; //數(shù)組長度
int main()
{
while(cin>>N!=0)
{
int a[100]={0};
for(int i=1;i<=N;i++)
{
cin>>a[i]; //輸入數(shù)組
}
sort(a+1,a+N+1);
int m;
cin>>m; //有m組查找
while(m--!=0)
{
int t;
cin>>t; //輸入查找數(shù)字
int base=1;
int top=N;//初試時宜雀，開始下標(biāo)1,結(jié)束下標(biāo)N
while(top>=base)
{
int mid;
mid=(base+top)/2;
if(t==a[mid])
{
cout<<"YES"<<endl;
break;
}
else if(t>a[mid])
{
base=mid+1;
}
else
{
top=mid-1;
}
}
if(top<base)
{
cout<<"NO"<<endl;
}
}
}
return 0;
}
