Cho một dãy số khoảng 1000000 kí tự số toàn 0 và 1. Biết rằng các số 0 đứng trước các chữ số 1: 000....0011...11. Hãy cho biết vị trí của số 0 cuối cùng trong
Cho một dãy số khoảng 1000000 kí tự số toàn 0 và 1. Biết rằng các số 0 đứng trước các chữ số 1: 000....0011...11. Hãy cho biết vị trí của số 0 cuối cùng trong dãy. Thuật toán: Ta tiến hành tìm kiếm nhị phân trên xâu kí tự để tìm ra vị trí số 0 cuối cùng như sau: - Tìm phần tử giữa xâu đang xét - So sánh kí tự ở vị trí giữa xâu với kí tự 0. - Nếu kí tự giữa xâu là kí tự 0 thì ta tìm ở nửa sau của xâu, nếu không phải kí tự 0 (mà là 1) thì ta tìm ở nửa trước của xâu. //giúp mình nha !! yhamks
Lời giải 1 :
#include<bits/stdc++.h>
using namespace std;
void nhap(int a[],int n) {
for(int i=0;i<n;i++)
{
cin>>a[i];
}
}
void xuly(int a[],int d,int c) {
int mid;
while(d<=c)
{
mid=(d+c)/2;
if(a[mid]==0)
d = mid + 1;
else c = mid - 1;
}
cout<<mid-1;
}
int main()
{
int n,a[100];
cin>>n;
nhap(a,n);
xuly(a,0,n-1);
return 0;
}
Thảo luận
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 7
Lớp 7 - Năm thứ hai ở cấp trung học cơ sở, một cuồng quay mới lại đến vẫn bước tiếp trên đường đời học sinh. Học tập vẫn là nhiệm vụ chính!
Nguồn : ADMIN :))Xem thêm tại https://loigiaisgk.com/cau-hoi or https://giaibtsgk.com/cau-hoi
Copyright © 2021 HOCTAPSGK