Задание 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;
}

Перевод числа из двоичной системы счисления в десятичную

Как вы думаете - сколько способов написать программу перевода числа из двоичной системы счисления в десятичную? Скажу просто - сколько программистов, столько и способов.
Вот некоторые из них (на С++):
1 вариант
    unsigned long long s;
    int i;
    string a;
    cin>>a;
    s=0;
   for(i=0;i<s.size();i++)
    {
        if(s[i]=="1") s=(s<<1)+1;//сдвиг влево на 1 байт плюс 1
        else s=(s<<1);
    }
    cout << "s=" << s<<endl;

2 вариант
    unsigned long long s, a, b;
    int i=0;
    cin>>a;
    s=0;
    while (a>0)
     {
         b=a%10; //выделяем последнюю цифру
         if (b==1) s=s+pow(2,i);
         a=a/10;
         i=i+1;
      }
    cout << "s=" << s<<endl;

3 вариант:
    unsigned long long s;
    string a;
    int i;   
    cin>>a;
    s=0;
   for(i=0;i<a.size();i++)
    {
        if(a[i]=="1")  s=2*s+1; //формула Горнера
        else s:=2*s;
     } 
    cout << "s=" << s<<endl;

4 вариант
using namespace std;
string n;
int l,a,i,k;
    cin >> n;
    l=n.size();
   a=0;
   k=1;
   if (n[l]=='1')
        {a=a+k;}
    for (i=l-1;i>=0;--i)
    {
        if (n[i]=='1')
        {a=a+k;}
        k=k*2;
    }
    cout << a << endl;

5 вариант
using namespace std;
int a,b,n;
int p=1;
n=0;
  cin >> a;
 while (a>0)
 {
     b=a % 10;
     a=a/10;
     if(b==1)
     {
         n=n+p;
     }
     p=p*2;
 }
 cout <<n;


6  вариант
    long long int t,q,g,u,n,s;
    float a,b,c;
    cin >> s;
    u=0;
    n=0;
    g=s;
    q=0;
    while (g!=0)
    {
        g=g/10;
        ++q;
    }
    while (n<=q)
    {
        a=pow(10,n);
        t=a;
        a=s%t;
        t=10*a/t;
        b=pow(2,(n-1));
        u=t*b+u;
        ++n;
    }
    cout << u;

7 вариант
 int b,c,d,i;
 char a[100];
 cin >> a;
 d=0;
 c=strlen(a);
 for (int i=c;i>=1;i--)
 {
   if (a[i-1]=='1')  { d=d+pow(2,c-i);}
 }
 cout << d;

8 вариант
    char a[10];
    int l, mult=1, s=0;
    cin >> a;
    l=strlen(a);
    for (int i=l;i>=1;i--)
    {
      s=s+((a[i-1]=='1')?1:0)*mult;
      mult=mult*2;
    }
    cout << s;

Если вам мало - напишите свой!

Некоторые секреты языков программирования

Есть задачи, которые можно достаточно быстро решить, зная особенности программирования на Паскале или Си.
Например, перевести число в римской системе счисления в десятичную. Известно, что римская система непозиционная и каждому символу соответствует одно и тоже значение:
M=1000
D=500
C=100
L=50
X=10
V=5
I=1
В зависимости от места в числе оно либо складывается либо вычитается: если число слева меньше стоящего рядом, то вычитается. Например, СМ = -100+1000=900.
Такого рода задачи решают либо через оператор выбора либо с помощью оператора условия. Данные хранятся в строковой переменной. Предлагаю другой вариант с помощью объявления массива с символьными индексами: var A:array['A'..'Z'] of integer;
Тогда при обращении к элементу массива с заданной буквой мы точно будем знать его значение в римской системе, т.е. A['M']:=1000, A['D']:=500 и т.д. Получим следующий код программы:
Var A:array['A'..'Z'] of integer; S:string; i,r:integer;
begin
readln(s);
A['M']:=1000;
A['D']:=500;
A['C']:=100;
A['L']:=50;
A['X']:=10;
A['V']:=5;
A['I']:=1;
r:=0;
for i:=1 to length(s)-1 do
if A[S[i]]<A[S[+1]] then r:=r-A[S[i]] else r:=r+A[S[i]];
r:=r+A[S[i+1]];
writeln(r);
end.
Все уместилось в один цикл.
Тоже самое можно сделать и в Си, так как символы в Си при считывании хранятся как байтовое его представление, то при работе с массивом достаточно указать количество символов в кодировочной таблице. Вот как будет выглядеть программа на Си:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int A[256],i,r=0,k; char s[100];
scanf("%s",&s);
A['M']=1000;
A['D']=500;
A['C']=100;
A['L']=50;
A['X']=10;
A['V']=5;
A['I']=1;
k=strlen(s);
for(i=0;i<k-1;i++)
{
if (A[s[i]]<A[s[i+1]]) r- = A[s[i]];
else r+ = A[s[i]];
}
r+ = A[s[k-1]];
printf("%d",r);
return 0;
}
Есть еще задача: вычислить частоту появления символов латинского языка (в %) в заданном тексте.
Var A:array['a'..'z'] of integer;
k,i:integer;
c:char;
begin
fillchar(A,sizeof(A),0);//инициализация массива
k:=0;
while not eof() do begin
read(c);
if c in ['a'..'z'] then begin A[c]:=A[c]+1;inc(k); end;
end;
for c:='a' to 'z' do if A[c]>0 then writeln(c,'-',A[c]/k*100:0:2);
end.
При этом сортировка в алфавитном порядке не нужна. Если нужно выводить в порядке убывания или возрастания частоты, то делаем сортировку, например, пузырек или любую другую.
Если учитывать заглавные символы, то нужно перевести все заглавные в строчные смещением на 32 в коде символа (известно, что в кодовой таблице заглавные символы отстоят от строчных ровно на 32 позиции): c:=chr(ord(c)+32); и в Си c+=32;
Точно также можно решить и другие похожие задачи, например, с числами или русскими буквами и пр.

В С++ есть удобный оператор ввода cin. С помощью него можно легко прочитать дату без перевода строки в число, учитываю точку как символ-разделитель:
#include <iostream.h>
#include <stdlib.h>
int main()
{
int day,month,year; char c;
cin>>day>>c>>month>>c>>year;//здесь символ с считывает точку
cout<<day<<"/"<<mounth<<"/"<<year;
return 0;
}
Для считывания времени символ-разделитель будет двоеточие.

Перевод натурального числа в двоичную систему счисления и обратно

Не совсем олимпиадная задача, но все же я подробно остановлюсь на ней, так как есть несколько вариантов решения этой задачи.
Известно, что остатки от деления на 2 дают цифры в двоичной системе.
Например, дано число 19:
19: 2 = 9 целых 1 в остатке
  9: 2 = 4 целых 1 в остатке
  4: 2 = 2 целых 0 в остатке
  2: 2 = 1 целых 0 в остатке
  1: 2 = 0 целых 1 в остатке
дальнейшие действия бесполезны: на ноль делим - получим ноль целых и ноль в остатке.
Для получения итогового числа собираем остатки с конца, получим: 10011
Итак, мы видим цикличность действий и условие останова (окончания цикла).
Запишем через переменные:
а - исходное число и число, которое делим на 2
с - остаток от деления
а=0 - условие останова
вывод цифр будем осуществлять в строку.

Напишем часть кода:

s:=''; readln(a);

while not (a=0) do 

begin

   a := a div 2;

   c := a mod 2;

   if  c=0 then s:=s+'0' else s:=s+'1';

end;

writeln(s);

По нашему мнению это правильно. Но давайте проверим:
Введем а = 19, т.к. a не равно 0 идем выполнять тело цикла:
a = a div 2 = 19 div 2 = 9
c = a mod 2 = 1 mod 2 =1
Что получается? Изменилось значение переменной а сразу после первого оператора присваивания! Возникает вопрос: а если поменять местами два оператора, что изменится?
c = a mod 2 = 19 mod 2 = 1
a = a div 2 = 19 div 2 =9
Что и требовалось в итоге.
Перепишем код программы:

s:=''; readln(a);

while not (a=0) do 

begin

   c := a mod 2; 

   a := a div 2;

   if  c=0 then s:=s+'0' else s:=s+'1';

end;

writeln(s);

Теперь посмотрим как собирается строка:
так как остаток равен 1, то выполнится оператор после слова else:
s=s+'1' =''+ '1'='1'

Переходим к началу цикла и проверяем условие продолжения цикла (т.е. отрицание условия останова): a<>0 (9<>0) и выполняем тело цикла:

c = a mod 2 = 9 mod 2 = 1
a = a div 2 = 9 div 2 = 4
s=s+'1'='1'+'1'='11'

Продолжим выполнение до выхода из цикла:

c = a mod 2 = 4 mod 2 = 0
a = a div 2 = 4 div 2 = 2

s=s+'0'='11'+'0'='110'

Стоп! Но ведь в результате стоит все наоборот: 10011, а не как у нас 110! Это потому что мы присоединяем цифры справа, а не слева полученной строки. Изменим оператор:
if  c=0 then s:='0'+s else s:='1'+s;

До этого все было нормально, теперь с измененным оператором
s='0'+s='0'+'11'='011'
И так далее.

Теперь рассмотрим второй вариант: используя операции shl и  shr - битовые сдвиги влево и вправо. Число 19 в двоичной системе и в памяти компьютера 00010011. Операция битового сдвига выглядит так:
19 shl 1 = [00100110]
19 shr 1 = [00001001]
Чтобы отличать десятичное число от двоичного представления, последнее заключим в квадратные скобки. Что мы имеем? При сдвиге влево все биты сдвигаются влево и добавляется 0 справа, а при сдвиге вправо все биты сдвигаются вправо, теряя 1 младший разряд, и добавляется 0 слева. Что нам это дает? Если сделаем сдвиг вправо, потом влево, то получим число без единицы, т.е. если вычитаем результат битовых операций из исходного числа, то получим младший разряд в двоичном представлении числа:
c:=a - (a shr 1) shl 1 = [00010011] - (19 shr 1) shl 1 = [00010011] - [00001001] shl 1 =
= [00010011] - [00010010] = 1.
Для дальнейшей работы нужно изменить переменную, используя операцию сдвига вправо:
a:=a shr 1 = 19 shr 1 = [00001001].

Получим следующий код программы:

s:=''; readln(a);

while not (a=0) do 

begin

   c :=a - (a shr 1) shl 1; 

   a := a shr 1;

   s:=chr(ord('0')+c)+s;

end;

writeln(s);

Объясню как образуется строчка
s:=chr(ord('0')+c)+s;
Цифры в таблице ASCII стоят по порядку от '0' до '9', поэтому, зная код нуля ord('0') и прибавляя нужное число C, можно получить символ, соответствующий этому числу.

В случае, если число достаточно большое, то используйте работу с вещественными числами (например, тип comp - у него нет дробных чисел) или длинную арифметику.

Теперь рассмотрим  обратный процесс:
 10011=1*2^4+0*2^3+0*2^2+1*2^1+1*2^0
Пусть число хранится в строке S. Тогда, зная длину строки, можно перебирать все символы строки по очереди и  выполнять умножение и сложение. Нули можно не учитывать в сложении. Но как получить степень двойки? Мы уже этот вопрос разбирали, когда обсуждали тему циклы:
p:=1;
for i:=1 to n do p:=p*2;

где n - степень числа. Но можно каждый раз не вычислять степень, а только домножать на 2 и складывать степени. Только нужно учесть в этом случае, что первым будет нулевая степень, следовательно числа нужно считывать из строки в обратном порядке:

Readln(S); 

p:=1; 

a:=0;

for i:=length(s) to 1 do

  if s[i]='1' then  a:=a+p;

  p:=p*2;

end;

writeln(a);

Вместо умножения на 2 можно использовать операцию битового сдвига влево на 1 бит:
  p:=p shl 1;
Действительно,
1 shl 1 =10 =2
2 shl 1 = 100 = 4
4 shl 1 =1000 = 8 и т. д.

Другой способ получить десятичное число - использовать схему умножения Горнера:
10011=1*2^4+0*2^3+0*2^2+1*2^1+1*2^0 = 1+2*(1+2*(0+2*(0+2*1)))
Построим рекуррентную формулу, начиная с самой первой вложенной скобки:

a=1*2+0=0+2*1
a=a*2+0=0+2*(0+2*1)
a=a*2+1=1+2*(0+2*(0+2*1))
a=a*2+1=1+2*(1+2*(0+2*(0+2*1)))
Если в начале взять a=0, то получим цикличный алгоритм:
a=a*2+1
a=a*2+0
a=a*2+0
a=a*2+1
a=a*2+1
Получили тело цикла: a:=a*2+c; где с-числовое представление символа '0' или '1'. Зная правила кодирования символов, для получения цифры из символа , воспользуемся следующим преобразованием:
с:=ord(S[i]) - ord('0');
Объясню еще раз: символы цифр в таблице ASCII стоят подряд:
'0' - допустим у нуля десятичный код 87
'1' - тогда у единицы код 88
'2' - у двойки код 89
... - и т.д.
Если знаем код числа и нуля - вычитаем и получаем соответствующую цифру:
ord('0') - ord('0') =  88-88 =0
ord('1') - ord('0') =  88-87 =1
ord('2') - ord('0') =  89-87 =2
и т.д.

Запишем код программы:

Readln(S); 

zero:=ord('0'); 

a:=0;

for i:=1 to length(s) do

  a:=a shl 1 + ord(S[i]) - zero;

end;

writeln(a);

Элегантно и просто, не правда ли?

Попробуйте получить аналогичные коды программ, если нужно преобразовать в другие системы счисления: восьмеричные, шестнадцатеричные и т. д.