Конкурс. Программирование.

[Proydoha]

Sasha:

По заявкам трудящихся проводим конкурс по программированию. В данной теме я буду выкладывать вопросы с указанием времени на их выполнение и максимального количества баллов, которые за него можно получить. Ответы принимаются в лс в формате: "Ответ #N". После объявления результатов по заданию ответы не принимаются. Разрешено присылать другой вариант решения до объявления результатов. Предыдущий ответ в таком случае проверяться не будут. После подведения итогов полученные баллы и наилучший на мой взгляд ответ будут выложены в данной теме.

На количество баллов присуждаемых за ответ влияет:
- Правильность решения
- Оптимальность выбранного алгоритма

На количество баллов присуждаемых за ответ НЕ влияет:
- Выбор языка реализации
- "Красота" кода
- Придерживание основных парадигм программирования

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

Обсуждения и аппеляции разрешены.

Начнем мы с более простых вопросов, а дальше видно будет.



Задание #1
Время выполения 3 дня
Количество баллов: 5

Дано 4 вида скобок: {}, [], <>, (). Дана входная строка с комбинацией открывающих и закрывающих скобок. Необходимо проверить данную строку на правильность (закрывающая скобка должна соответствовать открывающей, количество открывающих и закрывающих скобок должны быть одинаковыми).
Пример:
{[]<()>} - правильная
({[]} - неправильная
({<}>) - неправильная


Итоги:

Участники:		Ответы:		Баллы:
Proydoha		Исходник Результат		5
Jeka		Исходник/Результат		3

Комментарии:
Прокомментирую первое задание.

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

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

PUSH - занести 1 элемент в стек
POP - извлечь 1 элемент из стека

При чем работает стек по принципу LIFO (last in first out), тоесть последний помещенный в стек элемент будет извлечен первым. Образно это можно представить в виде ящика с книгами, где последняя положенная в ящик книга будет извлечена первой, а чтобы добраться до книги, которая лежит на самом дне (первая попала в коробку) необходимо сначала извлечь все книги, которые лежат над ней. Стек так же можно реализовать в виде массива с счетчиком хранящихся в нем элементов. Proydoha и Jeka так и поступили. Посколько не все участники знакомы с ООП я тоже буду рассматривать такой вариант, хотя это усложнит алгоритм.

Итак нужно объявить символьный массив и счетчик элементов с начальным значением -1, так как элементы в массиве нумеруются с 0, а в начале массив пуст.

В результате, когда мы встречаем открывающую скобку мы заносим ее в позицию mas[i+1] и увеличиваем значение счетчика на 1.

Когда встречаем закрывающую скобку сравниваем ее с последней запомненой открывающей, то есть, mas, и уменьшаем счетчик на 1, то есть перемещаем вершину стека (последний запомненный элемент) вниз на 1.

Если мы встретили закрывающую скобку, а счетчик равен -1, значит у нас нет соответствующей ей открывающей.

Если строка закончилась, а счетчик не равен -1, значит в стеке остались элементы, а значит количество открывающих скобой больше, чем количество закрывающих.

Не рассмотренной осталась часть сравнения скобок на соответствие закрывающих открывающим. Для этого воспользуемся оператором switch. Это аналог оператора if, который отличается тем, что имеет не 2 ветки, а более.

Синтаксис его таков:

Код Выделить Развернуть

switch(выражение)
{
   case <значение 1>:
   {
      <операторы 1>
   }
   ...
   case <значение n>:
   {
      <операторы n>
   }
   default://попадем сюда, если не одно из значений не подходит
   {
      <операторы d>
   }
}

Теоретически, оператор switсh можно заменить оператором if таким образом:

Код Выделить Развернуть

if(выражение == значение 1)
{
   <операторы 1>
}
else
{
   ...
   if(выражение == значение 2)
   {
      <операторы n>
   }
   else
   {
       <операторы d>
   }


Допустим с - просматриваемый символ строки. Получим следующий код:

Код Выделить Развернуть

switch(c)
{
   case '(':
   {
      // заносим в стек
   }
   case '<':
   {
      // заносим в стек 
   }
   case '{':
   {
      // заносим в стек
   }
   case ')':
   {
      // последний элемент в стеке должен быть (
   }
   case '>':
   {
      // последний элемент в стеке должен быть <
   }
   case '}':
   {
      // последний элемент в стеке должен быть {
   }
}


Ну вот в принципе как-то так. А если что не так - извините, я старался!



Задание #2
Время выполения 5 дней
Количество баллов: 2

Закодить такую вот формулу:



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

Итоги:

Участники:		Ответы:		Баллы:
Proydoha		Исходник Результат		2
Jeka				2
timelimit		Исходник/Результат		1

Комментарии:
Вот как я решал это задание на с++ (формула разбита на 3 части для избежания ошибок со скобками):

Код Выделить Развернуть

double chisl = pow(x-0.5,(double)1/2);
double znam = sqrt((x-x/2)*pow(x+x/2,3));
rez = pow(chisl/znam,(double)1/3);

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

Код Выделить Развернуть

double rez;
        try
        {
                double chisl = pow(x-0.5,(double)1/2);
                double znam = sqrt((x-x/2)*pow(x+x/2,3));
                rez = pow(chisl/znam,(double)1/3);

        }
        catch(...)
        {
                ShowMessage("Входные данные выходят за область допустимых значений");
                return;
        }

Стоит отметить, что блок try локализует объявленные в нем переменные, а значит переменная rez перестает быть видимой за его пределами, поэтому я объявил ее раньше. Такой код убережет нас не только от чисто математических проблем, а и к примеру переполнению значения и прочих неприятностей. Правда в данном случае я использовал библиотечные функции степени и корня, а в них уже перехватываются исключения связанные к примеру с взятием корня от отрицательного числа, а значит до нашего обработчика они не дойдут. Можно было бы конечно пытаться с этим бороться (если конечно исключения там действительно выбрасывались), но программа не падает, фейковых результатов не выдает, а значит я оставил все как есть.

Решил обратить внимание еще вот на что.

Код Выделить Развернуть

(double)1/2

Объясню почему я так написал. Компиляторы представляют литералы (числа) без плавающей запятой в виде int значения. А значит если написать просто 1/2, результатом вычисления будет 0. Потому что получив ответ 0,5 компилятор отбросит от него дробную часть (именно отбросит, а не округлит). Написав перед выражением команду (double), мы говорим компилятору о том что результат нужно явно преобразовать в значение double. Того же эффекта можно добиться написав:

Код Выделить Развернуть

1.0/2

Увидев вместо 1 - 1.0, компилятор поймет что это double значение и представит результат в том же типе.



Задание #3
Время выполения 7 дней
Количество баллов: 10

Необходимо написать программу на языке С++ для сортировки массива целых числел от 0 до 9. Числа передаются в функцию main в виде строки, разделенные пробелом. Количество чисел заранее не известно. Результат сортировки никуда выводить не нужно. Алгоритм сортировки должен быть вынесен в отдельную функцию. Баллы за решение начисляются пропорционально скорости работы алгоритма сортировки.

Итоги:

Участники:		Ответы:		Баллы:
Jeka				10
Proydoha		Исходник Исходник/Результат		7

Задание #4
Время выполнения: 5 дней
Количество баллов: 10

Дан двумерный массив, заполненный нулями и единицами. Необходимо "перевернуть" этот массив на 180 градусов.

Пример
Входной массив:
0 1 0 1 1
0 0 1 0 1
1 0 0 1 1
Выходной массив:
1 1 0 0 1
1 0 1 0 0
1 1 0 1 0

Итоги:

Участники:		Ответы:		Баллы:
Proydoha		Исходник Результат		9
Jeka				7
timelimit				7

Комментарии:
Допустим у нас есть массив int mas [ x ][ y ]. Так как в памяти он располагается линейно, то задача сводится к реверсированию одномерного массива mas[x*y]. Тут все легко, берем следующий цикл:

Код Выделить Развернуть


int x;
k = n * m;
for(int i = 0; i < k / 2; i++)
{
   x = mas[i];
   mas[i] = mas[k - i];
   mas[k - i];
}


Теперь посмотрим как этот цикл можно было бы оптимизировать. Есть очень важная деталь: при большом размере массива, время обмена в начале цикла будет значительно превосходить время в конце. Это связано с тем, что если данные, которые мы меняем находятся на расстоянии друг от друга большем, чем размер кеша процессора, то появляются издержки на кеширование каждой переменной по отдельности. Если вы не поняли смысла написанного - ничего страшного. Это выходит далеко за разделы любительского программирования. И еще одна деталь: наш массив может принимать только 2 значения, а значит вероятность того что данные для обмена будут одинаковыми очень высока, а именно 0,5. Тоесть поставив в цикл условие, что одинаковые данные менять не нужно, теоретически мы уменьшаем количество операций обмена в 2 раза. Правда тогда появятся проблемы с предсказанием циклов (об этом было написано в статье что я кидал выше), поэтому создавая скажем драйвера, где быстродействие является критичным, необходимо исследовать конкретный случай и какие методы оптимизации его улучшат, а какие принесут только вред (сейчас кстати проведу небольшое исследование на эту тему и отпишусь о результатах).

Перепишем цикл используя условие:

Код Выделить Развернуть


int x;
k = n * m;
for(int i = 0; i < k / 2; i++)
{
   if(mas[i] != mas[k-i];
   {
      x = mas[i];
      mas[i] = mas[k - i];
      mas[k - i];
   }
}


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



Задание #5
Количество дней: 5
Количество баллов: 15

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

Требования к правильным адресам:

1. Адрес содержит локальную часть и домен, разделенные символом @ (RFC 2822 3.4.1).

2. Локальная часть может содержать символы алфавита, цифры и символы !, #, $, %, &, ', *, +, -, /, =, ?, ^, _, `, {, |, } ~, возможно разделенные точкой внутри, но не в начале адреса, не в конце или не рядом с другой разделяющей точкой (RFC 2822 3.2.4).

3. Локальная часть может содержать закавыченные части, несущие внутри кавычек пробелы (RFC 2822 3.2.5).

4. Экранированные части, такие как \@ , хотя этот синтаксис и утратил значение со времени начала действия RFC 822 (RFC 2822 4.4).

5. Максимальная длина локальной части - 64 символа (RFC 2821 4.5.3.1).

6. Доменная часть содержит идентификаторы, разделенные точкой (RFC1035 2.3.1).

7. Части доменного имени между точками начинаются с буквы, за которой следует нуль или более букв, цифр или символов -, заканчивающихся буквой или цифрой (RFC 1035 2.3.1).

8. Максимальная длина части доменного имени между точками 63 символа (RFC 1035 2.3.1).

9. Максимальная длина доменного имени - 255 символов (RFC 2821 4.5.3.1).

10. Доменное имя должно быть разрешаемым с помощью А или МХ DNS-записи (RFC 2821 3.6).

Стандартное соглашение имеет в виду, что символы имени должны поддерживать семибитные кодировки, то есть в реальности это ASCII-символы и никаких многобайтных кодировок.

Итоги:

Участники:		Баллы:
Proydoha		11

Задание #6
Количество дней - 5

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

Написать программу для перевода двоичных чисел в десятичные.
Количество баллов - 10

Написать программу для перевода десятичных чисел в двоичные
Количество баллов - 9

Написать программу для перевода двоичных чисел в шестнадцатиричные.
Количество баллов - 6

Написать программу для перевода шестнадцатиричных чисел в двоичные.
Количество баллов - 5

Во всех заданиях незначащие нули лучше убирать! В задании речь идет о неотрицательных, целых числах, диапазоном не более типа int (integer).

Итоги:

Участники:		Баллы:
Jeka		10
Proydoha		10
timelimit		9

Задание #7
Количество баллов - 15
Количество дней - 6

Есть бесконечная незамкнутая железная дорога. На ней стоит два поезда, на некотором расстоянии. Между ними два семафора на другом некотором растоянии. Используя заданные операторы написать одну программу, которую поставят на эти поезда и при запуске которой поезда встретятся в одной точке жд. Операторы языка:
LEFT - сдвигает поезд влево на определенную единицу меры
RIGHT - вправо
IF <оператор если поезд попал на семафор> <если не попал>
LABEL - метка
GOTO - перейти по метке

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

Код Выделить Развернуть

label1:
IF // проверяем находится ли поезд на семафоре
<GOTO label2> // если да значит мы доехали до первого семафора, идем по метке 2
<LEFT GOTO label1>// если нет продолжаем наш путь влево на встречу приключениям семафору, и переходим по метке 1, чтобы проверить не оказались ли мы на семафоре после выполнения последнего оператора LEFT
label2://если мы попали сюда значит первый семафор уже позади, и нам просто нужно посторить те же самые процедуры, чтобы доехать до второго
IF//второй семафор?
<GOTO label3> // да? идем на конец программы - миссия выполнена
<LEFT GOTO label2>// нет? продолжаем усердно двигаться влево в поисках семафора
label3:

Итоги:

Участники:		Баллы:
Proydoha		4
Jeka		2

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

Код Выделить Развернуть


right
left
right

Ну и разумеется необходимо эти команды зациклить:

Код Выделить Развернуть


label1:
right
left
right
GOTO label1

Таким образом поезда будут бесконечно двигаться вправо, при этом реально передвигаясь на 1 отрезок вправо за 3 итерации управляющей программы.
Рано или поздно левый поезд достигнет семафора, и это наш шанс ускорить его, которым мы и воспользуемся. Просто напишем другую ветку программы на которую перейдем при попадании на семафор:

Код Выделить Развернуть


label2:
right
right
right
GOTO label2

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

Код Выделить Развернуть


label1:
RIGHT
LEFT
RIGHT
IF<GOTO label2><GOTO label1>
label2:
RIGHT
RIGHT
RIGHT
GOTO label2

Как я и говорил, задача очень простая, но решить ее тяжело.



Задание #8
Количество дней - 9
Количество баллов - 20

Написать программу, которая будет вычислять сколько дней прошло между введеными пользователем датами (формат ввода: дд.мм.гггг). Сторонними библиотеками работы со временем пользоваться запрещено!

Не забываем что высокосные года бывают не каждые 4 года!

Итоги:

Участники:		Баллы:
Jeka		20
Proydoha		20

Задание #9
Количество дней - ?
Количество баллов - 15

Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка.

Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4.

Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.



Итоги после 8 заданий:

Участники:		Баллы:
Proydoha		68
Jeka		54
timelimit		17

Архив темы со старого форума.

[Sasha]

Я проверил ответы на задание №2 от Jeka и Timelimit, но пока не могу проверить решение Proydoha так как он офлайн, а решение у него на сервере (впредь буду сохранять себе). Сейчас выложу 3 задание, а потом уже когда Proydoha будет онлайн выложу результаты предыдущего задания.

[Sasha]

Задание #3
Время выполения 7 дней
Количество баллов: 10

Необходимо написать программу на языке С++ для сортировки массива целых числел от 0 до 9. Числа передаются в функцию main в виде строки, разделенные пробелом. Количество чисел может быть от 1 до 100. Результат сортировки никуда выводить не нужно. Алгоритм сортировки должен быть вынесен в отдельную функцию. Баллы за решение начисляются пропорционально скорости работы алгоритма сортировки.

[Sasha]

Теперь немного поясню. Цель этого задания написать как можно более оптимальный алгоритм. Вы можете реализовывать любой алгорим сортировки, главное любым способом сократить время его выполнения. Учитываться будет только время сортировки, тоесть время затраченное на формирование исходного массива из строки, полученой функцией main учитываться не будет. Для обеспечения равности условий, компилировать программу я буду на своем компиляторе, от вас требуется только исходный код.
Слушаю ваши вопросы.

[Proydoha]

Стоило только выйти из дома, как тут же я понадобился онлайн : )

Слушаю ваши вопросы.

Где взять бесплатный компилятор С++?

[Sasha]

Результаты задания #2:
Proydoha - 2 балла
Jeka - 1 балл
timelimit - 1 балл

[Sasha]

Стоило только выйти из дома, как тут же я понадобился онлайн : )

Слушаю ваши вопросы.

Где взять бесплатный компилятор С++?

borlandc, watcom c++, компиляторы С++ встроены во все версии Linux

[Sasha]

Proydoha, буду благодарен если ты обновишь результаты в первой теме и как то лучше отделишь их от остальной истории. А то я немного не понял как ты собирался их оформлять.
Вот исходник Jeka: http://rghost.ru/14437361
Вот исходник timelimit:

http://public.dts.net.ua/index.php
Загрузил, называется архив zadanie2.
Пароль мой ник

C меня +.

[Catcatcat]

Стоило только выйти из дома, как тут же я понадобился онлайн : )

Слушаю ваши вопросы.

Где взять бесплатный компилятор С++?

если для виндов есть visual studio и Borland C++Builder 6

[Sasha]

По второму заданию:
Правильный результат давало только решение от Proydoha, а его возведение в степень отрицательных чисел и результат в комплексном виде поверг меня в восторг! (сдесь будет апплодирующий смайлик когда он появится).
Остальные участники не справились с заданием, однако в коде нашлись вещи, за которые можно было дать 1 балл.
Решение победителя:
http://10.1.12.237/show_source.php?test_area/Contest_2.php
http://10.1.12.237/test_area/Contest_2.php

Вот как я решал это задание на с++ (формула разбита на 3 части для избежания ошибок со скобками):

Код Выделить Развернуть

double chisl = pow(x-0.5,(double)1/2);
double znam = sqrt((x-x/2)*pow(x+x/2,3));
rez = pow(chisl/znam,(double)1/3);

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

Код Выделить Развернуть

double rez;
        try
        {
                double chisl = pow(x-0.5,(double)1/2);
                double znam = sqrt((x-x/2)*pow(x+x/2,3));
                rez = pow(chisl/znam,(double)1/3);

        }
        catch(...)
        {
                ShowMessage("Входные данные выходят за область допустимых значений");
                return;
        }
Стоит отметить, что блок try локализует объявленные в нем переменные, а значит переменная rez перестает быть видимой за его пределами, поэтому я объявил ее раньше. Такой код убережет нас не только от чисто математических проблем, а и к примеру переполнению значения и прочих неприятностей. Правда в данном случае я использовал библиотечные функции степени и корня, а в них уже перехватываются исключения связанные к примеру с взятием корня от отрицательного числа, а значит до нашего обработчика они не дойдут. Можно было бы конечно пытаться с этим бороться (если конечно исключения там действительно выбрасывались), но программа не падает, фейковых результатов не выдает, а значит я оставил все как есть.

UPD: решил обратить внимание еще на вот чем. Кто не понимает смысла строки типа

Код Выделить Развернуть

(double)1/2

объясню почему я так написал. Компиляторы представляют литералы (числа) без плавающей запятой в виде int значения. А значит если написать просто 1/2, результатом вычисления будет 0. Потому что получив ответ 0,5 компилятор отбросит от него дробную часть (именно отбросит, а не округлит). Написав перед выражением команду (double), мы говорим компилятору о том что результат нужно явно преобразовать в значение double. Того же эффекта можно добиться написав

Код Выделить Развернуть

1.0/2, увидев вместо 1 - 1.0, компилятор поймет что это double значение и представит результат в том же типе.

[Sasha]

Стоило только выйти из дома, как тут же я понадобился онлайн : )

Слушаю ваши вопросы.

Где взять бесплатный компилятор С++?

если для виндов есть visual studio и Borland C++Builder 6

Тссс... Никому не говори что в нашей стране они бесплатные
Хотя да, я действительно забыл о существовании бесплатной версии VS. Express кажись называется. Это конечно будет удобнее чем программирование в страшных сине-желтых экранах старых компиляторов, или же компилирование в командной строке линукса. Кстати на счет командой строки можно еще воспользоваться блокнотом, или же notepad++, который подсветит синтаксис, и скомпилировать из под командной строки, дело в том что с появлением .net такая возможность для .net языков есть в Windows.

[Catcatcat]

Я пользуюсь исключительно бесплатными продуктами

[Proydoha]

Express кажись называется

Только что сказала, что мой триал с ней закончился.

Я закачал консольный борланд с++ компилер 5.5.

Попробую подружиться с ним. С подключением всякого уже не справился и загадил папку бин файлами из папок либс и инклюд. Теперь ничего подключать не надо - всё уже здесь! : )

Вот исходник Jeka: http://rghost.ru/14437361

Файл удалён.

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

Не совсем понял что имеется ввиду. Оформляю первое сообщение в теме по такому шаблону:

Условия конкурса
--разделительная черта--
Текст задания
Таблица с результатами выполнения и баллами
Комментарии к выполненному заданию
--разделительная черта--
Текст следующего задания
...
...
--разделительная черта--
Таблица с суммарным количеством очков
Архив темы со старого форума

[Sasha]

Все, спасибо больше, дальше я сам.

[Proydoha]

Если я куда-то пропаду - значит у меня подох монитор.