Друзья, разбираем задачи прошедшего квеста на миллион. Для простоты, в разборе будем использовать формализованные формулировки задачи. Ознакомиться с исходными формулировками можно в самом квесте. Квест открыт и доступен для прохождения.
Тимур Гуев @tguev
Основатель BEEGEEK, автор курсов Поколение Python
Об одной изящной задаче
Easy
4 min
Хабр, привет! В этой статье хочу поделиться с вами одной изящной задачей из нашего прошедшего квеста, которая мне очень понравилась и, как мне кажется, заслуживает вашего внимания.
Имеется функция magic(), принимающая три целочисленных аргумента, в теле которой определены константы a, b, c, являющиеся натуральными числами. Требуется определить значения констант a, b и c за минимальное количество вызовов данной функции.
Квест в честь миллиона студентов на курсе для начинающих программистов
Easy
2 min
Хабр, привет! Давно я не писал этих слов... На связи Тимур, автор серии курсов по программированию "Поколение Python". 🐍
Последний раз я публиковал статьи около 10 лет назад. За это время произошло много интересного, обязательно расскажу об этом, но позже. А пока хочу поделиться новостью: на нашем курсе для начинающих питонистов набралось более миллиона студентов. Это первый курс на платформе Stepik с таким количеством студентов.
Для нас и для Stepik это очень большое событие, и мы бы хотели разделить его с нашими студентами и со всеми, кто изучает программирование вообще. Поэтому мы проводим онлайн-квест: его участники будут решать задачи по программированию, математике, логике, а самые успешные и удачливые получат призы. Ведь программирование — это не только про написание кода, это про умение решать самые разные задачи.
Под капотом у Stopwatch
8 min
Введение
Очень часто, нам разработчикам необходимо измерить время выполнения своего (и не только своего) кода. Когда я только начал программировать, я использовал структуру DateTime для этих целей. Прошло время, и я узнал о классе Stopwatch и начал его активно использовать. Думаю аналогичная ситуация была и у вас. Не то, чтобы я раньше не задавался вопросом о том, как работает Stopwatch, просто на тот момент знаний о том, что он позволяет измерять затраченное время точнее, чем DateTime мне хватало. Пришло время разъяснить себе, а так же читателям то, как на самом деле работает класс Stopwatch, а так же выяснить его преимущества и недостатки по сравнению с использованием DateTime.
Так ли прост строковый оператор +
6 min
Введение
Строковый тип данных является одним из фундаментальных типов, наряду с числовыми (int, long, double) и логическим (bool). Тяжело себе представить хоть, сколько либо полезную программу, не использующую данный тип.
На платформе .NET строковый тип представлен в виде неизменяемого класса String. Кроме того, он является сильно интегрированным в общеязыковую среду CLR, а так же имеет поддержку со стороны компилятора языка C#.
В этой статье я бы хотел поговорить о конкатенации, операции, которая выполняется над строками так же часто, как операция сложения над числами. Казалось бы, о чем тут можно говорить, ведь все мы знаем о строковом операторе +, но как оказалось, есть у него свои тонкости.
Длинная арифметика от Microsoft
9 min
Введение
Известно, что компьютер может оперировать числами, количество бит которых ограниченно. Как правило, мы привыкли работать с 32-х и 64-х разрядными целыми числами, которым на платформе .NET соответствуют типы Int32 (int) и Int64 (long) соответственно.
А что делать, если надо представить число, такое как, например, 29! = 8841761993739701954543616000000? Такое число не поместится ни в 64-х разрядный, ни тем более 32-х разрядный тип данных. Именно для работы с такими большими числами существует длинная арифметика.
Длинная арифметика — в вычислительной технике операции (сложение, умножение, вычитание, деление, возведение в степень и т.д.) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, используя базовые аппаратные средства работы с числами меньших порядков.
10 мифов о LINQ
5 min
Translation
Миф #1
Все LINQ запросы должны начинаться с ключевого слова 'var'. По сути основная цель ключевого слова 'var' — начать LINQ запрос!
Ключевое слово var и LINQ — это самостоятельные концепции. Ключевое слово var позволяет компилятору вывести тип локальной переменной на основании начального присваивания(неявная типизация). К примеру, следующий код:
var s = "Hello";
точный эквивалент для:
string s = "Hello";
потому что компилятор выводит тип переменной s как string.
Производящие функции — туда и обратно
9 min
«Производящая функция является устройством, отчасти напоминающим мешок. Вместо того чтобы нести отдельно много предметов, что могло бы оказаться затруднительным, мы собираем их вместе, и тогда нам нужно нести лишь один предмет — мешок».
Д. Пойа
Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
Д. Пойа
Введение
Математика делится на два мира — дискретный и непрерывный. В реальном мире есть место и для того и для другого, и часто к изучению одного явления можно подойти с разных сторон. В этой статье мы рассмотрим метод решения задач с помощью производящих функций — мостика ведущего из дискретного мира в непрерывный, и наоборот.
Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.
Интервью с Джоном Скитом
7 min
Translation
Во втором номере этого журнала, мы рады видеть Джона Скита в нашем «виртуальном» кресле. Джон Скит — настоящий помощник сообщества (взгляните на его значки на StackOverflow), ведущий C# специалист и автор множества книг. Джон является MS MVP начиная с 2003 года. В настоящее время он работает в компании Google.
Дамы и господа, без лишних слов, представляем вашему вниманию Программного Инженера и Джентльмена — Джона Скита.DNC: Привет Джон, мы очень рады, что ты нашел время в своём графике для этого интервью. Для начала мы все хотим знать больше о Джоне Ските, расскажи нам как все началось? Как Джон начал работать с компьютерами?
JS: Мой первый компьютер — общий для всей семьи был Sinclair ZX Spectrum 48 K, который мы купили когда мне было 8. Со временем я покупал и другие модели Spectrum-а, но затем постепенно перешел на PC. Долгое время я проводил большинство своего времени за компьютером, просто играя в игры, но программирование так же всегда присутствовало.
DNC: С какими сложными задачами ты столкнулся при работе на Sinclair? Задачи, которые погрузили тебя глубже в компьютерные науки?
JS: Одним из моих первых «больших» проектов на Spectrum-е было написание аналога языка Logo. В школе у нас были микрокомпьютеры BBC Micros и Logo использовался как язык для введения в вычисления; я действительно им наслаждался и хотел использовать его дома, но у нас не было интерпретатора для Logo. Я не имел понятия о тригонометрии и не имел хорошего представления о структурном программировании, но я проявил упорство и закончил с достаточно неплохой реализацией. Руководство, которое было вместе с Spectrum-ом было очень хорошим, я буквально выучил оттуда всю элементарную тригонометрию, за долго до того как мы начали изучать её в школе.
Интервью с легендой C# Эриком Липпертом
11 min
Translation
Материал взят из журнала DotNetCurry посвященному технологиям основанным на платформе .NET.
Дорогие читатели, мы очень рады видеть Эрика Липперта в этом номере журнала DNC. Эрик не нуждается в представлении людям знакомым с C#, но для остальных Эрик известен своей работой в команде разработчиков компилятора языка С#. Он посвятил значительную часть своей карьеры компании Microsoft, работая на различных должностях. До того как придти в Microsoft, Эрик работал в компании Watcom. Наши «старички» помнят Watcom как компанию, которая создала очень хорошие компиляторы для языков C++ и Fortran. В настоящее время Эрик работает в компании Coverity, помогая создавать продукты статического анализа кода.
Дорогие читатели, мы очень рады видеть Эрика Липперта в этом номере журнала DNC. Эрик не нуждается в представлении людям знакомым с C#, но для остальных Эрик известен своей работой в команде разработчиков компилятора языка С#. Он посвятил значительную часть своей карьеры компании Microsoft, работая на различных должностях. До того как придти в Microsoft, Эрик работал в компании Watcom. Наши «старички» помнят Watcom как компанию, которая создала очень хорошие компиляторы для языков C++ и Fortran. В настоящее время Эрик работает в компании Coverity, помогая создавать продукты статического анализа кода.
foreach or for that is the question
5 min
Вопрос о выборе цикла for/foreach стар, как мир. Все мы слышали, что foreach работает медленнее for-а. Но не все знаем почему… А вообще так ли оно? Когда я начинал изучать .NET, один человек сказал мне, что foreach работает в 2 раза медленнее for-а, без каких-либо на то обоснований, и я принял это как должное. Теперь, когда чьих-то слов мне мало, я решил написать эту статью.
В этой статье я исследую производительность циклов, а так же уточню некоторые нюансы.
Итак, поехали!
.NET и паттерны проектирования
8 min
Шаблон проектирования или паттерн — повторимая архитектурная конструкция, представляющая собой решение проблемы проектирования в рамках некоторого часто возникающего контекста.
Кажется, это определение мы слышали тысячу раз… Помимо знания терминов и паттернов интересно знать, как они применяются в реальных проектах.
В статье я рассмотрю несколько наиболее популярных паттернов используемых в .NET. Некоторые из них глубоко интегрированы в инфраструктуру .NET, в то время как другие просто применяются при проектировании базовых классов в BCL.
Паттернам проектирования посвящен не один десяток книг, но одна книга стоит особняком и это знаменитая книга «Банды четырех». Поэтому для большего понимания ситуации я буду приводить небольшое описание из этой книги.
Кажется, это определение мы слышали тысячу раз… Помимо знания терминов и паттернов интересно знать, как они применяются в реальных проектах.
В статье я рассмотрю несколько наиболее популярных паттернов используемых в .NET. Некоторые из них глубоко интегрированы в инфраструктуру .NET, в то время как другие просто применяются при проектировании базовых классов в BCL.
Паттернам проектирования посвящен не один десяток книг, но одна книга стоит особняком и это знаменитая книга «Банды четырех». Поэтому для большего понимания ситуации я буду приводить небольшое описание из этой книги.
.NET 4.5 — обновление на месте .NET 4.0
5 min
Translation
Вместе с бета версиями VS 2011 и Windows 8 многие люди будут устанавливать, и разбираться с .NET 4.5. В .NET 4.5 добавлено много новых усовершенствований, которые являются достаточно прозрачными, но важно понять, как с точки зрения CLR она работает на вашей машине.
Когда .NET 4.5 устанавливается она, фактически, заменяет .NET 4.0 на вашей машине. .NET 4.0 перезаписывается новой версией .NET 4.5, что в соответствии со словами Microsoft гарантирует 100%-ую совместимость. 100% совместимость звучит привлекательно, но все мы знаем, что добиться такого результата достаточно сложно. Но есть вещь гораздо более интересная, чем обратная совместимость, которая делает ситуацию с разворачиванием .NET 4.5 неудобной в лучшем и запутанной в худшем случае.
Когда .NET 4.5 устанавливается она, фактически, заменяет .NET 4.0 на вашей машине. .NET 4.0 перезаписывается новой версией .NET 4.5, что в соответствии со словами Microsoft гарантирует 100%-ую совместимость. 100% совместимость звучит привлекательно, но все мы знаем, что добиться такого результата достаточно сложно. Но есть вещь гораздо более интересная, чем обратная совместимость, которая делает ситуацию с разворачиванием .NET 4.5 неудобной в лучшем и запутанной в худшем случае.
x += x++
2 min
Translation
Хотел бы начать перевод с маленького опроса. Вопрос к .NET разработчикам пишущим на языке программирования C#.
Опрос в конце перевода.
Сегодня я смотрел внутренний список разработчиков языка C#. Один из вопросов был о поведении выражения «x += x++», а именно, каким должно быть правильное поведение. Я думаю этот вопрос более чем интересный, поэтому решил посвятить ему запись в своем блоге. Но для начала, НИКОГДА НЕ ПИШИТЕ ТАКОЙ КОД.
ОК, мы можем начать…
Опрос в конце перевода.
Сегодня я смотрел внутренний список разработчиков языка C#. Один из вопросов был о поведении выражения «x += x++», а именно, каким должно быть правильное поведение. Я думаю этот вопрос более чем интересный, поэтому решил посвятить ему запись в своем блоге. Но для начала, НИКОГДА НЕ ПИШИТЕ ТАКОЙ КОД.
ОК, мы можем начать…
Об одной изящной конструкции
Medium
7 min
Введение
Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:
Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит заданного числа .
Когда я прочитал условие задачи до конца, она не показалась мне сложной (она таковой и не является). Первое, что пришло мне в голову — это просто перебрать все знаменатели от до и для каждого знаменателя перебрать числители от до знаменателя, при условии, что числитель и знаменатель взаимно просты. Ну, а затем остается отсортировать их по возрастанию.
Такое решение верное, и задача прошла все назначенные ей тесты. Однако мой преподаватель сказал, что задачу можно решить намного красивее. Так я и познакомился с замечательной конструкцией: деревом Штерна — Броко.
Откуда растут руки у GetHashCode в .NET
12 min
Введение
Данная статья посвящена теме генерации хеш-кодов на платформе .NET. Тема является достаточно интересной, и думаю любой уважающий себя .NET разработчик должен ее знать. Поэтому поехали!
Что хранится в объектах помимо их полей?
Начнем нашу статью с того, что узнаем что хранится у объектов ссылочного типа помимо их полей.
У каждого объекта ссылочного типа есть так называемый заголовок (Header), который состоит из двух полей: указатель на тип которым является данный объект (MethodTablePointer), а так же индекс синхронизации (SyncBlockIndex).
Сортировка в .NET
16 min
Задача сортировки — это классическая задача, которую должен знать любой программист. Именно поэтому эта статья посвящена данной теме — реализации сортировки на платформе .NET. Я хочу рассказать о том, как устроена сортировка массивов в .NET, поговорить о ее особенностях, реализации, а также провести небольшое сравнение с Java.
Итак, начнем с того, что первые версии .NET используют алгоритм быстрой сортировки по умолчанию. Поэтому небольшой экскурс в быструю сортировку:
Итак, начнем с того, что первые версии .NET используют алгоритм быстрой сортировки по умолчанию. Поэтому небольшой экскурс в быструю сортировку:
Знай сложности алгоритмов
2 min
Translation
Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!
8 фактов, которые вы, возможно, не знали о C#
7 min
Translation
Вот несколько необычных фактов о языке C#, о которых знают лишь немногие разработчики.
Мы все знаем, как обычно выглядят индексаторы x = something["a"], а так же код необходимый для его реализации:
Но знали ли вы, что для доступа к элементам вы можете использовать params параметры x = something["a", "b", "c", "d"]?
Просто напишите ваш индексатор следующим образом:
1. Индексаторы могут использовать params параметры
Мы все знаем, как обычно выглядят индексаторы x = something["a"], а так же код необходимый для его реализации:
public string this[string key]
{
get { return internalDictionary[key]; }
}
Но знали ли вы, что для доступа к элементам вы можете использовать params параметры x = something["a", "b", "c", "d"]?
Просто напишите ваш индексатор следующим образом: