Смотритель: hubert
  • ,

Oracle снова судится с Google

Давным-давно, аж в 2007 году, компания Google представила Android. Вы, наверное, в курсе, что «зеленый робот» — близкий родственник нашей с вами любимой Java, а владеет всеми правами на неё компания Oracle. Только вот в 2007 году всё было не так: Java находилась в единоличном имуществе у совсем другой компании, а именно — у Sun Microsystems, своей родительницы. Надо сказать, Sun на тот момент была едва ли не крупнейшим апологетом Open Source и прочих элементов свободы, равенства и братства. Посему, её представители поздравили Google с запуском Android. Дескать, нам не жалко, пользуйтесь Java, от этого все только выигрывают.

google vs oracle
К сожалению, жить Sun оставалось недолго. В 2009 году эту чудесную компанию поглотил гигант Oracle вместе со всеми её изысканными софтварными технологиями и мудрёными серверами.

Oracle чужд какой-либо альтруизм, поэтому едва вспомнив об Android, новая хозяйка Java тут же подала на Google в суд с формулировкой «нарушение авторских и патентных прав на Java API».

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

Но Oracle не сдается просто так, и подаёт апелляцию. В 2014 году суд передумал, и решил, что структура, последовательность и организация API всё-таки подлежат копирайту, однако использование может подпадать под fair use. Эта формулировка провоцирует новый судебный процесс. Закончился он в 2016 году тем, что всё-таки признали в случае с Android fair use.

И вот, угадайте, что произошло в феврале 2017 года? Правильно, Oracle снова подаёт апелляцию. Делаем ставки, господа!
  • ,

Eclipse, NetBeans или IntelliJ IDEA? Выбираем IDE для Java-разработки

IDEA vs Netbeans vs Eclipse
Представляем вашему вниманию адаптацию статьи Мартина Хеллера, программиста и редактора ресурса JavaWorld.

Вы, вероятно, уже слышали о тройке самых популярных IDE для разработки на языке Java. Процентов 90 промышленных программистов пользуются либо Eclipse, либо NetBeans или же IntelliJ IDEA, и у каждой из этих IDE есть свои преимущества и недостатки. В этой статье мы постараемся описать их так, чтобы вы поняли, какая из них подходит именно вам. Хотя, конечно, лучше попробовать все три в работе, и выяснить, что лучше всего подходит именно вам. Этого не заменит ни один обзор.

Я и ранее работал с этими IDE, но для этого исследования я установил IntelliJ IDEA Ultimate 2016.2, Eclipse Neon Java EE, и NetBeans 8.1 Java EE на ноутбук MacBook Pro. Я тестировал IDE на нескольких open source Java-проектах.

Чего ожидать от IDE


Современная IDE «здорового Java-разработчика» должна поддерживать Java 8, Scala, Groovy, а также другие языки виртуальной машины Java, которые тот регулярно использует. Не оказалась бы лишней и поддержка основных серверов приложений и наиболее популярных веб-структур, в том числе — Spring MVC, JSF, Struts, GWT, Play, Wicket, Grails и Vaadin. IDE должна быть совместима с любыми билдами систем контроля версий, например, Ant, Maven или Gradle, вместе с Git, SVN, CVS, Mercurial или Bazaar. Дополнительно для среды разработки важно уметь работать с базами данных и клиентским слоем вашего стека, обладать поддержкой встроенного JavaScript, TypeScript, HTML, SQL, JavaServer Pages, Hibernate, а также API Java Persistence.

Наконец, логично надеяться на то, что IDE позволит редактировать, создавать, отлаживать и тестировать системы без лишнего напряжения. Идеально, если среда разработки поддерживает не только интеллектуальное автодополнение кода, но также интеллектуальный рефакторинг и метрики кода. Во многих случаях окажется не лишней поддержка фреймворков для тестирования и заглушек. Если ваша команда использует систему тикетов и CI/CD, нужно, чтобы IDE могла к ним подключиться. А еще решите, нужны ли вам развертывание и отладка в контейнерах и облаках.

Мы перечислили только основные ожидания (возможно, вам есть, что добавить), а теперь присмотримся к нашим соперникам.

IntelliJ IDEA

IDEA
IntelliJ IDEA с точки зрения возможностей и цены поставляется в двух вариантах: бесплатного Community edition, и платного Ultimate edition с расширенной функциональностью.
Community edition предназначена для JVM- и Android-разработки. Бесплатная версия поддерживает Java, Kotlin, Groovy и Scala; Android; Maven, Gradle и SBT; работает с системами контроля версий Git, SVN, Mercurial и CVS.

Ultimate edition приспособлена для веб- и enterprise-разработки. Эта версия IDE работает не только с Git, SVN, Mercurial и CVS, но также с Perforce, ClearCase и TFS; в ней вы сможете писать на JavaScript и TypeScript; естественно, есть поддержка Java EE, Spring, GWT, Vaadin, Play, Grails и ряда других фреймворков. И, конечно, не обошлось без SQL и инструментов для работы с базами данных.

Идея, которой руководствуются разработчики этой IDE, формируя ценовую политику, заключается в том, что её коммерческая версия (Ultimate) займет свое место на компьютерах профессионалов, за счет чего их производительность повысится. Если Java-программист ежегодно зарабатывает $50 тысяч (или того больше), возврат потраченных на платную IDE IntelliJ IDEA инвестиций (500 долларов за годовую подписку) произойдет очень быстро за счет даже незначительного ускорения его работы.

В последующие годы цена для бизнеса падает, для стартапов, фрилансеров она существенно ниже, а для студентов, учителей, Java-чемпионов и open source-разработчиков она и вовсе бесплатна.
IntelliJ IDEA подкупает своим глубоким пониманием кода, умной эргономикой, встроенными функциями для разработки и поддержкой многих языков.

Intellij IDEA warnings
Рисунок 1. IntelliJ IDEA показывает количество предупреждений (warnings) и предположения, основанные на статистическом анализе Java-кода. Вы можете изучить предположения подробнее, кликнув на них, как показано на картинке; во многих случаях вы получите список с выбором и вариантами исправлений.

Глубокое понимание кода

Подсветка синтаксиса и простое автодополнение кода — обычное дело для любых современных Java-редакторов. IDEA пошла дальше, предлагая «умное автодополнение». Этот термин означает, что среда разработки показывает список наиболее релевантных символов, применимых в данном контексте. Список символов зависит не только от контекста как такового, «общепринятого», но от стиля программирования разработчика, от того, насколько часто он использует те или иные операторы. «Завершение цепочки» и вовсе показывает список применимых символов, допустимых через методы или геттеры в текущем контексте. Кроме того, в случае со статическими членами или константами IDEA автоматически добавляет любые необходимые операторы импорта (import). Во всех случаях автодополнения, IDEA пытается угадать тип символа во время выполнения, уточнить свой выбор и даже применить приведение типов если необходимо.

Код Java часто включает фрагменты из других языков в виде строк. IDEA может вводить код SQL, XPath, HTML, CSS или JavaScript в строковые литералы Java. В этом смысле IDE может проводить рефакторинг кода на нескольких языках. Например, если вы переименуете класс в JPA-отображении, IDEA обновит соответствующий класс сущностей и выражений JPA.

Во время рефакторинга фрагмента кода, у разработчика возникает одно (вполне естественное) желание: чтобы все дубликаты этого кода также зарефакторились. IDEA Ultimate находит дубликаты и похожие фрагменты и также применяет к ним рефакторинг.

IntelliJ IDEA анализирует код при загрузке и непосредственно при вводе. Она указывает на предполагаемые проблемы (как на нашем рисунке выше) и, по желанию, предлагает список вероятных быстрых правок к обнаруженным проблемам.

Эргономика

IDEA ergonomics
IntelliJ IDEA спроектирована так, чтобы не выбивать разработчика из состояния потоковой продуктивности, если он уже в него попал. Окно Project, показанное на первом рисунке слева, исчезает по простому клику мышки, чтобы программист мог сосредоточиться на окне редактора кода. На все действия, которые нужны во время написания кода, есть комбинации клавиш для их быстрого вызова, в том числе — определения символов во всплывающих окошках.

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

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

Встроенные инструменты

IntelliJ IDEA обеспечивает единый интерфейс взаимодействия с большинством систем контроля версий, включая Git, SVN, Mercurial, CVS, Perforce и TFS. Вы можете управлять изменениями непосредственно в IDE, что очень удобно. Когда я тестировал IDEA, у меня возникало желание, чтобы последнее изменение в исходном коде показывалось в окне редактора в виде аннотации (как это происходит, например, в Visual Studio). Как оказалось, у IDEA есть для этого специальный плагин.

Также IDEA оснащена инструментами для сборки, средой выполнения тестов, инструментами покрытия (coverage tools) и встроенным терминальным окном. У IntelliJ нет собственного профайлера, но с помощью плагинов к ней можно подсоединить сторонние. Например, YourKit, созданный бывшим ведущим разработчиком JetBrains или VisualVM (это переупакованная версия профайлера NetBeans).

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

Серверное программирование на Java предполагает частое взаимодействие с базами данных, так что программисты IDEA версии Ultimate оценят удобство инструментов для работы с SQL и БД. Но если кому-то их возможностей будет мало, можно приобрести версию IDEA Ultimate с встроенной SQL IDE (DataGrip). Правда, это будет несколько дороже, чем обычная подписка IDEA Ultimate.

IntelliJ IDEA поддерживает все основные серверы приложений JVM, и позволяет разворачивать и проводить отладку на этих серверах, что нивелирует хорошо знакомые всем программистам Java Enterprise трудности. IDEA также поддерживает Docker (с помощью плагина, который добавляет к среде разработки специальное окно инструментов Docker. К слову, плагинов у IDEA — просто море.  

Настоящий полиглот

IDEA расширила поддержку кода Spring, Java EE, Grails, Play, Android, GWT, Vaadin, Thymeleaf, Android, React, AngularJS и других фреймворков. Вы, вероятно, заметили, что не все из них относятся к Java. IDEA непосредственно из коробки «понимает» и другие языки — Groovy, Kotlin, Scala, JavaScript, TypeScript и SQL. Если вы не нашли в этом списке нужного вам языка, в настоящий момент есть 19 языковых плагинов IntelliJ, в частности, для поддержки R, Elm и D.

Eclipse IDE

Eclipse
Eclipse долгие годы уверенно держал пальму первенства по популярности среди Java IDE. Эта среда полностью бесплатная, с открытым исходным кодом, написанным преимущественно на Java. Тем не менее, её модульная архитектура позволяет использовать Eclipse и с другими языками. Проект Eclipse, инициированный IBM, появился в 2001 году. Им хотели заменить семейство сред разработки IBM Visual Age, основанных на Smalltalk.
Ну а главной целью, о чем даже название говорит, было затмить Microsoft Visual Studio (eclipse по-английски означает затмение).

Портативность Java помогает Eclipse быть кроссплатформенной средой: эта IDE работает на Linux, Mac OS X, Solaris и Windows.
Хорошо это или плохо, Java Standard Widget Toolkit (SWT), по крайней мере частично, отвечает за внешний вид Eclipse.

Своей производительностью (или, как говорят некоторые доброжелатели, её отсутствию) Eclipse обязана JVM. Eclipse работает довольно медленно, поскольку упирается корнями в довольно старое «железо» и древние версии JVM. Даже сегодня она кажется медлительной, особенно если нацепить на неё много плагинов.
Часть расходов ресурсов Eclipse можно отнести на счёт её встроенного инкрементного компилятора, который запускается всякий раз при загрузке файла или обновлении кода. Полезная штука, именно она ловит ошибки при вводе текста.

Независимо от сборки, проект Eclipse поддерживает модель контента, которая содержит информацию об иерархии типов, ссылок и объявлениях Java-элементов.

Текущая версия Eclipse носит имя Neon (4.6.0). Я инсталлировал Eclipse Java EE IDE для веб-разработчиков (это далеко не единственная опция, вы можете выбрать что-то ещё). Он содержит минимальную Eclipse SDK, а плагины добавляются по требованию. К слову, работа с плагинами в этой IDE — не для слабонервных. Сторонние плагины часто конфликтуют между собой, хотя в их официальной спецификации об этом ничего не сказано.

Eclipse Workbench
Рисунок 2. Слева направо расположены четыре панели инструментальных средств Eclipse: Проводник пакетов, редактор Java, структура классов Java и список задач. Проект, загруженный в Eclipse на этом рисунке — JUnit test framework. Панели можно легко поменять местами.

Поддержка плагинов

Экосистема плагинов Eclipse — это одновременно сильная сторона этой IDE и одна из главных её проблем. Именно из-за несовместимости плагинов порой падают целые сборки, и программистам приходится начинать работу сначала.

В настоящее время для Eclipse написано более 1700 плагинов, официальных и неофициальных, которые могут работать отлично, а могут из рук вон плохо. Плагины Eclipse, поддерживают более 100 языков программирования и почти 200 фреймворков для разработки приложений. Большинство серверов Java также поддерживаются: если вы обозначите новое соединение с сервером из Eclipse, вы попадете в список папок производителей, где найдете около 30 серверов приложений. Только вариантов Apache Tomcat будет целых девять штук. Коммерческие производители, как правило, собирают свои решения вместе: например, есть только один пункт Red Hat JBoss Middleware, а уже внутри вы найдете WildFly и инструменты EAP-сервера, а также JBoss AS.

Редактирование, рефакторинг и отладка

Первый опыт работы с Eclipse, может привести в замешательство, и даже сбить с толку. Поначалу необходимо настроить Eclipse и привыкнуть к её концептуальной архитектуре рабочих пространств, ракурсов и видов. Всё это определяется плагинами, которые вы установили. Для серверной разработки на Java, вы, вероятно, будете использовать ракурсы Java, Java EE и Java browsing, вид, отображающий структуру пакета (Package Explorer), ракурс отладки, ракурс командной синхронизации веб-инструментов, ракурс разработки баз данных и ракурс отладки базы данных. На практике все обретает смысл, когда вы откроете нужные вам окна.
Eclipse практически всегда предлагает несколько способов решения той или иной задачи. Например, вы можете просматривать код с помощью ракурса просмотра Java (Java browsing perspective). Что выбрать — дело вкуса и выбора.

Специальный поиск Java позволяет найти объявления, ссылки и вхождения Java-пакетов, типов, методов, полей. Вы также можете использовать быстрый доступ к поиску и предпросмотр.

Распространенные паттерны кода можно сгенерировать из шаблонов кода. Рефакторинг Java в Eclipse, поддерживает 23 операции, начиная от общепринятых операций по переименованию и заканчивая менее очевидными преобразованиями (как в книге Мартина Фаулера).

Eclipse, поддерживает отладку как локально, так и удаленно, при условии, что вы используете JVM, которая поддерживает удаленную отладку. Отладка довольно стандартна: вы определяете контрольные точки, а затем просматриваете переменные в закладке отладки. Конечно, можно пошагово выполнять свой код и вычислять выражения.

У Eclipse — обширнейшая база документации самого разного возраста, ценности и полезности. Увы, обнаружить несоответствующую текущей версии картинку в инструкции, например, с устаревшим интерфейсом и расположением кнопок — обычное дело для этой IDE. К сожалению, проблема запоздалого обновления документации очень характерна для любых проектов с исходным кодом.

NetBeans

Netbeans
NetBeans появилась как студенческий университетский проект в Праге в 1996 году. В 1997 году IDE стала коммерческим продуктом, а в 1999 году её выкупила компания Sun Microsystems (родители Java) и уже на следующий год представила open source-релиз.
Актуальная версия 8.1 работает на машинах под управлением ОС Windows, Mac OS X, Linux и Solaris. Ну а пакет portable можно запустить на любых системах, для которых существует Java-машина. Себе я загрузил Java EE bundle, это один из шести возможных пакетов загрузки. Этот бандл поддерживает JavaScript и HTML, GlassFish и Tomcat, но не поддерживает PHP, C/C++/Fortran, Groovy и Grails: их можно получить в пакете «Всё включено» (или просто «All»). Тем не менее, при желании, я в любой момент смогу загрузить поддержку вышеназванных языков, выбрав соответствующий плагин (да и любой другой). Их у NetBeans поменьше, чем у Eclipse, зато они обычно не конфликтуют друг с другом.

Этой осенью Oracle (ей NetBeans досталась после поглощения Sun Microsystems) решила передать эту среду разработки под крыло Apache Software Foundation вместе со всеми правами, исходными кодами, торговой маркой, доменом «netbeans.org» и рядом других элементов инфраструктуры. Посему, будущее проекта пока туманно, хотя раньше у системы были определенные родственные привилегии. Так, именно NetBeans первой получила поддержку Java 8 практически сразу после выхода обновленной платформы, и была названа «официальной IDE для Java 8». Впрочем, через месяц после выхода это преимущество было утеряно: именно тогда другие IDE также получили поддержку восьмой Java.

Тем не менее, хочу отметить, поддержка Java 8 в NetBeans действительно хороша, и эта IDE отлично подходит для вплетения в «старый» код трюков восьмой версии. Её редакторы, анализаторы кода и конвертеры помогут программисту провести апгрейд кода, используя в нем конструкции, характерные для Java 8 — лямбда-выражения, функциональные операторы и ссылки на методы. Плагины JavaScript в NetBeans 8 отлично справляются с поддержкой Node.js и новейших инструментов JavaScript, таких как Gulp и Mocha, равно как и поддержку интерпретатора JavaScript Nashorn.

NetBeans Maven
Рисунок 3. Здесь NetBeans работает с тем же проектом на основе Maven, что и IntelliJ IDEA был открыт на рисунке 1. Обратите внимание на расширенную функциональность в контекстном меню и подменю рефакторинга.

Редактирование и рефакторинг

Редактор NetBeans поддерживает языки, обнаруживает ошибки в то время, когда вы печатаете, и помогает вам с помощью всплывающих подсказок и «умным» автодополнением кода. По субъективному ощущению IDE справляется с этой задачей быстрее, чем Eclipse, но несколько медлительнее IntelliJ IDEA. Кроме того, NetBeans обладает полным спектром инструментов рефакторинга (что показано на рисунке 3), которые позволяют программисту реструктуризировать код, не ломая его, выполнять анализ исходников, а также предлагает широкий набор подсказок для быстрых исправлений или расширения кода. В состав NetBeans входит инструмент проектирования для графического интерфейса пользователя Swing, ранее известный как «Project Matisse».

Разработчики высоко оценивают средство автоматизированного рефакторинга Inspect & Transform, появившееся в версии NetBeans 7.1. Оно позволяет провести анализ кода проекта и сделать предлагаемые улучшения. Хотя лично я предпочитаю сначала проверить весь собственный код unit-тестами, и только затем запускать инструменты, которые могут внести радикальные изменения. Я неоднократно страдал от всяческих автоматических исправлений, которые привели к невосполнимым последствиям.

Сборка, отладка и профилирование

У NetBeans есть отличная встроенная поддержка Maven и Ant, а также плагина для Gradle. Я очень обрадовался, когда обнаружил, что проекты Maven воспринимаются системой как «родные». Это означает, что их можно просто открывать, а не импортировать. NetBeans также содержит привлекательное (и полезное) графическое отображение для зависимостей Maven.

Отладчик Java NetBeans неплох, но с оговорками. Отдельный визуальный отладчик позволяет программисту делать снимки экрана пользовательского графического интерфейса и изучать интерфейсы приложений, выполненных с помощью JavaFX и Swing. Профайлер NetBeans делает более очевидным то, каким образом используется процессор и память, и обладает отличными инструментами для поиска утечек памяти.

Сравнение тройки гигантов

Я использовал все три IDE, Eclipse, NetBeans и IntelliJ IDEA, в течение многих лет в указанном хронологическом порядке. Всякий раз после перехода на другую IDE я чувствовал, что моя продуктивность повышается. Но даже когда я был твердо уверен, что мой окончательный выбор — IDEA, мне порой приходилось возвращаться к одной из двух оставшихся IDE. Так было, например, в то время, когда Eclipse была единственным инструментом, который поддерживал разработку под Android (сегодня есть Android Studio, текущая официальная IDE для Android, она основана на IntelliJ IDEA).

Конечно, все три интегрированные среды разработки имеют своих поклонников и противников. Я знаю множество Java-разработчиков, которые обожают IntelliJ IDEA, равно как и лояльные фанаты Visual Studio C++ и C#. Чаще всего эти люди рады тому факту, что их продуктивность возросла, и стоимость годовой подписки возвращается всего за несколько недель использования платной версии IDEA. Однако пользователи NetBeans и Eclipse также зачастую привязаны к своим инструментам и недоумевают, почему другие программисты готовы платить деньги за IDEA.

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

У Eclipse — самая развернутая экосистема плагинов среди всех IDE, а также наибольшая вероятность «слететь» из-за установки несовместимого набора этих самых плагинов. К сожалению, за время использования Eclipse, я неоднократно должен был удалять очередную поломанную сборку этой IDE и инсталлировать «чистый» бандл.
NetBeans хорошо подходит для большинства разработчиков, у неё отличный профайлер, и я порой его использую. Однако предпочитаю заплатить за IntelliJ IDEA Ultimate. Да и будущее NetBeans пока туманно.

Для начинающих Java-разработчиков, у которых пока нет средств для покупки инструментария, я рекомендую использовать NetBeans или IntelliJ IDEA Community Edition в зависимости от их задач. Первую стоит выбирать тем, кто занимается кодированием серверов Java, но только если вы не попадаете в категорию тех, кто может получить IntelliJ IDEA Ultimate бесплатно или с огромной скидкой (студенты или те программисты, которые разрабатывают проект open source).

«Легкие» Java IDE

Сегодня большинство Java-разработчиков используют IDEA, NetBeans или Eclipse, но порой возникает необходимость в более «легких» средах разработки или даже в редакторах кода наподобие Sublime Text, emacs или vim, которые поддерживают плагины Java.

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

  • DrJava — небольшая бесплатная среда разработки. Её создали для студентов Университета Райса, и она стала довольно популярной: DrJava загрузили уже более 2 млн раз. DrJava призвана развивать разработку, основанную на тестировании (test-driven development). Среда содержит «умный» редактор кода, панель взаимодействия для оценки кода приложения, отладчик уровня источника и инструменты модульного тестирования.
  • BlueJ бесплатная среда разработки на Java, созданная специалистами Кентского университета для начинающих программистов. Эта среда поддерживается Oracle. BlueJ отличается гораздо более лаконичным и простым интерфейсом, чем профессиональные IDE, такие, как NetBeans или Eclipse, и даже содержит специальный учебник по основам ООП.
  • JCreator — ещё одна небольшая Java IDE для Windows, написанная на C++ (из соображений увеличения производительности). Платная версия Pro оснащена отладчиком, поддержкой Ant и code wizards, ну а бесплатная версия (LE) — нет.
  • Eclipse Che — браузерная облачная IDE, поддерживает Java, C++, JavaScript, Python, PHP, Ruby и SQL.

Выбор Java IDE в зависимости от проекта

Я постарался описать важные преимущества каждой из трех самых значительных Java IDE и вскользь упомянул об их полезных маленьких соперниках. Чтобы правильно выбрать IDE нужно взвесить все «за» и «против» и сопоставить их с вашими потребностями и потребностями ваших проектов. Если вы присоединяетесь к команде, будет целесообразно использовать ту же IDE, что и другие разработчики, хотя это и не обязательно.
Если ваша команда размещает исходники на GitHub, естественно, будет удобнее, если ваша IDE поддерживает GitHub. Да, вы можете справиться с передачей кода и без IDE, используя клиент GitHub или командную строку git. Но насколько эффективными будут такие вот прыжки между разными системами?

Также важно, чтобы IDE поддерживала систему сборки. Например, если это Maven, вряд ли вы захотите пересобрать систему в Ant для локального тестирования. К счастью, все три большие Java IDE поддерживают и Ant, и Maven, и Gradle, либо из коробки, либо с плагином. А вот для «маленьких» IDE это может оказаться неверным.

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

Вряд ли такая ситуация хорошо отразится на вашей карме. Откровенно говоря, несоответствие JRE чаще появляется при ошибках в конфигурации, чем при отсутствии поддержки IDE за исключением тех случаев, когда IDE еще не успела обновиться до новой версии Java.

Просто поверьте: если ваша IDE полностью поддерживает фреймфорки и технологии, которые используются в проекте, это действительно помогает ускорить работу. Вы, скорее всего, и так справитесь. Но, если, IDE понимает, каким образом JPA statements относятся к классам сущностей и выражений JPA (как IntelliJ), на связанный с JPA код вы потратите гораздо меньше времени чем в случае тотального непонимания. Ну а если IDE поддерживает фреймворк для тестирования и используемый для проекта исполнитель кода, вы сможете проводить тесты, не меняя рабочую среду. Что тоже ускорит процесс разработки.

Наконец, работа идет быстрее, если IDE совместима с системой отслеживания ошибок и тикет-системой проекта. Снова-таки, вы можете воспользоваться автономным или веб-клиентом, скажем, JIRA, но сложно не согласиться с тем, что проверять тикеты гораздо быстрее не меняя окно, оставаясь непосредственно в IDE.

Бесплатная или платная?

После тестирования именно от IntelliJ IDEA Ultimate у меня возникло ощущение правильной среды разработки. Этакого Кадиллака мира IDE. Повторюсь: хоть она и не бесплатна, я считаю, что прирост производительности от её использования стоит годовой подписки.

Для начинающих, которые не могут себе позволить годовую подписку IntelliJ IDEA Ultimate, я рекомендую использовать NetBeans, а не Eclipse. Конечно, экосистема плагинов Eclipse сегодня развита куда больше, чем у любой другой IDE, однако она очень заросшая и неухоженная: начинающий разработчик рискует увязнуть в дебрях IDE вместо погружения в работу.

Я также коснулся «облегченных» альтернатив, две из которых были разработаны специально для учебных целей. Что ж, если вы только-только начинаете изучать языки и вам предпочтительнее минималистичная среда — почему бы и нет?
  • ,

IntelliJ IDEA не вполне подружилась с новой macOS Sierra

IntellJ IDEA Mac OS Sierra
На самом деле, всё не так плохо, как в заголовке. IntelliJ IDEA, как и положено добропорядочной IDE, работает в недавно представленной операционной системе для компьютеров Apple. Однако некоторые разработчики, которые уже успели перейти на Sierra, отмечают досадное недоразумение: стоит им даже легонько провести по трекпаду, как IDE мгновенно перемещает страничку с кодом на много позиций вниз. Сами понимаете, работать при такой вот особенности не слишком удобно.

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

Разработчики из JetBrains уже отреагировали на новость в официальном твиттере IntelliJ IDEA, отметив, что подпиливание приложения для macOS Sierra всё ещё продолжается, посему, придется немного подождать.
  • ,

Алгоритмы машинного обучения улучшат автодополнение кода в IntelliJ IDEA

IntelliJ IDEA алгоритмы машинного обучения
Большинство студентов JavaRush знают IDE IntelliJ IDEA и пользуются ею. Мы не зря рекомендуем именно эту среду разработки: она постоянно развивается, знает, как помочь новичкам и становится всё интереснее. Так, в сентябре на сайте компании появилась информация о новом плагине Completion Stats Collector, который использует машинное обучение для усовершенствования автодополнения кода. Если вы уже работали с этой IDE, то замечали, что при вводе команды часто всплывают подсказки-предположения о том, какое продолжение может быть у вводимой вами строки в зависимости от контекста. Это и есть автодополнение (или, по-английски, Code completition).

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

Естественно, Completion Stats Collector будет «отъедать» какую-то часть трафика, но разработчики обещают, что он не будет превышать 20 Кбайт/ч, что по современным меркам особой погоды не делает.
  • ,

JDK 9 выйдет немного позднее, чем ожидалось?

Java 9
Девятую версию JDK ожидали увидеть уже 23 марта 2017 года. Однако главный архитектор Java Platform Group в составе Oracle Марк Рейнхольд (Mark Reinhold) считает, что релиз нужно отложить на четыре месяца, и представить обновленный кит не раньше июля следующего года. Марк объясняет это теми соображениями, что к настоящему моменту багов в девятой версии JDK гораздо больше, чем в аналогичный срок было в JDK 8, соответственно на их исправление нужно больше времени.

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

Нововведения в JDK 9 приведены ниже:

  • Модуляризация — проект Jigsaw
  • REPL (jshell)
  • HTTP 2.0 клиент
  • Обновление Process API
  • Money API
  • JMH

Ключевым нововведением считается первый пункт в этом списке — Project Jigsaw, система модулей.

Project Jigsaw
Именно для работы над модуляризацией и нужно выделить больше времени, считает Рейнхольд.
  • ,

Java EE 8 появится в 2017 году

Java EE Roadmap
Enterprise-программисты всего мира, а особенно их менеджеры, напряженно ждали новостей от Oracle: они хотели знать, что ждет их главный рабочий инструмент — Java EE. В июле завеса тайны была приоткрыта. Объявленные нововведения восьмой версии Java EE, отмечают специалисты, вполне в духе времени и соответствуют потребностям рынка. Так, в реализации Java EE 8 будет уделено внимание удобству работы в облаках, Docker и контейнерам, мультиарендности. Кроме того, обещают улучшение возможностей реактивного программирования, поддержку HTTP/2, а также микросервисов.

Словом, те, кто обвиняли Java EE в анахронизме, оказались неправы. Другое дело, что для реализации всех нововведений понадобится несколько больше времени, чем предполагалось ранее.
В рамках конференции JavaOne 2016, ответственный за Java EE вице-президент Oracle Group Анил Гаур (Anil Gaur) представил вполне конкретный план развития платформы. Если вкратце, до конца 2016 года компания собирает отклики от сообщества, затем в 2017 (тоже, судя по всему, ближе к завершению года) выпускает Java EE 8 с начальной поддержкой микросервисов, а в 2018 — Java EE 9 с расширенной их поддержкой и модульной средой выполнения.

Анил Гаур считает Java EE 8 неким промежуточным мостиком к Java EE 9, вероятно, созданным для того, чтобы не утомлять сообщество слишком долгим ожиданием обновления.
  • ,

Гарвард CS50: задания третьей недели (лекции 7 и 8), часть 2

Лекции Гарвардского курса по основам программирования CS50
Дополнительные материалы: асимптотическая нотация, алгоритмы сортировки и поиска
Задания третьей недели, часть 1. Сортировка и поиск.

Игра начинается!





Настало время поиграть! Большинство людей знакомы с головоломкой «Пятнашки». Если формализовать, «Пятнашки» — это двумерное поле 4х4, в этом поле расположены не 16, а 15 квадратиков, то есть один слот остается пустым. Каждый из квадратиков пронумерован и может двигаться внутри поля по горизонтали или вертикали (если, конечно, есть куда двигаться). Цель — расположить числа по порядку, от 1 до 15 слева направо сверху вниз. Тогда пустое место окажется в правом нижнем углу.

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

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



Теперь перейдите в директорию ~/ рабочей среды, затем — в /pset3/fifteen и откройте файл fifteen.c.

В нем — код «движка» игры. Задание состоит в том, чтобы дописать код игры.

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

Будет удобнее запустить его в большем, чем обычно, окне терминала, которое можно открыть, нажав на зеленый плюс (+) рядом с одной из вкладок кода и выбрав New Terminal. Или же можно открыть терминальное окно на полный экран, кликнув на иконку Maximize в правом верхнем углу консоли.

Вы видите, что кое-что кое-как работает. Но на самом деле большая часть игры ещё не написана. И вот тут — приготовьтесь — ваш выход!

Исследование

Изучите код и комментарии fifteen.c, после чего ответьте на вопросы ниже:

  1. Помимо доски 4х4, какую размерность поля допускает наш движок?
  2. Какой структурой данных является игровое поле?
  3. Какая функция вызывается для приветствия игрока в начале игры?
  4. Какие функции вам необходимо реализовать?
  5. Примечание: если вы хотите, чтобы автопроверка ответила вам, правильно ли вы ответили на вопросы, рядом с файлом fifteen.c найдите файл fifteen.txt и запишите в него ответы на эти вопросы.

Реализация

Что ж, начнем реализовывать игру. Помните, двигаемся крохотными шажками, не пытайтесь сделать всё и сразу. Вместо этого давайте реализовывать функции по очереди и убедитесь, что они работают прежде, чем двигаться вперед. В частности, мы предлагаем вам реализовать функции игры в следующем порядке: init (инициализация), draw (прорисовка), move (сделать шаг), won (выигрыш). Дизайнерские решения (например, сколько пробелов нужно вставлять между нашими плитками-числами) — остаются за вами. Игровое поле должно выглядеть примерно так:

15 14 13 12

11 10  9  8

7  6  5  4

3  1  2  _

Еще раз обращаем внимание, что в стартовой позиции 1 и 2 расположены в обратном порядке (это касается классического поля 4х4 если количество плиток — нечетное). Если количество плиток чётное, а поле — 3х3, менять две «младших» плитки местами не нужно.

8  7  6

5  4  3

2  1  _


Чтобы протестировать вашу реализацию «Пятнашек», нужно попробовать поиграть в них (не забывайте, аварийный выход из программы до её естественного завершения можно вызвать комбинацией клавиш crtl+c). Убедитесь, что программа будет работать, если будут введены неправильные числа. И помните, что точно так же, как вы автоматизировали ввод в find, вы можете автоматизировать «прохождение» игры.
На деле, в папке ~cs50/pset3 есть файлы 3x3.txt и 4x4.txt, где собраны все последовательности шагов для победы на полях размерности 3х3 и 4х4. Чтобы протестировать программу, например, с помощью первого из файлов, выполните следующую команду:

./fifteen 3 < ~cs50/pset3/3x3.txt

Настройте нужный вам аргумент для ускорения анимации. Да и вообще, при желании вы всегда можете изменить игру. Чтобы поразвлекаться с «управляющими последовательностями ANSI», включая цвет. Обратите внимание на нашу реализацию clear и проверьте http://isthe.com/chongo/tech/comp/ansi_escapes.html чтобы усвоить новые трюки.

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

~cs50/pset3/fifteen

Если вам интересно увидеть более крутую реализацию, с автоматическим решением головоломки, посмотрите «Хакерскую» версию программы:

~cs50/hacker3/fifteen

Вместо того, чтобы ввести номер в окошке игры, напечатайте слово GOD. Здорово, не так ли?
Если хотите проверить правильность вашей программы официально с check50, обратите внимание, что check50 предполагает, что пустое пространство игрового поля заполнено 0; если вы выбрали другое значение, для корректной проверки замените его на нуль. Кроме того, check50 предполагает, что вы индексируете поля игрового поля в порядке [ряд] [столбец], а не доска [столбец] [строка].

check50 2015.fall.pset3.fifteen fifteen.c


Подробнее о реализации функций игры Fifteen

  • init (инициализация)
  • draw (прорисовка)
  • move (сделать шаг)
  • won (выигрыш)

init

В этой функции мы представляем игровое поле. Для этого используем двумерный массив целых чисел. Размерность массива — MAX x MAX, где MAX — константа, обозначающая максимальное количество плиток, которые могут поместится в строке или столбце поля.

Таким образом нам нужно определить переменную int board[MAX][MAX]

Однако вспомним, что размерность игрового поля определяет пользователь. Поэтому нужно определить переменную, которая бы обозначала размерность доски, которую должен ввести пользователь. Это int d.

где d — размерность доски, d <= MAX. Однако в Cи вы не можете менять размер массива, поэтому придется довольствоваться максимальной размерностью. В init вам нужно поместить значения на доску.


Почитайте больше о двумерных массивах, если вы с ними ещё не работали. Вкратце, у них два индекса, первый обозначает номер строки, второй — номер столбца. Для нашей задачи мы начинаем с максимального числа и заканчиваем в случае d = 3 («Восьмяшки») единицей и пустым углом. Если у нас все-таки «Пятнашки», тогда 1 и 2 меняем местами. Что же делать с пустым местом? Наш массив состоит из целых чисел, поэтому и пустота должна быть заполнена неким целым. Поэтому вы должны выбрать некое целое число для инициализации пустой плитки (а в случае физической игры, её отсутствие).

Чтобы инициализировать игровое поле и заполнить его стартовым набором плиток, можно использовать циклы.
Ведем циклы по индексам i и j, где board[i][j] — плитка, которая находится в строке номер i и столбце номер j. Заполняем доску в убывающем порядке. В случае, если количество плиток (без пустой) — нечетное, меняем местами 1 и 2.

draw
Эта функция должна напечатать текущее состояние игрового поля. Помним, что у нас могут быть значения с одним или двумя разрядами, поэтому для красивого форматирования после чисел 1-9 функция должна печатать пробел (#s). Это можно организовать с помощью плейсхолдера %2d.

printf (“%2d”, board[i][j]);

Также не забывайте о пустой клетке. Выберите символ, который будет её представлять (в нашем примере — это нижнее подчеркивание). Функция draw должна отрисовывать этот символ, как только вы попадаете на пустую клетку. Итак, наш цикл будет примерно таким:

for каждой строки 
for каждого элемента строки 
print значение и пробел 
print новую строку

Запомните, что порядок, в котором функция draw выводит на экран плитки, должен отображать порядок, в котором они находятся в массиве, определенном в функции init.
move
Как только вы инициализировали игровое поле и нарисовали начальные позиции плиток, нужно позволить пользователю редактировать положение плиток, то есть, совершать движения.

Итак, в Fifteen.c программа принимает вывод от пользователя, строит игровое поле и затем вызывает функцию move, и говорит, какую плитку он хочет подвинуть. Будьте внимательны: вы применяете функцию именно к номеру на плитке, а не к её положению на доске (в массиве). Таким образом, вам нужно найти актуальное положение плитки. Кроме того, вы должны позволить пользователю подвинуть плитку только тогда, когда это возможно.



На картинке выше мы можем подвинуть только плитки номер 2, 5 и 8. Как это определить? По значению пустой плитки. Таким образом, функция move работает примерно так:

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

won
Эта функция проверяет, завершилась ли игра после каждого шага пользователя. Она возвращает true, если плитки стоят в правильном порядке (в том числе и положение пустой плитки в правом нижнем углу). В таком случае программу можно завершить. Если же плитки всё еще разбросаны, функция возвращает false и передает бразды правления функции move.

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

Как подтвердить правильность кода и получить оценки


Внимание! Если вам важно проверить только правильность задач, после того, воспользуйтесь cs50check. Если же вы ходите получить оценки на платформе edx, проделайте процедуру, описанную ниже. Имейте в виду, эта процедура для проверки задач использует ту же cs50check. Разница только в том, что она запоминает результаты и подсчитывает общую оценку.

  1. Залогиньтесь в CS50 IDE
  2. Рядом с левым верхним углом CS50 IDE, там, где расположен её файловый браузер (не в терминальном окне), кликните правой клавишей мыши по вашей директории pset3 и нажмите Download. Вы должны увидеть, что браузер загрузил архив pset3.tar.gz.
  3. В отдельном окне или вкладке залогиньтесь в CS50 Submit
  4. Кликните по иконке Submit в левом верхнем углу экрана
  5. В списке папок слева кликните по директории Problem Set 3, затем нажмите на кнопку Upload New Submission. Она находится справа.
  6. На появившемся экране кликните по кнопке Add files…. Откроется окно выбора файлов с вашего компьютера.
  7. Перейдите к той папке, где вы сохранили pset3.tar.gz. Скорее всего, он находится в папке Downloads(«Загрузки») или там, куда ваш браузер складывает файлы по умолчанию. Когда найдете pset3.tar.gz, кликните по нему один раз чтобы выбрать, затем кликните Open («Открыть»).
  8. Нажмите Start upload. Ваши файлы будут загружены на серверы CS50.
  9. На появившемся экране вы должны увидеть окно No File Selected. Если вы переведете курсор мыши влево, вы увидите список загрузившихся файлов. Для подтверждения кликните по каждому из них. Если вы в чём-то не уверены, вы можете перезагрузить файлы, повторив те ж шаги. Вы это можете делать сколько угодно раз до конца 2016 года.
  • ,

Гарвард CS50: задания третьей недели (лекции 7 и 8), часть 1

Лекции Гарвардского курса по основам программирования CS50
Дополнительные материалы: асимптотическая нотация, алгоритмы сортировки и поиска
Часть вторая. «Пятнашки» на Си

Подготовка


Прежде, чем браться за задачи, посмотрите лекции 7-8, прочитайте и вникните в «Дополнительные материалы третьей недели». Они посвящены алгоритмам поиска (линейному и бинарному), сортировки (много их!), а также работе дебаггера (умение работать с дебаггером для отладки программ — чрезвычайно важный навык!).

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

  • Почему бинарный поиск требует отсортированного массива?
  • Почему оценка сортировки пузырьком равна O (n2)?
  • Почему оценка сортировки вставками — это Ω (n)?
  • Как работает сортировка выбором? Опишите в трех предложениях (или меньше).
  • Каков верхний предел (наихудший случай) времени работы сортировки слиянием?
  • Дебаггер GDB позволяет отладить программу. А если сформулировать конкретнее, что именно он позволяет делать?

Цели


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

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

Начинаем

Напомним, для решения практических задач на первой и второй неделе, вы писали программы с нуля и создали собственные каталоги pset1 и pset2 с помощью команды mkdir. Для практического задания третьей недели, нужно загрузить дистрибутив (или «дистро», мы так его называем), написанный нами, и добавить туда собственные строки кода. Сначала вчитайтесь в наш код и постарайтесь его понять. Важнейший навык этой недели — научиться читать чужой код.

Итак, залогиньтесь на cs50.io и выполните команду

update50

в терминальном окне, чтобы убедиться в актуальности версии рабочего пространства. Если вы случайно закрыли терминальное окно и не можете его найти, зайдите в меню View и убедитесь, что напротив пункта Console стоит галочка (поставьте её, если это не так). Кликните на(+), внутри зеленого круга на рамке терминального окна, выберите New Terminal.



После этого выполните команду

cd ~/workspace

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

wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip

чтобы загрузить ZIP-архив задачника в ваше рабочее пространство (wget — команда linux для загрузки). Если всё ок, в строке вы увидите такую фразу:

'pset3.zip' saved

Убедитесь, что вы действительно скачали pset3.zip выполнив команду:

ls

а затем запустите

unzip pset3.zip

чтобы разархивировать файл. Если теперь вы еще раз запустите команду ls, вы также увидите директорию pset3. Перейдите в неё, выполнив команду

cd pset3

а затем снова запросите просмотр содержимого директории:

ls

вы увидите, что в этой директории есть две поддиректории:

fifteen  find

Уже интригует!

Поиск

Давайте теперь нырнем в одну из этих поддиректорий. Для этого выполним команду:

cd ~/workspace/pset3/find

Если вы выведете содержимое этой папки на экран (вы уже, наверное, помните, как это делать), вот что вы должны увидеть:

helpers.c  helpers.h  Makefile  find.c  generate.c

Ух ты, файлов хватает. Но не беспокойтесь, сейчас мы с ними разберёмся.
В файле generate.c размещён код программы, которая использует «генератор псевдослучайных чисел» (генерация посредством функции drand48) чтобы сгенерировать большое количество случайных (по правде говоря, псевдослучайных, компьютеры не могут работать с чистой случайностью!) чисел, и разместить их по одному в строке. Скомпилируйте программу:

make generate

Теперь запустите её, выполнив команду:

./generate

Программа выдаст вам следующее сообщение:

Usage: generate n [s]

Это значит, что программа ожидает один или два аргумента командной строки. Использование первого, n, обязательно; это число означает, сколько псевдослучайных чисел вы хотите создать. Параметр s не является обязательным, на что указывают квадратные скобки. Число s можно назвать «семенами» для генератора псевдослучайных чисел. Под «семенами» подразумеваем входные данные в генератор псевдослучайных чисел, которые влияют на его вывод.

Например, если вы используете drand48, сначала вызвав srand48 (еще одна функция, цель которой заключается в „посеве“ drand48) с аргументом, скажем, 1, а затем вызовете drand48 три раза, drand48 может вернуть 2728, потом 29785, потом 54710.

Tсли вы вместо предыдущего, используя drand48, сначала вызовете srand48 с аргументом, скажем, 2, а затем снова используете drand48 три раза, drand48 может вернуть 59797, потом 10425, потом 37569. Но если вы повторно «посеете» drand48, вызывая srand48 снова с аргументом 1, в результате следующих трех вызовов drand48 вы снова получите 2728, потом 29785, потом 54710!

Видите, все происходит совсем не случайно.
Запустите программу еще раз, на этот раз, скажем, n = 10, как показано ниже; вы увидите список из 10 псевдослучайных чисел.

./generate 10

Давайте запустим программу в третий раз с тем же значением n; вы должны увидеть другой список из 10 цифр. Теперь попробуйте запустить программу с двумя параметрами. Давайте возьмем s = 0, как показано ниже.

./generate 10 0

Теперь запустите ту же команду еще раз:

./generate 10 0

Можно даже не спорить: вы снова увидели ту же самую «случайную» последовательность из десяти цифр. Вот что произойдет, если вы не будете менять «семена» генератора псевдослучайных чисел.

Теперь посмотрим на саму программу generate.c (помните, как?).
Комментарии в начале этого файла объясняют общую функциональность программы. А вот сам код мы, похоже, забыли прокомментировать. Внимательно вчитайтесь в код, и читайте его до тех пор, пока не уловите смысл каждой строки. После этого прокомментируйте этот код вместо нас, заменяя каждый TODO фразой, описывающей цель или функциональность соответствующей строки или строк кода. (примечание: unsigned int — это «беззнаковый» int, то есть он не может быть отрицательным). Чтобы получить более подробную информацию о rand или srand, выполните:

man drand48

или

man srand48

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

make generate

Если generate больше не компилится, чините, что сломали:)!

Напомним: команда make автоматизирует компиляцию кода, поэтому вам не придется выполнять команду clang вручную подставляя кучу переключателей. Но на самом деле make просто упрощает нам ввод, а на деле за ним спрятан тот же clang с нужными нам параметрами. Однако когда ваши программы станут больше по размеру, make не сможет больше выяснить из контекста, как компилировать код. В таком случае вам придется указать make, как нужно скомпилировать программы, особенно если они связаны с использованием различных исходных файлов (например, .c). Для решения этой проблемы мы будем использовать файлы конфигурации (Makefiles), которые точно указывают make, что нужно делать.

Как команда make узнала, как нам следует компилировать generate? На самом деле команда использовала конфигурационный файл, который мы уже написали. Этот файл называется Makefile и он лежит в той же директории, что и generate.c. Makefile — некий список правил, указывающих, как создать файл generate из generate.c. В файле вы найдете, в частности соответствующие строки:

generate: generate.c
    clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c

Первая строка говорит make, что „цель“ под названием generate должна быть создана путем вызова команды из второй строки. Более того, первая строка указывает make, что generate зависит от generate.c, смысл которого в том, что make будет только пересобирать generate в ходе последующих запусков, если этот файл был изменен. Неплохой трюк для экономии времени, не так ли? На самом деле, выполните команду ниже снова, если вы не меняли generate.c.

make generate

Вам сообщат, что generate уже обновлен до текущей версии.

Замечание: отступление в начале второй строки не является последовательностью пробелов, это, скорее, знак табуляции. К сожалению, make требует, чтобы командам предшествовали знаки табуляции, так что будьте осторожны, чтобы не изменить их на пробелы, иначе вы столкнетесь с непонятными ошибками! Флаг -Werror говорит команде clang считать предупреждения (плохо) ошибками (еще хуже), так что вы будете вынуждены (в хорошем, обучающем смысле!) исправить их.

Теперь посмотрим на файл find.c. Обратите внимание, эта программа ожидает один аргумент командной строки: „иглу“, которую нужно найти в «стоге сена» значений. После этого, просмотрите код и скомпилируйте программу, выполнив команду ниже.

make find

make практически вывел для нас следующее:

clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

Обратите внимание! Только что вы скомпиллировали приложение, состоящее е из одного, а из двух файлов: helpers.c и find.c. Каким образом об этом узнала make? Чтобы понять это, снова откройте файл Makefile, чтобы понять, что там на самом деле творится. Соответствующие строки ниже.

find: find.c helpers.c helpers.h
clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

Под зависимостью (после двоеточия) можно понимать то, что все изменения в файлы find.c, helpers.c, или helpers.h вынудят make пересобирать find следующий раз, когда она будет вызвана для этих целей.
Теперь запустите эту программу, выполнив, например, следующее:

./find 13

После этого вам поступит предложение предоставить некий стог (то есть целые числа), и подавать их по одной соломинке за раз. Как только вы устанете от ввода чисел, нажмите комбинацию клавиш Ctrl-D. Эта комбинация пошлет программе символ конца файла (EOF, end-of-file). Символ вынудит функцию GetInt из библиотеки CS50 вернуть константу INT_MAX, а она, в свою очередь в find.c заставит find прекратить набирать «стог».
Теперь программа будет искать иглу в том стоге сена, что вы предоставили, и в конечном счете она сообщит, была ли она найдена. Говоря кратко, программа выполняет поиск некоторого значения в массиве. По крайней мере, она должна, но загвоздка в том, что пока что она ничего не найдет! Но тут на помощь приходите вы! О важности вашей роли поговорим чуть позднее.

На самом деле процесс предоставления стога можно автоматизировать хотя бы по „слиянию“ вывода generate в find в качестве входных данных. Например, команда ниже передает 1000 псевдослучайных чисел в find, которая затем ищет среди этих значений 42.

./generate 1000 | ./find 42

Обратите внимание: когда generate передает исходные данные в find, вы не видите числа generate, но вы увидите работу find.

В качестве альтернативы, вы можете „перенаправить“ вывод generate в файл с помощью такой команды:

./generate 1000 > numbers.txt

Содержимое этого файла можно перенаправить на вход find с помощью команды:

./find 42 < numbers.txt

Давайте еще разок посмотрим на код в Makefile и обратим внимание на следующую строку:

all: find generate

Это означает, что вы можете собрать generate и find, выполнив следующую команду:

make all

Более того, команда под этой строкой эквивалентна команде над ней, поскольку make строит первую запись в Makefile по умолчанию.

make

Если бы вы только могли свести все эти практические задания к одной команде! Но — увы!
Наконец, обратите внимание на эти последние строки в Makefile:

clean:
    rm -f *.o a.out core find generate

Эта запись позволяет вам удалить все файлы, которые заканчиваются на .o или называются core (это мы поясним чуть позднее!), а также запустить программы find или generate просто выполнив строку:

make clean

Если захотите экспериментировать, то вот с чем будьте осторожны: не добавляйте, скажем, *.c в эту последнюю строку Makefile! (почему?) Все строки, которые начинаются со знака # — это просто комментарии.

Задание 1: Search


Пришло время для кое-чего интересного! Обратите внимание, find.c вызывает search, функцию, объявленную в helpers.h. К сожалению, мы забыли реализовать эту функцию полностью в helpers.c! (Надо отметить, что мы могли бы поместить содержимое helpers.h и helpers.c в один find.c. Но иногда лучше разделять программы на несколько файлов. Особенно если некоторые функции, точнее функции-утилиты, могут оказаться полезными и для других программ. Как, например, функции из библиотеки CS50.

Взгляните на helpers.c и вы увидите, что search всегда возвращает значение false, независимо от того, занесено ли данное значение value в values. Перепишите search таким образом, чтобы она использовала линейный поиск, возвращая true, если value входит в values и false, если value не входит в values. Позаботьтесь о том, чтобы вернуть false сразу, если n не является положительным.
Когда вы будете готовы к проверке правильности, попробуйте вызвать следующую команду:

./generate 1000 50 | ./find 127

Поскольку одно из чисел, выведенных с помощью generate, когда «засеивали» 50, равно 127, ваш код должен найти „иголку“! Для контраста попробуйте выполнить и такую команду:

./generate 1000 50 | ./find 128

Поскольку 128 не входит во множество чисел, выведенных функцией generate, когда «засеивали» 50, ваш код не должен найти «иглу». Проведите и другие тесты, запуская generate с каким-то семенем, анализируя выходные данные, и ища «иголку», которая должна быть в «стогу».

Обратите внимание, что main в find.c написана таким образом, что find возвращает 0, если «игла» найдена, иначе — возвращает 1. Вы можете проверить так называемый „выходной код“, который main возвращает при выполнении

echo $?

После запуска некоторых других команд. Например, если ваша реализация search — правильна, если вы запустите

./generate 1000 50 | ./find 127
echo $?

Вы увидите 0, пока 127 есть среди тех 1000 чисел, выведенных с помощью generate с семенем 50, поэтому написанный вами поиск search должен возвратить true. В этом случае main (написанный нами) должен вернуть 0 (то есть завершить работу). Если же вы зададите следующие входные данные

./generate 1000 50 | ./find 128
echo $?

Вы увидите 1, поскольку 128 не находится среди тех 1000 чисел, которые были выведены с помощью generate с семенем 50. В этом случае search (написанный вами) вернет false, и main (написанный нами) вернет 1 (и с тем закончит работу). Сечёте логику?

Когда всё будет готово для проверки с помощью check50, выполните такую команду:

check50 2015.fall.pset3.find helpers.c

Кстати, не стоит привыкать тестировать код с помощью check50 перед собственным тестированием. Всё-таки check50 не в реальности не существует, поэтому запуск кода с вашими собственными входными выборками, сравнение фактического вывода к ожидаемым выходных данных, — лучшая привычка, которую можно обрести на этом этапе. Правда-правда, не приобретайте вредную зависимость!

Если вам интересно поиграть с реализацией find, выполненной ассистентами cs50, выполните такую команду:

~cs50/pset3/find

Сортировка


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

Обратите внимание: find.c вызывает sort, функцию, объявленную в helpers.h. К сожалению, мы «забыли» реализовать эту функцию в полной мере в helpers.c! Загляните в helpers.c, и вы увидите, что происходит мгновенное возвращение sort, хотя функция main из find действительно передает ей фактический массив.
Теперь вспомните синтаксис объявления массива. Вы не только указываете тип элементов этого массива, но также задаете его размер в квадратных скобках. Так мы делаем для haystack в find.c:

int haystack [MAX];

Но при прохождении массива вы только указываете его имя. И мы это делаем точно так же, когда проходим haystack, чтобы выполнить sort в find.c:

sort (haystack, size);

(Догадайтесь, почему мы передаем размер этого массива отдельно?)
Когда мы объявляем функцию, которая принимает в качестве аргумента одномерный массив, не нужно указывать размер массива. Точно так же мы этого не делали, когда объявляли sort в helpers.h (и helpers.c):

void sort (int values [] int n);

Реализуйте sort, так чтобы функция действительно отсортировывала массив чисел от меньших к большим. Нужно, чтобы время ее работы было равно O (n2), где n — размер массива. Скорее всего, вы захотите реализовать метод пузырьковой сортировки, сортировка выбором, или вставкой, поскольку мы изучили их на третьей неделе. Тем не менее, важно отметить: „правильного“ способа реализации не существует для этих алгоритмов. Есть огромное количество вариаций. На самом деле, вы всегда можете улучшить их, если считаете нужным, до тех пор, пока ваша реализация сойдется к O (n2). Тем не менее, эксперименты оставьте для тела функции, а с целью упрощения проверки, не меняйте нашу декларацию sort. Она должна выглядеть так:

void sort (int values [] int n);

Поскольку функция возвращает значение типа void, она не должна возвращать отсортированный массив. Вместо этого, она должна „деструктивно“ сортировать фактический массив, по которому она «пробегает», перемещая его элементы. На четвертой неделе мы будем обсуждать, что массивы передаются не по значению, а по ссылке. То есть, sort не получит копии массива, а сам исходный массив.

Хотя вы не можете изменить нашу декларацию sort, вы всегда можете определить свою собственную функцию в helpers.c, которые затем можно будет вызвать из sort.

Выберите сами, как лучше протестировать реализацию вашей sort. Не стоит забывать, что printf и GDB вам помогут! И не забывайте, что вы можете создать ту же последовательность псевдослучайных чисел снова и снова, явно указывая значения семян для generate.

Бинарный поиск, советы


Первое, что необходимо понимать о функции find — у нас уже есть написанный код (дистрибутив). Мы просто заполняем некие пробелы в уже существующем коде.

Программа find.c запрашивает ввод чисел (то есть, заполнить «стог»), а потом ищет в нем «иголку» по запросу пользователя, используя для этого sort и search — функции, определенные в helpers.c. Таким образом, find уже написана, нам нужно написать helpers.

Итак, вот что нам нужно сделать:

  1. Реализовать search. Эта функция должна возвращать true, если значение найдено в «стогу» и false, если его там нет.
  2. Реализовать sort, функцию, сортирующую массив значений.

Изначально поиск реализован как линейный. Но вы можете сделать лучше. Алгоритм линейного поиска выполняется за время О(n). Ваша задача — написать алгоритм бинарного поиска. Время его исполнения — O(log n). Однако его проблема в том, что ему на вход нужно подавать отсортированные данные, иначе он не будет работать. Вы помните пример с разорванной книгой, и, вероятно, знаете, почему так.

Если вы прошлись бинарным поиском по элементам и их больше не осталось (то есть в этом «стоге» нашей «иголки» попросту нет), нужно, чтобы функция вернула false.

Бинарный поиск можно реализовать итеративно или рекурсивно (о рекурсии Дэвид Малан рассказал в восьмой лекции).
  • ,

Дополнительные материалы CS50 (Week 3, лекции 7 и 8): асимптотическая нотация, алгоритмы сортировки и поиска

Лекции Гарвардского курса по основам программирования CS50
Задания CS50, week 3, часть 1
Задания CS50, week 3, часть 2

Асимптотическая нотация


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

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

Пусть f(x) и g(x) — функции, определенные в некой окрестности x0, причем g там не обращается в 0.
Тогда f является «O» большим от g при (x -> x0), если существует константа C>0, что для всех x из некоторой окрестности точки x0 имеет место неравенство

|f(x)| <= C |g(x)|

Чуть менее строго:
f является «O» большим от g, если существует константа C>0, что для всех x > x0

f(x) <= C*g(x)

Не бойтесь формального определения! По сути, оно определяет асимптотическое возрастание времени работы программы, когда количество ваших данных на входе растет в сторону бесконечности. Например, вы сравниваете сортировку массива из 1000 элементов и 10 элементов и нужно понять, как возрастёт при этом время работы программы. Или нужно подсчитать длину строки символов путем посимвольного прохода и прибавлением 1 за каждый символ:

c - 1 
a - 2
t - 3

Его асимптотическая скорость = О(n), где n — количество букв в слове. Если считать по такому принципу, время, необходимое для подсчета всей строки, пропорционально количеству символов. Подсчет количества символов в строке из 20 символов занимает вдвое больше времени, нежели при подсчете количества символов в десятисимвольной строке.

Представьте, что в переменной length вы сохранили значение, равное количеству символов в строке. Например, length = 1000. Чтобы получить длину строки, нужен только доступ к этой переменной, на саму строку можно даже не смотреть. И как бы мы ни меняли длину, мы всегда можем обратиться к этой переменной. В таком случае асимптотическая скорость = O(1). От изменения входных данных скорость работы в такой задаче не меняется, поиск завершается за постоянное время. В таком случае программа является асимптотически постоянной.

Недостаток: вы тратите память компьютера на хранение дополнительной переменной и дополнительное время для обновления её значения.

Если вам кажется, что линейное время — это плохо, смеем заверить: бывает гораздо хуже. Например, O(n2). Такая запись означает, что с ростом n рост времени, нужного для перебора элементов (или другого действия) будет расти всё резче.
Но при маленьких n алгоритмы с асимптотической скоростью О(n2) могут работать быстрее, чем алгоритмы с асимптотикой О(n).


Но в какой-то момент квадратичная функция обгонит линейную, от этого не уйти.

Еще одна асимптотическая сложность — логарифмическое время или O(log n). С ростом n эта функция возрастает очень медленно. О(log n) — время работы классического алгоритма бинарного поиска в отсортированном массиве (помните разорванный телефонный справочник на лекции?). Массив делится надвое, затем выбирается та половина, в которой находится элемент и так, каждый раз уменьшая область поиска вдвое, мы ищем элемент.



Что будет, если мы сразу наткнемся на искомое, разделив в первый раз наш массив данных пополам? Для лучшего времени есть термин — Омега-большое или Ω(n).

В случае бинарного поиска = Ω(1) (находит за постоянное время независимо от размера массива).

Линейный поиск работает за время O(n) и Ω(1), если искомый элемент — самый первый.
Еще один символ — тета (Θ(n)). Он используется, когда лучший и худший варианты одинаковы. Это подходит для примера, где мы хранили длину строки в отдельной переменной, поэтому при любой её длине достаточно обратиться к этой переменной. Для этого алгоритма лучший и худший варианты равны соответственно Ω(1) и O(1). Значит, алгоритм работает за время Θ(1).

Линейный поиск


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

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

Линейный поиск — способ последовательного поиска, один за одним. Когда вы пересматриваете результаты поиска в Google сверху вниз, вы используете линейный поиск.

Пример. пусть у нас есть список чисел:

2 4 0 5 3 7 8 1

И нам нужно найти 0. Мы его видим сразу, но компьютерная программа так не работает. Она начинает с начала списка и видит число 2. Затем проверяет, 2=0? Это не так, поэтому она продолжает работу и переходит ко второму символу. Там её тоже ждет неудача, и только на третьей позиции алгоритм находит нужное число.

Псевдокод линейного поиска:



Функция linearSearch получает на вход два аргумента — ключ key и массив array[].Ключ — искомое значение, в предыдущем примере key = 0. Массив — список чисел, которые мы будем просматривать. Если мы ничего не нашли, функция вернет -1 (позицию, которой в массиве нет). Если же линейный поиск найдет нужный элемент, то функция вернет позицию, на которой находится искомый элемент в массиве.
В линейном поиске хорошо то, что он будет работать для любого массива, независимо от порядка элементов: мы всё равно пройдём по всему массиву. Это же является и его слабостью.

Если вам нужно найти число 198 в массиве из 200 чисел, отсортированных по порядку, цикл for пройдет 198 шагов.



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

Бинарный поиск и деревья


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



Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть.



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


Давайте найдем число 144. Делим список пополам, и попадаем на число 13. Оцениваем, больше или меньше искомое число, чем 13.



13 < 144, так что мы можем игнорировать всё, что находится левее 13 и само это число. Теперь наш список поиска выглядит так:



Тут чётное число элементов, поэтому выбираем принцип, по которому выбираем «среднее» (ближе к началу или концу). Допустим, мы избрали стратегию близости к началу. В таком случае, наша «середина» = 55.



55 < 144. Мы снова отбрасываем левую половину списка. К счастью для нас, следующее среднее число и будет 144.



Мы нашли 144 в массиве из 13 элементов с помощью бинарного поиска всего за три шага. Линейный поиск в такой же ситуации справился бы аж за 12 шагов. Поскольку этот алгоритм на каждом шаге уменьшает количество элементов в массиве вдвое, он найдет искомое за асимптотическое время О(log n), где n – количество элементов в списке. То есть, в нашем случае асимптотическое время = O(log 13) (это чуть больше трёх).

Псевдокод функции бинарного поиска:



Функция принимает на вход 4 аргумента: искомое key, массив данных array [], в котором находится искомое, min и max — указатели на максимальное и минимальное число в массиве, на которое мы смотрим на данном шаге алгоритма.

Для нашего примера изначально дана такая картинка:



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



Если это так, то key также больше, чем любое из чисел левее середины, и мы можем вызвать бинарную функцию снова, только теперь наш min = midpoint + 1. Если окажется, что key < midpoint, мы можем отбросить само это число и все числа, лежащие справа от него. И мы вызываем бинарный поиск по массиву от числа min и вплоть до значения (midpoint – 1).



Наконец, третья ветка: если значение в midpoint не больше и не меньше, чем key, ему ничего не остается, как быть искомым числом. Его мы и возвращаем в таком случае и заканчиваем работу программы.



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



И возвращаем (-1), чтобы указать, что мы ничего не нашли.

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

  1. Отсортировать список и применить бинарный поиск
  2. Сохранять список всегда отсортированным при одновременном добавлении и убирании из него элементов.

Один из способов хранения списков отсортированными считается бинарное дерево поиска. Бинарное (двоичное) дерево поиска — это структура данных, которая отвечает следующим требованиям:

  • Оно является деревом (структурой данных, эмулирующей древовидную структуру — имеет корень и другие узлы (листья), связанные «ветками» или ребрами без циклов)
  • Каждый узел имеет 0, 1 или 2 потомка
  • Оба поддерева — левое и правое — являются двоичными деревьями поиска.
  • У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
  • У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равно, нежели значение ключа данных самого узла X.



Внимание: корень «программистского» дерева, в отличие от реального, находится сверху. Каждая ячейка называется вершиной, вершины соединены ребрами. Корень дерева — ячейка с номером 13. Левое поддерево вершины 3 выделено цветом на картинке снизу:



Наше дерево соответствует всем требованиям к бинарным деревьям. Это значит, что каждое его левое поддерево содержит только значения, которые меньше или равны значению вершины, правое — только значения большие или равные значению вершины. Оба левые и правые поддеревья сами являются бинарными поддеревьями.

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



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



Если нужно найти максимальное число — идем от вершины вниз и вправо. Нахождение числа, которое не является минимальным или максимальным также весьма простое. Мы спускаемся от корня влево или вправо в зависимости от того, больше или меньше наша вершина искомой. Так, если нам нужно найти число 89 мы проходим вот такой путь:



Еще можно выводить числа в порядке сортировки. Например, если нам нужно вывести все числа в порядке возрастания, берем левое поддерево и начиная с самой левой вершины идем наверх.
Прибавить что-то в дерево тоже просто. Главное помнить о структуре. Скажем, нам нужно добавить в дерево значение 7. Идем к корню, и проверяем. Число 7 < 13, поэтому идем влево. Там видим 5, и идем вправо, поскольку 7 > 5. Дальше поскольку 7 > 8 и 8 не имеет потомков, мы конструируем ветку от 8 влево и на неё цепляем 7.





Также можно удалять вершины из дерева, но это несколько сложнее.
Есть три разных сценария для удаления, которые мы должны учесть.

  1. Самый простой вариант: нам нужно удалить вершину, у которой нет потомков. Например, число 7, которое мы только что добавили. В таком случае мы просто проходим путь до вершины с этим числом и удаляем его.
  2. У вершины есть одна вершина-потомок. В таком случае можно удалить нужную вершину, но её потомка нужно подсоединить к «дедушке», то есть вершине, из которой произрастал её непосредственный предок. Например, из того же дерева нужно удалить число 3. В таком случае, её потомка, единицу, вместе со всем поддеревом присоединяем к 5. Это делается просто, поскольку все вершины, слева от 5, будут меньше чем это число (и меньше, чем удалённая тройка).



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

    Давайте из нашего дерева удалим корневую вершину 13. Сначала ищем самое близкое к 13 число, которое его больше. Это 21. Меняем 21 и 13 местами и удаляем 13.






Есть разные способы строить бинарные деревья, одни хорошие, другие — не очень. Что будет, если мы попробуем построить бинарное дерево из отсортированного списка?



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



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

Алгоритмы сортировки



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

Сортировка выбором




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

  1. Находим минимальное неотсортированное значение.
  2. Меняем местами это значение с первым неотсортированным значением, ставя его таким образом в конец отсортированного массива.
  3. Если остались неотсортированные значения, возвращаемся к шагу 1.

На первом шаге все значения являются неотсортированными. Назовем неотсортированную часть — Unsorted, а отсортированную — Sorted (это просто английские слова, и делаем мы это только потому, что Sorted — гораздо короче, чем «Отсортированная часть» и будет лучше смотреться на картинках).



Находим минимальное число в неотсортированной части массива (то есть, на этом шаге — во всем массиве). Это число 2. Теперь меняем его с первым среди неотсортированных и ставим его в конец отсортированного массива(на этом шаге — на первое место). На этом шаге это первое число в массиве, то есть 3.



Шаг второй. На число 2 мы не смотрим, оно уже в отсортированном подмассиве. Начинаем искать минимальное, начиная со второго элемента, это 5. Убеждаемся, что 3 — минимальное среди неотсортированных, 5 — первое среди неотсортированных. Меняем их местами и прибавляем 3 к отсортированному подмассиву.



На третьем шаге мы видим, что в неотсортированном подмассиве самое маленькое число — 4. Меняем его с первым числом среди неотсортированных — 5.



На четвертом шаге мы обнаруживаем, что в неотсортированном массиве минимальное число — 5. Меняем его с 6 и прибавляем к отсортированному подмассиву.



Когда среди неотсортированных остается только одно число (наибольшее), это значит, что весь массив отсортирован!



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



В обоих, самом лучшем и самом худшем случаях, чтобы найти минимальный неотсортированный элемент, мы должны сравнить каждый элемент с каждым элементом неотсортированного массива, и делать это мы будем на каждой итерации. Но нам нужно просматривать не весь список, а только неотсортированную часть. Меняет ли это скорость алгоритма? На первом шаге для массива из 5 элементов мы делаем 4 сравнения, на втором — 3, на третьем — 2. Чтобы получить количество сравнений, нам нужно сложить все эти числа. Мы получаем сумму

формула

Таким образом, ожидаемая скорость алгоритма в лучшем и худшем случае — Θ(n2).

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

Пузырьковая сортировка

Алгоритм у пузырьковой сортировки — один из простейших.

Идем вдоль всего массива и сравниваем 2 соседних элемента. Если они в неправильном порядке, меняем их местами. При первом проходе в конце окажется («всплывет») самый маленький элемент (если мы сортируем в порядке убывания).

Повторять первый шаг, если хотя бы один обмен на предыдущем шаге был совершен.

Давайте отсортируем массив.



Шаг 1: идем по массиву. Алгоритм начинает работу с первых двух элементов, 8 и 6 и проверяет, находятся ли они в правильном порядке. 8 > 6, поэтому меняем их местами. Далее мы смотрим на второй и третий элементы, теперь это 8 и 4. Из тех же соображений меняем их местами. В третий раз сравниваем 8 и 2. Итого, мы делаем три обмена (8, 6), (8, 4), (8, 2). Значение 8 «всплыло» в конец списка на правильную позицию.



Шаг 2: меняем местами (6,4) и (6,2). 6 теперь на предпоследней позиции, и её можно не сравнивать с уже отсортированным «хвостом» списка.



Шаг 3: меняем местами 4 и 2. Четверка «всплывает» на свое законное место.



Шаг 4: проходимся по массиву, но менять нам уже нечего. Это сигнализирует о том, что массив полностью отсортирован.



А это — код алгоритма. Попробуйте реализовать его на Си!



Пузырьковая сортировка проходит за время O(n2) в худшем случае (все числа стоят неправильно), поскольку нам нужно сделать n шагов на каждой итерации, которых тоже n. На самом деле, как и в случае с алгоритма сортировки выбором, время будет несколько меньше (n2/2 – n/2), но этим можно пренебречь.
В лучшем случае (если все элементы уже стоят на своем месте), мы справимся за n шагов, т.е. Ω(n), поскольку нам нужно будет просто пробежаться по массиву один раз и убедиться, что все элементы стоят на своих местах (т.е. даже n-1 элементов).

Сортировка вставками


Основная идея этого алгоритма — разделение нашего массива на две части, отсортированную и неотсортированную. На каждом шаге алгоритма число переходит от неотсортированной к отсортированной части.



Давайте на примере ниже разберем, как работает сортировка вставкой. До того, как мы начали, все элементы считаются неотсортированными.



Шаг 1. Возьмем первое неотсортированное значение (3) и вставим его в отсортированный подмассив. На этом шаге весь отсортированный подмассив, его начало и конец и будут этой самой тройкой.



Шаг 2. Поскольку 3 > 5, мы вставим 5 в отсортированный подмассив справа от 3.



Шаг 3. Теперь работаем над вставкой числа 2 в наш отсортированный массив. Сравниваем 2 со значениями справа налево, чтобы найти правильную позицию. Поскольку 2 < 5 и 2 < 3 и мы дошли до начала отсортированного подмассива. Следовательно, мы должны вставить 2 слева от 3. Для этого подвигаем 3 и 5 вправо, чтобы появилось место для двойки и вставляем её в начало массива.



Шаг 4. Нам повезло: 6 > 5, поэтому мы можем вставить это число сразу за числом 5.


Шаг 5. 4 < 6 и 4 < 5, но 4 > 3. Следовательно, мы знаем, что 4 нужно вставить справа от 3.
Снова, мы вынуждены подвинуть 5 и 6 вправо, чтобы создать лакуну для 4.


Готово!

Обобщенный алгоритм:

Берем каждый неотсортированный элемент n и сравниваем его со значениями в отсортированном подмассиве справа налево, пока не определим подходящую позицию для n (то есть, в тот момент, когда находим первое число, которое меньше, чем n). Затем сдвигаем все отсортированные элементы, которые находятся справа от этого числа вправо, чтобы образовалось место для нашего n, м вставляем его туда, тем самым расширяя отсортированную часть массива.
Для каждого неотсортированного элемента n нужно:
  1. Определить место в отсортированной части массива, куда нужно вставить n
  2. Сдвинуть отсортированные элементы вправо, чтобы сделать лакуну для n
  3. Вставить n в образовавшуюся лакуну в отсортированной части массива.

А вот и код! Рекомендуем написать свою версию программы сортировки.



Асимптотическая скорость алгоритма

В самом плохом случае мы сделаем одно сравнение со вторым элементом, два сравнения с третьим и так далее. Таким образом наша скорость равна O(n2).
В лучшем случае мы будем работать с уже отсортированным массивом. Отсортированная часть, которую мы строим слева направо без вставок и передвижений элементов займет время Ω(n).

Сортировка слиянием

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



Допустим, у нас есть n элементов для сортировки. Если n < 2, заканчиваем сортировку, иначе — сортируем отдельно левую и правую части массива, и потом их объединяем.
Давайте отсортируем массив


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



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





Сортировка слиянием требует времени O(nlog n) для всех случаев. Пока мы делим массивы на половины на каждом уровне рекурсии получаем log n. Затем, для слияния подмассивов нужно всего n сравнений. Следовательно, O(nlog n). Лучший и худший варианты для сортировки слиянием — одинаковы, ожидаемое время работы алгоритма = Θ(nlog n).

Этот алгоритм — самый эффективный среди рассмотренных.



  • ,

Гарвард CS50: задания второй недели (лекции 5 и 6)

cs50 задания к лекциям 5 и 6

Лекции CS50 лежат здесь: http://javarush.ru/cs50.html. В этом материале — 3 задания, теоретические сведения к ним и руководство к действию.

Цели


• Углубиться в функции и библиотеки
• Познакомиться с криптографией, реализовать пару простых шифров

Дополнительные материалы


reference.cs50.net/ — разъяснение функций библиотек, используемых во время обучения. На английском.
http://computer.howstuffworks.com/c.htm стр. 11 – 14 и 39

Подготовка


Залогиньтесь на cs50.io, выполните

update50

чтобы убедиться в актуальности версии вашего рабочего пространства. Если вы случайно закрыли терминальное окно, зайдите в меню View и убедитесь, что напротив пункта Console стоит галочка (поставьте её, если это не так).


Кликните на(+), внутри зеленого круга на рамке терминального окна, выберите New Terminal.


Создайте рабочую директорию:

mkdir ~/workspace/pset2

Обратите внимание: между mkdir и ~/workspace/pset2 есть пробел. Напомним, ~ означает корневой каталог, ~/workspace — папка, называемая рабочим пространством, находится внутри корневого каталога, ~/workspace/pset2 — директория по имени pset2 внутри ~/workspace.
Теперь выполните:

cd ~/workspace/pset2

чтобы перейти в новую директорию.

Командная строка выглядит примерно так:

username:~/workspace/pset2 $

Если что-то не так, повторите шаги. Также можете вызвать команду

history

чтобы просмотреть последние несколько команд в хронологическом порядке. Также вы можете, установив курсор на командную строку и нажимая стрелку «вверх» на клавиатуре, просматривать все команды в порядке от последней введенной к первой. С помощью кнопки «вниз» вы можете идти обратно. Кстати, вместо того, чтобы каждый раз набирать одни и те же команды, вы можете прокручивать уже набранные команды и выполнять их снова, нажимая на Enter. Вы могли заметить, что Дэвид на лекциях делает именно так.

Задачи второй недели нужно сохранять в pset2.

Задание 0. Инициализация


Ознакомимся со строками поближе. В файле initials.c напишите программу, которая запрашивает имя пользователя (с помощью функции GetString получаем имя в виде строки) и затем выводит первые буквы имени (или имен) и фамилии в верхнем регистре без пробелов, точек и прочих знаков, только с переводом строки (\n). Предполагаем, что пользователи вводят исключительно буквы (в нижнем или верхнем регистре, или обоих сразу) плюс по одному пробелу между словами. Считайте, что ребята с именами Joseph Gordon-Levitt, Conan O’Brien или David J. Malan не будут пользоваться программой.

username:~/workspace/pset2 $ ./initials
<u>Zamyla Chan</u>
ZC
username:~/workspace/pset2 $ ./initials
robert thomas bowden
RTB

Для проверки корректности работы программы вызывайте check50:

check50 2015.fall.pset2.initials initials.c

Хотите поиграться с реализацией программы, подготовленной сотрудниками CS50? Набирайте строку:

~cs50/pset2/initials


Криптография

Криптография, наука о шифровке и дешифровке информации… На самом деле зашифрованные послания существуют с древних времён, и использовались армиями для передачи секретных сообщений. Ну и сейчас ваши пароли в Facebook и других сетях хранятся в зашифрованном виде.

Задание 1. Аве, Цезарь!


Теоретические сведения
Мы изучим один из простейших шифров — шифр Цезаря, названный в честь римского императора. В этом шифре каждая буква текста заменяется на другую, которая находится на фиксированное число букв ниже в алфавите. Это фиксированное число букв называется ключом. Так, ключ 1 переводит букву латиницы C в букву D, а Z — по циклу в A. Если ключ 3, то буква C перейдет в F, а Z — в C.

Примеры: используем шифр Цезаря с ключом 5 на слове cat.

c -> h
a -> f
t -> y 
Caesar (cat, 5) = hfy

Ключ = 7, слово = computer

c->j
o->v
m->t
p->w
u->b
t->a
e->l
r->y
Caesar(computer,7) = jvtwbaly



Шифр Цезаря прост, но, увы, ненадёжен (это взаимосвязанные вещи!): для английского алфавита — всего 25 вариантов шифровки, перебрать все варианты легко даже без компьютера. Тем не менее, шифр Цезаря часто используют в качестве шага в других шифрах, таких, как шифр Виженера (о нём — в следующем пункте).

«Математизируем» шифр Цезаря. Обозначим незашифрованный текст буквой p, pi — буква в тексте p, которая находится на позиции с номером i. Назовем секретный ключ буквой k, с — зашифрованный текст, а ci — буква в шифрованном тексте, которая находится на позиции i. Тогда вычислить каждую букву шифра можно по формуле:

ci = (pi + k) % 26

Привыкайте к такой формализации, она позволяет программировать алгоритм и выражает смысл шифра точно и сжато.
Если ключ k = 13 а изначальный текст p — «Be sure to drink your Ovaltine!», вот какой шифр мы получим:

Or fher gb qevax lbhe Binygvar!


Обратите внимание, O (первая буква в шифрованном тексте) смещена на 13 позиций от буквы B (первая буква в оригинальном тексте). То же самое с буквой r (вторая буква в шифровке) смещена на 13 букв от e (вторая буква в оригинале). Третья буква в шифровке, f, смещена на 13 букв от s (третья в оригинале), тут мы ходим по кругу от z до a.

Шифр Цезаря с ключом 13 имеет специальное название ROT13. Он симметричный: применив его дважды, мы вернемся к изначальному тексту. Конечно, есть еще и ROT26, этот вообще супер-секьюрный, но только если вы нечетко выражаете свои мысли=).

Условие

Написать в файле caesar.c, программу, шифрующую текст с помощью шифра Цезаря. На вход программы подавайте один аргумент командной строки: не негативное целое число. Для простоты назовем его k. Если пользователь выполняет программу без аргументов командной строки или более, чем с одним аргументом, приложение должно возмутиться и вернуть значение 1 (обычно так обозначают ошибки):
return 1;

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

return 0;

Если main не возвращает нуль явно, он возвращается автоматически (на самом деле int — тип, возвращаемый main, но об этом в другой раз). Согласно конвенции (правилам хорошего тона в программировании), если вы явно возвращаете 1 чтобы указать на ошибку, то нужно вернуть и 0 в качестве указателя на успешное завершение работы программы.

Хотя в английском алфавите только 26 букв, k может быть и больше 26. По сути, ключ k = 27 даст тот же результат, что и k = 1, но нужно позволить пользователю вводить любое неотрицательное число, не превышающее 2^31 – 26 (оно должно поместиться в int). Программа также должна учитывать, что строчные буквы шифруются строчными, а прописные — прописными.

С чего начинаем? Поскольку приложение должно принять значение k непосредственно в строке аргументов, заголовок функции main у нас имеет следующий вид:

int main(int argc, string argv[])

Из шестой лекции вы знаете, что argv — это массив строк. Массив можно представить, как ряд шкафчиков-ячеек в спортзале. В каждом из них спрятано некоторое значение. В нашем случае, внутри каждой ячейки лежит аргумент типа

string

Чтобы открыть первый шкафчик, используем argv[0], второй — argv[1] и так далее. Если у нас есть n замков, то нам нужно остановиться на argv[n — 1], поскольку argv[n] уже не существует (или существует, но принадлежит кому-то ещё, нам лучше его не трогать).

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

string k = argv[1];

Мы полагаем, что там действительно что-то есть! Напомним, argc — переменная типа int, равная количеству строк argv. Значит, лучше проверить значение argc прежде, чем пытаться открыть ячейку, ведь может статься, что её не существует.

В идеале argc = 2. Почему так? Внутри argv[0] обычно находится имя программы. То есть, argc всегда не меньше 1. Но нашей программе нужно, чтобы пользователь предоставил аргумент командной строки k, следовательно, argc = 2. Естественно, если пользователь в командной строке введет более одного аргумента, argc также подрастает и может быть больше, чем 2.

Если пользователь вводит целое число в строку, это еще не значит, что внесенное значение будет автоматически сохранено в тип int. Точнее, оно НЕ будет. Оно будет string, даже если выглядит точь-в-точь, как int! Так что нам нужно конвертировать string в int самостоятельно. К счастью, существует функция atoi, созданная для этих целей. Её синтаксис:

int k = atoi(argv[1]);

Обратите внимание: k имеет тип int, поэтому с ним можно провернуть арифметические действия. С этой функцией не нужно беспокоиться, введет ли пользователь целое число, или, скажем, foo: в таком случае atoi возвратит 0.

Функция atoi объявлена в библиотеке stdlib.h, поэтому не забудьте прописать её директивой #include в начале программы. Код и без этого скомпиллируется, поскольку мы уже включили эту функцию в библиотеку cs50.h. Тем не менее, лучше доверять нативным библиотекам.

Итак, вы получили k, сохраненное как int. Теперь запросим ввод текста. Если вы делали задания первой недели, то уже знакомы с функцией библиотеки CS50, которая называется GetString. Она-то нам и поможет.

После того, как вы получили k и начальный текст, приступим к шифрованию. Напомним, вы можете пройтись по всем символам строки и напечатать их с помощью следующего цикла:

for (int i = 0, n = strlen(p); i < n; i++)
{
    printf("%c", p[i]);
}

Другими словами, точно так же, как argv — массив строк, string является массивом символов. Поэтому мы можем использовать квадратные скобки для доступа к отдельным элементам строки точно так же, как получать отдельные строки в argv. Конечно, нет ничего криптографического в печати каждого из символов. Или, технически, когда k = 0. Но мы же должны помочь Цезарю зашифровать его текст! Аве, Цезарь!

Чтобы использовать strlen, нужно подключить ещё одну библиотеку.

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

username:~/workspace/pset2 $ ./caesar 13
Be sure to drink your Ovaltine!
Or fher gb qevax lbhe Binygvar!


Помимо atoi, вы можете найти другие классные функции в библиотеках ctype.h и stdlib.h. Для этого перейдите по ссылке и поройтесь там немного. Например, isdigit — явно что-то интересное=).
Когда переходите от Z к A (или от z к a), не забывайте об операторе деления по модулю % в языке С. Также изучите таблицу, она показывает символы ASCII не только для букв.

Чтобы проверить правильность работы программы с check50, выполните следующее:

check50 2015.fall.pset2.caesar caesar.c

А если вам интересно поиграть с кодом, сделанным сотрудниками СS50, выполните команду:

~cs50/pset2/caesar


Кстати, uggc://jjj.lbhghor.pbz/jngpu?i=bUt5FWLEUN0.

Разбор задания
  1. Получить ключ
  2. Получить текст
  3. Зашифровать
  4. Вывести на экран зашифрованное сообщение

1. Формируем функцию main так, чтобы пользователь вводил ключ в командной строке и проверяем ключ на корректность.

int main(int argc, string argv[])

argc:
• int
• количество аргументов, введенных в командную строку
• если argc = 2 все ок. Если нет, выводим инструкцию и закрываем программу.
• Если argc = 2 проверяем, является ли ключ целочисленным
• Argv — это массив строк, список с введенными в него аргументами

Массив — структура данных, содержащая разные данные одного типа в разных ячейках.


Например, пользователь ввел строку blastoff Team Rocket, тогда:


Переводим с помощью функции atoi() полученное в целое число. Если это невозможно, функция вернет 0.



2. Запрос у пользователя текста. Это просто: всё, что вводит пользователь, является строкой.
3. Шифрование. Алгоритм прост, но как пояснить компьютеру, какие буквы идут одна за другой? Самое время вспомнить о таблице ASCII!


Однако в строке могут быть не только буквы… Прежде, чем перейти к изменению строк, представьте, что нужно поменять только один символ. Мы хотим сменить буквы из начального текста, а не знаки или цифры. Что мы должны сделать? Для начала нам нужно проверить, есть ли этот символ в алфавите. Это можно сделать с помощью функции isalpha().

Если символ входит в алфавит, эта функция возвращает значение true и false во всех других случаях. Еще две полезные функции — isupper () и islower() возвращают true в случае, если буква прописная или строчная соответственно. Таким образом:

Isalpha(‘Z’) -> true
Isalpha(‘;’) -> false
Isupper(‘Z’) ->true
Isupper(‘z’) -> false
Islower(‘Z’) -> false
Islower(‘z’)->true


Если isalpha возвращает true, нам нужно поменять этот символ с помощью ключа.
Рассмотрим и разберем в качестве примера программу Замили, ассистента CS50.

/*
 * asciimath.c
 * by Zamyla Chan
 *
 * Calculates the addition of a char and an integer,
 * and displays both the resultant character and its
 * ASCII value.
 *
 * Usage: ./asciimath key [char]
 *
 */

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, string argv[])
{

    if (argc != 2)
    	
    	{
 printf("print the key next time \n"); 
        return 1;
    	}
    // key is the second command line argument 

  
    int key = atoi(argv[1]); //преобразование строки в int 

    int letter = 'A';
    
    printf("\nCalculating '%c' + %d...\n", letter, key);
    
    int result = (letter + key);
        
    printf("The ASCII value of %c is %d.\n\n", result, result);
   
    return 0;
    

}

Вас может удивить, почему ‘A’ — это целое число, тогда как она явно является буквой. Оказывается символы и целые числа — взаимозаменяемы. Поставив букву A в одиночные кавычки можно получить её ASCII-код в int. Будьте внимательны: вам нужны именно одинарные кавычки, без них компилятор будет искать переменную по имени A, а не символ.

Затем в строке

int result = (letter + key);


мы прибавляем значение ключа к ASCII-коду буквы и сохраняем их в переменной целого типа. Даже если результат имеет тип int, оператор printf использует плейсхолдер %с для символов. Таким образом, программа печатает символ, связанный с целочисленным результатом. Во втором случае мы выводим на экран число с помощью плейсхолдера %d.

Вы можете ввести этот код в сs50 IDE и поиграться с ним. Проверим работу asciimath для разных ключей. Возьмем значение 25, увидим следующую картинку:



А теперь пусть ключ будет 26:



Мы получили [, а вовсе не букву A. Это просто следующий символ ASCII после Z. Так что простое прибавление ключа работать не будет. Нам нужно использовать формулу шифра, чтобы возвращаться в начало алфавита как только буквы закончатся.
Помните, мы уже писали выше:

ci = (pi + k) % 26

Где ci — буква номер i в шифрованном тексте, pi — буква номер i в незашифрованном тексте, k — ключ, а %26 — остаток от деления на 26 (или «деление по модулю 26»).

Давайте применим эту формулу для буквы Y. Возьмем k = 2. Посчитаем (‘Y’ + 2) %26
ASCII-код буквы ‘Y’= 89. Тогда
(‘Y’ + 2) %26 = (89 + 2)%26 = 91%26 = 13

Но это вовсе не ASCII-значение нужной нам буквы A, которое равно 65.

Теперь давайте придадим каждой букве алфавита значение от 0 до 25 по порядку. В таком случае Y = 24.
(24+2)%26 = 0
Буква А как раз имеет такой индекс. Таким образом, эта формула относится к алфавитному индексу букв, а не их ASCII-значений.

Для печати зашифрованного символа вам нужно будет его ASCII-значение. И разберитесь с тем, как переключаться между ASCII-значением и номером в алфавите.
После того, как мы выяснили формулу для одного символа, нужно применить её для каждой буквы во вводимой с клавиатуры строке. Но только если это буквы!
И помните, для больших и малых букв нужны разные значения. Тут пригодятся функции isupper и islower. У вас может быть две формулы, одна для больших букв, другая — для малых, функции помогут выбрать, какую из них применить.

Как применить формулу к каждому отдельному символу в строке? Помним, что строка — это просто массив символов. Определить количество итераций в цикле поможет функция strlen (длина строки).


Задание 2. Parlez-vous français?

Теория

Шифр Виженера несколько безопаснее шифра Цезаря: в качестве ключа в нем используется слово и его сложно взломать вручную с помощью одного только частотного анализа или перебора. Каждая буква ключа генерирует число, и в результате мы получаем несколько несколько ключей для сдвига букв.

Пример:

p = Meet me in the park at eleven am 
В качестве ключевого слова возьмем 
k = bacon
Длина сообщения p = 25 
В то время как длина k = 5 
Поэтому его нужно повторять 5 раз.



Если число букв в сообщении не делится на ключ нацело, мы в последнем применении ключа используем только его часть:


Чтобы найти значение для смещения, используем позиции каждой буквы нашего ключа bacon в алфавите (от a до z). Считаем с нуля, как истинные программисты. И каждую букву в оригинальном тексте смещаем на заданное число, как в шифре Цезаря, возвращаясь при надобности после Z в начало алфавита. Таким образом, M сместится на 1, первая e вообще не сместится, а вторая сместится на 2 позиции. Ниже вы видите изначальное сообщение, расписанный ключ и результат его применения.


Шифр Виженера, конечно, понадежнее, но если вы знаете длину ключа, его сломать довольно просто. Как её выявить? Если оригинальный текст достаточно длинный, чтобы некоторые слова встречались в нем несколько раз, то вы увидите некоторые повторения:


Также можно использовать полный перебор, но вариантов немало: 26^n – 1 где n — длина неизвестного ключа. Но обычно это немало. Правда, для компьютера это не проблема.
А теперь математика шифра:

Пусть р – некоторый текст, k — ключевое слово, kj — j-я буква ключа, pi — буква под номером i в оригинальном тексте, ci — буква под номером i в шифровке. Тогда:

ci = (pi + kj) % 26

Задание
Условие

Написать программу vigenere.c, которая шифрует сообщение с помощью шифра Виженера. На вход программы подаем один аргумент командной строки: ключевое слово k, состоящее из букв английского алфавита. Если приложение запускается более чем с одним аргументом или с аргументом не входящим в алфавит, нужно вывести информацию об ошибке с завершением программы. То есть main будет возвращать 1 — в таком случае наши автоматические тесты поймут, что здесь все хорошо, и это условие учтено. Если всё хорошо, программа должна перейти к запросу строки текста p, который мы и шифруем полученным выше ключом k, напечатать результат и завершить выполнение программы, возвратив значение 0.
Уточнение

Нужно сделать так, чтобы в ключе k символы A и a обозначались как 0, B и b как 1, ..., Z и z как 25. Программа должна применять шифр Виженера только к буквам текста p. Остальные символы (цифры, знаки препинания, пробелы) нужно вывести без изменений. Если алгоритм собирается применить j-й символ k к i-му символу p, не входящему в алфавит, применяем этот j-й символ ключа к следующему алфавитному символу в тексте; вы не можете просто оставить его и перейти к другому символу в k. Наконец, программа должна сохранить регистр каждой буквы в p.

Не знаете, с чего начать?




Вот вам несколько советов от Замили, ассистента курса CS50

К счастью, программа очень похожа на шифр Цезаря, только в качестве ключа используется не целое число, а строка. Если вы успешно реализовали шифр имени римского правителя, он может стать прекрасным стартом для реализации второго задания. Вы, вероятно, уже смекнули, что шифр Виженера с одной буквой в качестве ключа — это тот же шифр Цезаря.
В алгоритме Виженера применяются те же шаги, что и в «Цезаре»:
  1. Получить ключ
    • кодовое слово — это второй аргумент командной строки argv[1]
    • должен входить в алфавит: функция isalpha

  2. Получить текст
  3. Зашифровать
  4. Напечатать шифрованный текст
Итак, второй аргумент командной строки argv[1] проверим на принадлежность к алфавитным символам. Делаем это с помощью уже знакомой isalpha. Если ключ корректен, получаем от пользователя строку и начинаем шифровать.

Формула шифра Виженера похожа на формулу шифра Цезаря. Каким образом вы преобразуете букву на соответствующее смещение шифра? Попробуйте сравнить значения по таблице ASCII.


Скорее всего, у вас получится отыскать закономерность между буквами и их алфавитными индексами используя последовательности в таблице. Догадались, как отнять одну букву от другой, чтобы получить желаемый результат? Смещения для больших и малых букв одинаковы, так что вам придется определить две похожие формулы для определения смещения для строчных и отдельно для прописных букв.
Также не забудьте, что цикл прохода по тексту должен игнорировать символы, не входящие в английский алфавит. И не забудьте сохранить регистр букв.
Если посмотреть на формулу шифра:

ci = (pi + kj) % 26

вы увидите две индексные переменные, i и j. Одна сохраняет позицию в исходном тексте, другая — в ключе. Если ваш текст длиннее ключа, индекс по ключу проходит с конца ключа снова в его начало.
Как это сделать? С помощью операции деления по модулю! Результат операции — остаток от деления двух чисел. Практическая польза этой операции в программировании просто огромна!

Представьте, что многочисленную группу людей нужно разделить на три подгруппы. Один из способов это сделать — попросить их рассчитаться на первый-второй-третий.


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



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

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

Так как мы автоматизируем некоторые тесты вашего кода, программа должна вести себя так, как показано ниже:

jharvard@appliance (~/Dropbox/pset2): ./vigenere bacon
Meet me at the park at eleven am
Negh zf av huf pcfx bt gzrwep oz


Как еще можно протестировать программу, кроме ручного вычисления зашифрованного текста? Мы добрые: для этого мы написали программу devigenere. Она принимает один и только один аргумент командной строки (ключевое слово), а её работа заключается в том, чтобы принять зашифрованный текст в качестве входных данных и вернуть обычный.
Запустите её:

~cs50/pset2/devigenere k

Где k — ключевое слово.
Если вы хотите проверить правильность вашей программы с помощью check50, выполните:

check50 2014.fall.pset2.vigenere vigenere.c


А если хотите оценить нашу реализацию vigenere, наберите:

~cs50/pset2/vigenere


Как подтвердить правильность кода и получить оценки


Внимание! Если вам важно проверить только правильность задач, после того, воспользуйтесь cs50check. Если же вы ходите получить оценки на платформе edx, проделайте процедуру, описанную ниже. Имейте в виду, эта процедура для проверки задач использует ту же cs50check. Разница только в том, что она запоминает результаты и подсчитывает общую оценку.
  1. Залогиньтесь в CS50 IDE
  2. Рядом с левым верхним углом CS50 IDE, там, где расположен её файловый браузер (не в терминальном окне), кликните правой клавишей мыши по вашему файлу initials.c, находящемуся в директории pset2 и нажмите Download. Вы должны увидеть, что браузер загрузил initials.c.
  3. Повторите для caesar.c.
  4. Повторите для vigenere.c.
  5. В отдельном окне или вкладке залогиньтесь в CS50 Submit
  6. Кликните по иконке Submit в левом верхнем углу экрана.



  7. В списке папок слева кликните по директории Problem Set 2, затем нажмите на кнопку Upload New Submission. Она находится справа.



  8. На появившемся экране кликните по кнопке Add files…. Откроется окно выбора файлов с вашего компьютера.



  9. Перейдите к той папке, где вы храните initials.c. Скорее всего, он находится в папке Downloads («Загрузки») или там, куда ваш браузер складывает файлы по умолчанию. Когда найдете initials.c, кликните по нему один раз чтобы выбрать, затем кликните Open («Открыть»).
  10. Кликните Add files ещё разок.
  11. Найдите caesar.c и откройте его.
  12. Проделайте то же самое для файла vigenere.c.
  13. Нажмите Start upload. Ваши файлы будут загружены на серверы CS50.
  14. На появившемся экране вы должны увидеть окно No File Selected. Если вы переведете курсор мыши влево, вы увидите список загрузившихся файлов. Для подтверждения кликните по каждому из них. Если вы в чём-то не уверены, вы можете перезагрузить файлы, повторив те ж шаги. Вы это можете делать сколько угодно раз до конца 2016 года.
  • ,

Пятая лекция CS50 уже на JavaRush [на русском!]

Посмотреть лекцию можно здесь: javarush.ru/cs50.html

Каждый год примерно 3% студентов Гарвардского курса по основам программирования CS50 пытаются смошенничать во время учёбы, например, выдав чужой код за свой. Этой статистикой David Malan поделился на пятой лекции CS50. Представляете, какой процент был бы в наших вузах?.. Впрочем, не будем о грустном, давайте лучше о знаниях. Вот что вам расскажут в текущей лекции:

cs50 5 лекция

  • Баги. Без этих верных спутников разработчиков никуда не деться, нужно научиться их выискивать. Дэвид расскажет о некоторых типах багов. Начнет с тех, которые сложнее выцепить: логических;
  • Откровение: бесконечный цикл на самом деле не такой уж и бесконечный;
  • Функциональная декомпозиция: прием для повышения читаемости кода и удобства кодирования;
  • Знай свои фигурные скобки: область действия переменных;
  • Объявление функций до реализации: специально для C;
  • Строки и как с ними работать;
  • Что такое ошибка сегментации;
  • Милые щеночки! В стриме. Не пропустите=).
  • Как едят шоколадки и M&M’s в Гарварде. Наглядное пособие.

… ну а следующая лекция будет еще интереснее: молочное чудо Ovaltine и криптография. Одно только звучание завораживает!
  • ,

Гарвард CS50: задания первой недели (лекции 3 и 4)

CS50 задания

Друзья, основные теоретические сведения вы можете почерпнуть из конспекта семинаров. Там, помимо основ С рассказано, как подключиться к специальной облачной IDE CS50 (это нужно сделать для выполнения и проверки заданий), описаны основные нужные команды Linux и структуры языка. Если вам будет недостаточно материала о C, изложенного в лекции и конспекте, обратитесь к другим источникам. Например, к тем, что указаны в конце данной статьи.

В топике "Дополнительные материалы"
  • Цели первой недели
  • IDE CS50
  • Командная строка и обновление рабочей среды
  • Работа в IDE
  • Hello, C!
  • Баги?
  • Проверка на правильность: тест check50
  • Основы С: сравнение со Scratch
  • Основные типы данных в C
  • Библиотеки С
  • И снова Hello C: разбор синтаксиса простейших программ
  • Еще немного о вводе/выводе в C
Материалы в этом топике:

Ввод данных с проверкой: специальные функции библиотеки cs50.h
Для более удобного прохождения этого курса, мы разработали специальную библиотеку CS50, в которой, в частности, есть очень полезные функции обработки введенных пользователем данных.

GetString() считывает введенную пользователем строку
GetInt() считывает введенную пользователем строку и проверяет, не записано ли в ней целое число
GetFloat()считывает введенную пользователем строку и проверяет, не записано ли в ней число с плавающей точкой
GetLongLong() считывает введенную пользователем строку и проверяет, не записано ли в ней длинное вещественное число.

Задание 1. Умный подсчет расхода воды



Логично: чем дольше вы принимаете душ, тем больше воды уходит на этот процесс. Давайте прикинем, сколько? Даже если ваш душ едва открыт, в минуту из него вытекает примерно 6 литров воды. А это 12 бутылочек воды, которые вы носите с собой для питья. Обычно человек принимает душ минут 10. Итого, чтобы помыться, нужно 120 полулитровых бутылок. Немало!

Создайте файл water.c в вашей директории ~/workspace/pset1. Программа должна подсчитывать сколько бутылочек воды уходит на душ зависимости от времени. То есть:

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

username:~/workspace/pset1 $ ./water
minutes: 10
bottles: 120

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

Чтобы проверить правильность выполнения программы с помощью check50, нужно ввести следующую строку в терминале:

check50 2015.fall.pset1.water water.c

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

~cs50/pset1/water


Задание 2. С нами Марио!


Знаете ли вы самого знаменитого водопроводчика в мире? С легкой руки компании Nintendo вымышленный усатый и немного полноватый дядечка в красной кепке стал героем для нескольких поколений геймеров. Если вы не знаете, о ком речь, вот вам ссылка на классическую игру 1985 года: поверьте, она всё ещё хороша и заслуживает внимания! Также можно найти вариант классического Super Mario для смартфонов или оффлайновых эмуляторов. Всё это нам нужно для общего развития, это еще, к сожалению, не задание;). А задание состоит вот в чем. В конце первого уровня Mario каждый игрок видел вот такую полупирамидку:

Создайте файл mario.c в вашей директории ~/workspace/pset1. Наша рограммка будет рисовать полупирамиду, подобную той, что вы видите, но прямо в консоли, без графики: каждый из блоков будет состоять из значка хэша (#). Даже если вы еще не сообразили, как это сделать, поверьте: это просто. Чтобы сделать задачу более интересной, добавим в неё возможность задавать высоту полупирамидки с помощью неотрицательного целого числа от 0 до 23. Высота пирамидки на картинке считается в самом высоком месте, то есть равна 8. Если пользователь неправильно вводит число, нужно попросить его сделать это ещё раз. Затем сгенерировать (с помощью printf пирамидку.

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

username:~/workspace/pset1 $ ./mario

height: <u>8</u>
       ##
      ###
     ####
    #####
   ######
  #######
 ########
#########

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

Если пользователь ввел неправильные данные (ввел не число, или число, которое меньше единицы или больше, чем 23), программа должна снова попросить его ввести данные, как в примере внизу, где подчеркнутый текст — то, что вводил пользователь с клавиатуры.

Для считывания введенной строки используйте GetInt. Она может помочь проверить неправильный ввод, но не для всех случаев.

username:~/workspace/pset1 $ ./mario
Height: -2
Height: -1
Height: foo
Retry: bar
Retry: 1
##

Чтобы скомпилировать программу, введите строку в терминале:

make mario

или более прозрачный, но длинный вариант:

clang -o mario mario.c -lcs50

после этого запустите программу на исполнение:

./mario

Если вы хотите проверить правильность выполнения программы, запускайте check50:

check50 2015.fall.pset1.mario mario.c

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

~cs50/pset1/mario


Задание 3. Время получать сдачу

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

Однако что будет, если кто-то рассчитается с кассиром крупной купюрой? Представьте, сколько мороки будет с тем, чтобы посчитать монетки на сдачу. Для минимизации количества выдаваемых монет можно использовать так называемые «жадные» алгоритмы. Они, согласно определению Национального Института Стандартов и Технологии (NIST) всегда находят оптимальное решение на каждом шаге решения задачи, допуская, что конечное решение (полученное из совокупности таких шагов) также будет оптимальным.

Что это значит? Представим, что кассир должен покупателю сдачу в 41 цент, а у него на поясе есть цилиндры с монетками для сдачи номиналом в 25, 10, 5 и 1 цент. Руководствующийся «жадным» алгоритмом кассир сразу же захочет выдать максимум, на первом же шаге. На этом шаге оптимальным или наилучшим решением будет выдать 25 пенсов. 41-25 = 16. Осталось выдать 16 пенсов. Очевидно, 25 пенсов слишком много, значит, остается 10. 16-10 = 6. Теперь выдаем по тому же принципу 5 пенсов, и затем — 1. Таким образом, покупатель получит всего четыре монеты номиналом 25, 10, 5 и 1 пенс.

Оказывается, «жадная» пошаговая инструкция выдачи денег оптимальна не только для этого случая, но также для номиналов валюты США (и Евросоюза тоже). То есть, если у кассира достаточно монет любого номинала, алгоритм будет работать лучшим образом, то есть, выдаст минимальное количество монет из всех возможных случаев.
Итак, какое минимальное количество монеток нам нужно, чтобы дать сдачу? Это и есть наша третья задачка.

Создайте файл greedy.c в своей директории ~/workspace/pset1.

Дано: монетки номиналом 25, 10, 5, 1 цент

Программа должна:

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

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

Мы попросили вас использовать GetFloat, чтобы пользователь мог вводить значение в долларах и центах через точку. Например, если мы должны $9.75, пользователь должен ввести 9.75, но не $9.75 или 975.

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

Остерегайтесь неточностей, свойственных числам с плавающей точкой. Например, 0.01 не может быть представлено непосредственно как float. Попробуйте использовать форматированный вывод, например, с 50 знаками после запятой, используя указанный ниже код:

float f = 0.01;
printf("%.50f\n", f);

Кстати, перед тем, как что-либо считать, будет логично перевести всю сумму в центы, (и заодно преобразовать её из float в int), что поможет избежать массы ошибок и сложностей.
Чтобы наш автоматический анализатор кода мог правильно проверить вашу задачу, убедитесь, что последняя строка вывода вашей программы не содержит никакой другой информации, кроме минимального количества монеток: целое число с символом \n после него (те, кто учится на JavaRush, прекрасно знают, о чём мы здесь говорим =)).

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

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
0.41
4

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

username:~/workspace/pset1 $ ./greedy
O hai! How much change is owed?
-0.41
How much change is owed?
-0.41
How much change is owed?
foo
Retry: 0.41
4

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

Если во время тестирования приложения вы поймете, что цикл не останавливается, вы можете прервать выполнение программы комбинацией ctrl-c (иногда — многократной).

Как компилировать и выполнять программу вы уже знаете.

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

check50 2015.fall.pset1.greedy greedy.c

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

~cs50/pset1/greedy

Как подтвердить правильность кода и получить оценки

Вариант 1

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

check50 2015.fall.pset1.name name.c


введенной в терминальной строке CS50 IDE.
Где name — название файла вашей задачи.

Вариант 2
Если же вы хотите получить оценки (по сути, тот же запуск check50, но с запоминанием результата и заполнением некоторых форм на английском, тогда проделайте следующие шаги:
Шаг 1 из 2

  1. Когда приложения готовы, залогиньтесь в CS50 IDE.
  2. В левом верхнем углу CS50 IDE в пределах его файлового браузера, а не терминального окна, кликните левой клавишей мыши с удержанием ctrl или правой клавишей мыши по вашему файлу hello.c (тому, который лежит в директории pset1 ) и нажмите Download. Вы должны обнаружить, что браузер загрузил hello.c.
  3. Повторите для water.c.
  4. Повторите для mario.c.
  5. Повторите для greedy.c.
  6. В отдельной вкладке или окне залогиньтесь в CS50 Submit.
  7. Нажмите Submit в левом нижнем углу окна.
  8. Под Problem Set 1 на появившемся окне нажмите на Upload New Submission.
  9. На появившемся окне жмите Add files…. Должно появиться окно с именем Open Files.
  10. Пройдите путь к месту, куда загружен hello.c. Обычно он находится в папке Downloads или в той папке, которая назначена у вас по умолчанию для загрузки. Найдя hello.c, нажмите на него один раз чтобы отметить, затем нажмите Open.
  11. Кликните Add files… снова, и окно Open Files снова появится.
  12. Теперь найдите таким же образом файл water.c. Кликните по нему, затем кликните Open (или «Открыть»).
  13. Теперь находите mario.c. И тоже кликайте и открывайте таким же образом.
  14. Все то же самое с файлом greedy.c.
  15. Нажмите Start upload чтобы начать загрузку ваших файлов на серверы CS50.
  16. На появившемся экране вы увидите окно с надписью No File Selected. Если вы переместите курсор мыши в левую часть окра, вы увидите список файлов, которые вы загрузили. Нажмите на каждый, чтобы подтвердить содержание каждого из них. (Нет необходимости нажимать на другие кнопки или иконки). Если уверены, что готовы отослать файл на проверку, считайте, вы все сделали! Если хотите проверить свой код самостоятельно ещё раз или исправить что-либо, возвращайтесь в CS50 Submit и повторите эти шаги. Вы можете повторно отправить столько раз, сколько вы хотите; оцениваться будет только самое последнее представление.

Шаг 2 из 2
(он не обязателен для оценки, если что=))
Теперь перейдите по ссылке http://cs50.edx.org/2016/psets/1/ где вы обнаружите специальные формы. В них нужно ответить на несколько теоретических вопросов, и затем нажать Submit под ними.

Вопросы со звездочками – обязательны:

  • Alright, should've seen this one coming! In just a few sentences, what's a library? * (Кратко опишите, что такое библиотека)
  • In just a few sentences, what role does
    #include <cs50.h>

    play when you write it atop some program? *(какова роль строки #include <cs50.h>, которая фигурирует в верхней части кода некоторых программ?)
  • About how many hours would you say you spent on Problem Set 0: Scratch?(сколько времени у вас заняли задачки нулевой недели (Scratch)
  • About how many hours would you say you spent on Problem Set 1: C?(как долго вы решали задачки первой недели по C?)
  • What's your opinion of CS50x thus far? *(Ваше мнение о CS50 в настоящий момент, выбрать вариант нравится-не нравится)
  • Have you asked for help from classmates or staff via CS50s Facebook Group at www.facebook.com/groups/cs50? *(обращались ли вы за помощью к другим студентам или ассистентам в группе facebook)
  • Have you asked for help from classmates or staff via CS50s Subreddit at www.reddit.com/r/cs50 *(обращались ли вы за помощью к другим студентам или ассистентам через Subreddit)
  • Have you asked for help from classmates or staff via Twitter using @cs50 or #cs50? *(просили ли вы помощи у других студентов или ассистентов в Twitter используя @cs50 или #cs50).


Друзья, если возникают какие-то вопросы, пишите их в комментариях под этим руководством. Если вы не достигли пятого уровня JavaRush, чтобы получить приглашение на info, рекомендуем это сделать. Это бесплатно, интересно и не очень сложно.

Ресурс кода:

Лекция три
cdn.cs50.net/2015/fall/lectures/1/w/src1w.zip
Лекция четыре
cdn.cs50.net/2015/fall/lectures/1/f/src1f.zip
cdn.cs50.net/2015/fall/lectures/1/f/src1f/

Дополнительная литература

cpp.com.ru/kr_cbook/ — русская версия классической книги по C от авторов языка — Брайана Кернигана и Дэнниса Ритчи. Широко известна в узких кругах как K&R. Перевод, правда, не самого нового издания.
Почитайте первые три главы. Там будет несколько больше материала, чем вам нужно, но достаточно для решения задач.
computer.howstuffworks.com/c.htm — ресурс, рекомендуемый авторами CS50. На английском языке. Стр. 1-7, 9 и 10.