Разбор задачи C2 (демо ЕГЭ 2004)
Определите, что делает следующая программа. Опишите в бланке ответа, что служит входными данными для программы. Что выводит программа в зависимости от входных данных?
| Программа на языке Паскаль | Программа на языке Бейсик |
|---|---|
|
Var a:array[1..1000] of integer; K,L,R,m,i,n:integer; b:boolean; begin readln(K); readln(n); for i:=1 to n do read(a[i]); b:=true; for i:=2 to n do if a[i-1]>=a[i] then b:=false; if not b then writeln(’данные некорректны’) else begin L:=1; R:=n; b:=false; while (L<=R)and not b do begin m:=(L+R)div 2; b:=(a[m]=K); if a[m]<K then L:=m+1 else R:=m-1 end; if b then writeln(m) else writeln(0) end end. |
DIM K,n,i,b,L,R, a(1000) AS INTEGER INPUT K INPUT n FOR i = 1 TO n INPUT a(i) NEXT i b = 1 FOR i = 2 TO n IF a(i – 1) >= a(i) THEN b = 0 NEXT i IF b = 0 THEN PRINT "данные некорректны" GOTO 10 END IF L = 1 R = n b = 0 WHILE (L <= R) AND (b = 0) m = (L + R) \ 2 IF a(m) = K THEN b = 1 ELSE b = 0 IF a(m) < K THEN L = m + 1 ELSE R = m – 1 END IF WEND IF b = 1 THEN PRINT m ELSE PRINT 0 10 END |
| Программа на Алгоритмическом | Программа на языке Си |
| алг нач целтаб А[1:1000] цел i, K,L,R,m,n лог b ввод K ввод n нц для i от 1 до N ввод a[i] кц b=да нц для i от 1 до N если a[i-1]>=a[i] то b:=нет все кц если b=нет то вывод ("данные некорректны") иначе L:=1 R:=n b:=нет нц пока (L<=R) и (b=нет) m:=div((L+R),2) если a[m]=K то b=да иначе b=нет все если a[m]<K то L:=m+1 иначе R:=m-1 все кц если b=да то вывод m иначе вывод 0 все все кон |
#include <stdio.h> void main(void) { int А[1000]; int i,K,L,R,m,n,b; scanf("%d", &K); scanf("%d", &n); for (i=0; i<N; i++){ scanf("%d", &a[i]); } b=1; for (i=1; i<N; i++) if (a[i-1]>=a[i]) b=0; if (b==0) printf("данные некорректны"); else{ L=1; R=n; b=0; while ((L<=R)&&(b==0)){ m=(L+R)/2; if (a[m]==K) b=1; else b=0; if (a[m]<K) L=m+1; else R=m-1; } if (b==1) printf("%d", &m); else printf("0"); } } |
Решение:
Данная программа делает следующее: используя метод двоичного поиска (деления пополам), ищет индекс элемента со значением K в отсортированном по возрастанию массиве.
В программе вводятся:- K - значение искомого элемента массива,
- n - количество элементов в массиве,
- a[индекс] - значение каждого элемента массива.
Есть 3 варианта работы программы (вывод программы):
- Массив не отсортирован по возрастанию. Программа выведет: "данные некорректны" и завершит свою работу.
- Массив отсортирован по возрастанию, в массиве нет элемента со значением K. Программа выведет 0 и завершит работу.
- Массив отсортирован по возрастанию, в массиве есть элемент со значением K. Программа выведет индекс элемента со значением K и завершит работу.