| |
 3.5 4
|
四年级学案：
1.课堂学习：
二分查找算法：
对n个已经从小到大排好序的整数数列中，找一个为k的整数，要输出这个k的整数在数列中是第几个。找不到就输出-1。
样例:
输入：
10 65
7 9 13 27 38 53 56 71 84 92
输出：
7
参考程序：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, i,j,a[10000]={0};
cin>>n>>k;
for(i=1;i<=n;i++)cin>>a[i];
int left = 1;
int right = n ;
while (left <= right) {
int t = (right + left)/ 2; // 计算中间位置
if (a[t] == k) {
cout<<t; // 找到目标，返回下标
break;
}
else if (k>a[t] )
left = t + 1; // 目标在右半部分
else
right = t - 1; // 目标在左半部分
}
if(left>right){cout<<-1;}
return 0;
}
2.作业：理解默写以上二分查找算法。
( 2026/3/12 17:22:30 ) |
| RE |
T
( ) |
| |
#include <iostream>
using namespace std;
struct node
{
int num;
node *next;
node *pre;
};
int main(){
freopen("p1532.in","r",stdin);
freopen("p1532.out","w",stdout);
int m,s,n,k,i;
node *head,*p,*q;
bool flag;
cin>>m>>s>>n>>k;
head=new node;
head->num=s;
head->next=head;
head->pre=head;
q=head;
for(i=1;i<=m-1;i++){
p=new node;
if (i+s==m) p->num=m ;else p->num=(i+s)% m;
p->pre=q;
q->next=p;
q=q->next;
}
p->next=head;
head->pre=p;
flag=true;
q=head;
while (m>1){
if (flag){
flag=false;
i=1;
while(i<n){
q=q->next;
i++;
}
cout<<q->num<<" ";
p=q->pre;
p->next=p->next->next;
q->next->pre=p;
delete q;
}
else{
flag=true;
i=1;
while (i<k){
p=p->pre;
i++;
}
cout<<p->num<<" ";
q=p->next;
q->pre=q->pre->pre;
p->pre->next=q;
delete p;
}
m--;
}
if (flag) cout<<q->num;else cout<<p->num;
fclose(stdin);
fclose(stdout);
return 0;
}
( ) |
|
