Общее·количество·просмотров·страницы

Java Dev Notes - разработка на Java (а также на JavaScript/Python/Flex и др), факты, события из АйТи

Архив блога

четверг, 30 сентября 2010 г.

Задачка на динамическое программирование: листинг операций

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

Заведем массив ops, который будет содержать в себе признаки операций для каждого числа. 1 - операция вычитания единицы, 2 - операция деления на два, 3 - операция деления на три.

Код:

public class Problem {
 
static int[] ops;
 
static int getMinSteps(int n) {
if (n==1) return 0;
else {
int[] steps = new int[n+1];
ops = new int[n+1];
steps[0] = -1;
steps[1] = 0;
ops[0] = ops[1] = -1;
for (int i=2; i<=n; i++) {
steps[i] = steps[i-1]+1;
ops[i] = 1;
if (i%2==0) {
int oldvalue = steps[i];
steps[i] = min(steps[i],steps[i/2]+1);
if (steps[i] != oldvalue) ops[i] = 2;
}
if (i%3==0) {
int oldvalue = steps[i];
steps[i] = min(steps[i],steps[i/3]+1);
if (steps[i] != oldvalue) ops[i] = 3;
}
}
return steps[n];
}
}
 
static int min(int a, int b) {
return a < b ? a : b;
}
 
public static void main(String[] args) {
if (args.length != 1) {
System.err.println("Should be exectly one argument (natural number)!");
return;
}
int n;
try {
n = Integer.parseInt(args[0]);
} catch (NumberFormatException nfe) {
System.err.println("Argument should be a natural number!");
return;
}
if (n <= 0) {
System.err.println("Wrong argument!");
return;
}
System.out.println("Minimum number of steps: " + getMinSteps(n));
printOps(n);
}
 
static void printOps(int n) {
System.out.println("Operations:");
int i=n;
while (i>1) {
if (ops[i] == 1) {
System.out.println("-1 ("+i+"-1="+(i-1)+")");
i--;
} else if (ops[i] == 2) {
System.out.println("/2 ("+i+"/2="+(i/2)+")");
i=i/2;
} else if (ops[i] == 3) {
System.out.println("/3 ("+i+"/3="+(i/3)+")");
i=i/3;
}
}
}
}


Пример вывода программы:

>java Problem 11212
Minimum number of steps: 15
Operations:
-1 (11212-1=11211)
/3 (11211/3=3737)
-1 (3737-1=3736)
-1 (3736-1=3735)
/3 (3735/3=1245)
/3 (1245/3=415)
-1 (415-1=414)
/3 (414/3=138)
/3 (138/3=46)
-1 (46-1=45)
/3 (45/3=15)
/3 (15/3=5)
-1 (5-1=4)
-1 (4-1=3)
/3 (3/3=1)

Задачка на динамическое программирование: Minimum steps to one

Формулировка задачи на английском:

On a positive integer, you can perform any one of the following 3 steps.
1.) Subtract 1 from it. ( n = n - 1 ) ,
2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 ) ,
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ).

Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
eg:
1.)For n = 1 , output: 0
2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 )
3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )


Теперь формулировка на русском языке (в моем переводе):

Дано натуральное число n (не равное нулю). Над ним можно совершить одну из трех операций:
1) вычесть единицу из него (n-1)
2) разделить на два (n/2)
3) разделить на три (n/3)

Для данного числа n найти минимальное число операций, в результате которых получается единица.
Пример:
1) n=1, ответ: 0
2) n=4, ответ: 2 (/2, /2)
3) n=7, ответ: 3 (-1, /3, /2)


Рассмотрим решение.

Для каждого данного n непонятно, какая из операций приведет к минимальному числу шагов. Поэтому нужно попробовать все варианты и выбрать из них вариант с минимальным числом шагов.
Если n == 1, то F(n) = 0.
Иначе (если n>1):
F(n) = 1 + min(F(n-1),F(n/2),F(n/3)).
При этом каждый раз нужно проверять, делится ли n без остатка на два или на три.

Решение в коде на Java:

public class Problem {
 
static int getMinSteps(int n) {
if (n==1) return 0;
else if (n==2 || n==3) return 1;
else if (n==4) return 2;
else {
int[] steps = new int[n+1];
steps[0] = -1;
steps[1] = 0;
steps[2] = steps[3] = 1;
steps[4] = 2;
for (int i=5; i<=n; i++) {
steps[i] = steps[i-1]+1;
if (i%2==0) {
steps[i] = min(steps[i],steps[i/2]+1);
}
if (i%3==0) {
steps[i] = min(steps[i],steps[i/3]+1);
}
}
return steps[n];
}
}
 
static int min(int a, int b) {
return a < b ? a : b;
}
 
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
System.out.println(getMinSteps(n));
}
}


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

вторник, 28 сентября 2010 г.

Оффтоп: Песенка студенческих отрядов

Песня студенческих отрядов:


В первые минуты Бог создал институты,
И Адам студентом первым был.
Адам был парень смелый, ухаживал за Евой,
И Бог его стипендии лишил.

У Адама драма - вызвали Адама
На проверку в божий деканат.
И на землю прямо выгнали Адама,
Так пошли студенты, говорят.

От Евы и Адама пошёл народ упрямый,
Нигде не унывающий народ.
Студент бывает весел от сессии до сессии,
А сессия всего два раза в год.

Что за предрассудки - есть три раза в сутки
И ложиться в чистую кровать?!
А мы без предрассудков едим один раз в сутки,
И на чистоту нам наплевать.

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

А есть, представьте, люди, которые нас судят.
Ну что за несознательный народ!
С наше поучите, с наше позубрите,
С наше походите на зачет.

суббота, 25 сентября 2010 г.

Загрузка данных из Google App Engine Datastore

Если понадобилось сделать полную копию данных, которые хранятся в GAE-приложении, то следует выполнить следующую команду:

./appcfg.py download_data --application=thebestapp --url=http://www.thebestapp.com/remote_api --filename=thebestapp.data

Здесь thebestapp - идентификатор приложения.

Как видим, здесь используется remote_api, поэтому его надо предварительно установить в список обработчиков URL в файле app.aml:

- url: /remote_api
script: $PYTHON_LIB/google/appengine/ext/remote_api/handler.py
login: admin


Почти аналогично эти данные закачиваются на локальный (девелоперский) сервер:


./appcfg.py upload_data --application=thebestapp --filename=thebestapp.data ~/thebestappdir --server=localhost:8080

Здесь ~/thebestappdir - каталог, откуда запускается приложение на локальном сервере.

По ссылке Uploading and Downloading Data можно подробнее прочитать о скачке и закачке данных в GAE.

UPDATE: Обновление приложения на сервере

Чтобы обновить приложение (т.е. закачать обновленные файлы приложения с локальной машины на продакшен-сервер) нужно выполнить следующую команду:

./appcfg.py upload application_dir

где application_dir - каталог, где установлено приложение.

Подробне см. ссылку: Uploading Your Application

См. также Загрузка исходного кода приложения Google App Engine

пятница, 17 сентября 2010 г.

Многопоточный сканер портов

Теперь пришел момент создать многопоточный сканер портов на Java. Это будет простая консольная утилита, которая в качестве параметров будет принимать имя или IP-адрес хоста, а также диапазон портов, которые нужно просканировать. Если диапазон не задан, то сканируются все порты от 0 до 65535.

Утилита состоит всего лишь из двух классов на Java. Рассмотрим первый класс - PortScanWorker. Этот класс является "рабочей лошадкой", в которой и осуществляется сканирование портов. Вот его код:

import java.net.*;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.io.IOException;
 
 
public class PortScanWorker implements Runnable {
 
static int globalId = 1;
 
private int id;
private List<Integer> ports;
private List<Integer> openPorts;
private InetAddress inetAddress;
private int timeout = 200;
CyclicBarrier barrier;
 
public PortScanWorker() {
id = globalId++;
}
 
public int getId() {
return id;
}
 
public void setBarrier(CyclicBarrier barrier) {
this.barrier = barrier;
}
 
public int getTimeout() {
return timeout;
}
 
public void setTimeout(int timeout) {
this.timeout = timeout;
}
 
public List<Integer> getOpenPorts() {
return openPorts;
}
 
public void setInetAddress(InetAddress inetAddress) {
this.inetAddress = inetAddress;
}
 
public void setPorts(List<Integer> ports) {
this.ports = ports;
}
 
public void run() {
//System.out.println("Started thread with id = " + id);
scan(inetAddress);
try {
barrier.await();
} catch (InterruptedException ex) {
return;
} catch (BrokenBarrierException ex) {
return;
}
}
 
void scan(InetAddress inetAddress) {
openPorts = new ArrayList<Integer>();
//System.out.println("scanning ports: ");
for (Integer port : ports) {
//System.out.print(port);
try {
InetSocketAddress isa = new InetSocketAddress(inetAddress,port);
Socket socket = new Socket();
socket.connect(isa,timeout);
System.out.println("Found opened port: " + port);
openPorts.add(port);
socket.close();
} catch (IOException ioe) {
//System.out.println("");
}
}
//System.out.println("FINISH, id = " + id);
}
}


Перед началом сканирования нужно задать несколько параметров. Первый из параметров - IP-адрес хоста, задается методом setInetAddress. Затем нужно задать список портов, которые будут сканироваться в данном потоке - это делается в методе setPorts. Наконец, нужно задать CyclicBarrier - это делается в методе setBarrier.

В методе scan происходит сканирование портов один за другим из списка ports. Если порт открыт, то он добавляется в список openPorts. После завершения работы метода scan в методе run происходит ожидание, пока остальные потоки не закончат работу. Ожидание происходит с помощью CyclicBarrier.

Теперь рассмотрим второй класс - Main:

import java.io.IOException;
import java.net.InetAddress;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;
import java.util.concurrent.CyclicBarrier;
 
public class Main {
 
public static final int MIN_PORTS_PER_THREAD = 20;
public static final int MAX_THREADS = 0xFF;
 
static InetAddress inetAddress;
static List<Integer> allPorts;
 
static List<Integer> allOpenPorts = new ArrayList<Integer>();
static List<PortScanWorker> workers = new ArrayList<PortScanWorker>(MAX_THREADS);
 
static Date startTime;
static Date endTime;
 
public static void main(String[] args) {
startTime = new Date();
 
processArgs(args);
 
if (allPorts.size()/MIN_PORTS_PER_THREAD > MAX_THREADS ) {
final int PORTS_PER_THREAD = allPorts.size()/MAX_THREADS;
 
List<Integer> threadPorts = new ArrayList<Integer>();
for (int i=0,counter=0; i<allPorts.size();i++,counter++) {
if (counter<PORTS_PER_THREAD) {
threadPorts.add(allPorts.get(i));
} else {
PortScanWorker psw = new PortScanWorker();
psw.setInetAddress(inetAddress);
psw.setPorts(new ArrayList<Integer>(threadPorts));
workers.add(psw);
threadPorts.clear();
counter=0;
}
}
PortScanWorker psw = new PortScanWorker();
psw.setInetAddress(inetAddress);
psw.setPorts(new ArrayList<Integer>(threadPorts));
workers.add(psw);
} else {
List<Integer> threadPorts = new ArrayList<Integer>();
for (int i=0,counter=0; i<allPorts.size();i++,counter++) {
if (counter<MIN_PORTS_PER_THREAD) {
threadPorts.add(allPorts.get(i));
} else {
PortScanWorker psw = new PortScanWorker();
psw.setInetAddress(inetAddress);
psw.setPorts(new ArrayList<Integer>(threadPorts));
workers.add(psw);
threadPorts.clear();
counter=0;
}
}
PortScanWorker psw = new PortScanWorker();
psw.setInetAddress(inetAddress);
psw.setPorts(new ArrayList<Integer>(threadPorts));
workers.add(psw);
}
 
System.out.println("Ports to scan: "+allPorts.size());
System.out.println("Threads to work: "+workers.size());
 
Runnable summarizer = new Runnable() {
public void run()
{
System.out.println("Scanning stopped...");
 
for (PortScanWorker psw : workers) {
List<Integer> openPorts = psw.getOpenPorts();
allOpenPorts.addAll(openPorts);
}
 
Collections.sort(allOpenPorts);
 
System.out.println("List of opened ports:");
for (Integer openedPort : allOpenPorts) {
System.out.println(openedPort);
}
 
endTime = new Date();
 
System.out.println("Time of run: " + (endTime.getTime() - startTime.getTime()) + " ms");
}
};
 
CyclicBarrier barrier = new CyclicBarrier(workers.size(),summarizer);
 
for (PortScanWorker psw : workers) {
psw.setBarrier(barrier);
}
 
System.out.println("Start scanning...");
 
for (PortScanWorker psw : workers) {
new Thread(psw).start();
}
}
 
static void processArgs(String[] args) {
if (args.length < 1) {
usage();
System.exit(1);
}
 
String host = args[0];
try {
inetAddress = InetAddress.getByName(host);
} catch (IOException ioe) {
System.out.println("Error when resolving host!");
System.exit(2);
}
 
System.out.println("Scanning host "+host);
 
int minPort = 0;
int maxPort = 0x10000-1;
 
if (args.length==2) {
if (args[1].indexOf("-")>-1) {
// range of ports pointed out
String[] ports = args[1].split("-");
try {
minPort = Integer.parseInt(ports[0]);
maxPort = Integer.parseInt(ports[1]);
} catch (NumberFormatException nfe) {
System.out.println("Wrong ports!");
System.exit(3);
}
} else {
// one port pointed out
try {
minPort = Integer.parseInt(args[1]);
maxPort = minPort;
} catch (NumberFormatException nfe) {
System.out.println("Wrong port!");
System.exit(3);
}
}
}
 
allPorts = new ArrayList<Integer>(maxPort-minPort+1);
 
for (int i=minPort; i<=maxPort; i++) {
allPorts.add(i);
}
}
 
static void usage() {
System.out.println("Java Port Scanner usage: ");
System.out.println("java Main host port");
System.out.println("Examples:");
System.out.println("java Main 192.168.1.1 1-1024");
System.out.println("java Main 192.168.1.1 1099");
System.out.println("java Main 192.168.1.1 (this scans all ports from 0 to 65535)");
}
}
 


Сначала в методе main происходит разбор аргументов с помощью метода processArgs. Также в методе processArgs заполняется массив allPorts, который содержит список всех портов, которые надо отсканировать.

Затем, после processArgs идет создание (но не запуск!) объектов потоков (класс PortScanWorker). Каждому объекту устанавливается хост и список портов, которые надо отсканить. Максимальное количество потоков, которое будет работать - 256 (параметр MAX_THREADS). Минимальное количество портов на один поток - 20 (параметр MIN_PORTS_PER_THREAD). В зависимости от того, какое ограничение будет выполнено, и создается список потоков. Все объекты-потоки сохраняются в список workers. После того, как все создано, выводится статистика по общему количеству портов, которое надо отсканить и количеству потоков, которое будет это делать:

System.out.println("Ports to scan: "+allPorts.size());
System.out.println("Threads to work: "+workers.size());


Затем создается барьер:

CyclicBarrier barrier = new CyclicBarrier(workers.size(),summarizer);


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

Runnable summarizer = new Runnable() {
public void run()
{
System.out.println("Scanning stopped...");
 
for (PortScanWorker psw : workers) {
List<Integer> openPorts = psw.getOpenPorts();
allOpenPorts.addAll(openPorts);
}
 
Collections.sort(allOpenPorts);
 
System.out.println("List of opened ports:");
for (Integer openedPort : allOpenPorts) {
System.out.println(openedPort);
}
 
endTime = new Date();
 
System.out.println("Time of run: " + (endTime.getTime() - startTime.getTime()) + " ms");
}
};


В этом Runnable и происходит все завершение работы. Найденные открытые порты копируются в общий список allOpenPorts, который затем сортируется и выводится на экран. Затем подсчитывается общее время работы, которое также выводится на экран. После этого программа завершает работу.

Но вернемся к созданному барьеру. После того, как барьер был создан, мы его устанавливаем для каждого PortScanWorker. И теперь, после того, как барьер установлен, ничего не мешает нам запустить потоки в работу:

for (PortScanWorker psw : workers) {
new Thread(psw).start();
}


Вот пример вывода программы:


Scanning host 192.168.1.1
Ports to scan: 65536
Threads to work: 256
Start scanning...
Found opened port: 80
Found opened port: 1900
Scanning stopped...
List of opened ports:
80
1900
Time of run: 51479 ms

Однопоточный сканер портов

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

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

Код сканера:

import java.net.*;
import java.util.ArrayList;
import java.util.List;
import java.io.IOException;
 
 
public class PortScanner {
 
private int minPort = 1;
private int maxPort = 0x10000;
private String host = "192.168.1.104";
private int timeout = 100;
 
public int getTimeout() {
return timeout;
}
 
public void setTimeout(int timeout) {
this.timeout = timeout;
}
 
public int getMinPort() {
return minPort;
}
 
public void setMinPort(int minPort) {
this.minPort = minPort;
}
 
public int getMaxPort() {
return maxPort;
}
 
public void setMaxPort(int maxPort) {
this.maxPort = maxPort;
}
 
public String getHost() {
return host;
}
 
public void setHost(String host) {
this.host = host;
}
 
public List<Integer> scan() {
try {
InetAddress ia = InetAddress.getByName(getHost());
return scan(ia);
} catch (IOException ioe) {
return null;
}
}
 
List<Integer> scan(InetAddress inetAddress) {
List<Integer> openPortsList = new ArrayList<Integer>(0xFF);
System.out.println("scanning ports: ");
for (int port = minPort; port <= maxPort; port++) {
System.out.print(port);
try {
InetSocketAddress isa = new InetSocketAddress(inetAddress,port);
Socket socket = new Socket();
socket.connect(isa,timeout);
System.out.println(" opened");
openPortsList.add(port);
socket.close();
} catch (IOException ioe) {
System.out.println("");
}
}
return openPortsList;
}
 
public static void main(String[] args) {
if (args.length < 1) {
usage();
return;
}
 
String host = args[0];
System.out.println("Scanning host "+host);
 
PortScanner scanner = new PortScanner();
 
if (args.length==2) {
if (args[1].indexOf("-")>-1) {
// range of ports pointed out
String[] ports = args[1].split("-");
try {
int minPort = Integer.parseInt(ports[0]);
int maxPort = Integer.parseInt(ports[1]);
scanner.setMinPort(minPort);
scanner.setMaxPort(maxPort);
} catch (NumberFormatException nfe) {
System.out.println("Wrong ports!");
return;
}
} else {
// one port pointed out
try {
int port = Integer.parseInt(args[1]);
scanner.setMinPort(port);
scanner.setMaxPort(port);
} catch (NumberFormatException nfe) {
System.out.println("Wrong port!");
return;
}
}
}
 
scanner.setHost(host);
List<Integer> openPortsList = scanner.scan();
if (openPortsList != null) {
if (openPortsList.size() >0) {
System.out.println("List of opened ports:");
for (Integer openedPort : openPortsList) {
System.out.println(openedPort);
}
} else {
System.out.println("No opened ports!");
}
} else {
System.out.println("Error happened!");
}
}
 
static void usage() {
System.out.println("Java Port Scanner usage: ");
System.out.println("java PortScanner host port");
System.out.println("Examples:");
System.out.println("java PortScanner 192.168.1.100 1-1024");
System.out.println("java PortScanner 192.168.1.100 1099");
System.out.println("java PortScanner 192.168.1.100 (this scans all ports from 1 to 0x10000)");
}
}


Все действие происходит в методе scan. В общем, там все довольно понятно, так что, мне кажется, объяснения излишни. Code is the best document!

П.С. Хороший открытый сканер портов на Java - Angry IP Scanner.

Постоянные читатели