Задать вопрос

Oxoron

Шарпер
Ответы пользователя по тегу Алгоритмы

  • Как оптимизировать алгоритм подсчёта суммы чётных чисел Фибоначчи?

    @Oxoron
    Шарпер
    Навскидку, числа Фибоначчи идут в периоде (нечет-нечет-чет).
    При этом четный член равен сумме предыдущих нечетных.
    3+5 = 8
    13 + 21 = 34
    55 + 89 = 144

    То есть, четное число - это полусумма своей тройки.
    Так что берем искомую последовательность, добавляем при необходимости один-два члена (чтоб получить полную тройку). Сумма первых 2k+1 чисел равна 2*F_{2k+1}. Сумма первых 2k чисел равна F_{2k+2}.

    Так что ищем сумму, отнимаем 1 и 2, отнимаем добавленные слагаемые, делим на два, получаем ответ.

    Формулу быстрого поиска энного числа Фибоначчи ищем на википедии.
    В результате при любых больших n поиск будет занимать почти одинаковое время.
    Ответ написан
    Комментировать
    Комментировать

  • Генеалогическое дерево на C#?

    @Oxoron
    Шарпер
    Делаешь класс Person{string Name, string FirstSurname, string SecondSurname, List parents, List wifes\husbunds, List children}.
    Имя, фамилия до свадьбы, фамилия после (кстати, свадеб может быть много, можно лист фамилий сделать), список родителей (дети могут жить в приюте, с приемными, с гомосексуалистами, а могут быть зачаты мидихлорианами), список жен\мужей, список детей. Все.

    При добавлении человеку А ребенка В проверяешь, есть у В персона А в списке родителей. Если нет - добавляешь. При добавлении человеку А супруги В проверяешь, есть ли у В персона А в списке мужей\жен. Если нет - добавляешь. И т.д. для каждой связи (в обе стороны).
    Ответ написан
    Комментировать
    Комментировать

  • Как оптимизировать Serial.WriteLine?

    @Oxoron
    Шарпер
    Вижу два возможных затыка.
    1. В методе отсылается лишь одно сообщение. Значит, метод вызывается порядка 115 тысяч раз в секунду (не уверен, что правильно назвал цифру, но суть понятна). Можно замерить число сообщений в очереди, и передать его методу Sender(). Получится
    void Sender(int messageQty)
        {
                for(int i=0; i< messageQty; i++)
                {
                        Serial.WriteLine((string)sd.Dequeue());
                }               
        } // Интересно, вызовы Dequeue можно избежать? Каким-нибудь foreach или другой структурой? Или они вообще не фатальны?


    2. У вас есть каст к строке, (string)sd.Dequeue(). Он тоже отжирает время. Если есть возможность, используйте Queue<string>. Как вариант, можете попробовать использовать sb.Dequeue().ToString()
    Ответ написан
    Комментировать
    Комментировать