На чём и как писать (часть 1. Eclipse и Java)
…
В продолжение предыдущего поста.
Оговорюсь сразу: нет,я не пытаюсь унизить этими картинками Java или C++. Или вообще сказать, что такой-то язык лучше сякого-то языка. Я лишь хочу показать, что для разных задач разные языки являются удобнее. В этом топике можно прочесть советы по выбору IDE для олимпиадного программмирования и Будет рассмотрена часть случаев, когда Java удобнее.
IDE
Казалось бы, к чему тут IDE? А вот к чему: компьютер, на котором Вы будете писать на ACM, будет совсем не ваш. И совсем такой же, как у ещё 9000 соревнующихся. И вполне возможно, что Вашей любимой, возможно экзотической, среды разработки там не будет. А будет там вот что:Borland Delphi 7.0— с 2009 года отсутствует- Microsoft Visual Studio 2005 Express Edition, C/C++
- Java 2 SDK 6.0
- Eclipse
- Far Manager 1.7b5
- MinGW (GNU C/C++)
Итак, выбор не велик. Морально устаревшая версия MS VS и Eclipse. Кстати, всегда последней версии. Ну и Far, но это не IDE. Поэтому я наберусь наглости и буду писать исключительно об Eclipse.
Шаблоны
Пожалуй, первое, чему нас учили — создавать шаблон в Eclipse. Шаблоны позволяют быстро, очень быстро создать каркас для написания программы. Такой, что достаточно написать три-четыре буквы от имени шаблона, нажать сочетание кнопок(Ctrl + Spacebar) и обнаружить в окне редактора уже полностью готовый каркас для программы. О том, как их создавать, можно почитать тут.Кнопочки + другие кнопочки ( + ещё другие кнопочки)
Комбинации клавиш — то, за что олимпиадники любят Eclipse. Всегда есть возможность нажать Ctrl + Spacebar и воспользоваться великой автоподстановкой (пользователи Visual Studio знают это под именем IntelliSense). Можно выделить код, нажать Ctrl + / И за/раскоментировать его. Можно нажать Ctrl + Alt + ↓ или ↑ чтобы скопировать текущую строку вверх или вниз, можно нажать Ctrl + D чтобы удалить текущую строчку… А можно залезть в настройки, отыскать там список сочетаний, и запомнить нужные.Как и когда писать на Java
Первое, с чем нужно разобраться при олимпиадном программировании на Java — это захапать себе большой стек, для чего запускаться в отдельном потоке. Второе — научиться быстро читать и писать данные. Я приведу свой текущий шаблон для Eclipse, снабдив его предварительно комментариями. Если что-то непонятно, то я могу пояснить.import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
// ${primary_type_name} - имя класса, его подставляет Eclipse. Очень хорошая идея - создавать класс с именем входного и выходного файлов.
// Правда они почти всегда с маленькой буквы, но это можно пережить.
public class ${primary_type_name} implements Runnable {
StringTokenizer st; // Этот класс быстро умеет разбивать скормленную ему строчку. По умолчанию разделитель - пробел
BufferedReader in; // Этот класс ОЧЕНЬ быстро умеет считывать данные из какого-либо потока
PrintWriter out; // Этот класс умеет писать данные, тоже быстро.
public static void main(String[] args) {
new Thread(new ${primary_type_name}()).start(); //Нам нужен большой стек, так что заведём новый поток.
}
public void run() {
try {
in = new BufferedReader(new FileReader("${primary_type_name}.in"));
out = new PrintWriter(new FileWriter("${primary_type_name}.out"));
solve();
} catch (Exception e) {
//Если есть исключение - выходим с кодом ошибки. Вместо 9000 может быть что угодно, не равное нулю.
System.exit(9000);
} finally {
//Не забываем про закрытие файла.
out.flush();
out.close();
}
}
//Получаем следующий токен
String nextToken() throws IOException {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}
//Следующее 32-битное целое число
int nextInt() throws NumberFormatException, IOException {
return Integer.parseInt(nextToken());
}
//...
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(nextToken());
}
//... Что бы вы думали?
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(nextToken());
}
void solve() throws NumberFormatException, IOException {
//А тут уже пишем решение задачи.
}
}
Отлично! Теперь мы готовы решить нашу (возможно, первую) олимпиадную задачу на Java. Выберем что-нибудь простое, но требующее именно этого языка. Путь это будет №1196 с Тимуса. Внимательно прочитайте условие и немного подумайте над решением, прежде чем возвращаться к этой статье. Предположим на секунду, что среди читателей какой-то
int n = nextInt();
int[] teachers = new int[n];
for(int i = 0; i < n; i ++)
teachers[i] = nextInt();
int m = nextInt();
int result = 0;
for(int i = 0; i < m; i ++) {
int students = nextInt();
for(int j = 0; j < n; j ++)
if(teachers[j] == students) {
result ++; break;
}
}
out.println(result);int n = nextInt();
TreeSet<Integer> teachers = new TreeSet<Integer>();
for(int i = 0; i < n; i ++)
teachers.add(nextInt());
int m = nextInt();
int result = 0;
for(int i = 0; i < m; i ++)
if(teachers.contains(nextInt()))
result ++;
out.println(result);Как видите, получилось даже меньше кода, чем при решении «в лоб». Второй же способ использует встроенные быструю сортировку и двоичный поиск Java:
int n = nextInt();
int[] teachers = new int[n];
for(int i = 0; i < n; i ++)
teachers[i] = nextInt();
Arrays.sort(teachers);
int m = nextInt();
int result = 0;
for(int i = 0; i < m; i ++) {
int students = nextInt();
int pos = Arrays.binarySearch(teachers, students);
if(pos > 0 && pos < teachers.length && teachers[pos] == students)
result ++;
}
out.println(result);Оба решения, очевидно, работают за O(n⋅logn + m⋅logn) = O((m + n)logn). А если не очевидно, то нужно бы
To be Continued
… Нажав на кнопку «предпросмотр» я ужаснулся обилию текста, и решил, что стоит разнести эту тему на два топика. Так что ждите во второй части рассказ о том, как и когда писать на C/C++ и разбор характерной задачи.
* All source code was highlighted with Source Code Highlighter.
комментарии (91)