EduTranslator

Научные работы со всего мира

EduTranslator

Рубрика: Программирование

РУКОВОДСТВО ПО СТИЛЮ ОФОРМЛЕНИЯ

НЕЙМИНГ

КЛАССЫ, ИНТЕРФЕЙСЫ, ЭНУМЫ

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

Следует избегать неинформативных названий, таких как Data, Info, или Engine. Также старайтесь не прикреплять эти бесполезные слова к хорошим именам. Если у вас есть класс, представляющий звезду, назовите его Star, а не StarData.

Хороший способ обозначить интерфейс – назвать в соответствии с тем, что можно сделать с классами, которые его реализуют. Например, интерфейс, представляющий нечто с пространственными координатами, может называться SpatiallyLocatable. Это облегчает распознавание интерфейса по сравнению с классом.

МЕТОДЫ

Методы тоже должны иметь информативные названия. Например, do() не является хорошим именем для метода.

Что касается метод-получателей и метод-модификаторов, существует два широко используемых формата:

  • value()и value(newvalue);
  • стиль JavaBeans – getValue()и setValue(newvalue).

Мы предпочитаем второй, поскольку многие инструменты в «экосистеме» Java предполагают, что вы будете использовать именно его.

ПОЛЯ

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

Все имена статических полей должны быть в верхнем регистре, например static int BEST_NUMBER = 1338. Довольно часто они также будут final. Статическое или нет, вы должны пометить поле как final, если не предполагается его переназначение. Нам нравятся постоянные классы.

КОНЦЕПЦИЯ И СТРУКТУРА ПАКЕТА

Убедитесь, что вы кодируете правильную информацию в классах. Поля никогда не должны быть открытыми, чтобы никто не мог изменить их свойства извне. Используйте метод-получатель и метод-модификатор для предоставления внешнего доступа к переменным экземпляра (только если их нужно модифицировать!). Так программист получит гораздо больше контроля. Вы можете, например, предотвратить setAge(-3); от лишнего запуска. Убедитесь, что методы чтения не раздают ссылки на изменяемое внутреннее состояние класса.

Java предлагает четыре уровня видимости для полей, которые подробно описаны здесь. В большинстве случаев целесообразно использовать ключевое слово private и писать метод-получатель и метод-модификатор для закрытого поля. Однако иногда лучше не использовать модификатор и сделать поле доступным для всех классов в одном пакете. Это полезно, когда вы реализуете часть программы, которая требует совместной работы нескольких классов. Например, если вы реализуете класс Graph, вероятно, понадобятся также классы Node и Edge. Поля Node и Edge могут быть открыты, чтобы Graph мог легко ими управлять. Более консервативная стратегия состоит в том, чтобы сделать поля закрытыми, также, как и методы получения и изменения значения.

Вы должны использовать пакеты с умом. У вас может быть один пакет, названный в честь рассматриваемого проекта, и он может иметь только Main и несколько очень специфичных для проекта классов. Если вы строите структуру данных, у вас может быть пакет для структуры такого типа. Например, List находится в пакете collect со многими другими видами коллекций. Не поддавайтесь желанию создать пакет util. Это так же безбожно, как и называть класс Data.

СТИЛЬ КОДИРОВАНИЯ

ИСКЛЮЧЕНИЯ

Уделяйте внимание исключениям! Мы видим такой код слишком часто:

try { 

  something();

} catch (SomethingException e){ 

  e.printStackTrace(); 

}

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

ИТЕРАЦИИ

Если вы хотите использовать итератор, по возможности используйте цикл for-each, а цикл не for. Ваше намерение будет яснее, а код легче усваивается (людьми).

КОММЕНТАРИИ

Пишите полезные комментарии. Мы ожидаем два типа комментариев.

Комментарии к методу – если метод публичный, он должен иметь комментарии в стиле javadoc. Javadoc’и похожи на обычные многострочные замечания, за исключением того, что они разграничены символами /** и */ вместо обычных /* и */. Вы можете генерировать документацию из своего javadoc, используя mvn site, как описано в проекте boggle.

Краткое руководство по Javadocs можно найти здесь:

http://students.cs.byu.edu/~cs240ta/fall2012/tutorials/javadoctutorial.html

Более полное руководство можно найти здесь:

http://www.oracle.com/technetwork/java/javase/documentation/index-137868.html

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

README

Есть несколько вещей, которые мы просим вас написать в README.

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

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

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

Ханойская башня: Несколько способов решить головоломку

Статью можно найти на сайте um.edu.mt

Автор Ярослав Скленар
Отставной адъюнкт-профессор
Департамента статистики и исследований операций
Факультета Науки, Университет Мальты

Вступление

Ханойская башня – это хорошо известная игра (головоломка), обычно используемая для объяснения и демонстрации силы рекурсии. Есть много вебсайтов, где предлагается ее подробное объяснение, например:

http://en.wikipedia.org/wiki/Tower_of_Hanoi

http://hanoitower.mkolar.org/

http://www.cut-the-knot.org/recurrence/hanoi.shtml

http://mathworld.wolfram.com/TowerofHanoi.html

и другие. Головоломка также подходит для демонстрации возможностей динамического программирования. Узнать об этом больше можно в статье Моше Снедовича: http://archive.ite.journal.informs.org/Vol3No1/Sniedovich/. Он использует этот подход, чтобы найти длину самого короткого решения, длину почти проигнорированного самого длинного решения и многое другое. Мы тоже используем особенности динамического программирования, но чтобы найти количество различных решений проблемы.

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

Теория

Я предполагаю, что читатель знаком с головоломкой, поэтому просто кратко резюмирую:

Есть три платформы (полюса) – левый (L), центральный (C) и правый (R).

Башня – это коллекция дисков (колец), расположенных один над другим таким образом, что диск меньшего размера всегда помещается на диск побольше. Изначально есть башня высотой n, состоящая из дисков 1…n увеличивающегося размера, где 1 – верхний самый маленький диск, расположенный на платформе L.

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

  • можно передвигать только один диск за раз;
  • диск можно положить или на пустую платформу, или на диск большего размера.

Задание: мы хотим переместить башню из дисков 1…n с платформы L на платформу R, следуя правилам.

Состояние задания определяется тремя взаимоисключающими наборами.

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

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

Пусть F (n, a, b, c) – общее количество различных решений головоломки с перемещением башни высотой n с платформы a на платформу b и использованием платформы c. Поскольку между платформами нет никакой разницы, обозначенной правилами, мы можем использовать F (n) для краткого обозначения.

Теорема: F(n) можно вычислить по рекурсивной формуле:

Доказательство: Очевидно, что для n = 1 есть два решения без циклов: переместить диск из L в R или переместить диск из L в C, а затем из C в R. Чтобы достичь конечного состояния, самый большой диск n необходимо переместить с L на R. Это можно сделать (всегда без циклов) двумя различными способами, которые рассмотрим отдельно.

1) Переместить башню (n-1) с L на C, переместить диск n с L на R, переместить башню (n-1) с C на R. Существует F(n-1) способов переместить башню (n-1) с L на C, точно так же как и F(n-1) способов переместить башню (n-1) с C на R. Эти два пути передвижения башен высотой (n-1) независимы, поэтому в первом случае получаем F(n-1)2 возможных решений.

2) Переместить башню (n-1) с L на R, переместить диск n с L на C, переместить башню (n-1) с R на L, переместить диск n с C на R, переместить башню (n-1) с L на R. Как видим, существует три независимых движения башни (n-1), поэтому общее количество решений в этом случае составит F(n-1)3.

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

Легенды

Существует легенда, вероятно придуманная французским математиком Эдуардом Лукасом в 1883 году вместе с самой головоломкой:

«Легенда гласит, что группа восточных монахов является хранителями трех башен, состоящих из 64 золотых колец. Первоначально все 64 кольца были сложены на одной башне, каждое верхнее меньше кольца, расположенного под ним. Монахи должны перемещать кольца из первой башни в третью по одному, но никогда не перемещать большее кольцо поверх меньшего. Как только порядок 64 колец будет нарушен, миру придет конец».

(Больше о легенде можно узнать в источнике: http://hanoitower.mkolar.org).

Хорошо известно, что для оптимального решения головоломки с башнями требуется 2n-1 ходов. Предполагая, что один ход занимает 1 секунду, с помощью простых вычислений приходим к результату, что решение для n = 64 занимает около 585×109 лет.

Можем предложить другую легенду:

«Возьмите только 5 колец и попробуйте все возможные решения. После этого Вселенной придет конец».

Если мы примем во внимание это (нереалистичное) предположение и то, что каждое решение (их длительность отличается) в среднем занимает всего 1 секунду, потребуется около 89.67×1020 лет, чтобы перепробовать все. Достаточно времени, чтобы завершить дела перед большим взрывом.

И еще одна легенда:

«Возьмите только 4 кольца и позвольте каждому человеку на Земле решать головоломку по-своему. Когда все возможные решения закончатся, Вселенной придет конец».

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

Результаты

Вот несколько способов увеличить высоту башни:

F(1) = 2

F(2) = 12

F(3) =  1872

F(4) =  6,563,711,232

F(5) ≈  2.827798101718050e+029

Ниже приведены все решения для башен высотой 1,2 и 3 (выдержка). Каждая строка содержит одно решение, которое начинается с его номера. Движения, разделенные пробелами, имеют формат:

    kAB

где k – номер диска, который мы перемещаем с платформы A на платформу B. Обратите внимание, что первое решение является самым коротким с 2n-1 ходами, а последнее – самым длинным с 3n-1 ходами.

1 (высота башни)

2 (количество сгенерированных решений)

    1 1LR

    2 1LC 1CR

    2 (высота башни)

12 (количество сгенерированных решений)

1 1LC 2LR 1CR

2 1LC 2LR 1CL 1LR

3 1LR 1RC 2LR 1CR

4 1LR 1RC 2LR 1CL 1LR

5 1LR 2LC 1RL 2CR 1LR

6 1LR 2LC 1RL 2CR 1LC 1CR

7 1LR 2LC 1RC 1CL 2CR 1LR

8 1LR 2LC 1RC 1CL 2CR 1LC 1CR

9 1LC 1CR 2LC 1RL 2CR 1LR

10 1LC 1CR 2LC 1RL 2CR 1LC 1CR

11 1LC 1CR 2LC 1RC 1CL 2CR 1LR

12 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1C

 3 (высота башни)

 1872 (количество сгенерированных решений)

1 1LR 2LC 1RC 3LR 1CL 2CR 1LR

2 1LR 2LC 1RC 3LR 1CL 2CR 1LC 1CR

3 1LR 2LC 1RC 3LR 1CR 1RL 2CR 1LR

4 1LR 2LC 1RC 3LR 1CR 1RL 2CR 1LC 1CR

5 1LR 2LC 1RC 3LR 1CR 2CL 1RC 2LR 1CR

6 1LR 2LC 1RC 3LR 1CR 2CL 1RC 2LR 1CL 1LR

7 1LR 2LC 1RC 3LR 1CR 2CL 1RL 1LC 2LR 1CR

8 1LR 2LC 1RC 3LR 1CR 2CL 1RL 1LC 2LR 1CL 1LR

9 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RC 2LR 1CR

10 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RC 2LR 1CL 1LR

11 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RL 1LC 2LR 1CR

12 1LR 2LC 1RC 3LR 1CL 1LR 2CL 1RL 1LC 2LR 1CL 1LR

13 1LR 2LC 1RL 1LC 3LR 1CL 2CR 1LR

14 1LR 2LC 1RL 1LC 3LR 1CL 2CR 1LC 1CR

15 1LR 2LC 1RL 1LC 3LR 1CR 1RL 2CR 1LR

16 1LR 2LC 1RL 1LC 3LR 1CR 1RL 2CR 1LC 1CR

17 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RC 2LR 1CR

18 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RC 2LR 1CL 1LR

19 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RL 1LC 2LR 1CR

20 1LR 2LC 1RL 1LC 3LR 1CR 2CL 1RL 1LC 2LR 1CL 1LR

      . . .

 1865 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL  1RC 1CL 3CR 1LR 2LC 1RL 2CR 1LR

 1866 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LR 2LC 1RL 2CR 1LC 1CR

 1867 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LR 2LC 1RC 1CL 2CR 1LR

 1868 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LR 2LC 1RC 1CL 2CR 1LC 1CR

 1869 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RL 2CR 1LR

 1870 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RL 2CR 1LC 1CR

 1871 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RC 1CL 2CR 1LR

 1872 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR 3LC 1RC 1CL 2RC 1LC 1CR 2CL 1RC 1CL 3CR 1LC 1CR 2LC 1RC 1CL 2CR 1LC 1CR

Вы можете скачать текстовый файл со всеми решениями для башни высотой 3.

Количество различных решений даже для небольших башен впечатляет. Чтобы проверить формулу, я написал программы в Turbo Pascal 7, которые генерируют решения в текстовом файле в вышеуказанном формате. Проверьте, все ли варианты уникальны, затем смоделируйте, чтобы проверить. Эту формулу можно использовать и для демонстрации решений вручную. Если хотите, можете скачать эти программы. Все должно быть понятно из комментариев в исходных файлах.