infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи 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 варианта работы программы (вывод программы):

  1. Массив не отсортирован по возрастанию. Программа выведет: "данные некорректны" и завершит свою работу.
  2. Массив отсортирован по возрастанию, в массиве нет элемента со значением K. Программа выведет 0 и завершит работу.
  3. Массив отсортирован по возрастанию, в массиве есть элемент со значением K. Программа выведет индекс элемента со значением K и завершит работу.

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В.А., 2012-2020. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта