Monthly Archives: Сентябрь 2014

Перебор всех возможных вариантов

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

Для начала придумаем задачу, на примере которой будем рассматривать алгоритмы.
Пусть у нас имеется множество S, состоящее из 4-х элементов: * + /, и наша задача — перебрать все возможные комбинации из 3-х элементов, используя элементы множества S. Причем, выбираемые элементы могут повторяться. Например: «+*+».

Первый алгоритм

Сопоставим каждому элементу число, начиная с 0.
* — 0
— 1
+ — 2
/ — 3

Можно догадаться, что нужно перебрать элементы от 0 0 0 до 3 3 3:
0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 0 1


3 2 3
3 3 0
3 3 1
3 3 2
3 3 3

Всего получится 64 варианта (4 * 4 * 4 = 64)

Далее нужно провести обратную операцию, сопоставив числу элемент множества S.
Например, набору 2 0 2 соответствует +*+

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

Реализация:

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов
int size = 3;//кол-во элементов
int arr[] = new int[size];//массив для хранения текущего варианта множества
outer: while(true){//вечный цикл
 
	//вывод варианта множества на экран
	for(int ndx : arr){
		System.out.print(abc[ndx]);
	}
	System.out.println();
 
	int i = size - 1;//ставим курсов в самую правую ячейку
	while(arr[i] == abc.length - 1){//движемся влево, если ячейка переполнена
		arr[i] = 0;//записываем в ячейку 0, т.к. идет перенос разряда
		i--;//сдвиг влево
		//если перенос влево невозможен, значит перебор закончен
		if(i < 0)break outer;
	}
	arr[i]++;//увеличиваем значение ячейки на единицу
}

В результате программа выведет все 64 варианта:

***
**-
**+
**/
*-*
*--
...
...
/++
/+/
//*
//-
//+
///

Второй алгоритм
Для начала посчитаем сколько всего возможных комбинаций, это число равно n ^ k, где n — это размер алфавита (кол-во допустимых символов), а k — кол-во элементов в комбинации.
Для нашего множества S, состоящего из *,,+ и /, n равно 4. И т.к. нужно перебрать все комбинации из трех элементов, то k равно 3.
Получаем: n ^ k = 4 ^ 3 = 64.
В итоге мы должны получить 64 комбинации.
Вот если бы существовал способ преобразования номера комбинации в элементы комбинации.
И такой способ существует: для этого нужно номер комбинации преобразовать в k-значное число в системе счисления по основанию n.
Первой комбинации будет соответствовать число 0, а последней 63.
Перебирая числа от 0 до 63, нам нужно каждое число преобразовать в число в систему счисления по основанию 4. Для получения разрядов числа нужно целочисленно разделить число на 1, 4, 16 (т.е. n^0, n^1, n^2) и результат взять по модулю n.
Пример: для числа 57 при k = 3 и n = 4
(57 / 1) % 4 = 57 % 4 = 1 (-)
(57 / 4) % 4 = 14 % 4 = 2 (+)
(57 / 16) % 4 = 3 % 4 = 3 (/)
Т.е. комбинации под номером 57 соответствует комбинация -+/

char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов (алфавит)
int N = abc.length;//N - размер алфавита
int K = 3;//кол-во элементов в комбинации
 
int pow[] = new int[K + 1];//массив для степеней числа N: N^0, N^1, .., N^K   
pow[0] = 1;
for (int i = 1; i <= K; i++) {//вычисляем степени числа N
	pow[i] = pow[i - 1] * N
}
 
//перебираем все номера комбинаций
for (int i = 0; i < pow[K]; i++) {
	char arr[] = new char[K];
	//вычисляем элементы комбинации
	for (int j = 0; j < K; j++) {
		//каждый элемент получаем из массива abc по индексу,
		//индекс - это число в системе счисления по основанию N (0..N-1)
		//в соответствующем разряде j (от 0 до K-1 включительно)
		arr[j] = abc[(i / pow[j]) % N];
	}
	//вывод в консоль
	for(char ch : arr){
		System.out.print(ch);
	}
	System.out.println();
}

Вывод программы:

0 ***
1 -**
2 +**
3 /**
4 *-*
.....
57 -+/
58 ++/
59 /+/
60 *//
61 -//
62 +//
63 ///

В данном алгоритме перебор идет как бы слева направо, но это не важно, т.к. мы перебираем все комбинации.

No Carrier на Google Play

После публикации приложения на Google Play выяснилось, что на планшетах заказчика приложение не поддерживается. Причем мой планшет Asus поддерживается, а Samsung Galaxy Tab 4 не поддерживается, хотя там и там Android 4.4.2.
Если на Samsung Galaxy Tab искать приложение в Google Play, то оно не находится, т.к. не поддерживается. Если зайти на страничку приложения по ссылке, то можно увидеть сообщение «No Carrier». Сразу поняли, что дело в телефонных вызовах. У нас в приложении есть возможность набрать номер службы поддержки, поэтому в манифесте прописано разрешение:

<uses-permission android:name="android.permission.CALL_PHONE" />

Сперва подумали, что нужно вставить в планшет нормальную симку, а не LTE, но мой планшет вообще устанавливал приложение с Google Play без симки.
В итоге: где-то вычитал, что некоторые планшеты почему-то не могут совершать звонки.
Т.к. в нашем приложении вызов службы поддержки — это вспомогательный функционал, то прописали в манифесте необязательность телефонных вызовов:

<uses-feature android:name="android.hardware.telephony" android:required="false" />

После того, как прописали необязательность телефонных звонков, в Google Play к 5200-м поддерживаемым устройствам добавилось еще 500 устройств, в том числе Samsung Galaxy Tab 4. Проблема решилась!

Соответствие разрешений (uses-permission) и функций (uses-feature) можно посмотреть здесь:
http://developer.android.com/guide/topics/manifest/uses-feature-element.html#permissions-features

Карточная игра «Верю — не верю»

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

Правила можно посмотреть в Википедии

Я сделал упрощенную версию из 36 карта без джокеров. Игра написана на Visual Basic 6.0 более 10 лет назад и с тех пор не поддерживалась.
Выкладывают приложение как есть. В Windows 8 местами появилась проблема с кодировкой.
В игре три соперника: вы и два компьютера, причем каждый играет только за себя. Что очень важно: компьютер не смотрит ваши карты!

Скачать Верю-не верю

Сперва появится окно, где нужно указать свое имя:
01 login

Далее откроется главное окно:
02 main page

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

Выкладываю также исходный код. Ценности он, может, ни какой и не представляет, но все же…
Скачать исходный код

Перебор всех подмножеств заданного множества (Java)

Пусть дано множество, состоящее из четырех элементов: {a,b,c,d}.
Необходимо перебрать все возможные подмножества данного множества:
1) {} — пустое множество
2) {a}
3) {b}
4) {a,b}
5) {c}
6) {a,c}
7) {b,c}
8) {a,b,c}
9) {d}
10) {a,d}
11) {b,d}
12) {a,b,d}
13) {c,d}
14) {a,c,d}
15) {b,c,d}
16) {a,b,c,d}

Причем подмножества {a,b} и {b,a} считаются одним и тем же подмножеством.

Данную задачу будем решать с использованием битовых масок и битовых операций.
Сразу приведу реализацию:

char arr[] = new char[]{'a','b','c','d'};
int N = arr.length;
for (int mask = 0; mask < (1 << N); mask++) {//перебор масок			
	for (int j = 0; j < N; j++) {//перебор индексов массива
		if((mask & (1 << j)) != 0){//поиск индекса в маске
			System.out.print(arr[j] + " ");//вывод элемента
		}
	}
	System.out.println();//перевод строки для вывод следующего подмножества
}

А теперь пояснения.
1 << N — побитовый сдвиг единицы на N позиций влево.
В двоичном виде единица выглядит так 00000001. В нашем случае N = 4.
После сдвига на 4 позиции влево появится новое число, двоичный вид которого 00010000. Теперь, если вычесть из этого числа единицу получим: 00001111. Если опустить ведущие нули, то получим 1111. Четыре единицы — это состояние, когда в подмножество попадают все элементы, 0000 — пустое множество, 1010 — подмножество состоит из первого и третьего элемента множества (нумерация с нуля, отсчет ведется справа) и т.д.
Т.е. мы перебираем числа, двоичное представление которых от 0000 до 1111.

После того как мы получили маску (mask), необходимо узнать в каких позициях стоят единицы. Проверять будем следующим образом.
Например, на каком-то шаге цикла программы маска равна 1100, мы перебираем все позиции путем сдвига единицы: 0001, 0010, 0100 и 1000. Для проверки воспользуемся операцией побитового И (если в одинаковых позициях стоят единицы, то результат единица, иначе ноль). В Java обозначается как &
В нашем случае:
1100 & 0001 = 0000
1100 & 0010 = 0000
1100 & 0100 = 0100
1100 & 1000 = 1000
Т.е. если в итоге получилось число отличное от нуля, то включаем элемент в множество.
0100 — включаем в множество элемент с индексом 2
1000 — включаем в множество элемент с индексом 3
Нумерация с нуля и справа.
Результат работы программы (первая строка пустая — это пустое множество):


a 
b 
a b 
c 
a c 
b c 
a b c 
d 
a d 
b d 
a b d 
c d 
a c d 
b c d 
a b c d 

В данной реализации мы хранили маски в типе int.
(1 << 30) равно 1 073 741 824 Безопасное значение N для типа int: 30. Свыше 30 будет переполнение переменных типа int, поэтому нужно использовать long.
При N > 30 перебор будет ощутимо все медленнее и медленнее.

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

1L << j

Т.е. нужно к единице приписать L, и тогда результат операции будет long, в противном случае будет int с переполнением.