Андрей недавно выучил алгоритм бинарного поиска. этот алгоритм предназначен для поиска числа в отсортированном массиве чисел. к сожалению, андрей правильно уловил идею, но не до конца запомнил детали того, как нужно реализовывать этот алгоритм. реализация андрея работает следующим образом: поддерживается отрезок, на котором осуществляется поиск (изначально – весь массив) следующие действия повторяются до тех пор, пока элемент не будет найден или отрезок не станет иметь нулевую длину: выбирается элемент, находящийся в середине отрезка если элемент равен искомому числу, алгоритм завершается если элемент больше, чем искомое число, от отрезка оставляется только левая часть (та, что левее середины) если элемент меньше, чем искомое число, от отрезка оставляется только правая часть (та, что правее середины) учитель андрея по информатике заметил, что реализация андрея может выполнить разное количество итераций, в зависимости от того, на какой позиции находится искомое число, в то время как правильная реализация всегда работает за одинаковое количество итераций. теперь андрей хочет узнать, сколько итераций сделает его алгоритм в следующих условиях: массив заполнен 65535 числами от 0 до 65534, каждое число встречается один раз числа по возрастанию искомое число – 3001
Ответы
// 10.
var
n: integer;
begin
read(n);
Write((n div 100 mod 2 = 0) or (n mod 10 mod 2 = 0) or (n mod 100 div 10 mod 2 = 0));
end.
// 11.
var
n: integer;
a,b,c:integer;
begin
read(n);
a:=n div 100; b:=n mod 100 div 10; c:=n mod 10;
Write((a+b=c)or(a+c=b)or(c+b=a));
end.
// 12.
var
n: integer;
a,b,c,d:integer;
begin
read(n);
a:=n div 1000; b:=n mod 1000 div 10 div 10; c:=n mod 100 div 10; d:=n mod 10;
Write(a+b+c+d-1=a*b*c*d);
end.
// 13.
var
n,k: integer;
a,b,c:integer;
begin
Write('n,k= '); read(n,k);
a:=n div 100; b:=n mod 100 div 10; c:=n mod 10;
Write((b+c<k)and(a>5));
end.
var
n: integer;
begin
read(n);
Write((n div 100 mod 2 = 0) or (n mod 10 mod 2 = 0) or (n mod 100 div 10 mod 2 = 0));
end.
// 11.
var
n: integer;
a,b,c:integer;
begin
read(n);
a:=n div 100; b:=n mod 100 div 10; c:=n mod 10;
Write((a+b=c)or(a+c=b)or(c+b=a));
end.
// 12.
var
n: integer;
a,b,c,d:integer;
begin
read(n);
a:=n div 1000; b:=n mod 1000 div 10 div 10; c:=n mod 100 div 10; d:=n mod 10;
Write(a+b+c+d-1=a*b*c*d);
end.
// 13.
var
n,k: integer;
a,b,c:integer;
begin
Write('n,k= '); read(n,k);
a:=n div 100; b:=n mod 100 div 10; c:=n mod 10;
Write((b+c<k)and(a>5));
end.
const nx = 20;
var x: array[1..nx, 1..nx] of integer;z:array[1..nx*2] of integer;
i, j, k,n,r,t: integer;
begin
Writeln('Введите размер матрицы n');Read(n);
for i := 1 to n do begin
for j := 1 to n do begin
Read(k);x[i, j] := k; end;end;
Writeln('Исходный массив');
for i := 1 to n do begin
for j := 1 to n do begin
Write(x[i, j]:4);
if x[i, j]>0 then begin t:=t+1; z[t]:=x[i, j];end;
end;
Writeln; end;
Writeln;Writeln('Одномерный массив');
for j := 1 to t do
Write(z[j]:4);
end.
var x: array[1..nx, 1..nx] of integer;z:array[1..nx*2] of integer;
i, j, k,n,r,t: integer;
begin
Writeln('Введите размер матрицы n');Read(n);
for i := 1 to n do begin
for j := 1 to n do begin
Read(k);x[i, j] := k; end;end;
Writeln('Исходный массив');
for i := 1 to n do begin
for j := 1 to n do begin
Write(x[i, j]:4);
if x[i, j]>0 then begin t:=t+1; z[t]:=x[i, j];end;
end;
Writeln; end;
Writeln;Writeln('Одномерный массив');
for j := 1 to t do
Write(z[j]:4);
end.
Ответить на вопрос
Поделитесь своими знаниями, ответьте на вопрос:
1. 0..65534 -> 32767
2. 0..32766 -> 16383
3. 0..16382 -> 8191
4. 0..8190 -> 4095
5. 0..4094 -> 2047
6. 2048..4094 -> 3071
7. 2048..3070 -> 2559
8. 2560..3070 -> 2815
9. 2816..3070 -> 2943
10. 2944..3070 -> 3007
11. 2944..3006 -> 2975
12. 2976..3006 -> 2991
13. 2992..3006 -> 2999
14. 3000..3006 -> 3003
15. 3000..3002 -> 3001
Если лень перебирать вручную, можно воспользоваться программой
var k,l,r,x,f:integer;
begin
f := 3001;
l := 0;
r := 65534;
x := (l + r) div 2;
k := 1;
while (x <> f) and (l < r) do
begin
writeln(k,' ',l,' ',r,' ',x);
k := k + 1;
if f < x then r := x - 1
else l := x + 1;
x := (l + r) div 2
end;
writeln(k,' ',l,' ',r,' ',x);
end.