Задание 27(С4) с пробного ЕГЭ 2015 Вариант 2.

Задача:

По каналу связи передается последовательность слов в алфавите {А, Е, Р}. Длина каждого слова не превосходит 10 букв, слова могут не быть осмысленными словами русского языка. Каждое слово передается в виде целого числа, полученного следующим образом:

1. Сначала слово кодируется с помощью неравномерного двоичного кода с кодовыми словами: Е - 0; Р - 10; А - 11.

2. К полученной двоичной последовательности b₀b₁...b_m (длина последовательности - m+1) справа приписывается еще одна цифра b_m+1 = 1;

3. Искомое число N вычисляется по формуле:

N = b₀ + 2¹ · b₁ + 2² · b₂ + ... + 2^m · b_m + 2^m+1 · b_m+1.

Например, символьная последовательность ААЕЕР будет преобразована в 11110010, затем в 111100101, а затем - в число: 1 + 2 + 4 + 8 + 64 + 256 = 335. Отметим, что 335 = 101001111₂.

Напишите программу, которая, получив на вход натуральное число, определяет, сколько раз в исходном слове встречаются гласные буквы, и выводит полученное значение на экран. Само слово выводить не нужно. 

Пример входных данных:
5483
Пример выходных данных:
4
Примечание:
В этом примере исходное слово: АЕРАЕРР
кодовая двоичная последовательность: 110101101010
после добавления 1 справа получим: 1101011010101

Решение с рассуждениями:
1) Что нам по задаче дано: одно натуральное число N.
2) Что нужно получить: количество гласных букв в закодированном слове K (счетчик).
3) Сформулируем алгоритм решения: чтобы найти закодированные символы, нужно перевести число N в двоичную систему, перевернуть двоичное представление и удалить последний символ единицу. Затем сначала выделяем группы цифр и соотносим их с кодами символов. Символы сохраняем в строку и проверяем каждый символ в строке. Если это гласная буква, то увеличиваем счетчик.
Если реализовать этот алгоритм, то можете получить только 2 балла. Попробуем упростить наши действия.
4) Определим диапазон натурального числа: максимальное количество символов в слове 10, максимальное количество бит на кодирование символа - 2, получим 2*10+1=21 бит, т.е. 3 байта. Целое число без знака не менее 3 байт - это длинное целое, занимающее 4 байта.
5) Как будем хранить двоичное представление числа? В виде строки S или в массиве целых чисел A, длиной не менее 21.
6) Как перевести число в двоичное представление? Посмотрим на примере перевода числа 83:
83 : 2 = 41 целых 1 в остатке
41 : 2 = 20 целых 1 в остатке
20 : 2 = 10 целых 0 в остатке
10 : 2 = 5 целых 0 в остатке
5 : 2 = 2 целых 1 в остатке
2 : 2 = 1 целых 0 в остатке
1 : 2 = 0 целых 1 в остатке
Собираем с конца -1010011 и переворачиваем - 1100101. Запишем алгоритм так:
пока N не равно 0 делать
   сохраняем остаток от деления N на 2  
   заменяем N на результат целочисленного деления N на 2
конец цикла пока
7) Видно, что переворачивать строку или массив не нужно. Так, если мы последовательно будем находить остатки, то их сразу будем заносить в массив или добавлять в строку справа. Переводить число в символ также не обязательно - можно просто проверить остаток на 0 и добавить к строке символ '0' или '1' если это 1.
8) Кроме этого, можно заметить, что удаление единицы можно заменить условием на N>1 вместо N<>0.
9) Как будем выделять коды символов?
Заметим, что с нуля начинается только один символ Е. Если встретилась '1', то проверяем следующий символ. Если это '0', то - символ Р (10), иначе - А (11). Таким образом можно сразу увеличивать счетчик K при проверке этих условий.
Попробуем реализовать этот алгоритм на Паскале с использованием строки:

var N: longint; i, b, m, K:integer; S:string[20];
begin
 readln(N);
 K:=0; S:='';
 while N>1 do begin
  b:=N mod 2; 
  N:=N div 2;
  if b=0 then S:=S+'0' else S:=S+'1';
 end;
 m:=length(S);
 i:=1;
 while i<=m do 
   if s[i]='0' then begin K:=K+1; i:=i+1; end
   else
      if s[i+1]='1' then begin K:=K+1; i:=i+2; end
      else i:=i+2;  
 writeln(K); 
end.

Программа на Паскале с использованием массива:

var N: longint; i, b, m, K:integer; A:array[1..20] of byte ;
begin
 readln(N);
 K:=0; i:=0;
 while N>1 do begin
  b:=N mod 2; 
  N:=N div 2;
  i:=i+1; 
  A[i]:=b;
 end;
 m:=i;
 i:=1;
 while i<=m do 
   if A[i]=0 then begin K:=K+1; i:=i+1; end
   else
      if A[i+1]=1 then begin K:=K+1; i:=i+2; end
      else i:=i+2;  
 writeln(K); 
end.

Оба варианта тянут на 3 балла. Попробуем написать на 4 балла.

10) Заметим, что цифры 0 или 1 мы получаем последовательно и их же потом и проверяем последовательно. Тогда зачем их хранить в массиве/строке? Будем сразу находить остатки и проверять условие. Приведем программу на С++:

#include <iostream>
using namespace std;
int main()
{
 int N, K=0, b;
 cin>>N; 
 while (N>1)
 { 
   b=N%2;
   N=N/2;  
   if (b==0) K++;
   else
    if (N%2==1)
   {
      K++; 
      N=N/2;
    }
  }
 cout<<K;
 return 0;
}