Ключевое слово
09 | 04 | 2020
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 09 Июнь 2010 19:10 #31

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Не очень понял. Комбинаторно предлагаете? Есть очень простое решение.

алгоритмические задачки 09 Июнь 2010 23:00 #32

  • AlekseiNK
  • AlekseiNK's Avatar
  • OFFLINE
  • Гроссмейстер
  • Posts: 216
  • Thank you received: 16
  • Karma: 6
PP написал(а):
Простая задачка. Как определить все возможные анаграммы для слова (слово подается на вход пользователем)?
Например:
апельсин -- спаниель
пасечник -- песчаник, песчинка
Может быть воспользоваться народной мудростью: Если не знаешь как решить задачу, то отсортируй входные данные.

Каждому слову ставим в соответствие слово из этих же букв но в алфавитном порядке. Например мама-аамм. В словаре в котором мы ищем анаграммы делаем аналогичную процедуру.
Следуй за белым кроликом.

алгоритмические задачки 09 Июнь 2010 23:25 #33

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2

алгоритмические задачки 22 Сен 2010 19:06 #34

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
Это разрушает мозг


habrahabr.ru/blogs/regex/104768/
Тест простоты числа регулярным выражением
/^1?$|^(11+?)\1+$/
Применять его следует не к самому целому числу. Вместо этого, нужно создать строку из единиц, где количество единиц соответствует самому числу и уже к этой строке применить регулярное выражение. Если совпадения нет — число простое.
Так как же оно работает? Выглядит как настоящая головоломка, но на самом деле все просто. Проигнорируйте его часть до символа |, поскольку она предназначена просто для выяснения, является ли строка совсем пустой или состоит из одной единицы.

Подвыражение (11+?) совпадает со строками вроде 11, 111, и т.д… Часть \1+ будет искать далее по строке совпадения с результатами поиска первого подвыражения. В первый раз совпадение произойдет по строке «11» и потом поиск строки «11» будет произведен снова, а затем снова до конца строки. Если поиск завершится успешно, число не является простым. Почему? Потому, что будет доказано, что длина строки делится на 2 и, соответственно, само число тоже делится на два. Если совпадения не произойдет, движок регулярных выражений начнет искать строку «111» и ее повторения (таким образом реализуя дальше решето Эратосфена — прим. пер). Если первое подвыражение становится достаточно длинным (n/2) и совпадений по-прежнему не будет обнаружено, число будет являться простым.
Каждому - своё.
Last Edit: 08 Нояб 2014 07:33 by Vladimirovich.

алгоритмические задачки 07 Окт 2010 17:01 #35

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
#include iostream

using namespace std;

template int M, int N
struct X
{
enum { value = XN, M%N::value };
};

template int N
struct XN, 0
{
enum { value = N };
};

int main(int argc, char** argv)
{
cout X6,5::value endl; //Напечатаем значение Х6,5
}

Что это за алгоритм? Что будет напечатано?

алгоритмические задачки 07 Окт 2010 19:40 #36

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
PP написал(а):
Что это за алгоритм? Что будет напечатано?
Убивать таких программистов надо

Каждому - своё.

алгоритмические задачки 07 Окт 2010 23:15 #37

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Почему? Код совершает вычисления во время компиляции между прочим.

алгоритмические задачки 08 Окт 2010 00:01 #38

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 40040
  • Thank you received: 89
  • Karma: 24
PP написал(а):
Код совершает вычисления во время компиляции между прочим.
Как такое может быть?

алгоритмические задачки 08 Окт 2010 01:08 #39

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Хайдук написал(а):
Как такое может быть?
C++ templates. Очень мощная штуковина если знать, как пользоваться

алгоритмические задачки 08 Окт 2010 07:30 #40

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
PP написал(а):
Почему? Код совершает вычисления во время компиляции между прочим.
Ну наверно точнее сказать, что во время компиляции компилятор заполняет дыры в коде с темплейтами, а также вычисляет константы.
Будет там не 6,5, а переменные, и он ничего предвычислять не будет.

А вообще темплейты зло, разрушающее мозг

Каждому - своё.

алгоритмические задачки 08 Окт 2010 07:58 #41

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
1


Это НОД как я понимаю.
Заставить компилер рекуррентно что-то вычислять - это изящно

Каждому - своё.

алгоритмические задачки 08 Окт 2010 15:14 #42

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Vladimirovich написал(а):
Это НОД как я понимаю.
Ага, алгоритм Евклида!

алгоритмические задачки 03 Дек 2010 18:32 #43

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
theoryandpractice.ru/posts/804-slozhno-o...u-devushku-ot-odetoy
Сложно о простом: как отличить голую девушку от одетой

130722_howtogirl.jpg
Каждому - своё.
Last Edit: 22 Июль 2013 06:32 by Vladimirovich.

алгоритмические задачки 03 Дек 2010 21:27 #44

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Вот хорошая задачка для нейросетей. Тот алгоритм, про который идет речь в статье, мне кажется неправильным. Они через цвета ищут кожу. А если это боди-арт? Надо анатомические части распозновать имхо, а потом уже искать на них трусы. Вот прототип кода

find_nudity(const vectorBodyParts x)
{
size_t n=x.size();
for(size_t i=0; in; i++)
{
if( x.type == boops)
return(find_bra(x);
if(x.type == buttocks)
return(find_panties_back(x));
if(x.type == ({}))
call_chess_tiger_for_opinion(x);
}
return false;
}

алгоритмические задачки 04 Дек 2010 05:45 #45

  • Крыс
  • Крыс's Avatar
  • OFFLINE
  • Отец Русской Демократии
  • Posts: 33839
  • Thank you received: 61
  • Karma: 14
Vladimirovich написал(а):
как отличить голую девушку от одетой
Визуально или тактильно?

алгоритмические задачки 04 Дек 2010 06:20 #46

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
PP написал(а):
call_chess_tiger_for_opinion(x);

Каждому - своё.

алгоритмические задачки 04 Дек 2010 21:47 #47

  • Автор: инфолио
  • Автор: инфолио's Avatar
Vladimirovich написал(а):
как отличить голую девушку от одетой
Визуально или тактильно?
По аналогии с известным алгоритмом про кошку и кота (споймать и отпустить, если побежал - кот, если побежала - кошка), так и тут- алго_ритмически...
(Я хоть и пенсионер, но остальные органы чувств, кроме упомянутых с учетом интуиции со счетов нельзя сбрасывать). З павагай к алгоритмическому мышлению, учитывающему освещенность, влажность, расстояние, циклы и т.п.

алгоритмические задачки 25 Фев 2011 06:54 #48

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Известная задача о маршруте коня по шахматной доске. А как алгоритмизировать?

алгоритмические задачки 25 Фев 2011 08:38 #49

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
PP написал(а):
Известная задача о маршруте коня по шахматной доске. А как алгоритмизировать?
В смысле найти все варианты?
Каждому - своё.

алгоритмические задачки 25 Фев 2011 15:02 #50

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
В смысле найти алгоритм, который позволяет обойти всю доску начиная с любого поля.

алгоритмические задачки 25 Фев 2011 15:13 #51

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
PP написал(а):
В смысле найти алгоритм, который позволяет обойти всю доску начиная с любого поля.
Ну надо наверно граф сформировать где ребра - ходы коня между полями, и искать Гамильтонов путь.
Задача в теории графов шибко известная, так что должны быть алгоритмы лучшие, чем я придумаю за 5 мин

Каждому - своё.

алгоритмические задачки 25 Фев 2011 16:31 #52

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Vladimirovich написал(а):
Ну надо наверно граф сформировать где ребра - ходы коня между полями, и искать Гамильтонов путь.
Ну Гамильтонов путь искать задача неблагодарная (обычно).

алгоритмические задачки 25 Фев 2011 19:06 #53

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
PP написал(а):
Ну Гамильтонов путь искать задача неблагодарная (обычно).
Ничего, сейчас компы мощные

Если честно, то я не помню алгоритмов небрутфорсовых для этого, хотя оный еще у Эйлера был.
Вроде самый логичный по человечьи, разбить доску на 4 четверти. Отработать ходы на доске 4х4 а потом связать.
Каждому - своё.

алгоритмические задачки 26 Фев 2011 04:26 #54

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Vladimirovich написал(а):
хотя оный еще у Эйлера был.
Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб

алгоритмические задачки 01 Март 2011 16:28 #55

  • Автор: инфолиократ
  • Автор: инфолиократ's Avatar
Сразу вспомнил, как когда-то в школе на т.н. математической неделе, кажется в физмат классе дружно решали все задачку, как обойти все поля конем, начиная с левого нижнего угла и заканчивая правым верхним, пока не пришел отсутствовавший ученик, кажется перворазрядник и не сказал: не пыжтесь, не найдете.

алгоритмические задачки 01 Март 2011 20:23 #56

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Для малых досок работает очень простой алгоритм.

алгоритмические задачки 03 Апр 2011 18:28 #57

  • Vladimirovich
  • Vladimirovich's Avatar
  • NOW ONLINE
  • Инквизитор
  • Posts: 84269
  • Thank you received: 1250
  • Karma: 61
habrahabr.ru/blogs/algorithm/116758/
Визуализация графов. Метод связывания ребер
Иногда полезно представить граф в графической форме, так чтобы была видна структура. Можно привести десятки примеров, где это может пригодиться: визуализация иерархии классов и пакетов исходного кода какой-нибудь программы, визуализация социального графа (тот же Twitter или Facebook) или графа цитирования (какие публикации на кого ссылаются) и т.д. Но вот незадача: количество ребер в графе зачастую настолько велико, что нарисованный граф просто невозможно разобрать......
Каждому - своё.
Last Edit: 08 Нояб 2014 07:35 by Vladimirovich.

алгоритмические задачки 04 Апр 2011 05:31 #58

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Vladimirovich написал(а):
Визуализация графов. Метод связывания ребер
Супер! Кажется вот оригинальная статья.

Отредактировано PP (2011-04-04 09:41:37)

алгоритмические задачки 04 Апр 2011 17:52 #59

  • evgeny
  • evgeny's Avatar
  • OFFLINE
  • Бравый солдат
  • Posts: 2984
  • Thank you received: 31
  • Karma: 1
инфолиократ написал(а):
Сразу вспомнил, как когда-то в школе на т.н. математической неделе, кажется в физмат классе дружно решали все задачку, как обойти все поля конем, начиная с левого нижнего угла и заканчивая правым верхним, пока не пришел отсутствовавший ученик, кажется перворазрядник и не сказал: не пыжтесь, не найдете.
Интересно, а откуда перворазрядник знал ответ?
Для решения задачи не надо быть шахматистом, надо просто знать правила (конь ходит буквой Г) и не быть дальтоником.

алгоритмические задачки 30 Апр 2011 19:25 #60

  • PP
  • PP's Avatar
  • OFFLINE
  • Боярин
  • Posts: 25396
  • Thank you received: 160
  • Karma: 2
Если кто не слышал, тут очень много задачек есть
projecteuler.net/index.php?section=problems
Last Edit: 08 Нояб 2014 07:35 by Vladimirovich.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум