Свершилось! Аркадий Дьяконов darkaha@mail.ru победил задачи, поставленные перед нашими читателями экспертами компании ABBYY, за что и был награжден сертификатом на FineReader. Слава ему!

 

Правильные ответы

 

Задача 1

Дан массив из целых чисел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.

 

Решение

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

Одно из решений задачи:

// Далее считаем, что массив, в котором ищем подмассив, именуется как array.
// Его размер же именуется как arraySize
int maxSum = array[0];
int maxStartIdx = 0;
int maxEndIdx = 0;
int currentSum = 0;
int currentStartIdx = 0;
for( int i = 0; i < arraySize; i++ ) {
    currentSum += array[i];
    if( currentSum > maxSum ) {
        maxSum = currentSum;
        maxStartIdx = currentStartIdx;
        maxEndIdx = i;
    } else if( currentSum < 0 ) {
        currentSum = 0;
        currentStart = i + 1;
    }
}
 

Задача 2

Дан текст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичное время, объясните их преимущества и недостатки.

 

Решение

  1. Префиксное дерево (оно же бор). Строится за O(length(Text)k), где k — размер алфавита. Можно сделать log(k), если при построении в узлах дерева хранить какое-то сбалансированное дерево, чтобы искать символ за логарифм. Для решения задачи нужно при построении в листьях хранить счетчик. Когда при построении дерева прошли слово и добавили новый лист, нужно поставить 1 или сделать +1 (если лист уже существовал). Построение бора есть тут.
  2. Нам понадобится хеш-функция для строки и какая-нибудь хеш-таблица для этих же строк. Каждый раз через хеш добавляем строку в таблицу. Если строка была, то делаем +1 к счетчику, иначе заводим новый, равный 1 (используем готовый контейнер CHashTable<CString, int>). Проходим по таблице и проверяем счетчики для вывода статистики.
 

Задача 3

Даны числительные языка хауса:

đari bakwai da hamsin da shidda — 756
sitta da đari bakwai da biyar — 6705
saba’a da đari biyar da sittin — 7560

Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda.
Запишите на хауса: 67 и 5605.

 

Решение

saba’in da biyar — 75
đari shidda da sittin da shidda — 666
67 — sittin da biyar
5605 — hama’a da dari shidda da biyar
 

Задача 4

Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?

 

Решение

Сгенерируем пять чисел x1, x2, x3, x4, х5.
Их сумма Х = x1 + x2 + x3 + x4 + х5, принимает значение 5 <= X <= 25, то есть ровно 21 значение.

Далее Х % 7 + 1 и будет равновероятно выдавать нам числа от 1 до 7. Может потребоваться несколько выполнений цикла.

6 комментариев

  1. bestdark

    26.06.2016 at 18:45

    Решение 4й задачи неверное
    Генерироваться числа будут и правда в диапазоне от 1 до 7
    Но вот не с равной вероятностью
    Дело в том что сумма этих чисел не равномерно распределена
    сумма будет равняться 5 только в том случае если все числа будут равны 1 (единственный вариант 1 1 1 1 1)
    А вот например сумма 6 может быть в 5 разных вариантах (1 1 1 1 2\1 1 1 2 1\1 1 2 1 1\1 2 1 1 1\2 1 1 1 1)
    Таким образом взятые по модулю 7 числа также не будут иметь равномерное распределение
    Вот такой код на visual c++ это доказывает
    #include «stdafx.h»
    #include
    int main()
    {
    int counter[7];
    memset(counter, 0, sizeof(int) * 7);
    for (int x1 = 1; x1 <= 5; x1++)
    for (int x2 = 1; x2 <= 5; x2++)
    for (int x3 = 1; x3 <= 5; x3++)
    for (int x4 = 1; x4 <= 5; x4++)
    for (int x5 = 1; x5 <= 5; x5++)
    counter[(x1 + x2 + x3 + x4 + x5)%7]++;
    for (int i = 0; i < 7; i++)
    std::cout << i + 1 << " — " << counter[i] << "\n";
    return 0;
    }
    Результат работы программы:
    1 — 450
    2 — 451
    3 — 450
    4 — 446
    5 — 441
    6 — 441
    7 — 446

    • bestdark

      26.06.2016 at 18:47

      вот второй строке кода подключаеться iostream
      при отправке коментария код испортился

    • mrPrizrak

      28.06.2016 at 15:40

      Согласен, решение 4-ой задачи неверное.
      Чтобы распределение исходов было равновероятным нужно:

      1. Делаем 7 вызовов функции [ rnd(5) — 1 ]
      2. Склеиваем результаты и получаем семизначное число
      3. Предполагаем, что полученное число записано в системе счисления с основанием 5, и переводим в десятичную
      4. Вычисляем остаток от деления на 7
      5. Прибавляем единицу. Полученное значение — и есть ответ

      Пояснение — в результате работы шагов 1-2 мы получаем случайное число в диапазоне от 0000000 до 4444444. Распределение результатов при этом равномерное. Количество возможных вариантов без остатка делится на 7. Таким образом, деление полученного числа на 7 равновероятно дает остаток от деления в диапазоне [0..6]

      • bestdark

        30.06.2016 at 16:31

        Это тоже неверный ответ
        7 вызовов функции дают нам 5^7 различных вариантов набора чисел
        Каждому такому набору вы ставите в соответствие 7 различных значений
        Но так как 5^7 не кратно 7 то распределение не может быть равномерным

        Такое контр-доказательство применимо практически ко всем подобным методам

        Проблема в том что количество вариантов которые мы получаем генерируя рандомные числа в пределах 1..5 никогда не будет кратно 7
        Тогда мы не можем равномерно распределить ответы

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

        Например генерируем 2 числа r1 r2
        берем сумму r1+5*(r2-1)
        Если сумма будет меньше либо равно 21 то берем ёё по модулю 7 и прибавляем 1
        В противном случае генерируем другие числа и начинаем заново

        P.S. ваш метод можно упростить не используя системы исчисления в явном виде
        просто берем сумму случайных чисел с коефициентами 5^0,5^1,5^2 и т.д.

  2. stacco

    28.06.2016 at 22:40

    В ответе на третью задачу, кажется, есть ошибка: исходя из предоставленных данных можно предположить, что 67 наиболее вероятно переводится sittin da bakwai или, менее вероятно sittin da saba. В то время как sittin da biyar скорее всего — 65.

Оставить мнение

Check Also

Господин Самоуничтожение. Как в домашних условиях смастерить Rubber Ducky со встроенной пиротехникой

Представь: ты втыкаешь в USB какую-то флешку, и вдруг в браузере открывается окно, где гру…