понедельник, 16 июля 2012 г.
суббота, 2 июня 2012 г.
понедельник, 7 мая 2012 г.
Поиск кратчайшего пути в лабиринте
Моя реализация волнового алгоритма Ли.
Лабиринт хранится в файле in.txt. (# - стена; S - старт; G - финиш; свободный сектор - точка или пробел)
В результате: в командную строку выводится количество шагов
в файл out.txt выводится лабиринт и все кратчайшие пути
Лабиринт хранится в файле in.txt. (# - стена; S - старт; G - финиш; свободный сектор - точка или пробел)
В результате: в командную строку выводится количество шагов
в файл out.txt выводится лабиринт и все кратчайшие пути
/*
Входной файл: in.txt
Выходной файл: out.txt
Условные обозначения во входном и выходном файлах:
'.' = доступная позиция
'#' = стена
'S' = старт
'G' = финиш
'+' = путь
*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <dos.h>
#include <windows.h>
#include <stdio.h>
#define FALSE 0
#define TRUE 1
//максимальный размер лабиринта
#define MAX_NROWS 80
#define MAX_MCOLS 160
int nRows=0;
int mCols=0;
char maze[MAX_NROWS][MAX_MCOLS]={'#'}; //матрица-лабиринт
int steps[MAX_NROWS][MAX_MCOLS]={0};//матрица расстояний от старта
//до всех возможных точек
int find_min_path(int x,int y);
int find_path(int x, int y,int step);
//функция загрузки лабиринта из файла в массив
int load() {
FILE *f;
if ((f = fopen("in.txt","r"))==NULL)
return FALSE;
char ch;
int i=0,j=0;
do {
do {
ch = fgetc(f);
if (ch==' ') //пробелы заменяем на точки
ch='.';
maze[i][j]=ch;
if (i>MAX_NROWS || j>MAX_MCOLS)
return FALSE;
if (j>mCols)
mCols=j;
j++;
} while (ch!='\n' && ch!=EOF);
j=0;
i++;
if (i>nRows )
nRows=i;
} while (!feof(f));
fclose(f);
return TRUE;
}
// функция сохранения результата в файл
//(лабиринт со всеми кратчайшими путями)
int save() {
FILE *f;
f = fopen("out.txt","a+");
for (int i = 0; i <nRows;i++ )
{
for (int j = 0; j <mCols;j++ )
{
fputc(maze[i][j],f);
}
fputc('\n',f);
}
fputs("\n\n",f);
fclose(f);
}
//функция нахождения произвольного символа в лабиринте
//(для нахождения координат старта и финиша)
void findSymbol(int &x,int &y,char Symbol) {
for (int i = 0; i <nRows;i++ )
{
for (int j = 0; j <mCols;j++ )
{
if (maze[i][j]==Symbol){
x=i;
y=j;
return;
}
}
}
}
int num = 0; //минимальное количество шагов
int main(void)
{
load();
int x=0,y=0;
findSymbol(x,y,'S');
find_path(y, x,0);
findSymbol(x,y,'G');
find_min_path(y,x);
printf("Success!\n");
save();
printf("Steps: %i\n",num);
getch();
return 0;
}
//рекурсивная функция заполнения матрицы расстояний
int find_path(int x, int y,int step)
{
//если вышли за пределы лабиринта - возвращаемся
if ( x < 0 || x > mCols - 1 || y < 0 || y > nRows - 1 ) return FALSE;
//если дошли до финиша - возвращаемся
if ( maze[y][x] == 'G' ) return FALSE;
//если наткнулись на стену - возвращаемся
if (maze[y][x] == '#') return FALSE;
//если путь свободен - увеличиваем количество шагов
//и запоминаем его в мацциве
if (maze[y][x]!='S' && maze[y][x]!='G') {
step++;
if (steps[y][x]>step || steps[y][x]==0)
{
steps[y][x]=step;
}
}
//4 напровления - 4 вызова
//идем в определенном направлении если мы там еще не были
//(расстояние м матрице расстояний==0)
//или соблюдаются все условия:
//1) расстояние там больше текущего+1
//2) расстояние там не рамно текущее-1
//(что бы не пойти обратно тому же пути)
if (maze[y][x+1]!='S')
if ((steps[y][x+1]>(step+1) && steps[y][x+1]!=(step-1)) || steps[y][x+1]==0)
if ( find_path(x + 1, y,step) == TRUE ) return FALSE;
if (maze[y][x-1]!='S')
if ((steps[y][x-1]>(step+1) && steps[y][x-1]!=(step-1) ) || steps[y][x-1]==0)
if ( find_path(x - 1, y,step) == TRUE ) return FALSE;
if (maze[y+1][x]!='S')
if ((steps[y+1][x]>(step+1) && steps[y+1][x]!=(step-1) ) || steps[y+1][x]==0)
if ( find_path(x, y + 1,step) == TRUE ) return FALSE;
if (maze[y-1][x]!='S')
if ((steps[y-1][x]>(step+1) && steps[y-1][x]!=(step-1) ) || steps[y-1][x]==0)
if ( find_path(x, y - 1,step) == TRUE ) return FALSE;
return FALSE;
}
//рекурсивная функция, обходящаа лабиринт с финиша до старта
//по кратчайшему пути
int find_min_path(int x,int y)
{
//если вышли за пределы лабиринта - возвращаемся
if ( x < 0 || x > mCols - 1 || y < 0 || y > nRows - 1 ) return FALSE;
//если данная позиция - не старт и не финиш, то помечаем ее как путь
if (maze[y][x]!='S' && maze[y][x]!='G') {
maze[y][x] = '+';
}
//если дошли до старта - возвращаемся
if ( maze[y-1][x] == 'S' ) return FALSE;
if ( maze[y+1][x] == 'S' ) return FALSE;
if ( maze[y][x-1] == 'S' ) return FALSE;
if ( maze[y][x+1] == 'S' ) return FALSE;
//изнаем расстояния во всех 4-х направлениях
int up = 0;
int right =0;
int left = 0;
int down = 0;
if (y!= 0)
up = steps[y - 1][x];
if (x!= 0)
left =steps[y][x - 1];
if (x!= mCols-1)
right = steps[y][x+1];
if (y!= nRows-1)
down = steps[y+1][x];
//и ищем минимальное
int min = up;
if ((right<min && right!=0) || min==0)
min = right;
if ((left<min && left!=0)|| min==0)
min = left;
if ((down<min && down!=0) || min==0)
min = down;
if (num==0 )
num=min;
//там, где минимальное, туда и идём
if (up==min && up!=0)
if ( find_min_path(x,y - 1) == TRUE ) return TRUE;
if (right==min && right!=0 )
if ( find_min_path(x + 1,y) == TRUE ) return TRUE;
if (left==min && left!=0)
if ( find_min_path(x - 1,y) == TRUE ) return TRUE;
if (down==min && down!=0)
if ( find_min_path(x,y + 1) == TRUE ) return TRUE;
return FALSE;
}
понедельник, 16 апреля 2012 г.
Полезные сайты
http://www.hash-database.net/find.php - разшифровка хэшей по словарю.
http://home.paulschou.net/tools/xlate/ - перевод bin<->hex<->ASCII<->Text<->Base64<->hash
http://home.paulschou.net/tools/xlate/ - перевод bin<->hex<->ASCII<->Text<->Base64<->hash
пятница, 6 апреля 2012 г.
Словарь басовых грувов: Death Metall
Характерные черты: Экстримально быстрые темпы Медиаторная (переменный штрих) и трехпальцевая техника Очень сложные рифы Альтернативные строи инструментов
Представители: Steve DiGiorgio ( Death) Shane Embuty (Napalm Death) Chris Richards Frank Watkins (Obituary) Alex Webster (Cannibal Corpse)
Вот что сказал в дез-метале известный продюсер Скотт Берн: "Что-что, а динамика уж точно не является характерной чертой дез-метала: это очень громкая музыка с начала и до конца песни. Эта музыка очень простая и жестокая (брутальная). Пения в классическом понимании здесь нет - только гортанные звуки."(перевод кривой, но смысл передаёт). Эта фраза очень точно описывает данное музыкальное направление. Death Metall - пожалуй, один из самых экстремальных поджанров металла (да и музыки в целом). У деза много противников, в основном из-за текста песен и различных выходок музыкантов, однако он очень популярен и имеет огромное количество поклонников. Дез-металл, пожалуй, самый технически-сложный музыкальный стиль.
Гармония:
Дез-метал установил собственные стандарты для гармонии песен: повсеместное использование тритонов, несвязанные аккорды, очень сложные рифы и экстремальный хроматизм. Часто используется уменьшенное арпеджио и тоновые переходы. Дэт-метал известен своей неровной сменой музыкального темпа и размера, чрезвычайно быстрой и сложной гитарной игрой и двойными басовыми барабанными партиями. Типично использование бласт-бита для добавления звуку мощи.
Техника:
Популярен медиатор и трехпальцевая техника (все способы хороши, чтобы играть 100500 нот в секунду).
Звучание:
Бас глубокий и часто перегруженный. Особой эффект иногда достигается вырезанием середины при помощи эквалайзера. Строй баса опускают до предела: чем тяжелее звучит инструмент - тем лучше.
Пример:
11_-_Track_11.mp3
четверг, 29 марта 2012 г.
Словарь басовых грувов: Progressive Metall
Характерные черты: Самые различные размеры и тональности Техничность Мелодическая независимость Постоянно развивающаяся гармония Пальцевая техника
Представители: Joe Dibiase (Fates Warning) Doug Keyser John Myung (Dream Theater) Peter Nordin Joey Vera (Armored Saint)Прогрессивный металл - ответвление тяжелого металла, характеризующееся расширенным форматом песен, разнообразием тональностей и размеров. В прогрессивном металле стали часто использоваться клавиши и другие инструменты, не входящие в стандартный набор тяж-мета (барабаны, бас, две гитары). Прогрессивный металл позаимствовал у прог-рока сложную структуру песен и страсть к экспериментам, но отличается от него более быстрыми темпами и тяжелым, перегруженным звуком. Как и в случае с роком, очень тяжело сказать, какой метал является "прогрессивным". Единственное, что объединяет все прогрессивные группы - желание сделать что-то новое, начать новую главу в музыке, записать то, чего раньше никто не слышал, открыть новые способы выражения музыкальной мысли. У прогрессивного металла всегда были преданные фанаты, хоть их и не очень много. Чаще всего они сами являлись музыкантами. Сейчас популярность прогрессивного метала постоянно растет (в первую очередь в андеграунде).
Гармония:
В прогрессивном металле использовалось всё от чистой диатонической гармонии до различных экзотических гамм и ладов. Единственная константа - это то, что гармония всегда разнообразная и никогда не стоит на месте. Бас часто мелодически независимый.
Техника:
Прогрессивные басисты часто ориентируются на высокотехничное исполнение. Чаще всего играют пальцами, хотя иногда встречаются басисты, использующие медиатор. Пальцы дают большую универсальность, а медиатор позволяет получать более агрессивный звук.
Звучание:
Бас обычно глубокий и полный, часто перегруженный дисторшеном. Используются и другие эффекты, но очень умеренно (преимущество отдаётся технике, а не звучанию).
Пример:
10_-_Track_10.mp3
Словарь басовых грувов: Heavy Metall
Характерные черты: Быстрые темпы Тяжелый, часто перегруженный звук Медиатор и трехпальцевая техника Галоп Нестандартный строй инструмента
Представители: Geezer Butler (Black Sabbath, Оззи Осборн) Cliff Burton (Metallica) Steve Harris (Iron Maiden) Rudy Sarzo (Quiet Riot)
Тяжелый металл - агрессивный, более быстрый и перегруженный потомок рока. Ранние группы, такие как Black Sabbath, Motorhead, Saxon, Talus и Deep Purple создали основу современного металла, внеся много нового в музыку. Именно эти группы ввели в обиход многое из того, что сейчас определяет металл, как музыкальный стиль ("все гитарные рифы уже когда-то были придуманы Black Sabbath"). Инновации коснулись техники игры на гитаре, обработки звука, гармонии, ритма и мелодии.
Ведущие гитаристы играли невиданные ранее соло, в то время как ритм-гитаристы уже не были просто "дополнительными музыкантами" - они создавали аккомпанемент, в большой степени определяющий стиль музыки, играя при этом очень важную роль (в принципе, отсюда пошло явное разделение на ритм-гитару и соло-гитару: солист бегал вверху грифа, играя головокружительные пассажи или просто мелодию; ритм-гитарист, в свою очередь, заполнял середину и создавал гармоническую и ритмическую основу песни).
Бас всё еще не был в центре внимания и часто просто повторял партию ритм-гитары, хотя некоторые басисты всё таки выделялись своими соло и сумасшедшей техникой. Встречалось также, что басовая партия являлась ведущей и фактически создавала песню. Бывало это редко, но метко (вспомнить хотя бы Клифа Бёртона из Металлики и его басовую партию в песне Orion).
Гармония:
Металлические песни в основном строились на мажорных и минорных пентатониках. Использовались также звучащие более экзотически гармонический минор и фригийский лад. Часто использовался тритон, благодаря своему специфическому звучанию. Аккорды могли использоваться самые разнообразные, однако невероятно популярным стал нейтральный power-аккорд (практически каждая ритм-партия строилась на таких аккордах).
Техника:
Часто играли медиатором, что позволяло держать быстрые темпы. Стала очень популярна трёхпальцевая техника игры (тремя пальцами очень удобно играть характерный для металла галоп).
Звучание:
Звучание баса часто очень глубокое и плотное. Часто используется перегруз(distortion) для получения еще более тяжелого звука в сочетании с гитарами. В практику вошло использование нестандартных строев (практически всегда в сторону понижения) (тот же drop-D).
Пример:
09_-_Track_09.mp3
Подписаться на:
Сообщения (Atom)