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Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи C4 (демо ЕГЭ 2011)

Время выполнения-60 мин, уровень сложности-высокий

На вход программе подается набор символов, заканчивающийся точкой (в программе на языке Бейсик  символы можно вводить по одному в строке, пока не будет введена точка, или считывать данные из файла). Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию  языка программирования, например, Borland Pascal 7.0), которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно  один ноль.

Если требуемое число составить невозможно, то программа должна вывести на экран слово “NO”. А если  возможно, то в первой строке следует вывести слово “YES”, а во второй – искомое симметричное число.  Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:
Do not 911 to 09 do.
В данном случае программа должна вывести
YES
91019

Решение:

Программа читает все входные символы до точки один раз, подсчитывая в массиве, хранящем 10 целых чисел, количество каждой из цифр. Сами входные символы при этом не запоминаются. Затем проверяется — сколько в этом массиве нечетных элементов. Если больше одного, то задача решения не имеет. При наличии решения сначала печатается половина имеющихся цифр 9 (если таковые имеются, в случае нечетного числа цифр – меньшая половина), затем 8 и т.д. до 0, потом печатается цифра, которая встречается во входных данных нечетное число раз, а затем – оставшаяся половина цифр 0 (если таковые имеются, в случае нечетного числа цифр – меньшая половина), 1, и т.д. до 9. Если никаких цифр, кроме 0, во входных данных нет, то задача имеет решение, только если этот ноль единственный. Если нулей четное число, а ненулевая цифра единственная, то решения не существует.

Программа написана на языках:

  • Паскаль (среда разработки Turbo Pascal 7.0),
  • Бейсик (среда разработки Quick Basic 4.5),
  • Си (среда разработки Borland C++ 3.1),
  • Алгоритмический язык (среда разработки Кумир 1.9.0).

Чтобы прочесть комментарии к программе, наведите мышью на соответствующую строку. Строки, снабженные комментарием, выделены фиолетовым цветом.

Напротив названия языка программирования в скобках содержатся ссылки на скачку исходников и ехе (исполняемых файлов).

Паскаль (исходник, exe-файл) Алгоритмический язык(исходник)
var a:array['0'..'9'] of integer;
   c, c_centr: char;
   i, k: integer;
   f: boolean;
begin
  for c:='0' to '9' do a[c]:=0;
  read(c);
   while c<>'.' do
   begin

      if c in ['0' .. '9'] then
        a[c] := a[c] + 1;

    read(c);
  end;
   k := 0;

   for c := '0' to '9' do
     if a[c] mod 2 = 1 then
     begin
       k := k + 1;
       c_centr := c
     end;

   f := (a['0'] = 1);
   for c := '1' to '9' do
     if (a[c] > 1) or (a[c] = 1) and (a['0'] = 0) then
       f := true;

   if (k > 1)or not f then writeln('NO')
  else
  begin
     write(char(13)+char(10));
    writeln('YES');
     for c := '9' downto '0' do
       for i := 1 to a[c] div 2 do
         write(c);

    if k = 1 then
      write(c_centr);

    for c := '0' to '9' do
      for i := 1 to a[c] div 2 do
        write(c);

  end
end.
алг
нач
   целтаб a[0:9]
   сим с
   цел i, j, k, int_c, с_centr
   лог f, usp
    нц для i от 0 до 9
      a[i]:=0
    кц

    ввод с
   нц пока с<>"."
     int_c:=лит_в_цел(с,usp)
       если usp=да
         то a[int_c]:=a[int_c]+1

     все
     ввод с
   кц
   k:=0
   нц для i от 0 до 9
     если mod(a[i],2)=1
       то 
         k:=k+1
         c_centr:=c
     все
   кц

   f:=(a[0]=1)
   нц для i от 1 до 9
     если (а[i]>1) или (a[i]=1) и (a[0]=0)
       то f:=да
     все
   кц

   если (k>1) или не f
    то вывод 'NO'

    иначе
      вывод  'YES', нс
      нц для i от 9 до 0 шаг -1
         нц для j от 1 до div(a[i],2)
            вывод i
         кц
      кц

      если k=1
        то вывод c_centr
      все

      нц для i от 0 до 9
         нц для j от 1 до div(a[i],2)
             вывод i
         кц
      кц  

  все  
кон 
Бейсик (исходник) СИ (исходник, exe-файл)
DIM k, i, j, ccentr, a(9), f AS INTEGER
DIM c AS STRING
FOR i = 0 TO 9
   a(i) = 0
NEXT i

INPUT c
DO WHILE (c <> ".")
   IF c >= "0" AND c <= "9" THEN
     a(ASC(c) - ASC("0")) = a(ASC(c) - ASC("0")) + 1
   END IF

   INPUT c
LOOP
k = 0
FOR i = 0 TO 9
   IF a(i) MOD 2 = 1 THEN 
     k = k + 1
     ccentr = i
   END IF
NEXT i

IF a(0) = 1 THEN f = 1
ELSE f = 0
FOR i = 1 TO 9
   IF a(i) > 1 OR a(i) = 1 AND a(0) = 0 THEN
     f = 1
NEXT i

IF k > 1 OR f = 0 THEN
   PRINT "NO"

ELSE
   PRINT "YES"
   FOR i = 9 TO 0 STEP -1
     FOR j = 1 TO a(i) / 2
       PRINT i;
     NEXT j
   NEXT i

   IF k = 1 THEN PRINT ccentr;
   FOR i = 0 TO 9
     FOR j = 1 TO a(i) / 2
       PRINT i;
     NEXT j
   NEXT i

END IF
END
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <alloc.h>
#include <ctype.h>

#define false (0)
#define true (!false)
typedef unsigned char bool;

void main()
{
   int a[10],i,j,int_c,k,c_centr;
   char c;
   bool f;
    for(i=0;i<10;i++){
     a[i]=0;
    }

   scanf("\n%c",&c);
   while(c!='.'){
      if(isdigit(c)){
        int_c=c-'0';
        a[int_c]=a[int_c]+1;

     }
     scanf("%c",&c);
   }
   k=0;
    for(i=0;i<10;i++){
      if(a[i]%2==1){
        k=k+1;
        c_centr=i;
     }
   }

   f=(a[0]==1);
   for(i=1;i<10;i++){
     if((a[i]>1)||(a[i]==1)&& (a[0]==0))  f=true;
   }

  if((k>1)||!f ) printf("\nNO");
  else{
     printf("\nYES\n");
     for(i=9;i>-1;i--){
       for(j=1;j<(a[i]/2+1);j++){
         printf("%d",i);
       }
     }

     if (k==1) printf("%d",c_centr);
     for(i=0;i<10;i++){
       for(j=1;j<(a[i]/2+1);j++){
         printf("%d",i);
       }
     }

  }
   getch();
}

Работа программы на этих языках:

Задача C4 ЕГЭ по информатике 2011 работа программы

Задача C4 ЕГЭ по информатике 2011 работа программы в Кумире

Работа программы, когда получается симметричное число, но оно содержит ведущие нули:

Задача C4 ЕГЭ по информатике 2011 работа программы при наличии ведущих нулей

Задача C4 ЕГЭ по информатике 2011 работа программы при наличии ведущих нулей Кумир

Перейти к С4-2012.

Перейти к С4-2010.

Перейти к С4-2009.

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

 

Rambler's Top100

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