• Как реализовать выполнение очереди комманд в дочернем потоке?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В цикле в условие while (!_commandQueue.IsEmpty) добавить проверку какого-нибудь внешнего флага, который установить в false, когда источник команд примет решение, что делать больше ничего не надо: while(fgoing || !_commandQueue.IsEmpty).
    По хорошему, надо бы при пустой очереди ждать не секунду, а какого-нибудь события, которое возникнет, когда добавится новая команда. Иначе команду, которая пришла через 1.2 секунды после первой, он отправит только через две секунды.
    Ответ написан
    6 комментариев
  • 3D триангуляция?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В общем, делается так.
    Пусть фигура задана набором треугольных граней с известной ориентацией. В каждом ребре сходится чётное число граней (возможна, например, фигура из двух тетраэдров, склеенных по ребру), и при обходе любого ребра ориентации граней, сходящихся в нём, чередуются (например, идут грани ABC, BAD, ABE, BAF). Даже если в исходной модели таких странных рёбер нет, они могут возникнуть на промежуточном этапе.
    Выбираем любые две грани со следующими свойствами:
    - у них есть общее ребро AB;
    - при обходе этого ребра они являются последовательными
    - внутренний угол между этими гранями меньше 180 гр.
    Такие грани найдутся всегда. Пусть это ABC и BAD.
    Рассмотрим тетраэдр ABCD. Проверим, нет ли у него внутри других вершин. Если нет - заменим грани ABC и BAD на CAD и BCD (вырезав, тем самым, ABCD из модели). Если есть - возьмём ту вершину E из них, которая ближе всего к грани ABC, и заменим грань ABC на три грани ABE, AEC, EBC.
    После этого просмотрим грани, и если оказалось, что какая-то грань встречается дважды с противоположными ориентациями (ABC и ACB) - выбрасываем обе копии.
    Процесс повторяем, пока все грани не исчезнут.
    Всё.
    Ответ написан
    4 комментария
  • Где, когда и как лучше использовать лямбда-выражения?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Я использую лямбда-выражения в двух случаях:
    - когда это действительно "выражение", т.е. всё вычисление укладывается в одну формулу;
    - когда для вычислений нужно использовать значения переменных текущего метода.
    При этом я помню, что "под ковром" компилятор создаст для каждого контекста с лямбда-выражением отдельный класс, и захваченные переменные будут полями этого класса (а само лямбда-выражение - его методом). Причём они будут использоваться, как поля, не только для кода, вычисляющего это выражение, но и для всей работы с этими переменными. Так что, если в конкретном месте приходится думать об эффективности, то надо всё взвесить.
    Ответ написан
    1 комментарий
  • Используются ли в программировании дифференциальное и интегральное исчисления?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В программировании не используется. Используется в конкретных приложениях, для которых используется также и программирование. Программисту, в общем, всё равно, что программировать, решение дифф.уравнения или подсчёт какой-нибудь статистики - были бы формулы. Дифференциальное и интегральное исчисления используются на два шага выше - когда происходит формализация конкретной практической задачи и выбор математической модели (ещё даже не алгоритмов!) для неё.
    Иногда, правда, соответствующие подходы используются уже при поиске алгоритмов для других задач. Скажем, один из алгоритмов решения полиномиальных систем (метод гомотопий) можно свести к решению хитрого дифференциального уравнения. Но, в любом случае, это не программирование, а алгоритмистика.
    Ответ написан
  • Как решить задачу про разрез(написать программу)?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала проверяете, есть ли свеча в центре. Если есть, то очевидно, нельзя (любой разрез, делящий торт пополам, проходит через центр).
    Потом для каждой свечи находите направление на неё из центра. В большинстве языков это делается вызовом функции atan2(y,x) (в предположении, что центр находится в точке (0,0)). Она выдаёт угол в радианах, лежащий в промежутке от -pi до pi.
    Сортируете углы по возрастанию: a1<=a2<=...<=an.
    Если an-a1 < pi-eps, то все свечи лежат внутри угла, меньшего pi, и разрез есть.
    Если для какого-то k a{k+1}-ak > pi+eps, то есть пустой угол, больший pi, и разрез тоже есть.

    Сложности возникают, когда an-a1 или a{k+1}-ak очень близки к pi, и надо точно проверить, больше угол, чем pi, меньше, или равен. Здесь всё зависит от жестокости авторов задачи.
    Если числа заданы, как целые, не превосходящие по модулю 10^9, то достаточно посчитать определитель x{k+1}*y{k}-x{k}*y{k+1}, и по его знаку определить, с какой стороны линия, соединяющая свечи, пройдёт от центра. Произведения укладываются в int64, и всё просто.
    Если числа целые и не превосходят 10^18, то дело хуже. Существуют алгоритмы проверки, не выходящие за int64 (специально написанный алгоритм Евклида), но возможно, что проще воспользоваться длинной арифметикой.
    Хуже всего, если координаты - вещественные числа произвольного формата. Боюсь, что тут придётся писать свой парсер - простого хорошего способа надёжно проверить, что свечи с координатами, скажем (1.2E220, 2.7E-180) и (-2.8E200, 6.3E-200) лежат строго на одной прямой, проходящей через центр, я не знаю.
    Ответ написан
    Комментировать
  • Как узнать, является ли чмсло суммой какого-нибудь n первых чисел натурального ряда?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Считаете число D=8*S+1. Если оно оказалось полным квадратом (т.е. если взять целую часть квадратного корня из D и возвести в квадрат, то снова получится D), то ответ - да, и n=(sqrt(D)-1)/2. Иначе S искомой суммой не является.
    Ответ написан
    Комментировать
  • Зачем вы пошли в разработчики?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    1) Так получилось. Оказалось, что самому программировать проще, чем объяснять алгоритмы другим.
    2) Вполне.
    3) Пусть выбирают что хотят. Хоть разработчиком, хоть ветеринаром, хоть пилотом истребителя. Лишь бы им нравилось.
    4) Совершенно неважно. Лишь бы можно было вдоволь заниматься интересными делами.
    5) Собираюсь, после технологической сингулярности. При первых возможностях аплоадинга пойду осваивать виртуальный мир.
    Ответ написан
    Комментировать
  • Сколько времени вы максимально искали баг?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если баг воспроизводится, и время от запуска программы до момента, когда эффект, вызванный этим багом, меньше 10 минут (под дебагером), то обычно дня хватает. При условии, что он не вызван неправильным пониманием поведения чужой программы (скажем, плохо документированным форматом их входных данных, которые должны создаваться моей программой).
    В случае, если баг возникает редко, зависит от аппаратуры и компьютера, на которых идёт запуск, то могут уйти и годы. Анализируются лог-файлы, уточняется место, где что-то пошло не так, придумываются дополнительные промежуточные проверки, дополнительная отладочная печать - и программа снова отправляется на работу, до следующего проявления бага.
    Ответ написан
    Комментировать
  • Почему именно синус?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    В этой задаче синус не нужен.

    double r=sqrt(x*x+y*y);
    double cf=1+10/r;
    double x1=x*cf,y1=y*cf;

    (x1,y1) - координаты искомой точки.
    Ответ написан
    3 комментария
  • Как математически описать перебор кода из 7 цифр?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    "как минимум 2 цифры и они должны повторяться как минимум дважды"
    Если разных цифр ровно две, то ясно, что имеется в виду. А если больше? Скажем, годится ли код 1122234, в котором две цифры повторяются не менее двух раз, но две другие - нет?

    Боюсь, что годится только прямой перебор. На C это бы выглядело так:
    char s[8],stat[4];
      int i,j,k;
      s[7]='\0';
      for(i=0;i<16384;i++){
         k=i;
         for(j=0;j<4;j++) stat[j]=0;
         for(j=0;j<7;j++){
            stat[k%4]++;
            s[j]=(char)((k%4)+'1');
            k/=4;
        }
        if((stat[0]>=2)+(stat[1]>=2)+(stat[2]>=2)+(stat[3]>=2)>=2) printf("%s\n",s);
      }

    Код не проверялся.
    Ответ написан
  • Цикл в 100.000 итераций vs "умного" цикла?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Что известно про заполненные ячейки? Они образуют непрерывный фрагмент? Прижат ли он к началу массива, или к концу, или у него известна минимальная длина?
    Если ваш алгоритм применить к массиву, в котором заполнены ячейки с 10001 по 19999, он их не заметит, и скажет, что массив пуст. Так и предполагается?
    Если заполнен непрерывный участок с неизвестной заранее длиной L, то есть простой способ найти его за O(N/L) операций (а потом обработать за O(L)).
    Ответ написан
    4 комментария
  • Как построить 3D модель, используя плоскость и линию?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Соединяются точки, находящиеся либо на соседних строках матрицы на одном кадре, либо на одной и той же строке на соседних кадрах. В результате получается сетка из четырёхугольников. Их можно разделить на треугольники по более короткой диагонали.
    Если на какой-нибудь строке зелёной точки не найдётся - в модели будет дырка.
    Ответ написан
    4 комментария
  • Нельзя изменять данные в структуре на прямую?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Предполагаю, что поле Company в объекте Im.Work описано тоже как свойство:
    public Company Company{ get; set; }

    В этом случае, когда вы пишете Im.Work.Company.CompanyName="Name", вызывается метод get для Company, возвращает копию структуры (потому что вернуть ссылку не может), и дальше вы пытаетесь в этой копии, никуда её не положив, поменять одно из полей. Оригинал от этого точно не изменится, и, по-видимому, компилятор не даёт выполнить заведомо бессмысленное действие (изменить объект, который сейчас будет уничтожен).
    Ответ написан
    8 комментариев
  • Математика и олимпиадное программирование?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Математика, в общем, и не нужна. Для геометрических задач полезно знать геометрию, уметь работать в координатах. Для задач, в формулировке которых фигурирует "вероятность" и "математическое ожидание" - полезно знать, что это такое. Собственно, всё. Гораздо важнее знать много алгоритмов, какой где применяется и как его написать для данной ситуации.
    Ответ написан
  • Взлом шифра Вернама(одноразовый блокнот). Как сделать?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Предполагаем, что известно, на каком языке сообщения, и статистика распределения символов (а также сочетаний по 2, 3 символа...)
    Зависит от того, сколько у нас сообщений.
    Если их достаточно много, то строим статистику символа с каждым порядковым номером по всем сообщениям (символ k встретился P[k] раз). Эта статистика должна получаться из стандартной статистики L для языка как P[k]=L[k^c], где c - искомый символ. Для каждого c считаем вероятность того, что на этом месте оказался именно он, и дальше начинаем искать наиболее вероятный текст для какого-нибудь сообщения.
    Если сообщений только два, то придётся использовать распределение групп символов, смотреть, из каких сочетаний наиболее вероятно получится фрагмент из C1^C2, и дальше распутывать их с помощью каких-нибудь цепей Маркова. Не знаю, получится ли.
    Сильно облегчит дело, если сообщения - фрагменты обычных ASCII-файлов, со всеми знаками пунктуации и переводами строк. Можно воспользоваться тем, что перевод строки имеет код 0D,0A, пробел - 20, другие знаки пунктуации - от 21 до 3F, большие буквы - от 41 до 5A, маленькие - от 61 до 7A (это если текст английский. Для русского ещё лучше). Смотрим на поведение битов 40 и 20. Если в каком-то месте в разных закодированных сообщениях значения бита 40 различны, значит в некоторых это буква, в остальных - знак пунктуации. Причём, буква вероятнее в тех, в которых более частое значение. Немного похимичив, получаем разделение текстов на слова, строки и предложения. Заодно в части сообщений проявляются некоторые буквы. Дальше работаем с распределением одно-, двух- и трёхбуквенных слов. Может быть, повезёт.
    Ответ написан
    5 комментариев
  • Можно ли посчитать количество цифр в документе, в котором содержатся результаты подсчёта?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Я не уверен, можно ли решить эту задачу, если документ состоит из 97 девяток.
    Ещё одна девятка будет в левом столбце таблицы. Какая-нибудь из цифр от 0 до 8 вряд ли встретится 9 раз. Так что девяток будет 98+ число девяток в последней клетке таблицы. Вот и получается:
    Если в последней клетке 0 девяток, то в ней число 98+0=98
    Если в ней одна девятка, то в ней 98+1=99
    Если в ней две девятки, то в ней 98+2=100
    Во всех случаях получаем противоречие.

    UPD. Задача решается довольно просто.
    Пусть у нас уже собрана статистика о числе разных цифр в теле документа (B[0] нулей, B[1] единиц...)
    Сразу прибавим к этим числам по единичке, чтобы учесть левый столбик.
    Оценим сверху число цифр в правой части таблицы. Например, как S=10*(log_10(B[0]+..+B[9])+2).
    Каждая цифра в полном документе встретится не более B[n]+S раз, значит, в правой части таблицы для неё будет число, лежащее от D0[n]=B[n] до D1[n]=B[n]+S.
    Прооптимизируем диапазоны D0..D1. Для этого для каждой цифры переберём все числа от D0[n] до D1[n], посмотрим количество разных цифр в каждом из этих чисел, возьмём минимальное и максимальное значение вхождений. Например, если D0[n]=997, D1[n]=1013, то в клетке, соответствующей n, 0,1 и 9 могут встретиться от 0 до 3 раз, а остальные цифры - 0 или 1 раз.
    Просуммируем полученные диапазоны по всем n - получим новую таблицу диапазонов D0n,D1n. Пересечём их с D0,D1.
    Есть 3 варианта.
    Все полученные диапазоны совпали с D0..D1. Выходим из цикла.
    Один из новых диапазонов пуст. В этой ветке решений нет, возвращаемся из функции.
    Какой-то диапазон изменился. Продолжаем оптимизировать.

    После того, как диапазоны стабилизировались, смотрим их длины. Если все они длины 1 (т.е. D0=D1), то мы нашли решение. Если нет - то берём самый короткий диапазон длины больше 1, перебираем все его значения D0[n]<=u<=D1[n], подставляем каждое из них в копию таблицы диапазонов (D0n[n]=D1[n]=u) и рекурсивно вызываем функцию оптимизации.
    Перебор оказывается небольшим, вот примеры (ncall - число рекурсивных вызовов):

    For 1 2 3 4 5 6 7 8 9 10
    0->5 1->7 2->5 3->5 4->6 5->10 6->9 7->10 8->10 9->12
    ncall=696

    For 1 1 1 0 0 0 0 0 0 0
    0->2 1->7 2->5 3->1 4->1 5->2 6->1 7->2 8->1 9->1
    ncall=486

    For 0 0 0 0 0 0 1 0 0 0
    ncall=464

    For 0 0 0 0 0 0 0 1 0 0
    0->1 1->7 2->2 3->3 4->1 5->1 6->1 7->3 8->1 9->1
    0->1 1->6 2->3 3->3 4->1 5->1 6->2 7->2 8->1 9->1
    0->1 1->6 2->4 3->1 4->2 5->1 6->2 7->2 8->1 9->1
    ncall=482

    For 3997 19995 5677 998 799996 392 7 94 8998 99985
    0->4014 1->20000 2->5679 3->1000 4->800001 5->394 6->10 7->96 8->9000 9->99994
    0->4013 1->20001 2->5679 3->1001 4->800000 5->394 6->10 7->96 8->9000 9->99994
    ncall=47356
    Ответ написан
    4 комментария
  • А у вас есть тетрадка, куда вы записываете наброски кода?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Раньше использовал большие 160-листовые тетради формата A4. Записывал всё подряд - планы, структуры программ и алгоритмов, описания на псевдокоде, в сложных случаях - куски кода, заметки при отладке... Пару лет назад попытался перейти на S Note на Самсунге, но пришел к выводу, что экран слишком маленький - тетрадка даёт гораздо лучшее разрешение. Сейчас использую для записей жёлтые блокноты (формата A5), думаю, что скоро опять вернусь к тетрадкам. Если они ещё будут в продаже.
    Ответ написан
    2 комментария
  • Как найти повторяющееся слово в строке?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Попробуйте алгоритм Кнута — Морриса — Пратта. Если с его помощью найти строку в самой себе, то ответом будет как раз сдвиг на повторяющееся слово. Но придётся повозиться с таблицей побочных переходов.

    В общем, получается вот такой простой алгоритм (правда, на C++):
    int maxrepword(char *A){
    	int *ref=new int[strlen(A)];
    	int b=0,s=1;
    	ref[0]=-1;
    	while(A[s]){
    		if(A[s]==A[b]) ref[s++]=b++;
    		else if(b==0) ref[s++]=-1;
    		else b=ref[b-1]+1;
    	}
    	delete[] ref;
    	return s-b;
    }

    Возвращает длину искомого слова. Время работы - линейное.
    Ответ написан
    Комментировать
  • Как держать в голове проект по программированию над которым работаешь не каждый день?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Можно просто периодически читать/просматривать код, вспоминая, что к чему, как оно выглядит, откуда вызывается и кого вызывает, в каких ситуациях работает та или иная часть кода... Чтобы ориентироваться на местности, надо по ней иногда гулять, и не бояться заблудиться :)
    Ответ написан
    Комментировать
  • По каким формулам вычислить новые координаты объекта в трёхмерном пространстве при относительном перемещении?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала вам надо чётко определить, что такое "Углы поворота объекта по всем трём осям". Поскольку повороты не коммутируют, то задание поворота несколькими углами - это всегда последовательность поворотов относительно некоторых осей на определённый угол (или поворот вокруг одного вектора - но это уже кватернионное представление). Например, углы Эйлера - последовательность поворотов относительно OZ, OX и снова OZ.
    Если у вас объект получается из базового объекта последовательностью поворотов (OX,a), (OY,b), (OZ,c) (a,b,c - углы в радианах), и есть вектор (dx,dy,dz) в локальной системе координат повёрнутого объекта, то получить сдвиг объекта на этот вектор в глобальной системе координат можно так:
    dy1=cos(a)*dy+sin(a)*dz; dz1=-sin(a)*dy+cos(a)*dz; // поворот относительно OX
    dx1=cos(b)*dx-sin(b)*dz1; dz2=sin(b)*dx+cos(b)*dz1; // поворот относительно OY
    dx2=cos(c)*dx1+sin(c)*dy1; dy2=-sin(c)*dx1+cos(c)*dy1; // поворот относительно OZ
    Тогда (dx2,dy2,dz2) - искомый вектор сдвига.
    Если углы заданы в градусах, они переводятся в радианы умножением на pi/180.
    Общее правило: преобразование координат, которое использовалось для перемещения объекта из его базового состояния в текущее - это то же преобразование, которое используется для перевода координат из текущей локальной системы координат объекта в глобальную.
    Ответ написан