У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные

Дано два входных файла ( файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте ( все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

6
1 100
2 200
5 4
7 3
8 2
10 190

При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1·2 + 3·1 + 5·1 + 6·1 + 8·2.

Решение:

Что просят?

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

Как считать стоимость?

Пусть у нас только 4 пункта:

Посчитаем стоимость доставки по формуле |расстояние| * боксы (для каждого пункта считаем расстояние к нему, умноженное на кол-во боксов каждого пункта):

Последние числа – это стоимость доставки боксов в текущий пункт. Например, стоимость доставки в первый пункт равна 32, во второй 24 и т.д. Результаты получены квадратичным(неэффективным) алгоритмом:

   cst[] = [0 0 0 0 0 0] ; массив стоимостей
   dst[] = [1 2 5 7 8 10] ; расположения пунктов
   box[] = [2 3 1 1 1 2] ; боксы (контейнеры)
   Для i от 1 до N ; dst[i] - предполагаемый пункт
   ; dst[j] – отсюда повезём боксы(box[j]) в i-й пункт
      Для j от 1 до N 
         cst[i] = cst[i] + |dst[i]-dst[j]| × box[j]

Эффективный алгоритм

Получим числа 32, 24, 24, 48 эффективным(не квадратичным) способом. Для начала вычислим первое число (32):

   cst[] = [0 0 0 0] ; массив стоимостей
   Для i от 1 до N ;
      cst[1] = |dst[i]-dst[1]| × box[i]

   ; cst[] = [38 0 0 0] получили первое число

32 – это стоимость доставки в 1-й пункт из всех остальных пунктов. Сюда входят стоимости всех боксов справа от первого пункта и не входят боксы собственно 1-го пункта(1-й пункт не доставляет боксы сам себе – |1-1|×3=0).

Чтобы вычислить стоимости доставок в следующие пункты, воспользуемся данными о доставках, хранящихся в предыдущих пунктах. Когда мы будем получать стоимости доставок в следующие пункты, вычислять заново все боксы не нужно. Нужно лишь на каждом шаге подкорректировать данные предыдущих пунктов. Например, рассмотрим вычисление стоимости для 2-го пункта:

У 2-го пункта, предыдущий пункт – 1, его стоимость 32. Это число, для 2-го пункта, содержит недостающие и лишние данные. Недостающие данные – это та стоимость, которую мы не учли для 1-го пункта: для 1-го пункта не учтены 3 бокса (свои боксы себе возить ненужно), поэтому их нужно добавить для 2-го пункта. Лишние данные – это та стоимость, которая вошла при перевозки боксов всех пунктов, но на расстояние между 2-м и 1-м пунктом. Значит нужно вычесть длину смещения между нынешним пунктом(2) и предыдущим(1) умноженное на все боксы (другими словами, после смещения вправо предыдущая стоимость содержит лишнее значение равное длине смещения умноженное на все боксы).

Вычитание лишних и добавление недостающих данных

Вычитание лишних данных для 2-го пункта:

32 – (3-1)*2 + (3-1)*4 + (3-1)*1

но лучше так:

32 – (3-1)*(2 + 4 + 1)

Такое упрощение позволит получить оптимальный способ решения задачи – вторая скобка содержит сумму всех боксов(без 1-го пункта), и поскольку кол-во боксов известно заранее, их сумму можно вычислить один раз, для одного пункта, чтобы затем использовать для остальных пунктов. Например, для 3-го пункта вычитание будет таким:

…– (6-3)*(4 + 1)

т.е. для 3-го пункта двойку убрали.

Теперь рассмотрим добавление недостающих данных для 2-го пункта:

…+ (3-1)*3

для 3-го:

…+ (6-3)*(3+2)

Общая картина вычислений начиная со 2-го пункта (1-й пункт вычислен заранее неэффективным способом):

32 – (3-1)*(2 + 4 + 1) + (3-1)*3 = 24
24 – (6-3)*(4 + 1) + (6-3)*(3 + 2) = 24
24 – (9-6)*(1) + (9-6)*(3 + 2 + 4) = 48

boxes = 10 ; все боксы – посчитанные на 1-м проходе
left = box[1] ;left=3 боксы слева
right = boxes - left ; right=7 боксы справа
Для i от 2 до N ; начинаем со второго пункта
   cst[i] = cst[i-1] - (dst[i] - dst[i-1]) * right
                     + (dst[i] - dst[i-1]) * left

; dst[i]-dst[i-1] – расстояние на которое мы переместились слева направо
; cst[i] – стоимость доставки в текущий пункт
; cst[i-1] – ранее вычисленная стоимость доставки, которую нужно подкорректировать

; настроим боксы от которых ушли и к которым пришли
   right = right - box[i]   
   left = left + box[i]

; получение числа 24 из 32 для 2-го пункта:
; 24 = 32 – (3 - 1) * 7 + (3 - 1) * 3
Настраиваем указатели для 3-го пункта
; right = 7-2  к этим пришли, зн. их вычтем
; left = 3+2  от этих ушли, зн. их добавим

; получение числа 24 из 24 для 3-го пункта:
; 24 = 24 – (6 - 3) * 5 + (6 - 3) * 5
Настраиваем указатели для 4-го пункта
; right = 5-4  к этим пришли, зн. их вычтем
; left = 5+4  от этих ушли, зн. их добавим

; получение числа 48 из 24 для 4-го пункта:
; 48 = 24 – (9 - 6) * 1 + (9 - 6) * 9

Полный код на Python

f=open('27_B.txt')
n=int(f.readline())

dst=[0]*n #расположения пунктов
box=[0]*n #контейнеры(боксы)
cst=[0]*n #стоимости
boxes=0 #все контейнеры(боксы)

k=36

for i in range(n):
    x,y=map(int,f.readline().split())

    dst[i]=x
    box[i]=y//k + 1*(y%k!=0)

    cst[0] += (dst[i]-dst[0])*box[i]
    boxes += box[i]#суммируем все боксы

left = box[0]
right = boxes - left
for i in range(1,n):
    cst[i] = cst[i - 1] - (dst[i] - dst[i - 1]) * right \
                        + (dst[i] - dst[i - 1]) * left

    right -= box[i]
    left += box[i]

print(min(cst))

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 10 000.

Пример организации исходных данных во входном файле:

7
1
3
4
93
8
5
95

В ответе укажите два числа: сначала значение искомой длины для файла А, затем – для файла B.

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

Эффективный поиск подпоследовательности

Рассмотрим суть эффективного поиска числовой подпоследовательности, сумма которой делится на нужное число без остатка. Для простоты возьмём такую последовательность, у которой две подпоследовательности делятся, например, на 10: [2 1 5 7 8 4 12 8]

Просуммируем каждое число последовательности и разместим полученные суммы под числами последовательности:

Чтобы найти первую подпоследовательность (5 7 8), посмотрим на сумму, которая стоит под числом 8. Это число 23. Его можно превратить в 20, если вычесть 3, а число 3 стоит как вторая сумма. Значит, для поиска подпоследовательности, сумма которой делится на 10 без остатка, нужно из одной суммы вычесть другую: 2+1+5+7+8 – 2+1 = 5+7+8.

Подпоследовательность 2 1 называют «хвостом» подпоследовательности 2 1 5 7 8, который нужно вычесть, чтобы получить нужный результат:

Как теперь найти, что из общей суммы: 2+1+5+7+8 нужно вычесть именно 2+1, чтобы гарантированно получить результат, который делится на 10 без остатка?

Есть такое правило:

…которое говорит, что если два числа при делении на k дают один и тот же остаток, то их разность делится на k без остатка. У нас a – это сумма 2+1+5+7+8, b – это сумма 2+1, а k это 10

Теперь исследуем остатки, которые получатся при делении каждой суммы на 10:

Есть одинаковые остатки! Это поможет найти и вычесть хвост у последовательности, и задача решена. Рассмотрим как следить за остатками.

Массив остатков

Наша задача сохранить все суммы, и пометить какой у них остаток при делении на k. Для этого создадим массив tailSum размером k. Индекс элемента этого массива – это остаток при делении очередной суммы на k. Эту сумму нам нужно занести в массив по её остатку. Тем самым мы пометим под каким остатком хранится та или иная сумма.

Так вот, один и тот же остаток должен встретится ещё раз в процессе суммирования. А это значит, что в массиве tailSum – по индексу остатка – уже сохранена ранее сумма, и если её вычесть из общей суммы(totalSum), – получится нужная сумма(curSum).

Рассмотрим всё это по шагам:

 m = [2 1 5 7 8 4 12 8]
 k = 10
 totalSum = 0
 tailSum - [0 0 0 0 0 0 0 0 0 0]

  1 шаг
 totalSum = 2
 ;если tailSum[2 % k] = 0
 ;то в tailSum[2 % k] = 2
 tailSum - [0 0 2 0 0 0 0 0 0 0]
  
  2 шаг
 totalSum = 3
 ;если tailSum[3 % k] = 0
 ;то в tailSum[3 % k] = 3
 tailSum - [0 0 2 3 0 0 0 0 0 0]
  
  3 шаг
 totalSum = 8
 ;если tailSum[8 % k] = 0
 ;то в tailSum[8 % k] = 8
 tailSum - [0 0 2 3 0 0 0 0 8 0]
  
  4 шаг
 totalSum = 15
 ;если tailSum[15 % k] = 0
 ;то в tailSum[15 % k] = 15
 tailSum - [0 0 2 3 0 15 0 0 8 0]
  
  5 шаг
 totalSum = 23
 ;если tailSum[23 % k] != 0
 ;то curSum = totalSum - tailSum[23 % k] 23 – 3
 curSum = 20 ;нужная сумма

Программа на Python

   m = [2,1,5,7,8,4,12,8] #данная последовательность
   n = len(m)
   k = 10
   totalSum = 0
   tailSum = [0]*k  #[0 0 0 0 0 0 0 0 0 0]
   for i in range(n):
      totalSum += m[i]
      r = totalSum % k
      if tailSum[r] == 0: #был ли такой остаток или нет?
      # такого остатка ещё не было =>
      сохраняем сумму(потенциальный хвост)
      и помечаем под каким она остатком
         tailSum[r] = totalSum
      else: #такой остаток уже есть => 
      вычитаем предыдущую сумму(хвост) из текущей
         curSum = totalSum - tailSum[r]

Длина подпоследовательности

Длина подпоследовательности – это разность между двумя значениями циклической переменной i. Первое значение (начало подпоследовательности) сохраним в массив tailLen. Второе значение (конец подпоследовательности). Первое значение соответствует моменту, когда мы сохраняли первую сумму для отсечения хвоста, второе – когда нашли в tailSum не нулевое значение. Следовательно, tailLen аналогичен tailSum:

   …
   tailLen = [0]*k
   for i in range(n):
      …
      if tailSum[r] == None:
         …
         #i – первое значение длины - сохраним в tailLen
		 tailLen[r] = i
      else:
          …
		 #i – второе значение длины - из него вычтем первое
         curLen = i - tailLen[r]

Максимальная и самая короткая сумма

Максимальная сумма находится обычным делом. Кроме этого, текущая сумма может быть равной максимальной(встретились две одинаковые нужные суммы), тогда нужно убедиться, что кол-во элементов текущей суммы(currLen) меньше кол-ва элементов максимальной суммы(maxSum). Раз так – модифицируем переменные maxSum и minLen текущими значениями суммы и длины:

   …
   maxSum = minLen = 0
   for i in range(n):
   …
   else:
      …
      if curSum > maxSum or \
         (curSum == maxSum and curLen < minLen):
            maxSum = curSum
            minLen = curLen

Полный код на Python (подпоследовательность не сначала)

   m = [2,1,5,7,8,4,12,8]
   n = len(m)
   tailSum=[0]*k
   tailLen=[0]*k
   minLen=float('inf')
   totalSum=curSum=maxSum=curLen=0
   for i in range(n):
      totalSum += m[i]
      r = totalSum % k
       if tailSum[r] == 0:
          tailSum[r] = totalSum 
          tailLen[r] = i
       else: 
          curSum = totalSum - tailSum[r]
          curLen = i - tailLen[r]
          if curSum > maxSum or \
            curSum == maxSum and curLen < minLen:
             maxSum = curSum
             minLen = curLen
   print(minLen,)

Если нужная подпоследовательность вначале массива, то остаток r равен нулю, а totalSum – есть найденная сумма. При увеличении totalSum – сумма будет увеличиваться, значит проверять на максимум не нужно. Остаётся проверить длину на минимум:

Полный код на Python (подпоследовательность сначала)

   m=[5,7,8,8,4,12]
   n = len(m)
   tailSum=[0]*k
   tailLen=[0]*k
   minLen=float('inf')
   totalSum=curSum=maxSum=curLen=0
   for i in range(n):
      totalSum += m[i]
      r = totalSum % k
       if r == 0 and i < minLen:
          maxSum = totalSum 
          minLen = i+1
   print(minLen,)

Полный код на Python

   f=open('27_B.txt')
   n=int(f.readline())
   k=43
   totalSum=curSum=maxSum=curLen=0
   tailSum=[0]*k
   tailLen=[0]*k
   minLen=float('inf')
   for i in range(n):
      totalSum+=int(f.readline())
      r=totalSum%k
      if r!=0:
         if tailSum[r] == 0:
            tailSum[r] = totalSum
            tailLen[r] = i
         else:
            curSum = totalSum - tailSum[r]
            curLen = i - tailLen[r]
            if curSum > maxSum or \
              curSum == maxSum and curLen < minLen:
               maxSum = curSum
               minLen = curLen
      elif i < minLen:
         maxSum = totalSum
         minLen = i+1
print(minLen)

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.

Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Входные данные

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 10 000 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

6
1 3
5 12
6 9
5 4
3 3
1 1

Для указанных входных данных значением искомой суммы должно быть число 32.

В ответе укажите два числа: сначала значение искомой длины для файла А, затем – для файла B.

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

Сумма максимумов

Выберем данную последовательность из шести пар и просуммируем максимальное число каждой пары:

   l = [1,5,6,5,3,1] # первое число пары
   r = [3,12,9,4,3,1] # второе число пары
   n = len(l) # а можно и len(r)
   s = 0
   for i in range(n):
      a=l[i]; b=r[i]
      s += max(a, b)

Сумма будет 33(переменная s). Если бы сумма не делилась на 3, то она бы являлась ответом. Но она делится, значит, одно максимальное число(неважно какое), которое попало в сумму, нужно поменять на минимальное из той же пары – да так поменять, что это минимальное в паре число, должно быть самым минимальным среди всех минимальных(это условие максимально возможной суммы).

Поиск нужного минимума

В нашем примере, вместо максимального числа 5, нужно использовать 4. Как его найти эффективно?

В процессе суммирования находим минимальную разницу между парами, которая не делится на 3:

   ...
   min = 10001
   for i in range(n):
      ...
      d = abs(a-b)
      if(d%3 != 0) and (d < min):
         min = d

Единица в последней паре не подойдёт в качестве минимума, потому что оба числа пары равны и от того первое выражение условия даст отрицание.

Вывод на экран

Переменную min применим, если сумма делится на 3, иначе выведем сумму:

   ...
   for i in range(n):
      ...
   if s%3==0:
      print(s-min)
   else:
      print(s)

Полный код на Python

   f = open('27.txt')
   n = int(f.readline())
   s = 0
   min = 10001
   for i in range(n):
      a,b = map(int,f.readline().split())
      s += max(a,b)
      d = abs(a-b)
      if(d%3 != 0) and (d < min):
         min = d
# вывод на экран
   if s%3==0:
      print(s-min)
   else:
      print(s)

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i < j и a_i > a_j (первый элемент пары больше второго; i и j – порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел n (2 ≤ n ≤ 12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.

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

Пример входных данных:

6
60
140
61
100
300
59

Пример выходных данных для приведённого выше примера входных данных:

140 100

Пояснение.Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m=120: 60+300, 140+100 и 61+59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Поиск пары

Пары будут двух типов: каждый элемент пары не кратный m, а сумма элементов кратна, и каждый элемент пары кратный m – сумма также кратна.

Рассмотрим, как искать пару, сумма которой кратна m, но каждый элемент не кратный. Есть правило:

которое говорит, что если два числа при делении на m дают остатки, сумма которых делится на m, то и сумма чисел делится на m. Например: пусть m=5, a=8 и b=12, тогда:

Теперь как найти, среди последовательности чисел, пару 8 и 12, сумма которой делится на 5.

Удобнее всего через так называемый массив остатков r размером m. На самом деле элементы этого массива – это числа последовательности, а индексы этих элементов – остатки от деления элементов на m. Пусть наши 8 и 12 расположены в такой последовательности: [ 8 14 12 ], тогда массив остатков r[m] будет таким:

Мы ищем пару по индексам: пусть под одним индексом есть ненулевой элемент массива, тогда если мы обнаруживаем, что есть ещё ненулевой элемент, индекс которого даёт сумму с первым индексом кратную 5, то сумма элементов также кратна 5.

Как найти 2-й индекс? По m и по 1-му индексу: 2-й индекс = m – 1-й индекс. В нашем случае 2-й индекс это 3, а 1-й – это 2. Всё потому что, когда мы проверяем число 8(индекс 3) - его пара под индексом 2 хранит нулевое значение и поэтому по 3-му индексу пару найти невозможно:

Но когда проверяем число 12 (индекс 2) - его пара под индексом 3 хранит не нулевое значение:

Вот тогда то, мы и находим нужную пару:

 
   m = 5
   d = [8,14,12] # последовательность
   r = [0,0,0,0,0] # массив «остатков»
   for i in range(len(d)):
      a = d[i] # a удобнее чем d[i]
      p = a % m
      if r[m-p]>0: # false при a=8, true при a=12 
         print (r[m-p], " ", a) # 8 12
      r[p] = a # заполняем массив остатков (пока они различны)

Первый больше второго

По условию, первый элемент пары должен быть больше, значит наша последовательность - [ 8 14 12 ] - не содержит нужной пары. Поменяем местами 8 и 12 и в условии учтём, что предыдущий сохранённый элемент массива остатков больше чем текущий:

 
   m = 5
   d = [12,14,8] # последовательность
   r = [0,0,0,0,0] # массив «остатков»
   for i in range(len(d)):
      a = d[i] # a удобнее чем d[i]
      p = a % m
      if r[m-p]>a: # предыдущий r[m-p] больше текущего a 
         print (r[m-p], " ", a) # 8 12
      r[p] = a # заполняем массив остатков (пока они различны)

Теперь предыдущая последовательность - в связи с тем, что она неправильная - не будет найдена.

Пара с максимальной суммой

По условию, нужная пара должна давать максимальную сумму среди всех нужных пар, т.е. пар может быть несколько, а выбрать нужно ту, которая даёт максимальную сумму. Добавим в условие выражение, которое сравнивает сумму текущей пары с парой сохранённой ранее

Кроме этого, нужно учесть, что в последовательности может быть не одно число с одним и те же остатком, тогда если оно больше предыдущего, то в массиве остатков меняем предыдущее на текущее. Если остатки разные, то массив остатков будет заполняться, так же как и раньше:

 
   m = 5
   d = [22,38,8,14,2] # Нужная 38 и 2 среди ещё одной 22 и 8
   r = [0,0,0,0,0] # массив «остатков»
   left = 0; right = 0 # элементы нужной пары
   for i in range(len(d)):
      a = d[i] # a удобнее чем d[i]
      p = a % m
      if r[m-p]>a and r[m-p]+a > left+right:
         left = r[m-p]
         right = a
      if a>r[p]: # a > предыдущего с таким же остатком
         r[p] = a # значит заменим его на a
   print (l, " ", r) # 38 2

Один тип пары мы выбрали, переходим к другому типу – каждый элемент которого кратный m.

Пара элементов кратные m

Случай с одной парой, причём пусть, первый элемент меньше второго(далее исправим): [10, 14, 15]

 
   m = 5
   d = [5,14,10] # последовательность
   r = [0,0,0,0,0] # массив «остатков»
   for i in range(len(d)):
      a = d[i] # a удобнее чем d[i]
      p = a % m
      if r[m-p]>0: # false при a=8, true при a=12 
         print (r[m-p], " ", a) # 8 12
      r[p] = a # заполняем массив остатков (пока они различны)

Первый больше второго(среди кратных m)

Поменяем местами 5 и 10, затем изменим условие:

 
   m = 5
   d = [10,14,5] # последовательность
   r = [0,0,0,0,0] # массив «остатков»
   for i in range(len(d)):
      a = d[i] # a удобнее чем d[i]
      p = a % m
      if r[0]>a: # предыдущий r[0] больше текущего a 
         print (r[0], " ", a) # 10 5
      r[p] = a # заполняем массив остатков (пока они различны)

Теперь предыдущая последовательность, в связи с тем, что она неправильная, не будет найдена.

Пара с максимальной суммой(среди кратных m)

Аналогично соответствующему пункту данной задачи добавим переменные для максимальных элементов пар и изменим условие:

 
   m = 5
   d = [10,35,5,14,15] # Нужная 35 и 15, ненужная 22 и 8
   r = [0,0,0,0,0] # массив «остатков»
   left = 0; right = 0 # элементы нужной пары
   for i in range(len(d)):
      a = d[i] # a удобнее чем d[i]
      p = a % m
      if r[0]>a and r[0]+a > left + right:
         left = r[0]
         right = a
      if a>r[p]: # a > предыдущего с таким же остатком
         r[p] = a # значит заменим его на a
   print (l, " ", r) # 35 15

Теперь учтём, что может быть два типа пар.

Полный код на Python

 
   d = [10,35,5,14,15,22,38,8,14,2]
   m = 120
   r = [0] * m # числа, которых ищут по остатку
   left=0; right=0
   n = len(d)
   for i in range(n):
      a = d[i]
      p = a % m
      if p == 0: # кратные m
         if r[0] > a and r[0] + a > left+right:
            left = r[0]
            right = a
      else:# не кратные m
         if r[m-p]>a and r[m-p]+a > left+right:
            left = r[m-p]
            right = a
      if a>r[p]: # a > предыдущего с таким же остатком
         r[p] = a
   print(l," ",r)

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

Пример входных данных:

7
58
2
3
5
4
1
29

Пример выходных данных для приведённого выше примера входных данных:

5

Пояснение.Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58·4, 58·1, 58·29, 2·1, 2·29, 3·29. Из них на 29 делятся 5 произведений.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Внимание! Для простоты, вместо деления на 29 будем проверять на чётность.

Эффективный алгоритм по времени, но не по памяти

Будем умножать конкретное число x с остальными числами последовательности, которые стоят на расстоянии ≥ 4 от x. Следовательно, ближайшие к x три числа пропускаем мимо. x.

Закрасим ненужные 3 числа красным, x – зелёным, а умножаемые с x–ом числа – синим цветом.

Может быть два случая:

1. x – чётный
2. x – нечётный

Тогда суммируем либо все синие числа(случай 1), либо только те синие, которые делятся на 2 (случай 2).

В 1-м случае кол-во чётных результатов будет равно кол-ву произведений x–а с числами синего цвета:

шаг 1

одно произведение: 6 * 8, здесь x = 6, он на 5-ом месте последовательности (нумерация с 1)

шаг 2

два произведения: 2 * 8 и 2 * 3, здесь x = 2, он на 2-ом месте последовательности

шаг 4

четыре произведения: 4 * 8, 4 * 3, 4 * 4, 4 * 7, здесь x = 4, он на 8-ом месте последовательности

В 2-м случае кол-во чётных результатов будет равно только кол-ву чётных синих чисел:

шаг 3

два произведения: 1*8 и 1*4, здесь x = 1, он на 7-ом месте последовательности

Для 1-го случая считать чётные произведения будет разница положения x–а и кол-во розовых чисел:

   count = count + x – 3

Для 2-го случая понадобится переменная, которая считает чётные синие числа

   count = count + b ;где b уже знает сколько чётных синих

Остаётся считать кол-во чётных синих чисел:

   b = b + 1

Полный код на Python

   d = 4 #расстояние до ближайшего нужного числа
   a = [8,3,4,7,6,2,1,4]
   n = len(a)
   count = 0 #кол-во чётных пар всего
   b = 0 #кол-во чётных синих чисел
   for i in range(d,n): #прицеливаемся на x=6
      if a[i-d]%2 == 0:
         b += 1
      if a[i]%2 == 0: #x делится на то что нужно?
         count += i-d+1 #count=count+x-3
      else:
         count += b
   print(count)

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.

Пример входных данных:

4
2
6
13
39

Пример выходных данных для приведённого выше примера входных данных:

4

Пояснение.Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234).

Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Решение

Пример входных данных неудачный: он не содержит чисел 26, поэтому мы не можем учесть такие пары, в которых либо ОБА элемента делятся на 26, либо ТОЛЬКО ОДИН. Пусть будет такая последовательность: 26 3 8 52 78. Из неё получаем неповторяющиеся пары: 26-3, 26-8, 26-52, 26-78, 3-8, 3-52, 3-78, 8-52, 8-78, 52-78. Теперь посчитаем, сколько будет произведений пар, которые делятся на 26.

ОБА элемента делятся на 26

Если оба элемента делятся на 26, то и их произведения тоже делятся. Из неповторяющихся пар, есть три пары, у которых оба элемента делятся на 26: 26-52, 26-78, 52-78. Формула, которая вычисляет кол-ва таких пар: (n26·(n26-1))/2, где n26 – это количество чисел в последовательности, которые делятся на 26. У нас n26=3(26,52 и 78), значит (3·(3-1))/2=3

ТОЛЬКО ОДИН элемент делится на 26

Шесть пар, у которых только один элемент делится на 26: 26-3, 26-8, 3-52, 3-78, 8-52, 8-78. Формула, которая вычисляет кол-ва таких пар: n26·(n-n26), где n – это количество чисел в последовательности. У нас n=5, значит 3·(5-3)=6

26=2·13

Теперь, случай, где элементы не кратны 26, но их произведение дадут число 26. Это число можно получить по двум множителям: 2 и 13. Значит нужно посчитать кол-во пар, у которых один элемент 2, другой 13. Для этого есть формула: n2·n13, где n2 – это кол-во чисел, которые делятся на 2 и n13 – кол-во чисел, которые делятся на 13.

Полный код на Python

   f = open('2018_27.txt') #4 2 6 13 39
   n = int(f.readline())#n=4
   n26 = n2 = n13 = 0
   for i in range(n):
      x = int(f.readline())
      if x%26 == 0:
         n26 += 1
      elif x%13 == 0:
         n13 += 1
      elif x%2 == 0:
         n2 += 1      
   print((n26*(n26-1))//2+n26*(n-n26)+n2*n13)

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить « бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.

Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.

Пример входных данных:

11
12
45
5
3
17
23
21
20
19
18
17

Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.

Пример выходных данных для приведённого выше примера входных данных: 54

Решение

Пусть для простоты расстояние будет не 6, а 3, и возьмём небольшие числа: 6 1 3 5 7 9 2 4 8. После того как составим алгоритм заменим 3 на 6.

Множители на расстоянии

Сохраним 1-ые 3 элемента входных данных в массив. Затем настроимся к оставшимся числам последовательности:

   a = [6 1 3 5 7 9 2 4 8]
   m = [6 1 3] # сохраняем первые 3 
   for i in range(3,n):# i = [3..n)

Получилась заготовка для обращений чисел, расположенных на расстоянии трёх элементов. Элементы массива m выделены синим цветом, а нужные элементы массива a – зелёным.

Умножение

Схема умножения для первых трёх шагов:

Перед умножением элемента массива m, проверим его на минимум и сохраним его в minx:

   …
   minx = 1001   
   for i in range(3,n):# a[3] = 5
      if m[i%3] < minx: #[3%3]=0, [4%3]=1, [5%3]=2
         minx = m[i%3]

На третьем шаге в minx будет 1 – это значит, что не нужно беспокоиться о «пропущенном» произведении: 6*7, 6*9… – раз нужно минимальное произведение, то проверять произведения 6-ки со всеми кроме ближайших по условию не нужно.

Теперь умножаем числа расположенные на расстоянии 3-х элементов:

   …
   x = a[i] # a[i] = 5
   p = minx * x	 

Проверим произведение на минимум и чётность:

   …
      if (p%2==0 and p < minp):
         minp = p

minp – хранит минимальное чётное произведение, которое будет результатом

Следующее умножение

Теперь самое интересное. В конце цикла заменяем текущий элемент массива m, на x, т.о., за три шага создаём следующую тройку для произведения:

   …
      m[i%3] = x # при i=3, m[0] = 5	 

Т.е. когда, на втором шаге, будут умножаться 1 на 7 – в первом элементе массива m вместо 6 будет значение 5, которое через два шага будет умножаться на 2, и т.д. Так, выделены красным элементы массива m после трёх шагов цикла:

Теперь полный код, в котором заменено значение 3 на 6

Полный код на Python

 
  a=[12,45,5,3,17,23,21,20,19,18,17]
  n=len(a) # n=11
  m=[0]*6
  minp=1000001;minx=1001
  for i in range(6):
     m[i]=a[i]

  for i in range(6,n):
     if m[i%6] < minx:
        minx=m[i%6]
     x=a[i]
     p=minx*x
     if(p%2==0 and p < minp):
        minp=p
     m[i%6]=x
# если ни одного произведения не нашлось, то выведем -1
  if minp == 1000001:
     print (-1)
  else:
     print(minp) 

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

Завуч школы № 50 решила наградить двух учащихся, которые лучше всех в школе сдали информатику.

Программа должна вывести на экран фамилии и имена этих учеников.

Если наибольший балл набрало больше двух человек – вывести количество таких учеников.

Если наибольший балл набрал один человек, а следующий балл набрало несколько человек — нужно вывести только фамилию и имя лучшего.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников школы № 50.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
Круглов Василий Тарасова Дарья
Другой вариант выходных данных:
7
Третий вариант выходных данных:
Гусарский Илья

Решение:

Нужно, из множества всех учеников получить подмножество учеников конкретной школы(№50). Далее в этом подмножестве выбрать лучших учеников. Эффективная программа должна реализовать этот сложный отбор одним циклом:

	
	Цикл по всем ученикам
		Если ученик из 50-й школы то	
			Выбор лучших
	

Выбор лучших

Введём переменные:

max1 – максимальный бал или максимум,

max2 – второй максимум,

ball – текущий бал ученика 50-й школы.

Выбор лучших – это алгоритм с вложенным ветвлением. Для простоты рассмотрим его по частям. Их четыре:

1. Пусть есть возрастающая последовательность чисел, например, такая [1 2 3 4 5]: один максимум(5) и один второй максимум(4). Тогда алгоритм можно написать так:

	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
	

2. Теперь случай, где два одинаковых максимума(5): [1 5 3 4 5]. Добавим новую ветку условия:

	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
		иначе если ball = max1 то
			max2 = ball			
	

т.е. max1 и max2 содержат одинаковые значения.

3. Второй максимум(4) правее максимума(5): [1 5 3 4 2]. Добавим третью ветку условия:

	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
		иначе если ball = max1 то
			max2 = ball
		иначе если ball = max2 то
			max2 = ball
	

(во 2-м и 3-м условиях стоят одинаковые операторы – можно было бы написать одно сложное условие, однако далее операторы будут меняться).

4. Последний случай. Количество вторых максимумов(4) может быть более одного: [1 5 4 2 4]; здесь также добавляем условие, в котором подсчитывается их количество.

Наконец, количество максимумов(5) может быть более двух [1 5 2 5 5] – их также нужно подсчитывать. Добавим для них переменные и дополним алгоритм:

n1 – количество максимумов,

n2 – количество вторых максимумов.

	max1 = max2 =-1
	n1 = n2 = 0
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
			n2 = n1
			n1 = 1
		иначе если ball = max1 то
			max2 = ball
			n1 = n1 + 1
		иначе если ball = max2 то
			max2 = ball
			n2 = 1
		иначе если ball = max2 то
			n2 = n2 + 1
	

Обратим внимание на строку n2=n1. Здесь в n1 сохранено количество «бывших» максимумов: оно может быть либо 1, либо больше 1. И ещё, оператор последнего условия не содержит присваивания переменной max2, дело в том, что в max2 уже было присвоено значение.

Имена

Осталось добавить имена учеников:

s – фамилия и имя ученика из 50-й школы,

s1 – фамилия и имя ученика с максимальным баллом,

s2 – фамилия и имя ученика с вторым максимальным баллом.

	max1 = max2 =-1
	n1 = n2 = 0
	s1 = s2 = ""
	цикл для всех из 50-й школы
		s = Ф. И. ученика из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
			n2 = n1
			n1 = 1
			s2 = s1
			s1 = s
		иначе если ball = max1 то
			max2 = ball
			n1 = n1 + 1
			s2 = s
		иначе если ball = max2 то
			max2 = ball
			n2 = 1
			s2 = s
		иначе если ball = max2 то
			n2 = n2 + 1
	

Аналогично, оператор последнего условия не содержит присваивания имени потому, что ранее оно уже было присвоено корректным значением.

Вывод результатов

Двое лучших – это либо два одинаковых максимальных балла, либо один максимум и один второй максимум. Один лучший – это когда один победитель, а количество вторых максимумов более одного. В остальных случаях получим вывод, в котором количество максимумов – больше двух:

	если n1==1 и n2==1 или n1==2 то
		печать s1, s2
	иначе если n1==1 и n2>1 то
		печать s1
	иначе
		печать n1

Цикл по всем ученикам

Переходим на Python. Найдём количество учеников из всех школ. Если данные нашей задачи хранятся в файле, то первая строка файла содержит это значение. Вот как можно подключиться к файлу, а затем извлечь всех учеников в переменную N:

	f = open("имяфайла.txt", encoding='utf-8', mode="r")
	N = f.readline()
	

N, нам понадобится для организации цикла по всем ученикам:

	for i in range(int(N))

Ученик из 50-й школы

После N идут строки со значениями, значения разделены пробелом. Функция split разбивает каждую прочитанную строку в массив подстрок:

	array = f.readline().split()

Откуда: array[0] – первая подстрока с фамилией, array[1] – вторая подстрока с именем, array[2] – номер школы и наконец, array[3] – набранный балл. Теперь проверить 50-ую школу можно так:

	school = int(array[2])
	if school == 50:

Фамилия и имя получается сложением:

	s = array[0] + " " + array[1]

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  max1 = max2 = -1
  n1 = n2 = 0
  s1 = s2 = ""
  for i in range(n):
      a = f.readline().split()
      #a[0] - Фамилия
      #a[1] - Имя
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
      s = a[0] + " " + a[1]
      school = int(a[2])
      ball = int(a[3])
      if school == 50:
          if ball > max1:
              max2 = max1
              max1 = ball
              n2 = n1
              n1 = 1
              s2 = s1
              s1 = s
          elif ball == max1:
              max2 = ball
              n1 += 1 
              s2 = s
          elif ball > max2:
              max2 = ball
              n2 = 1
              s2 = s
          elif ball == max2:
              n2 += 1
  # Вывод результатов
  if n1==1 and n2==1 or n1==2:
      print (s1, " ",s2)
  elif n1==1 and n2>1:
      print(s1)
  else:
      print(n1)
  f.close()

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

Районный методист решила выяснить номер школы, ученики которой набрали наибольший средний балл, с точностью до целых.

Программа должна вывести на экран номер такой школы и её средний балл.

Если наибольший средний балл набрало больше одной школы — вывести количество таких школ.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более, чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
50 74
Другой вариант выходных данных:
7

Решение:

Сумма баллов

Пусть количество школ 3, а количество учеников 6 (N=6). И пусть будут такими номера школ и баллы учеников:

2 6

3 15

1 8

2 10

3 9

2 7

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

Получаем такой массив после суммирования:

Алгоритм суммирования массива баллов:

	Цикл для i от 0 до 5 учеников
		m = № школы из i-й строки данных
		ball = балл ученика m-й школы
		sum[m] = sum[m] + ball
	

Данные массива sum после выполнения алгоритма:

sum[0]=8

sum[1]=23

sum[2]=24

Средний бал

Средний балл = сумма баллов школы/количество учеников школы.

где числитель – это массив из пункта Сумма баллов, а знаменатель – это ещё один массив такого же размера, только каждый элемент этого массива – это количество учеников в конкретной школе. Другими словами, знаменатель – это количество плюсов на схеме из пункта Сумма баллов. Значит, во время суммирования баллов каждой школы, увеличиваем на 1 i-й элемент второго массива:

	Цикл для i от 0 до 5 учеников
		m = № школы из i-й строки данных
		ball = балл ученика m-й школы
		sum[m] = sum[m] + ball
		cnt[m] = cnt[m] + 1
	

Данные массива sum и cnt после выполнения алгоритма:

sum[0]=8

sum[1]=23

sum[2]=24

cnt[0]=1

cnt[1]=3

cnt[2]=2

Ну, а теперь вычисление среднего балла. Для этого понадобится ещё один цикл, но уже по школам:

	Цикл для i от 0 до 2 школ
		sum[i] = sum[i] / cnt[i]
	

Данные массива sum после выполнения алгоритма:

sum[0]=8

sum[1]=7,66

sum[2]=12

Однако мы не учли отсутствие номеров некоторых школ. Это значит, что массивы sum и cnt где-то содержат нули – будет деление на ноль. Полный код на Python учтёт это.

Поиск лучших школ

По условию лучших школ может быть либо одна, либо две и более. В первом случае нужно сохранить номер школы и средний балл – это обычный поиск максимума:

	max = sum[0] ;сохраняем в max ср.балл школы №1
	n = 0 ;номер школы, пока 0
	Цикл для i от 1 до 2 школ ;начинаем со школы №2
		если sum[i] > max то
			max = sum[i]
			n = i;сохраняем в n № школы
	

Во втором случае нужно сохранить количество школ. Это сравнение на равенство среднего балла текущей школы с сохранённым ранее максимальным средним баллом – max :

	max = sum[0] ;сохраняем в max ср.балл школы №1
	n = кол-во = 0 ;номер школы и кол-во учеников, пока 0
	Цикл для i от 1 до 2 школ ;начинаем со школы №2
		если sum[i] > max то
			max = sum[i]
			кол-во = 1
			n = i   ;сохраняем в n № школы
		иначе если sum[i] = max то
			кол-во = кол-во + 1
	

Нужно написать эффективную по памяти программу, для этого можно исключить переменную n. Тогда в max сохранять не значение среднего балла первой школы(sum[0]), а индекс самой школы, затем произвести изменения в условном операторе. Это будет сделано в полном коде на Python.

Вывод результатов

Проверяем количество лучших школ, если лучшая школа одна, то выводим номер школы и её средний балл. В остальных случаях выводим количество:

	если кол-во = 1 то
		печать n max
	иначе
		печать кол-во
	

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  nsch = 99 #кол-во школ [1..99]
  sum = [0] * nsch # массив суммарных баллов по каждой школе
  cnt = [0] * nsch # массив количеств учеников в каждой школе

  #суммируем баллы и считаем кол-во учеников по каждой школе
  for i in range(n):
    #a[0] - Фамилия (она не нужна)
    #a[1] - Имя (оно не нужно)
    #a[2] - номер школы [1..99]
    #a[3] - балл ученика(цы)
      a = f.readline().split()
      isch = int(a[2])-1 # isch - [0..98]
      sum[isch] += int(a[3])
      cnt[isch] += 1

  #средний балл
  for i in range(nsch):
#из-за отсутствия номеров некоторых школ, избегаем деления на 0
      if cnt[i]>0:
          sum[i] = sum[i] / cnt[i]

  #Поиск лучших школ
  max = 0
  n = 0
  for i in range(1,nsch):
      if sum[i] > sum[max]:
          max=i
          n=1
      elif sum[i] == sum[max]:
          n += 1
  
  #Вывод результатов
  if n == 1:
      print(max+1," ",sum[max])
  else:
      print(n)

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

Районный методист решила выяснить номера школ, ученики которых набрали средний балл по школе, больший, чем районный средний балл (все средние баллы вычисляются с точностью до целых).

Программа должна вывести на экран номера таких школ, в любом порядке.

Если такая школа окажется только одна — вывести также средний балл по этой школе, с указанием, что это средний балл.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия><Имя><Номер школы><Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
5 50 74 87
Другой вариант выходных данных:
7
Средний балл = 74

Решение:

Средние баллы по району и школе

Cр.балл по району = Все баллы / N

Средний балл по школе = Сумма баллов по школе / кол-во учеников школы

Сумму баллов по школе получаем как в примере 2011 С4 №2: создаём массив sum из 99 элементов(кол-во школ), заносим сумму баллов школы в каждый элемент. Добавим подсчёт кол-ва учеников в массив cnt:

	Цикл для i от 0 до N-1
		m = № школы из i-й строки данных
		ball = балл ученика m-й школы
		sum[m] = sum[m] + ball ;суммы баллов по m-ой школе
		cnt[m] = cnt[m] + 1 ;кол-во учеников m-ой школы

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

Т.к. некоторых номеров школ нет, то соответствующие элементы массивов sum и cnt содержат нули. Для этого нужно следить, чтобы, при вычислении среднего, не было деления на ноль:

	avg = 0 ;переменная для всех баллов
	Цикл для i от 0 до 98 школ
		если sum[i] > 0 то
		avg = avg + sum[i] ;суммируем все баллы
		sum[i] = sum[i] / cnt[i]  ;средний балл по школе

Обратим внимание на две строки условия. Сначала суммируем баллы всех школ. Затем на место суммы баллов по школе, помещаем средний балл по этой же школе – тем самым не создаём лишнюю переменную для среднего значения.

Средний балл по району:

	avg = avg / N

Вывод результатов

Вывод номера или номеров школ проведём с помощью сравнения среднего балла по школе со средним баллом по району. Если балл по школе больше балла по району, то выведем её номер:

	Цикл для i от 0 до 98 школ
		если sum[i] > avg то
			печать i

Ну, а если школа единственная, то нужна переменная n, которая посчитает кол-во сравнений и переменная ball, которая сохранит балл этой единственной школы:

	m=0
	Цикл для i от 0 до 98 школ
		если sum[i] > avg то
			m = m + 1
			ball = sum[i]	
			печать i
	если m = 1 то
		печать "Средний балл:" ball			

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  nsch=99 # кол-во школ [1..99]
  sum = [0] * nsch # массив суммарных баллов по каждой школе
  cnt = [0] * nsch # массив количеств учеников в каждой школе

  #суммируем баллы и считаем кол-во учеников по каждой школе
  for i in range(n):
      #a[0] - Фамилия (она не нужна)
      #a[1] - Имя (оно не нужно)
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
      a = f.readline().split()
      isch = int(a[2])-1 # isch - [0..98]
      sum[isch] += int(a[3])
      cnt[isch] += 1

  #средний балл по школе
  avg = 0
  for i in range(nsch):
    if cnt[i] > 0:
        avg = avg + sum[i]  # суммируем все баллы
        sum[i] = sum[i] / cnt[i] # средний балл по школе

  #средний балл по району
  avg /= n

  #Вывод результатов
  m = 0
  for i in range(nsch):
      if sum[i] > avg:
          m += 1
          ball = sum[i]
          print(i+1, end=' ')
  if m == 1:
      print("Средний балл:",ball)
	

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

Районный методист решила выяснить фамилии учеников, которые набрали наибольший балл, по каждой школе в отдельности, но только если из школы информатику сдавало не меньше трёх человек. Если в школе информатику сдавало меньше трёх человек, информацию по этой школе выводить не нужно. Если наибольший балл в какой-то школе набрали несколько человек, нужно вывести на экран их количество.

Программа должна вывести на экран информацию в виде:

<Номер школы> <Фамилия ученика>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

в отдельной строке для каждой школы.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 0 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
5 Иванов
50 10
74 Сидоров

Решение:

Количество учеников сдававших экзамен в школе

Каждая строка данных содержит номер школы, который мы присвоим в переменную m. Эта m будет индексом массива cnt, который будем использовать для хранения кол-ва учеников в школе номером m:

    cnt [99] ;кол-во учеников в школе
    Цикл для i от 0 до N-1 ;цикл по строкам данных
        m = № школы из i-й строки данных
        ;считаем кол-во учеников в m-й школе
        cnt[m] = cnt[m] + 1

Т.о., каждый элемент массива cnt – это кол-во учеников в школе, номер которой есть индекс элемента

Наибольший балл

Вспомним пример ЕГЭ 2011 С4 №1, первая часть пункта Выбор лучших. Только здесь понадобится сохранять не одно лучшее значение, а лучшие значения для каждой школы: в массиве bal:

    bal [99] ;кол-во учеников в школе
    Цикл для i от 0 до N-1 ;цикл по строкам данных
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball

Количество лучших учеников

Продолжаем воспоминания примера ЕГЭ 2011 С4 №1 второй части пункта Выбор лучших, и добавим вторую ветку нашему алгоритму. В ней, в массиве amt, будем считать количество одинаковых максимальных баллов школы номером m.

    bal [99] ;кол-во учеников в школе
    amt [99] ;кол-во лучших в школе
    Цикл для i от 0 до N-1 ;цикл по строкам данных
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball
            amt[m] = 1 ;кол-во лучших в школе m пока 1
        иначе если ball = bal[m] то
            amt[m] = amt[m] + 1 ;считаем кол-во лучших в школе m

Имена

Такой же пункт Имена как в примере ЕГЭ 2011 С4 №1, а в нашей задаче нужно учесть только фамилию, если лучший в школе единственный:

    bal [99] ;наибольший балл в школе
    amt [99] ;кол-во лучших в школе
    nam [99] ;фамилия одного лучшего в школе
    Цикл для i от 0 до N-1
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        s = фамилия ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball
            amt[m] = 1
            nam[m] = s
        иначе если ball = bal[m] то
            amt[m] = amt[m] + 1

Алгоритмы, которые мы рассмотрели, выполняются в одном цикле. В полном коде мы их объединим в один.

Вывод результатов

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

	Цикл для i от 0 до 98 школ
        если сnt[i] > 2 то
            если amt[i] = 1 то
                печать i nam[i] ;номер школы и имя лучшего
            иначе
                печать i amt[i] ;номер школы и кол-во лучших

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  nsch = 99 #кол-во школ [1..99]
  cnt = [0] * nsch #кол-во учеников в школе
  bal = [0] * nsch #наибольший балл в школе
  amt = [0] * nsch #кол-во лучших учеников в школе
  nam = [''] * nsch #фамилия одного лучшего в школе

#суммируем баллы и считаем кол-во учеников по каждой школе
  for i in range(n):
      #a[0] - Фамилия
      #a[1] - Имя, оно не нужно
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
     a = f.readline().split()
     m = int(a[2])-1 #isch - [0..98]
     ball = int(a[3])
     if  ball > bal[m]:
        bal[m] = ball
        amt[m] = 1
        nam[m] = a[0]
    else:
        amt[m] += 1
    #считаем кол-во учеников в m-й школе
    cnt[m] += 1

#Вывод результатов
  m = 0
  for i in range(nsch):
     if cnt[i] >= 3:
        if amt[i] == 1:
           print(i+1," ", nam[i])
        else:
           print(i+1, " ", amt[i])

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

В районе считается подозрительной ситуация, когда в школе более двух учащихся набирают одинаковый наибольший балл по школе.

Районный методист решила выяснить номера таких школ.

Программа должна вывести номера этих школ, в любом порядке.

Если такая школа окажется одна, нужно вывести наибольший балл в этой школе, с указанием того, что это наибольший балл.

Если таких школ не окажется, нужно вывести об этом сообщение.

Напишите эффективную, в том числе и по используемой памяти, программу, которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 0 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
5 50 74 87
Другой вариант выходных данных:
7
Наибольший балл = 74
Третий вариант выходных данных:
Нет таких школ

Решение:

Поиск максимума в каждой школе и подсчёт их совпадений

Подобное было в С4 2011 №1 и №4. Каждая строка данных содержит номер школы, который мы присвоим переменной m. Её значение будет индексом массивов bal и amt. Массив bal хранит наибольший балл школы номером m, а массив amt – кол-во учеников школы номером m с наибольшим баллом:

    bal [99] ;наибольший балл в школе
    amt [99] ;кол-во одинаковых лучших учеников в школе
    Цикл для i от 0 до N-1 ;по строкам данных
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball
            amt[m] = 1
        иначе если ball = bal[m] то
            amt[m] = amt[m] + 1

Вывод результатов

Массивы bal и amt заполнили, теперь посчитаем кол-во «подозрительных» школ: если их несколько, то выведем их номера; если их нет, то выведем сообщение; если она одна, то выведем номер школы и наибольший балл. Подсчёт «подозрительных» школ будем вести в переменную k:

    k = 0 ;кол-во подозрительных школ
    Цикл для i от 0 до 99 ; по всем школам
        если amt[i] > 2 то
            ball = bal[i] ;для случая когда k=1
            печать i " " ;номер подозрительной школы и пробел
            k = k + 1
    ;после того как прошлись по школам, рассмотрим два случая
    если k = 0 то ;когда подозрительных школ нет
        печать "таких школ нет"
    иначе если k = 1 то ;и когда подозрительная школа одна
        печать  ;перешли на следующую строку
        печать "Наибольший балл:" ball

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = f.readline()
   nsch = 99 #кол-во школ [1..99]
   bal = [0] * nsch #массив наибольших баллов по каждой школе
   #массив количеств одинаковых лучших учеников в школе
   amt = [0] * nsch 

   #суммируем баллы и считаем кол-во учеников по каждой школе
   for i in range(int(n)):  
      #a[0] - Фамилия (она не нужна)
      #a[1] - Имя (оно не нужно)
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
  
  
  a = f.readline().split()
  m = int(a[2])-1 #m - [0..98]
  ball = int(a[3])

  if ball > bal[m]:
     bal[m] = ball
     amt[m] = 1
  elif ball == bal[m]:
     amt[m] += 1
   #Вывод результатов
   k = 0
   for i in range(nsch):
   if amt[i] > 2:
       ball = bal[i]
  print(i + 1, end=' ') #номер подозрительной школы
  k += 1
   if k == 0:
       print(" Таких школ нет")
   elif k == 1:
       print() #перешли на следующую строку
       print("Наибольший балл:", ball)

При программировании школьной тестирующей системы по английскому языку выяснилось, что файлы с вопросами к тестам легко доступны и каждый может перед тестом открыть их и заранее узнать вопросы. Было решено закодировать файлы. Для этого придумали следующий алгоритм.

Каждая строка файла кодируется отдельно.

В каждой строке ищутся отдельные слова, и все символы слова сдвигаются по алфавиту циклически вправо на длину слова.

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

Циклический сдвиг символа по алфавиту вправо на X — замена символа на символ, стоящий в алфавите на X позиций дальше. Если при этом происходит выход за пределы алфавита, счёт начинается с начала алфавита.

Пример циклического сдвига символов на 3 позиции: буква «Е» превращается в букву «Н», буква «t» — в букву «w» буква «Y» — в букву «В».

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна закодировать строку по указанному алгоритму.

На вход программе подается строка, состоящая из не более чем 250 символов латинского алфавита, пробелов, знаков препинания, разного рода скобок, кавычек и других символов. Строка заканчивается символом «#». Других символов «#» в строке нет.

Программа должна вывести закодированную по указанному алгоритму строку.

Пример входных данных:
Day, mice. «Year» — a mistake#
Пример выходных данных:
Gdb, qmgi. «Ciev» — b tpzahrl#

Решение:

Длина слова

Чтобы сдвинуть символы на длину слова, нужно знать её величину. Посчитаем длину каждого слова строки s:

    s = "…" ;строка со словами и другими символами
    n = длина строки s
    flag = ЛОЖЬ
    Для i от 1 до n ;по каждому символу строки s
        если s[i] буква то;буква-не буква
            если flag то
                len = len + 1
            иначе
                len = 1
                flag = ИСТИНА

После этого алгоритма значение len будет иметь длину слова, а значение i – позицию последнего символа слова. Так что, в стиле Python – [(i-len):i] будет слово из массива.

Двигаем символы

Когда мы достигли последнего символа в слове, самое время сдвинуть каждый его символ:

    …
        если s[i] буква то;буква-не буква
            …
        иначе
            если flag то
                flag = ЛОЖЬ
                Для k от 1 до len ;по каждому символу слова
                    если s[i-k] + len  выходит за алфавит то 
                        s[i-k] = s[i-k] + len – 26 
                    иначе 
                        s[i-k] = s[i-k] + len
    печать s 

Переменная flag отвечает за начало подсчёта символов слова в первой ветке условия – «буква-не буква», а во второй ветке – за то, чтобы сдвиг символов в слове был только один раз.

Полный код на Python

   s = "Bike, Zip, Roller, 1345asdfads#"
   total = len(s)
   n = 0
   flag = False

   for i in range(total):
      c = s[i]
      if c.isalpha():
         if flag == False:
            len = 1
            flag = True
          else:
             len += 1
      elif flag == True:
         flag = False
         stmp = ""
         for k in range(len):
            #i-len - возврат к первому симолу слова
            if ord(s[i-len + k].upper()) - ord("A") + len > 25:
               stmp += chr(ord(s[i - len + k]) + len - 26 )
            else:
               stmp += chr(ord(s[i - len + k]) + len )
      #замена одной подстроки на другую
      s = s.replace(s[i - len:i], stmp) 

   print (s)
 

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

Районный методист решила, что оценку «отлично» должны получить 20% участников (целое число, с отбрасыванием дробной части).

Для этого она должна определить, какой балл должен был набрать ученик, чтобы получить «отлично».

Если невозможно определить такой балл, чтобы «отлично» получили ровно 20% участников, «отлично» должно получить меньше участников, чем 20%.

Если таких участников не окажется (наибольший балл набрали больше 20% участников) — эти и только эти ученики должны получить «отлично».

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна вывести на экран наименьший балл, который набрали участники, получившие «отлично». Известно, что информатику сдавало больше 5-ти учеников. Также известно, что есть такое количество баллов, которое не получил ни один участник.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть всего по три пробела в каждой строке).

Пример входных данных:
Иванов Иван 50 87
Пример выходных данных:
78

Решение:

Количество оценок

Посчитаем кол-во каждых оценок:

	k[100] ;кол-во оценок
	Для i от 0 до N-1 ;цикл по строкам данных
		ball = оценка из i-й строки данных 
		k[ball] = k[ball] + 1 ;считаем кол-во оценок

Индекс массива k – это конкретная оценка, а его элемент будет хранить кол-во этих оценок.

Количество лучших из 20% участников

Критерий – это 20% от N. Если суммировать оценки, например, в переменную s, то можно получить кол-во лучших оценок равное 20% или более

	s = 0 ;кол-во оценок
	i = 99 ;начинаем с самой высокой оценки, её индекс = 99
	p = N DIV 5 ;p – 20% от N
	Пока s < p  ;цикл по
		s = s + k[i]
		i = i – 1 ;спускаемся к следующей оценке

После этого цикла i будет содержать значение оценки

Возможные варианты

Рассмотрим некоторые варианты разного количества лучших оценок. Для простоты, диапазон оценок [1;5].

1. N=10 (p=2) из них две пятёрки: k = [? ? ? ? 2] или одна пятёрка, и одна четвёрка: k = [? ? ? 1 1]. В 1-м случае нужно вывести оценку 5, а во 2-м – 4. После алгоритма выше, s = 2. Тогда, для нужного вывода, достаточно условия на равенства p с s :

	s = 0 ;кол-во оценок
	i = 99 ;начинаем с самой высокой оценки, её индекс = 99
	p = N DIV 5 ;p – 20% от N
	Пока s < p  ;цикл по
		s = s + k[i]
		i = i – 1 ;спускаемся к следующей оценке
	если s = p то
		печать i

аналогично, для N=20 (p=4) получим такие выводы для соответствующих последовательностей:

k = [? ? ? ? 4] печать 5

k = [? ? ? 3 1] = [? ? ? 2 2] = [? ? ? 1 3] печать 4

k = [? ? 2 1 1] = [? ? 2 2 0] = [? ? 2 0 2] печать 3

и т. д.

2. N=20 (p=4) из них три пятёрки и две четвёрки: k = [? ? ? 2 3] или наоборот [? ? ? 3 2]. s = 5, т.е. больше p. По условию нужно выводить либо ровно 20%, либо меньше чем 20%. Тогда для этих двух последовательностей, выводим не четвёрку, а пятёрку. Значит, увеличим i на 1:

	s = 0 ;кол-во оценок
	i = 99 ;начинаем с самой высокой оценки, её индекс = 99
	p = N DIV 5 ;p – 20% от N
	Пока s < p  ;цикл по
		s = s + k[i]
		i = i – 1 ;спускаемся к следующей оценке
	если s = p то
		печать i
	иначе
		i = i + 1 ;возвращаемся к пятёркам
		печать i

По условию некоторых баллов не набрал никто, например, четвёрок: k = [? ? 2 0 3]. Новый алгоритм выше на выводе даст значение 0. Исключим нулевое/вые вхождения:

	иначе
		i = i + 1 ;возвращаемся к пятёркам
		Пока k[i]=0 ;встретили нулевую оценку
			i = i + 1 ;уходим от нулевой оценки
		печать i

3. Последнее, когда одно значение баллов, и оно больше 20%: N=10 (p=2) k = [? ? ? ? 3] печать 5. Здесь значение s должно быть равно k[i]:

	иначе
		если s=k[i] то
			печать i
		иначе
			i = i + 1
			Пока k[i]=0
				i = i + 1
			печать i

Полный код на Python

   f = open("11C4v01.txt", encoding='utf-8', mode="r")
   n = int(f.readline())
   k = [0] * 100 #кол-во оценок
   for i in range(n):
      #a[0] - Фамилия (она не нужна)
      #a[1] - Имя (оно не нужно)
      #a[2] - номер школы [1..99] (он не нужен)
      #a[3] - балл ученика(цы)	  
      a = f.readline().split()
      iball = int(a[3]) - 1 #iball - [0..99]
      k[iball] += 1

   p = n // 5
   s = 0
   i = 100
   while s &lt p:
      i = i - 1
      s = s + k[i]
   if s == p:
      print(i+1)
   else:
      if k[i] == s:
         print(i+1)
      else:
         i = i + 1
         while k[i] == 0:
            i = i + 1
         print(i+1)

После единых выпускных экзаменов по информатике в район пришла информация о том, какой ученик какой школы сколько баллов набрал. По положению об экзамене оценку “2” (неудовлетворительно) получают ученики, набравшие меньше 40 баллов. Оценку “3” (удовлетворительно) получают 30% учеников среди оставшихся, за исключением тех из них, кто набрал больше 60 баллов.

Если количество “троечников” оказывается больше 30%, то следует выбрать меньшую границу для оценки “4” (но только если при этом “3” получит хоть кто-нибудь).

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая должна вывести на экран наибольший балл, который набрали участники, получившие “удовлетворительно” и количество таких учеников. Известно, что информатику сдавало больше 50-ти учеников. Также известно, что есть такое количество баллов, которое не получил ни один участник.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более, чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число диапазоне от 1 до 100. Эти данные записаны через пробел, причем ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входных данных:
Иванов Иван 50 87
Пример выходных данных:
78

Решение:

Количество оценок

Аналогично 2011 С4 № 7 – посчитаем кол-во каждых оценок:

	k[100] ;[1..100] кол-во оценок
	Для i от 0 до N-1 ;цикл по строкам данных
		ball = оценка из i-й строки данных 
		k[ball] = k[ball] + 1 ;считаем кол-во оценок

Индекс массива k – это конкретная оценка, а элемент этого индекса будет хранить кол-во этих оценок.

Количество двоечников и 30% от не двоечников

Посчитаем кол-во двоечников, затем мы их исключим из общего кол-ва учеников:

	s = 0 ;кол-во двоечников
	Для i от 1 до 39 ;первые 39 строк массива с оценками
		s = s + k[i] ;суммируем всех двоечников
	p = (N - s) * 30 DIV 100 ;30% от не двоечников

Кол-во троечников

В 2011 С4 №7 мы искали только 20% лучших, значит критерий поиска был простым: s &lt p. Теперь нужно искать не более 30% троечников и у них максимальный балл 60, значит критерий будет составным:

	s = 0 i = 40 ;сбрасываем сумму и начинаем с троечников
	Пока s < p И i < 61  ;составной критерий для троечников
		i = i + 1 ;переходим к следующей оценке
		s = s + k[i];суммируем всех троечников

Возможные варианты

Рассмотрим некоторые варианты разного количества троечников.

1. Кол-во троечников составляет ровно 30%, и их максимальный балл меньше 60:

	Пока s < p И i < 61  ;составной критерий для троечников
		i = i + 1 ;переходим к следующей оценке
		s = s + k[i];суммируем всех троечников
	если s = p то ;кол-во 3-ков 30% и их макс балл < 60
		;максимальная оценка и кол-во таких оценок
		печать i s

2. Кол-во троечников меньше 30%, и их максимальный балл равен 60:

	иначе если i = 60 И s < p то
		;максимальная оценка и кол-во таких оценок
		печать 60 s
   

Но! Если максимальный балл будет меньше чем 60, программа всё равно выведет 60… (в этом место нужно доработать).

3. Троечники набравшие более 30% и какой-то один одинаковый:

	иначе если  s = k[i] то
		;максимальная оценка и кол-во таких оценок
		печать i s

4. Остальные троечники набравшие более 30% неодинаковые баллы:

	;убираем троечников, которые вышли за допустимую границу
	s = s - k[i]
	i = i – 1
	Пока k[i]=0
		i = i - 1
	печать i s ;максимальная оценка и кол-во таких оценок

Подобный алгоритм описан в В 2011 С4 v07, только там, для избавления от отсутствующих оценок, нужно перемещаться в другую сторону массива оценок.

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  k = [0] * 100 #кол-во оценок
  for i in range(n):
	#a[0] - Фамилия (она не нужна)
	#a[1] - Имя (оно не нужно)
	#a[2] - номер школы [1..99] (он не нужен)
	#a[3] - балл ученика(цы)
	a = f.readline().split()
	iball = int(a[3]) - 1 #iball - [0..99]
	k[iball] += 1
  s = 0
  i = 0
  for i in range(39): #[0..38] т.е. первые 39 баллов
	s = s + k[i]
  print("i:",i," s:",s)
  p = (n-s)*30 // 100
  s = 0
  
  #старое значение i=38, а троечники начинаются с 39,
  зн. увеличим i на 1 до обращения к массиву k:
  while s < p and i < 59: #здесь 60 это индекс 61-го балла!
	i = i + 1
	s = s + k[i]

  if s == p:
	print(i+1," ",s)

  elif i == 59 and s < p:
	#выведет 60 даже если максимальный балл троечников < 60
	print("60", s)

  elif s == k[i]:
	print(i + 1, " ", s)
  else:
	s -= k[i]
	i -= 1
  while k[i] == 0:
	i -= 1
  print(i + 1, " ", s)

На вход программе подается последовательность символов, заканчивающаяся символом #. Другие символы # во входной последовательности отсутствуют.

Программа должна вывести на экран латинскую букву встречающуюся во входной последовательности наибольшее количество раз (во второй строке).

Если таких букв во входной последовательности окажется несколько, программа должна вывести на экран всех, через пробел, в алфавитном порядке.

Строчные и прописные буквы не различаются.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна решать поставленную задачу.

Пример входных данных:
Day, mice. «Year» — a mistake#
Пример выходных данных:
A
4

Решение:

Количество каждой буквы в строке

    s = "…" ;строка со словами и другими символами
    n = длина строки s
    num[26] ;массив количества латинских букв алфавита
    Для i от 1 до n ;по каждому символу строки s
        если s[i] буква то ;буква-не буква
            k = номер буквы
            ;увеличиваем счётчик количества таких букв
            num[k] = num[k] + 1

Найдём максимум и их количество

Найдём буквы, встречающиеся наибольшее количество раз, и число этих раз в массиве s:

    ic = 0 ;индекс первой буквы ('A') в массиве num
    k = 1 ;счётчик количества максимумов в массиве num
    Для i от 1 до 26 ;от 'B' до 'Z'
        если num[i] > num[ic] то ; находим максимум
            ic = i ;индекс первой буквы меняем на индекс второй
            k = 1
        иначе если num[i] = num[ic] то ;такой же максимум
            k = k + 1 ;увеличиваем счётчик кол-ва максимумов

Вывод результатов

    если k = 1 то ;если максимум один
        печать ic ;символ ic
    иначе
    Для i от 0 до 26 ;от 'A' до 'Z'
        если num[i] = num[ic] то
            печать i ' ' ;символ i
    печать num[ic] ;кол-во максимумов
			

Полный код на Python

   #s = "Day, mice. 'Year' - a mistake#"
   s = "ABCD ABCE ABCF#"
   num = [0] * 26 #массив кол-ва букв алфавита

   for c in s:
      if c.isalpha():
         k = ord(c.upper()) - ord('A')
         num[k] += 1
   k = 1
   ic = 0
   for i in range(1,len(num)):
      if num[i] > num[ic]:
         ic = i
         k = 1
      elif num[i] == num[ic]:
         k += 1

   if k == 1:
      print (chr(ic + ord('A')))
   else:
      for i in range(0, len(num)):
         if num[i] == num[ic]:
            print(chr(i + ord('A')),end=" ")
         print()
   print(num[ic])

На вход программе подается последовательность символов, заканчивающаяся символом #. Другие символы # во входной последовательности отсутствуют.

Программа должна вывести на экран символы латинского алфавита, в порядке увеличения частоты встречаемости во входной последовательности.

Если буква во входной последовательности не встречается, её выводить не нужно.

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

Строчные и прописные буквы не различаются.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна решать поставленную задачу.

Пример входных данных:
Aced, ccedaa f#
Пример выходных данных:
FDEAC

Решение:

Количество каждой буквы в строке

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

    s = "…" ;строка со словами и другими символами
    n = длина строки s
    num[26] ;массив количества латинских букв алфавита
    Для i от 1 до n ;по каждому символу строки s
        если s[i] буква то ;буква-не буква
            k = номер буквы
          ;увеличиваем счётчик количества таких букв
            num[k] = num[k] + 1
			

Сортировка

Отсортируем массив num по возрастанию:

    Для i от 1 до 25 ;от 'A' до 'Y'
        Для j от 25-i
            если num[j] > num[j+1] то
                t = num[j]
                num[j] = num[j+1]
                num[j+1] = t ;

Получили отсортированную по возрастанию, частоту встречаемости символов, но неизвестно какие это будут символы – индексы будут утеряны.

Выход такой: завести массив символов по алфавиту sym. Далее, одновременно с сортировкой массива num, будут перестановки элементов массива sym с теми же индексами, что и индексы массива num:

    …
    sym = [a,b,c,…,z]
    Для i от 1 до 25 ;от 'A' до 'Y'
        Для j от 25-i ;
            если num[j] > num[j+1] то
                t = num[j]              c = sym[y]
                num[j] = num[j+1]       sym[j] = sym[j+1]
                num[j+1] = t            sym[j+1] = c

Вывод результатов

Если дана строка Aced, ccedaa f , то после сортировки массивы num и sym будут такими:

num — [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 3 3]

sym — [b g h I j k l m n o p q r s t u v w x y z f d e a c]

Выводим символы массива sym, начиная с символа f:

    j = 22 ;индекс символа 'f'
    Для i от j до 26 ;от 22 до 26
        печать sym[i]

Найти значение первого символа легко: если посмотреть на массив num, то в нём 21 нуль:

    j = 0 ;индекс символа 'f'
    Пока num[j] = 0 ; после цикла j будет равно 22
        j = j + 1
    Для i от j до 26 ;от 22 до 26
        печать sym[i]

Полный код на Python

   s = "Aced, ccedaa f#" #символ '#' в этом коде не нужен
   num = [0] * 26 #массив кол-ва латинских букв алфавита
   sym = [0] * 26 #массив латинских букв алфавита ('a'.. 'z')

   for i in range(26):
      sym[i] = chr(i+65)

   for c in s:
      if c.isalpha():
         k = ord(c.upper()) - ord('A')
         num[k] += 1

   for i in range(26 - 1):
      for j in range(26 - i - 1):
         if num[j] > num[j + 1]:
            num[j], num[j + 1] = num[j + 1], num[j]
            sym[j], sym[j + 1] = sym[j + 1], sym[j]

   j=0
   while num[j] == 0:
      j += 1
   for i in range(j, 26):
      print(sym[i],end=" ")

это упорядоченная последовательность действий

– последовательное выполнение команд, его блок схема состоит из:

1. Блок Ввод: операторы определения имён переменных, установления их типа и присваивания переменным неким значениям.
2. Блок Вычисления: операторы сравнения арифметические, логические, тригонометрические операции, операции извлечения квадратного корня и т.д. Присваивание результату значения полученного в вычислениях.
3. Блок Вывод: вывод полученных результатов на экран.

Нарисуем блок схему следующей записи:

1	Ввод значения для переменной x
2	y = x + 20
3	y = 2y
4	Вывод результата значения переменой y

Блок схема вышеприведённого алгоритма, есть интерактивная модель, которая в режиме реального времени описывает: поведение алгоритма, вычисление уравнений и вывода значений переменных в соответствующие элементы модели.

Алгоритм ветвление это выполнение команд, с проверкой истинности некоего условия и в зависимости от результата этой проверки происходит разветвление одной последовательности на несколько. Блок схема алгоритма ветвления состоит из тех же блоков что и линейный, плюс блок Условие:

Блок Условие, здесь проверяется истинность условия, если оно истинно то, происходит переход в одну часть программы иначе в другую. Условие представлено в виде логического выражения, где сравниваются между собой числа, переменные.

Различают три структуры ветвления: Неполное, полное и вложенное.

Алгоритм неполного ветвления способен решить одно условие.
Нарисуем блок схему следующего условия:

Для наглядности представим условие на оси Х

Теперь изобразим блок схему. Блок схема вышеприведённого условия, есть интерактивная модель, которая в режиме реального времени описывает: поведение алгоритма, вычисление уравнений и вывода значений переменных в соответствующие элементы модели. Перед запуском алгоритма, можно выбрать начальное значение переменной x:

Алгоритм полного ветвления способен найти одно решение из двух возможных.

Пример. Дана система из двух условий:

Для наглядности, эту систему можно представить графически

Блок схема вышеприведённого условия, есть интерактивная модель, которая в режиме реального времени описывает: поведение алгоритма, вычисление уравнений и вывода значений переменных в соответствующие элементы модели. Перед запуском алгоритма, можно выбрать начальное значение переменной x:

Когда выбора из двух вычислений недостаточно применяют условия, содержащие в себе вложенные условия. Так в следующей записи

переменная y может принять три результата, значит полного ветвления не достаточно, здесь нужна дополнительная команда или команды условия.

Для наглядности представим систему условий графически:

Блок схема вышеприведённого условия, есть интерактивная модель, которая в режиме реального времени описывает: поведение алгоритма, вычисление уравнений и вывода значений переменных в соответствующие элементы модели. Перед запуском алгоритма, можно выбрать начальное значение переменной x:

Большинство вычислений требует многократного повторения одних и тех же действий или повторного выполнения определённых операторов. Для этих вычислений применяют циклические алгоритмы, т.е. многократно повторяющиеся части программы. Есть два типа циклов: с известным числом повторений(счётчик) и неизвестным(условие).

Изучим блок схему и алгоритм цикла со счётчиком для следующего примера: Вывести значения функции y = 2x+4 в интервале от 2 до 5, с шагом 1, или сокращённо:

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

В блок схеме, счётчик цикла это переменная x, после выполнения очередного тела цикла, значение счётчика будет суммировано на величину шаг. Затем следует возвращение для проверки истинности условия цикла: если текущее значение x меньше 5, то цикл повторяется, иначе программа выходит за пределы цикла.

Цикл со счётчиком выполняет известное число повторений тела цикла, а есть ещё циклы с условием, которые выполняют тело цикла вечное количество повторений при истинности условия. Они бывают двух видов: с предусловием, и с постусловием.

Составим блок-схему предыдущей задачи, используя цикл с предусловием

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

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

Составим блок-схему предыдущей задачи, используя цикл с постусловием

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

После присваивания, выполняется тело цикла, затем проверяется истинность условия, а в остальном работа аналогична циклу с предусловием. Главное его отличие от цикла с предусловием, это выполнение тела цикла хотя бы один раз вне зависимости от истинности условия.

А & ¬А = 0

А | ¬А = 1

¬¬А = А

(А V B) = A Λ B

(А Λ B) = A V A

Логическое умножение: А & В = В & А

Логическое сложение: А | В = В | А

Логическое умножение: (А & В) & C = A & (В & C)

Логическое сложение: (А | В) | C = A | (В | C)

A & (В | C) = (А & В) | (A & C) — дистрибутивность умножения относительно сложения

A | (В & C) = (А | В) & (A | C) — дистрибутивность сложения относительно умножения

(А | В) & (C | D) =
(А & C) | (A & D) |
(B & C) | (B & D)

(А V A) = A

(А Λ A) = A

А V (А Λ В) = A

А Λ (А V В) = A

А V (A Λ В) = A Λ B

Пример 1. Упростить логическое выражение: (А & В) | (A & ¬B)

Решение:

По закону дистрибутивности: (А & В) | (A & ¬B) = А & (В | ¬B)

По закону исключённого третьего: А & (В | ¬B) = А & 1 = А

Пример 2. Даны четыре логических выражения:

1. A V B V C
2. (A Λ B) V C
3. (A V B) Λ C
4. А V B V C

Какое из них равносильно выражению (А V B) V C ?

Решение:

По закону де Моргана: (А V B) = A Λ B

Получаем (A Λ B) V C

Полученное выражение соответствует примеру под номером 2

Пример 3. Даны четыре логических выражения:

1. А & ¬C
2. А | ¬C & B | ¬C
3. ¬C & ( A | B)
4. (А & B) | ¬C

Какое из них равносильно выражению (А | ¬C) & ¬(¬B & C) ?

Решение:

По закону де Моргана ¬(¬B & C) = (¬¬B | ¬C)

По закону двойного отрицания: (¬¬B | ¬C) = (B | ¬C)

Получаем (А | ¬C) & (B | ¬C)

В скобках сложение и одинаковая переменная ¬C, вынесем её за скобки по распределительному закону:

(А | ¬C) & (B | ¬C) = (А & B) | ¬C

Полученное выражение соответствует примеру под номером 4

Логические задачи решаются различными методами, мы рассмотрим метод рассуждений как один из самых простых.

Для задач, в условии которых сказано, что часть утверждении персонажей ложна, а часть истинна, удобно использовать метод рассуждений. Идея этого метода заключается в том, что делается предположение об истинности одного из утверждений, и далее, на основе этого предположения анализируются остальные утверждения. Анализ остальных утверждений «может привести к двум случаям — либо задача оказалась решена, либо встретилось противоречие. Если встретилось противоречие, это означает, что первоначальная гипотеза об истинности одного из утверждений была неверна, и это утверждение на самом деле ложно. Далее, с учетом этой информации продолжаем анализ утверждений пока не решим задачу.

Условия логических задач бывают нескольких типов, рассмотрим три из них.

Задачи такого типа, содержат условия из нескольких двойных высказываний, в которых одно высказывание истинно другое ложно. В результате нужно найти истинные высказывания.

Задача: Перед гран-при гонок класса Формула 1, болельщики высказали следующие предположения: один болельщик — Хэмильтон – победит, а Масса доберётся вторым, другой болельщик – нет, Масса приедет третьим, а победит Райкконен, и наконец, третий болельщик скажет, а я уверен что одержит победу Алонсо, а Хамильтон будет последним.

После соревнований выяснилось, что каждый болельщик был прав только в одном предположении. Какое место занял спортсмен?

Решение:

Обозначим высказывания буквами:

А — Хэмильтон – победит, а Масса второй

В — Масса третий, а Райкконен первый

С — Хэмильтон последний, а Алонсо первый

1. Предполагаем что 1-й параметр высказывания А, истина, тогда 1-й параметр высказывания С – ложь, а второй истина. Получилось, что победили одновременно два пилота, значит наше первое предположение неверно и получаем что 2-й параметр высказывания А есть истина.
2. Т.к. 2-й параметр высказывания А, истина, то 1-й параметр высказывания B ложь, а второй истина.
3. Т.к. второй параметр высказывания В истина, тогда 2-й параметр высказывания С ложно, а первый истина. Итого:

1. Райкконен
2. Масса
3. Алонсо
4. Хэмильтон

В этом типе имеется четыре объекта и на основании условий нужно расставить персонажи или предметы по этим четырём предметам.

Задача: Ольга, Светлана, Татьяна и Алёна сидят на первых четырёх партах, но неизвестно кто на какой. Определите, кто из них носит косички, хвостик, распущенные волосы и короткую стрижку, если известно что:

1. Ольга не на первой парте
2. Алёна сидит дальше от доски чем, чем Светлана.
3. Светлана сидит перед Ольгой
4. Татьяна не сидит на соседней с Еленой парте
5. У девочки с короткой стрижкой номер парты чётный
6. Девочка с хвостом не Татьяна и не Светлана
7. Девочка с косичками сидит на второй парте

Решение:

Обозначим высказывания буквами:

Из 1-го, 2-го, 3-го и 4-го известия, рассадим девочек по партам:

Первое условие

Второе условие

Третье условие

Четвёртое условие

Из 5-го, 6-го и 7-го известия, выберем девочкам причёски:

Пятое условие

Шестое условие

Седьмое условие

В этом типе есть три персонажа, один из которых, может говорить правду, другой лгать, а третий говорить правду через раз. И на основании этих данных сделать вывод по сказанному этими персонажами.

Задача: Три друга Коля, Саша и Миша. Один из них всегда говорит правду, другой всегда лжёт, а третий говорит через раз то ложь, то правду. Кто из них правдив, а кто нет неизвестно, Миша и Коля сказали следующее:

Миша: Саша никогда не врёт, а от Коли никогда не услышишь правды

Саша: Миша сказал правду про меня

Определите, кто из друзей говорит правду, правду через раз и лжёт.

Решение:

1. Пусть Миша говорит правду, но он утверждает, что и Саша всегда прав, что противоречит условию задачи о правдивости только одного персонажа. Значит, Миша либо говорит правду через раз, либо всегда лжёт.
2. Пусть теперь Саша всегда говорит правду. Тогда 1-е утверждение Миши верно, а второе ложно, раз оно ложно, значит Коля всегда говорит правду. Снова неверно, т.к. получили двух правдивых персонажей. Получаем вывод — Саша также как и Миша либо говорит правду через раз, либо всегда лжёт. Значит 100% Коля всегда прав.
3. Предположим что Миша прав наполовину, значит его 2-е утверждение ложно, а второе истинно, т.е. правдивость Саши – не подходит. Значит, Миша всегда лжёт, а Саша прав наполовину.

Логика это наука о формах и способах мышления. К формам мышления можно отнести понятие, высказывание и умозаключение.

Понятие это выделение одного объекта от других по определённым признакам, параметрам свойствам.

Высказывание — суждение или повествовательное предложение, в котором что-то утверждается или отрицается.

Умозаключение это форма мышления, благодаря которой из двух или более суждений получается ещё одно суждение, которое является выводом. Оба первоначальных суждений, должны быть истинными и их называют условием к получению вывода. Между этими суждениями должна быть связь. Третье суждение это вывод он же является следствием и в зависимости от вида умозаключения может быть истинным или ложным.

Виды умозаключений: индукция, дедукция.

Дедукция: рассуждение или переход от общего правила к частному. Вывод всегда истинный.

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

Рассмотрим примеры дедукции и индукции:

Как уже было сказано для получения истинного умозаключения (не обязательно чтобы его вывод был всегда истинным), между условиями должна присутствовать связь, одно должно исходить из другого. Рассмотрим такой пример дедуктивного умозаключения:

• Все студенты – учащиеся
• Этот человек – студент
• Этот человек – учащийся

Сначала мы говорим о всех студентах, затем связываем некоего человека со студентом всё хорошо. НО, если связи нет, получится неправильное строение умозаключения, из которого может получится(хотя и не всегда) неправильный вывод. Поменяем местами второе и третье высказывание:

• Все студенты – учащиеся
• Этот человек – учащийся
• Этот человек – студент

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

Бывают случаи, когда при неправильном строении условия, чисто случайно может получиться правильный вывод:

• Резина не проводит электричество
• Вода не резина
• Вода проводит электричество

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

Даны высказывания, по ним сделать вывод:

• Все певцы знают ноты
• Фёдор Шаляпин певец
• Значит …

• Настоящие водители, знают ПДД
• Иванов настоящий водитель
• Значит …

Логическое выражение – это простое или сложное высказывание. Сложное высказывание строится из простых с помощью логических операций: инверсия, конъюнкция, дизъюнкция, импликация и эквивалентность. Первые три операции – это главные логические операции они просты в своей работе и представляют основу работы процессора компьютера.

Инверсия

это логическое отрицание соответствует русской частице НЕ, обозначается ещё ¬, A, Not. Она заменяет истинное высказывание на ложное и наоборот. Унарная(одноместная) т.е. отрицает какое то одно высказывание.

1. (2 × 2 = 4) — ИСТИНА или TRUE или 1
2. ¬(2 × 2 = 4) — ЛОЖЬ или FALSE или 0
3. (2 × 2 = 5) — ЛОЖЬ или FALSE или 0
4. (2 × 2 = 5) — ИСТИНА или TRUE или 1

Таблица истинности логического отрицания:

Конъюнкция

это логическое умножение соответствует русскому союзу И, обозначается &, Λ, And. Истинное значение будет только при истинности обоих операндов, все остальные ложь. Бинарная(двуместная).

• (2 × 2 = 5) & (3 × 3 = 8) = ЛОЖЬ
• (2 × 2 = 5) & (3 × 3 = 9) = ЛОЖЬ
• (2 × 3 = 6) Λ (2 × 4 = 8) = ИСТИНА
• (2 × 2 = 4) Λ (3 × 3 = 9) = ИСТИНА

Таблица истинности логического умножения

это логическое сложение соответствует русскому союзу ИЛИ, обозначается |, V, Or. Ложное значение будет только при ложности обоих операндов, все остальные истина. Бинарная(двуместная).

• (2 × 2 = 5) | (2 × 4 = 8) = ИСТИНА
• (2 × 2 = 5) | (2 × 3 = 9) = ЛОЖЬ
• (2 × 2 = 4) V (2 × 3 = 6) = ИСТИНА
• (2 × 2 = 4) V (3 × 3 = 1) = ИСТИНА

Таблица истинности логического умножения:

Из этих трёх простых логических операций, строят множество других сложных логических операции, мы рассмотрим две из них: импликация и эквивалентность

это логическое следование образуется соединением двух высказываний в одно с помощью оборота речи ЕСЛИ .. ТО, обозначается →, ложно тогда, когда из истиной предпосылки 1-го высказывания следует ложный вывод. Бинарная(двуместная).

A V B = А → B

Таблица истинности логического следования:

Для понимания смысла импликации может пригодиться житейская модель: А — начальник. Он может приказать «работай» (1) или сказать «делай что хочешь» (0). В — подчиненный. Он может работать (1) или бездельничать (0). В таком случае импликация — не что иное, как послушание подчиненного начальнику. По таблице истинности легко проверить, что послушания нет только тогда, когда начальник приказывает работать, а подчиненный бездельничает.

Ещё житейский пример импликации: A(Идёт дождь), B(раскрыть зонтик), результат ложь если человек намокнет. Человек будет мокрым в одном случае, если будет идти дождь, и он не раскроет зонтик.

это логическое равенство образуется соединением двух высказываний в одно с помощью оборота речи ТОГДА И ТОЛЬКО ТОГДА, обозначается ↔, ~, истинно когда оба высказывания одновременно либо истинны, либо ложны. Бинарная(двуместная).

(A Λ B) V (A Λ B) = A ↔ B

Таблица истинности логического равенства:

Для понимания эквивалентности удобны два высказывания: А = «Компьютер вычисляет» и В = «Компьютер включён».

При составлении логических условий поиска в базах данных, легко ошибиться. Например, в базе данных БИБЛИОТЕКА есть сведения о книгах разных авторов, то при выборе всех книг Лермонтова и Есенина хочется в условии выбора поставить (Лермонтов И Есенин), но мы получим результат книг автором которых будет и тот, и другой автор, чего не может быть. Нужно заменить логическую операцию (И) на (ИЛИ) — (Лермонтов ИЛИ Есенин).

Выполним задание на обработку сложных условий.

Задача. В поле Условие, записано логическое выражение, выписать в поле Ответ, записи соответствующие условию:

Каждое высказывание можно выразить в виде логической формулы(логического выражения) состоящей из логических переменных и операций. Для записи логического выражения из составного высказывания выделяют простые высказывания и логические связи между ними. Затем нужно учесть последовательность выполнения логических операций согласно их приоритету:

1. скобки
2. ¬ — инверсия — логическое отрицание
3. & — конъюнкция — логическое умножение
4. | — дизъюнкция — логическое сложение
5. → — импликация — логическое следование
6. ↔ — эквивалентность – логическое равенство

Пример 1. Вычислим истинность сложного высказывания:

не 2×2=5 и 2×2=4 или 3×3=8 и 3×3=9

Решение:

1. Выделим простые высказывания с помощью переменных A, B, C и D:
   А = 2×2=5 значение -ложь (0);
   В = 2×2=4 значение -истина (1);
   C = 3×3=8 значение -ложь (0);
   D = 3×3=9 значение -истина (1)
2. Тогда составное высказывание перепишем в следующей форме:
   не A и B или C и D
3. заменим в составном высказывании значения логических переменных:
   не 0 и 1 или 0 и 1
4. Подставим логические операции, получим логическое выражение:
   ¬0 × 1 V 0 × 1
5. Запишем по действиям, учитывая последовательность выполнения операций:
   1. ¬0 = 1
   2. 1 × 1=1
   3. 0 × 1 = 0
   4. 1 V 0 = 1

Ответ: не 2×2=5 и 2×2=4 или 3×3=8 и 3×3=9 = 1

Пример 2: Для какого имени истинно логическое условие:

¬ (Первая буква согласная → Третья буква гласная)

1. Юлия 2. Пётр 3. Алексей 4. Ксения.

Решение: По условию нужно получить истину(1), а отрицание ¬ (…) логическому условию вынуждает нас найти в скобках ложь НЕ(ЛОЖЬ)=ИСТИНА. Т.к. в условии операция импликация, а в ней ложь только в одном случае, когда из истиной предпосылки следует ложный вывод, т.е. нужно найти первую букву действительно согласную, а третью НЕгласную(т.е. согласную).

Ответ: Пётр.

Пример 3: Какое из названий имён удовлетворяет условию:

первая буква гласная & последняя буква гласная ↔ имя содержит букву «о»?

1. Иван 2. Алёна 3. Игорь 4. Ирина.

Решение: По условию нужно получить истину. Операция & имеет приоритет выше чем ↔, значит последовательность решения такая:

1. первая буква гласная & последняя буква гласная
2. Результат 1-го пункта ↔ название содержит букву «о»

Финальное решение примера это пункт 2 содержащий истину операции ↔.
Это либо 1↔1, либо 0↔0. Истинность 1-го пункта – имя под номером 2 или 4. Истинность 2-го пункта это имя 3 с буквой «о» что не верно.
Значит, ищем ложность обоих пунктов: ложность 1-го пункта – имя под номером 1 или 3. Ложность 2-го пункта это либо имя 1 буквы «о»,
либо имя 3 без буквы «о».

Ответ: Иван.

Пример 4: Какое из названий имён удовлетворяет условию:

первая буква гласная & последняя буква гласная ↔ ¬название содержит букву «а»?

1. Иван 2. Алёна 3. Игорь 4. Ирина.

Решение: По условию нужно получить истину. Операция & имеет приоритет выше чем ↔, а операция ¬
имеет приоритет выше чем &, значит последовательность решения такая:

1. ¬ название содержит букву «а»
2. первая буква гласная & последняя буква гласная
3. Результат 2-го пункта ↔ результат 1-го пункта

Финальное решение примера — это пункт 3 содержащий истину операции ↔. Это либо 1↔1, либо 0↔0. Истинность 1-го пункта – имя под номером 3. истинность 2-го пункта – имя под номером 2 и 4. Истинность 3-го пункта не может быть из-за неравенства 1-го и 2-го пункта. Значит для истинности 3-го пункта, ищем ложность 1-го и 2-го пунктов: ложность 1-го пункта – имя под номером 1, 2 или 4 или 4. Ложность 2-го пункта это либо имя 1, либо имя 3.

Ответ: 1.

Для каждого составного высказывания(логического выражения) можно построить таблицу истинности ТИ, учитывающая истинность или ложность всех возможных комбинаций исходных значений простых высказываний.

Пример. Постройте ТИ для сложного высказывания ¬А & В | A & B

Решение:

1. Определим количество строк в ТИ, оно равно количеству возможных комбинаций логических переменных. Если количество переменных n, то количество строк = 2ⁿ. У нас переменные это А и В значит количество строк 4
2. Определим количество столбцов в ТИ, оно равно количеству переменных плюс количество логических операций. В нашем случае переменных две, а операций четыре(¬, &, | и &), т.е. количество столбцов равно шести.
3. Построим ТИ с указанным количеством строк и столбцов плюс одна строка сверху с обозначениями столбцов и внесём в таблицу исходные значения логических переменных.
4. Заполним ТИ, выполняя логические операции в необходимом порядке.

Логические выражения, у которых последние столбцы ТИ совпадают, называются равносильными. Обозначаются такие выражения знаком =.

Пример. Докажем, что выражения A Λ B и (А V B) равносильны.

Решение:

1. Построим сначала ТИ логического выражения A Λ B:

A	B	A	B	A Λ B
0	0	1	1	1
1	0	0	1	0
0	1	1	0	0
1	1	0	0	0

2. Теперь построим ТИ логического выражения (А V B):

A	B	(A V B)	(А V B)
0	0	0	1
1	0	1	0
0	1	1	0
1	1	1	0

Значения последних столбцов ТИ совпадают, соответственно логические выражения
A Λ B и (А V B) равносильны

Пример. Докажите с помощью ТИ, что операция импликации A → B равносильна логическому выражению A V B

Пример. Докажите с помощью ТИ, что операция эквивалентности A ↔ B равносильна логическому выражению (A V B ) Λ ( A V B )

Пример. Дан фрагмент таблицы истинности выражения F.

Какое выражение соответствует F?

1. ¬X & ¬Y & Z
2. ¬X | ¬Y | Z
3. X | Y | ¬Z
4. X | Y | Z

Решение:

Первая проверка первого выражения дала несовпадение, значит последующие две, не производим, а переходим ко второму выражению.

Вторая проверка второго выражения дала не совпадение, значит последующую, не производим, а переходим к третьему выражению

В третьем выражении, все три проверки дали совпадение, значит четвёртое выражение можно не проверять, хотя на всякий случай проверить можно, ведь если проверка в четвёртом выражении даст совпадение, то в каком то случае мы допустили ошибку.

Ответ: 3

Первый вид данных с которым стали работать ЭВМ это числа. Числа представлены в двух форматах: формат с фиксированной точкой и формат с плавающей запятой.
Они представлены в ячейках 1 байт, 2 байта, 4 байта и 8 байт.

Целые положительные числа для одного байта

Для представления целого положительного числа N в форме с фиксированной точкой состоящего из одного байта его нужно:

1. Перевести число N в двоичную систему счисления
2. Полученный результат дополнить слева нулями до восьми разрядов

Задача. Представим в одном байте число N = 53₁₀

Решение:

1. Переведём в двоичную систему, получим 110101₂
2. Дополним слева нулями 00110101₂

Диапазон положительных (беззнаковых) чисел в одном байте лежит от минимального восьми нулей до максимального восьми единиц.
В десятичном представлении от 0 до 255, 2⁸=256.

А как представить отрицательные числа, если минимальное число это ноль? В этом случае используют знаковые числа – старший(левый) бит используют для знака. Если в нём 0, то знака нет – число положительное и остальные семь бит используют для числа ≥ 0, если в старшем бите 1, то знак есть – число отрицательное и остальные семь бит используют для числа < 0.

Диапазон положительных знаковых чисел для одного байта от 0 до 127, а отрицательных от -1 до -128.

Запись целого отрицательного числа -N в байте:

1. Получить внутреннее(двоичное) представление целого положительного числа N.
2. Получить обратный код этого числа заменой 0 на 1, и 1 на 0.
3. К полученному числу прибавить 1.

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

N – M = N + (-M), значит N + (-N) = 0

распишем последнее равенство в двоичном виде на примере числа 53:

53 — 00110101₂.

-53 — 11001011₂.

Получаем: 00110101₂ + 11001011₂ = 100000000₂

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

Т.к. одного байта не хватает для представления чисел больших чем 255, используют соседние байты. Двух байтные или 16 битные числа, имеют диапазон для незнаковых от 0 до 65535, а для знаковых -32768..32767.
Четырёх байтные или 32 битные числа, имеют диапазон для незнаковых от 0 до 4294967296, а для знаковых -2147483648..2147483647.

Числа с плавающей запятой R представлены в форме произведения мантиссы m на основание системы счисления p в некоторой степени n или порядка:

R = m × pⁿ

Порядок(степень) показывает на какую позицию и в каком направлении должна сместиться запятая. Например, число 25,324 можно представить как:

2,5324 × 10¹

0,25324 × 10²

0,025324 × 10³

0,0025324 × 10⁴

и т.д. Следовательно, представление числа в форме с плавающей запятой неоднозначно. Чтобы эту неоднозначность убрать в ПК используют нормализованную форму чисел с плавающей запятой. Мантисса(значащие цифры) в нормализованной форме будет удовлетворять условию:

0,1 ≤ m < 1

Наше число 25,324 в нормализованной форме будет 0,25324×10²

В памяти ПК мантисса будет в виде целого числа содержащая её значащие цифры (ноль и запятая не учитываются)
и порядка т.е. m = 25324, а n = 2.

в старшем бите 1-го байта хранится знак числа. Семь оставшихся битов отводится на порядок. Три оставшихся байта отводится на значащие цифры мантиссы.

Вслед за числовой информацией стали использовать текстовую или символьную информацию. Где каждый символ это прописные, строчные буквы, цифры, знаки пунктуации, скобки и т.д.

Изначально был придуман алфавит, состоящий из 256 символов, т.е. один символ представлен в виде 8-ми бит или 1-го байта.
Т.к. информация в ПК состоит из нулей и единиц, то символ в таком алфавите кодируется от 00000000₂ до 11111111₂. Такое количество символов достаточно чтобы закодировать прописные,
строчные буквы латинского, национального алфавита, 10 цифр, скобки, знаки пунктуации и всевозможные знаки.

Текстовая информация вводится в ПК путём двоичного кодирования. Т.е. изображение символа преобразуется в двоичный код.
Когда пользователь нажимает на клавиатуре клавишу с символом, в оперативную память поступает двоичный код этого символа. Чтобы на экране вместо этого двоичного кода мы видели символ,
точнее его изображение, двоичный код извлекает из таблицы графическое изображение символа, соответствующего этому коду. Эта таблица называется кодовая.
Кодовая таблица это стандарт, при котором каждому символу ставится свой порядковый номер в двоичном коде. Наименьший номер 0 наибольший 255.

ASCII

Рассмотрим, как в таблице размещены 256 символов.

Первую половину таблицы от 0 до 127 разработали в США, называется она ASCII, эти символы одинаковы для всех стран, там размещены строчные, прописные буквы латинского алфавита, цифры 0..9, знаки препинания, скобки и другие символы. Символы алфавита расположены по порядку, что удобно для сортировки символьной информации, широко применимой в электронных таблицах, базах данных.

Вторая половина таблицы от 128 до 255 содержит символы национальных алфавитов, т.е. для стран, где не применяют латиницу. Для русского алфавита могут применяться разные варианты таблиц . Например, в MS DOS эта таблица называлась 866, MS Windows это 1251.

Наглядно понять кодовую страницу можно в браузере Internet Explorer, где можно изменить шрифт командой меню Вид/Кодировка/Дополнительно/ далее поэкспериментировать с выбором различных вариантов кодовых таблиц.

Unicode

Но 256 символов недостаточно для представления «экзотических» символов (иврит, китайских, арабских и т.д.), поэтому в настоящее время разработали международный стандарт Unicode где на каждый символ отводится не один, а два байта, следовательно можно закодировать 2¹⁶=65536 различных символов.

Задача. Сколько бит занимает слово круг в кодировке CP1251?

Решение: Один символ в кодировке CP1251 состоит из 1-го байта. Количество символов в слове круг умножаем на один байт и восемь бит – получаем:

4 × 1 × 8 = 32 бит

Задача.Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16 битном коде Unicode, в 8 битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?

Решение: Здесь неважно в какой кодировке получить длину символов. Итак, один символ в Unicode в два раза больше символа КОИ-8(или любого 8 битного символа) значит, ПОЛУЧЕННАЯ ИНФОРМАЦИЯ УМЕНЬШИЛАСЬ В ДВА РАЗА, т.е. на один полученный символ отводится в два раза меньше бит, чем тому же символу до кодировки. Сообщение уменьшилось на 480 бит, даёт нам право узнать, сколько бит было до кодировки: 480 × 2 = 960. Поскольку один символ занимает 16 бит, получаем 960 ÷ 16 = 60 символов содержало сообщение

Но можно не вычислять сколько бит было до кодировки, если догадаться что сообщения в Unicode в два раза больше чем в КОИ-8, значит 480 делим на 8 получаем тоже значение — 60

Задача. Скорость передачи данных через модем 56 Кбит/с. Передача текстового файла через модем заняла 12с. Определите, сколько символов содержал переданный текст, если он был представлен в кодировке Unicode.

Решение: Определим сколько бит было передано за 12 с: Переведём Килобиты в биты: т.к. 1Кбит = 1000бит, то 56 × 1000 = 56000, а за 12 с будет передано 56000 × 12 = 672000. Т.к. в кодировке Unicode под каждый символ отводится 2 байта, или 16 бит, вычислим количество символов 672000 ÷ 16 = 42000.

Задача. Для кодирования букв А, Б, В и Г решили использовать двухразрядные последовательные двоичные числа(от 00 до 11) Если таким образом закодировать последовательность БАВГ. Какой получится результат в 16-ричном коде?

Решение: Выпишем каждый код для каждой буквы, выпишем коды в нужной последовательности, переведём каждый код символа в 16-ричную систему: А(00), Б(01), В(10), Г(11). Б(01) А(00), В(10), Г(11). Получим 1023₁₆

Графическая информация

Чтобы изображение представить в ПК его разбивают на мелкие участки (фрагменты, точки) и каждому фрагменту разбитого изображения,
присваивают числовое значение цвета. Получается как мозаика. Это разбиение называют пространственная дискретизация.

Качество разбитого изображения зависит от:

1. Размера фрагментов, чем размер меньше, тем качество выше, т.е. количество фрагментов из которого состоит изображение, будет больше
2. От количества возможных цветов, которые представляют фрагмент изображения. Чем больше цветов, тем качество выше

Разрешающая способность

Графическая информация на экране представлена в виде растрового изображения. Оно формируется из определённого количества строк. Каждая строка содержит определённое количество точек(пикселей). Такое формирование называют разрешающей способностью монитора или разрешение. Например разрешение 800×600, это формирование на экране изображения состоящего из 600 горизонтальных строк по 800 точек (пикселей) в каждой строке. Бывают ещё разрешения: 1024×768, 1280×1024.

Глубина цвета

Каждая точка(пиксель) может отображать цвет, физически это биты. Количество различных цветов зависит количество бит на точку, это количество называют глубиной точки или просто глубина. Количество цветов N которое может отобразить точка вычисляется по формуле N=2ⁱ где i число бит в точке.

Если пиксель однобитный как в старых компьютерах, то экран может отобразить только 2¹ = 2 цвета, либо чёрный либо белый. Для двухбитного пикселя количество различных цветов — 4. Для цветного изображения каждая точка может иметь различное число бит: 4, 8, 16, 24 и 32.

В современных мониторах, цветное изображение, получается путём смешивания трёх цветов красный, зелёный, синий в одной точке. Такая цветовая модель называется RGB по первым буквам названий английского цвета (Red, Green, Blue).
На каждый цвет выделяют 8 бит, поэтому один пиксель содержит 24 бита. Другими словами, для красного, зелёного или синего, есть 2² = 256 уровней интенсивностей цвета
от 00000000₂ до 11111111₂. Число возможных цветов при такой глубине получается по формуле: 2²⁴ = 16777216.

Графический режим – величина разрешающей способности и глубины цвета.

Задача. Рассчитаем объём видеопамяти в байтах для 1-го из графических режимов: разрешающей способности 800×600 и глубины 24 бита.

Решение:

800×600 = 480000 — количество точек

теперь учтём, что каждая точка весит 24 бита, получаем:

24×480000 = 11 520 000 бит = 1 440 000 байт

Рассмотрим основные позиционные системы:

Из основания видно, сколько различных цифр в алфавите содержит та или другая система.

Свойства позиционных систем счисления:

1. В позиционных системах значение цифры зависит от её положения (разряда) в числе.
2. В позиционных системах счисления с основанием N, основание каждого следующего числа в N раз больше предыдущего.

Согласно свойствам позиционных систем счисления разложим число 5327 в разных системах по следующему правилу: каждую цифру умножаем на основание числа, которое возведено в степень равной позиции цифры в числе минус 1. Затем полученные числа суммируются:

5 = 5 * 10³ = 5 * 1000 = 5000

3 = 3 * 10² = 3 * 100 = 300

2 = 2 * 10¹ = 2 * 10 = 20

7 = 7 * 10⁰ = 7 * 1 = 7

5000 + 300 + 20 + 7 = 5327

5 = 5 * 8³ = 5 * 512 = 2560

3 = 3 * 8² = 3 * 64 = 192

2 = 2 * 8¹ = 2 * 8 = 16

7 = 7 * 8⁰ = 7 * 1 = 7

5327₈ = 2560 + 192 + 16 + 7 = 2775₁₀

5 = 5 * 16³ = 5 * 4096 = 20480

3 = 3 * 16² = 3 * 256 = 768

2 = 2 * 16¹ = 2 * 32 = 32

7 = 7 * 16⁰ = 7 * 1 = 7

5327₁₆ = 20480 + 768 + 32 + 7 = 21287₁₀

Перевод чисел в десятичную систему счисления осуществляется по упомянутым выше разложениям чисел, при этом разложенное число суммируется, а полученный результат и есть число в десятичной системе.

Для записи дробных чисел используется отрицательные степени основания:

27,461₁₀ = 2*10¹ + 7*10⁰ + 4*10^-1 + 6*10^-2 + 1*10^-3

Разложим числа записанные в разных системах счисления:

101,01₂ = 1*2² + 0*2¹ + 1*2⁰ + 0*2^-1 + 1*2^-2

673,2₈ = 6*8² + 7*8¹ + 3*8⁰ + 2*8^-1

8A,F₁₆ = 8*16¹ + A*16⁰ + F*16^-1

Для перевода десятичного числа в двоичное, последовательно делим число на 2, до тех пор, пока частное не будет меньше делителя. После этого, записываем остатки в обратном порядке, а на первое место помещаем последнее частное(которое меньше делителя)

Переведём число 19₁₀ в двоичное:

Остаток в обратном порядке есть 0011, теперь последнее частное ставим вперёд:

10011₂ = 19₁₀

Аналогично переводят десятичные целые числа в остальные системы заменяя в делителе основание. Пример переведём число 680₁₀ в шестнадцатеричное:

Остаток в обратном порядке есть A8, теперь последнее частное ставим вперёд:

2A8₁₆ = 680₁₀

Последовательно умножаем дробную часть на 2, записывая целую часть в прямом порядке. Повторить до тех пор, пока не получится нулевая дробная часть.

Переведём число 0,75₁₀ в двоичное:

Переписываем целую часть в прямом порядке 0,75₁₀ = 0,11₂

Аналогично переводят десятичные дробные числа в остальные системы заменяя в множителе основание.

Переведём число 0,4062510₁₀ в восьмеричное:

Переписываем целую часть в прямом порядке 0,4062510₁₀ = 0,32₈

Числа записанные в двоичной, восьмеричной и шестнадцатеричной системе являются числами основания которых есть степень 2. Значит, их легко перевести в двоичную систему для этого нужно знать, сколько разрядов в двоичной системе нужно для записи всех цифр восьмеричной и шестнадцатеричной системы.

Мы уже изучили измерение информации, поэтому можем посчитать, сколько каждой системе счисления требуется бит (разрядов) для записи всех их символов:

2 = 2ⁱ, 2 = 2¹, i = 1.

8 = 8ⁱ, 8 = 2³, i = 3.

16 = 16ⁱ, 16 = 2⁴, i = 4.

Т.о. для перевода целого 2-го числа в 8-ое, его нужно разбить на группы по 3 цифры(триады) справа налево. Если в крайней левой группе окажется меньше трёх цифр, то дополнить слева нулями. Затем каждую группу преобразовать нужную систему. Для перевода полезно подготовить таблицу преобразования:

Пример. Переведём двоичное число 101001₂ в восьмеричное:

Решение. Разобьём по 3 цифры(нули слева добавлять не нужно) 101 001 получим 5₈ и 1₈: 101001₂ = 51₈

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

Пример. Переведём дробное двоичное число 0,11010₂ в восьмеричное:

Решение. 110 10(дополним справа нулями) 110 100. Получим 6₈ и 4₈: 0,11010₂ = 0,64₈

Перевод целого 2-го в 16-ное аналогичен, только здесь разбиваем группы по 4 цифры(тетрады) справа налево, и также если в крайней левой группе меньше четырёх цифр, то добавляем слева нулями

Пример. Число из предыдущего примера 101001₂ переведём в шестнадцатеричное:

Решение. Разобьём по 4 цифры справа налево 10 1001 (дополнив нулями крайнюю левую группу) 0010 1001 получаем 2₁₆ и 9₁₆: 101001₂ = 29₁₆

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

Пример. Переведём дробное двоичное число 0,110101₂ в восьмеричное:

Решение. 1101 01(дополним справа нулями) 1101 0100. Получим D₁₆ и 4₁₆: 0,110101₂ = 0,D4₁₆

Для перевода чисел из восьмеричной или шестнадцатеричной систем счисления в двоичную нужно каждое число преобразовать в группу из трёх (триаду) или в группу из четырёх (тетраду) двоичных цифр соответственно:

47₈ = разбиваем на триады: 4 = 100, 7 = 111. 47₈ = 100111₂

AB₁₆ = разбиваем на триады: A = 1010, B = 1011. AB₁₆ = 10101011₂

Сложение производится по обычному правилу столбиком, но нужно учитывать, что если при сложении двух чисел
получается число с основанием большим чем у слагаемых, то полученное при сложении число нужно перевести соответствующую
систему счисления. Пример 5 + 7 = 12, НО 5₈ + 7₈ ≠ 12, точнее нужно 12 перевести в
восьмеричную систему(можно так 12 − 8 = 4. 4 пишем, а 1 переносим): 5₈ + 7₈ = 14₈.

Аналогично для сложения шестнадцатеричных чисел 5 + 7 будет также 12, но 12 в 16-ричном коде будет С.

Пример. Вычислим B₁₆ + D₁₆

Решение. B₁₆ = 11₁₀, D₁₆ = 13₁₀. 11₁₀+13₁₀ = 24₁₀ , 24 − 16 = 8 пишем 1 переносим: B₁₆ + D₁₆ = 18₁₆

Пример. Сложим большие шестнадцатеричные числа ABC₁₆ и CD₁₆

Решение:

1. C₁₆ + D₁₆ = 12₁₀ + 13₁₀ = 25₁₀, 25 − 16 = 9, 9 пишем 1 переносим,
2. B₁₆ + C₁₆ = 11₁₀ + 12₁₀ = 23₁₀, 23 – 16 = 7 + 1(которую перенесли), 8 пишем, 1
3. A₁₆ + 1₁₆, 10₁₀+1₁₀ = 11₁₀, 11 = B₁₆

Ответ: ABC₁₆ + CD₁₆ = B89₁₆

Пример. Вычислим 2005₁₆ − B7₁₆

Решение:

1. 5₁₆ − 7₁₆ , но 5 < 7, значит занимаем 10₁₆ из 4-го разряда (а в 3-й и 2-й на место нулей сваливается 10₁₆ – 1₁₆ = 16 − 1 = 15 = F₁₆)
   получаем 10₁₆ + 5₁₆ = 16 + 5 = 21. Теперь 21 – 7 = 14 = E₁₆
2. После заёма, во втором разряде есть 15. Вычитаем из него B₁₆ получаем: 15 – B₁₆ = 15 – 11 = 4₁₀ = 4₁₆
3. После заёма, в третьем разряде есть 15, но вычитать нечего просто оставляем F₁₆
4. И наконец, после заёма, в четвёртом разряде вместо 2 оставляем 1₁₆

Ответ: 2005₁₆ − B7₁₆ = 1F4E₁₆

Арифметические операции над числами в разных системах счисления, производятся путём перевода их в одинаковую систему.

Пример. Вычислим 36₈ + 47₁₆, , а результат представим в двоичную, восьмеричную и шестнадцатеричную систему счисления.

Решение:

1. 36₈ раскладываем на триады — 3₈ = 011₂, 6₈ = 110₂, 36₈ = 011110₂
2. 47₁₆ раскладываем на тетрады — 4₁₆ = 0100₂, 7₁₆ = 0111₂, 47₁₆ = 01000111₂
3. 36₈ + 47₁₆ = 011110₂ + 01000111₂ = 1100101₂

Теперь полученное число 1100101₂ переведём восьмеричную и шестнадцатеричную систему:

1100101₂ делим на триады = 001₂, 100₂ и 101₂ = 1₈, 4₈, и 5₈=145₈

1100101₂ делим на тетрады = 0110₂, 0101₂ = 6₁₆, и 5₁₆ = 65₁₆

1100101₂ = 145₈ = 65₁₆

Информация это сообщения (текст, звук, графика, видео)…

А в чём её измерить. В информатике за единицу измерения информации приняли бит который может хранить одно из двух различных значений либо 0, либо 1. Для простоты можно вместо 0 и 1 выбрать любые два взаимно противоположные понятия:

ДА-НЕТ;

СВЕТЛО-ТЕМНО;

ХОЛОДНО-ЖАРКО;

ДЕНЬ-НОЧЬ;

ПЛЮС-МИНУС;

БЕЛЫЙ-ЧЁРНЫЙ

Сообщение, уменьшающее неопределённость знаний в 2 раза несёт 1 бит информации.

Перед бросанием монеты есть ДВА равновероятных результатов, т.е. неопределённость знаний равна двум. Игральный кубик с шестью гранями перед броском несёт неопределённость знаний равной шести. Значит неопределённость знаний о некотором событии это количество возможных событий.

После того как подбросили монету, мы увидели ОДИН результат. Произошло одно из двух событий. Неопределённость уменьшилась в 2 раза: было 2 варианта, остался 1, мы получили 1 бит информации. Сообщение о том, что произошло одно событие из двух, несёт 1 бит информации.

Теперь узнаем в цифрах, сколько информации может нести сообщение

Сколько информации несёт сообщение о том, что произошло 1 событие из 4 возможных? Например: Есть шкаф с четырьмя полками, на каждой по одной книге, сколько бит информации мы получили узнав о том, что некто взял книгу из третей полки?

Ответом будет количество возможных вопросов, ответы на которых могут быть лишь ДА или НЕТ. При этом после очередного полученного ответа мы должны исключить ровно половину.

Итак, перед первым вопросом разделим шкаф с четырьмя полками пополам, узнав в какой половине НЕ лежит книга, делим эту половину на два. Теперь перед вторым вопросом делим эту половину пополам и задаём второй вопрос и т.д. Теперь по действиям:

Итак, книгу взяли, и до 1-го вопроса есть четыре полки с тремя книгами. Делим шкаф пополам:

Задаём 1-й вопрос: «Книга лежала в левой или в правой части?» Ответ: в правой. Левую часть исключаем, а правую делим пополам:

Задаём 2-й вопрос: «Книга лежала в левой или в правой части?» Ответ: в левой. Больше делить нечего. Ответ: Было задано два вопроса, соответственно получили 2 бита информации.

Т.е. сообщение КНИГУ ВЗЯЛИ ИЗ ТРЕТЬЕЙ ПОЛКИ несёт 2БИТА информации, при условии что количество полок 4. При этом сообщении неопределённость уменьшилось в 4 раза.

Тоже самое сообщение, но при количестве полок 8, уменьшает неопределённость в 8 раз, а несёт уже 3 бита информации, поскольку здесь уже пришлось бы задавать три вопроса. 8 платформ на поезд, пассажир не знает на какую платформу подадут поезд, после объявления номера платформы неопределённость уменьшилась в 8 раз и несёт 3 бита информации,

Получим формулу позволяющую выводить количество информации из множества событий. Обозначим N число возможных событий, i количество информации содержащейся в сообщении о том, что произошло одно из N возможных событий.

Итак пример с монетой N=2, i=1 с книгами в четырёх полках N = 4, i = 2, с платформами N = 8, i = 3. Связь между этими величинами выражается уравнением:

2ⁱ = N

А если величина N известна, а найти нужно i, то уравнение будет показательным

i=log₂N

его называют формулой Хартли.

Но проще выписать в таблицу хотя бы из 10 чисел степени двойки и запомнить их:

Задача. Сколько бит информации несёт сообщение о том, что из колоды в 32 карты достали даму пик?

Решение: т.к. события равновероятные, то неопределённость равна количеству карт, т.е. N = 32, если i количество информации в сообщении о результате вытаскивания одной карты, то имеем уравнение 2ⁱ = 32, по формуле Хартли имеем log₂ 32 = 5. Ответ: i = 5

В информатике используется величина байт равная 8 битам, т.е. в одном байте может произойти 2⁸ = 256 событий. Или, одним байтом можно закодировать 256 различных символов.

Для большого количества байтов применяют приставки КИЛО, МЕГА, ГИГА, ТЕРА и получают килобайты(Кб), мегабайты(Мб), гигабайты(Гб) и терабайты(Тб):

• 1 Кб = 2¹⁰ = 1024 байт
• 1 Мб = 2²⁰ = 1024 Кб
• 1 Гб = 2³⁰ = 1024 Мб
• 1 Тб = 2⁴⁰ = 1024 Гб

Другими словами: число 1024, это количество байт в килобайте, это количество килобайт в мегабайте, это количество мегабайт в гигабайте.

В компьютерных сетях используют килобиты(Кбит), мегабиты(Мбит) и гигабиты(Гбит):

• 1Кбит = 1000 бит
• 1Мбит = 1000 Кбит = 1000 000 бит
• 1Гбит = 1000 Мбит = 1000 000 Кбит = 1000 000 000 бит

Гигабайты, мегабайты, килобайты, байты в биты и наоборот

Переведём последовательно 2 гигабайта в биты через мегабайты, килобайты и байты:

2 Гб = 2 × 1024 = 2048 Мб

2048 Мб = 2048 × 1024 = 2097152 Кб

2097152 Кб = 2097152 × 1024 = 2147483648 байт

2147483648 байт = 2 147 483 648 × 8 = 17179869184 бит

Перевод из бит в байты производится делением на 8, а из байт в килобайты, из килобайт в мегабайты и из мегабайт в гигабайты – делением на 1024

Для измерения физических величин(х, m, t) есть эталонные единицы(м, кг, с). И для измерения информации нужно ввести измеряемую величину. Алфавитный подход позволит измерить информационный объём текста на некотором языке.

Мощность это полное число символов в алфавите, обозначают N.

Каждый символ имеет информационный вес, который зависит от мощности N алфавита. Наименьшая N, или наименьшее число символов в алфавите = 2, и состоит из 0 и 1. А информационный вес этого алфавита i =1 и называется бит.

С увеличением N увеличивается информационный вес. 1 символ в 4-х символьном алфавита весит 2 бита, т.е. все символы такого алфавита могут закодированы всеми возможными комбинациями из 2 цифр двоичного алфавита:

00

01

10

11

Значит, имея 4 различных символа, получаем информационный вес любого из них равный 2 (Если N=4, то i=2). Используя 3 различные цифры, можно составить 8 различных комбинаций. Значит, имея N = 8, получаем информационный вес i =3.

Количество информации во всём тексте (или информационный объём текста) I состоящим из К символов равно
произведению информационного веса символа i на количество символов К: I = i × K.

Задача. Компьютерный текст состоит из алфавита мощностью
256 знаков(символы, цифры, знаки препинания, скобки). Какой информационный объём имеет слово информация?

Решение. Воспользуемся формулой I = i × K, где К это количество символов
в слове информация т.е. 10, а i это сколько бит весит один символ:
N = 2ⁱ, N по условию = 256, находим i=8 . Итого: I = 8 × 10 = 80 бит

Решение задач на поиск различных ситуаций(не путать с информационным объёмом текста). Здесь нужно найти, количество предметов и количество свойств, которыми обладает этот предмет (символы, цвета, сигналы и т.п.). Затем, вычислить число различных ситуаций которые могут возникнуть располагая такими предметами. Данное число получается по следующей формуле:

количество свойств ^{количество предметов}

Задача 1. Сколько различных последовательностей длиной в 6 символов можно составить из цифр 0 и 1?

Решение: Нужно представить блок из 6 ячеек, каждая из которых может хранить два разных значения в нашем случае это 0 или 1, 2⁶ = 64

Наглядно представить решение этой задачи можно с помощью flash ролика где можно перебрать все 64 значения нажимая на биты

Задача 2. Сколько различных последовательностей длиной в 8 символов можно составить из цифр 0 и 1?

Решение: Нужно представить блок из 8 ячеек, каждая из которых может хранить два разных значения в нашем случае это 0 или 1, 2⁸ = 256.

Задача 3. Дано устройство, состоящее из двух переключателей, каждый из которых может быть установлен в один из трёх режимов. Сколько различных функций может реализовать устройство?

Решение: Здесь предмет это переключатель (но не устройство), он обладает тремя различными свойствами, количество переключателей два. Получаем: 3²=9.

Наглядно представить решение этой задачи можно с помощью flash ролика, где нажимая на каждый из двух предметов можно перебрать 9 различных значений (один предмет содержит 3-х различных изображения)

Задача 4. Два туристских лагеря расположенных по разные стороны реки условились передавать друг другу сообщения при помощи цветных фонариков красного и синего цвета, зажигая или гася их на 1 минуту. Каждую минуту наблюдатель с другого берега может зафиксировать одно из трёх событий: светит красный, светит синий или не светит никакой. Сколько различных сообщений можно передать за пять минут?

Решение: Здесь можно попасться, если принять во внимание что различных сообщений два: красный цвет и синий, но в условии идёт речь что принимающий турист считает выключенный фонарик как третье сообщение. Итак, различных событий три, количество повторений этих событий пять: 3⁵.

Задача 5. Сколько различных сообщений мог бы передать светофор, если бы у него одновременно горели сразу три фонаря, а каждый фонарь мог бы менять цвет на красный, жёлтый, зелёный и синий?

Решение: Здесь предмет это фонарь(но не светофор!!!), один фонарь обладает четырьмя различными свойствами, количество предметов три: 4³.

Задача 6. Табло состоит из ламп, способные находится в следующих различных состояниях: лампа горит, лампа не горит или лампа мигает. Сколько различных сообщений может передать табло, если в нём четыре лампы?

Решение: Здесь предмет это лампа(не табло), этот предмет обладает тремя различными свойствами, количество предметов четыре: 3⁴.

Решение задач с информационным объёмом сообщений, ведётся с применением формулы I = i × K, где I это информационный объём, i информационный вес предмета из всех участвующих в задаче предметах и K количество предметов участвующих в конечном результате задачи

Задача 7. В скачках участвуют 20 лошадей. Специальное устройство регистрирует прохождение каждой лошадью финиша, записывая её номер с использованием минимально возможного количества бит, одинакового для каждой лошади. Каков информационный объём сообщения, записанного устройством в байтах, если до финиша добрались 8 лошадей?

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

Задача 8. В некоторой стране автомобильный номер длинной 5 символов составлен из заглавных букв(33) и десятичных цифр в любом порядке. Каждый номер помещают в память ПК с использованием минимально возможным и одинаково целым количеством байт, а каждому символу в номере отводится одинаковое количество минимально возможных бит. Сколько байт хватит для записи 35 номеров?

Решение:

1. Сколько бит хватит для каждого символа в номере, если каждый символ состоит из 43 различных знаков: 6
2. Сколько целых байт понадобится ПК чтобы записать один номер: имеем 30 бит, подгоняем биты до такого количества чтобы они уложились в ровное количество байт, т.е. чтобы деление на 8 было без остатка. Получаем 32 бита итого 4 байта на номер
3. Один номер 4 байта количество номеров 35: итого 140 байт

Задача 9. В 2011 году на гран при F1 участвуют одиннадцать команд каждая команда представлена двумя пилотами(в том числе и российский пилот Виталий Петров). Специальное устройство регистрирует прохождение финиша каждого пилота, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого пилота. Каков информационный объём сообщения, записанного устройством, если до финиша добралось 17 пилотов?

Решение: Итак есть 22 пилота, в такое количество может уложиться пять бит чтобы устройство смогло всех зафиксировать, т.е. на каждого пилота по пять бит. К финишу приехало 17 пилотов получаем 17 * 5