Задать вопрос
Ответы пользователя по тегу Алгоритмы
  • Случайный рандом с коэффициентом шанса, как сделать?

    myjcom
    @myjcom Куратор тега C++
    И это вприницпи работает. Как мне сделать так, что бы у каждого предмета можно было выставлять определённый коофицент выпадения? Или хотя бы подскажите куда копать, в каком направлении.

    Смотри:
    В урну поместили 2 шара: черный и белый, какова вероятность того, что первый наугад вынутый шар окажется белым?

    Дальше

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

    Дальше
    В урну поместили четыре шара: 2 белых, черный и красный, какова вероятность того, что первый наугад вынутый шар окажется белым?

    Учитывай что полная вероятность равна 1.0

    Вот так это работает, а все остальное вздор... .

    Другими словами тебе нужно N штук каждого элемента пропорционально твоему коэфиценту выпадения. Потом https://en.cppreference.com/w/cpp/algorithm/random...

    А дальше рандомно дёргать из контейнера, оставлять их там или удалять зависит от задачи.

    Использовать распределения или нет аналогично. https://en.cppreference.com/w/cpp/numeric/random

    Более сложные варианты я описывать не возьмусь.
    Ответ написан
    Комментировать
  • Как определить оценку сложности алгоритма?

    myjcom
    @myjcom
    много читал по этой теме


    В хаскеле все просто
    isSorted :: (Ord a) => (a -> a -> Bool) -> [a] -> Bool
    isSorted cmp xs = and (zipWith cmp xs (tail xs))
    
    cp :: Int -> Int -> Bool
    cp x y = x <= y
    
    main = print (isSorted cp [1,2,7,4,5]) -- False

    main = print (isSorted cp [1,2,3,4,5]) -- True
    Ответ написан
    5 комментариев
  • Как найти все цифры в строке и сформировать из них новую?

    myjcom
    @myjcom Куратор тега C++
    Нужна функция сортировки

    Нет.

    #include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
      string src;
      getline(cin, src);
    
      string dst;
      copy_if(src.begin(), src.end(), back_inserter(dst), ::isdigit);
    
      cout << dst;
    }
    Ответ написан
  • Как применять модель "случайных блужданий без самопересечений" в java?

    myjcom
    @myjcom
    не могу найти ошибку

    Условие в while...
    int y = n/2;
    ... 
    && (y > (n-1))
    всегда false.
    т.к. (n / 2) <= (n - 1)

    Соответственно

    Программа в каждом случае выдаёт 0.

    int deadEnds = 0;
    ... 
    100*deadEnds/trials == 0
    0/n = 0

    https://rextester.com/CQOHTE74063
    Ответ написан
    Комментировать
  • Как развить алгоритмические навыки программирования?

    myjcom
    @myjcom
    jajabin, попробуйте использовать классический подход.
    Есть много книг по алгоритмам, обзоры/отзывы/рецензии можно найти в интернете.
    Что лучше/хуже для конкретного индивида может понять только сам индивид. Возможно вам конкретика нужна, "сколько вешать в граммах" или "ткните пальцем"
    как правильно себе построить план?

    В общем случае план одинаков +/- нюансы конкретного издания. (теория + практика)
    Тут главное не распыляться, а начать.
    Левитин А.В.
    Алгоритмы: введение в разработку и анализ (написана доступным языком, много упражнений для закрепления)
    Кратко

    5d64febe62b08896920686.png

    и Алгоритмические головоломки (немного теории и практика, практика и еще раз практика) этого же автора.

    Поллис Г., Хайнеман Дж., Селков С.
    Алгоритмы. Справочник с примерами на C, C++, Java ... (поможет понять что где когда и как применять)

    Да и еще, тут такое дело
    придется немного вспомнить математику и логику уровня старших классов школы, ну или даже 1 курса ВУЗа. Можно и без этого конечно, на уровне Грокаем алгоритмы, но тогда это уже совсем не то, скучно будет.
    Ответ написан
    1 комментарий
  • Как выглядит алгоритм: Модульная инверсия на языке Java?

    myjcom
    @myjcom
    Java
    C++ (наглядно)

    Нигде не могу найти примера алг-ма "Модульная инверсия", для того, чтобы разобраться самостоятельно и понять данный алгоритм.

    Чтобы понять, надо найти книгу
    Алгоритмы для начинающих: теория и практика для разработчика

    Год издания: 2018
    Автор: Луридас П.
    Переводчик: Егорова Е.М.
    Издательство: М.: Эксмо
    ISBN: 978-5-04-089834-3

    Страница 167
    5.2. Криптосистема RSA
    там все изложено доступным языком.
    Ответ написан
    Комментировать
  • Как посчитать количество отрицательных элементов в матрице?

    myjcom
    @myjcom
    Добавлю
    тут 2(3)
    for (int i = 0; i < column; ++i)
        {
            for (int j = 0; i < row; ++j)
            {
                if(matrix[i][j] < 0)
                    arr[j]++;
            }
        }


    И arr надо calloc
    И что если размеры row col будут разные. У вас цикл наоборот а индексы прежние.
    Ответ написан
    Комментировать
  • Как корректно вывести на экран кол-во пересылок и сравнений в пузырьковой сортировке массива?

    myjcom
    @myjcom Куратор тега C++
    Как-то так:
    #include <iostream>
    #include <map>
    #include <string>
    #include <iomanip>
    using namespace std;
    
    
    void swap(int& a, int& b)
    {
      int c = a;
      a = b;
      b = c;
    }
    
    struct info
    {
      int swapCount = 0;
      int compCount = 0;
    };
    
    class Counter
    {
      public:
        static Counter& Instance()
        {
          static Counter tsCounter;
          return tsCounter;
        }
    
        info& getCount(string fn)
        {
          return callCount[fn];
        }
    
        void print()
        {
          for(auto& a : callCount)
          {
            cout << a.first   << "\n"
                 << setw(15) << left << "swap: " << a.second.swapCount << "\n"
                 << setw(15) << left << "compare: " << a.second.compCount << "\n";
          }
          cout.flush();
        }
    
      private:
        map<string, info> callCount;
        Counter(){}
        Counter(const Counter&) = delete;
        Counter& operator=(const Counter&) = delete;
    };
    
    void mysort(int* a, size_t sz)
    {
      for(int i = 0; i < sz - 1; ++i)
      {
        int minIdx = i;
        for(int j = i + 1; j < sz; ++j)
        {
          if(a[j] < a[minIdx]) minIdx = j;
        }
        swap(a[i], a[minIdx]);
        Counter::Instance().getCount(__FUNCTION__).swapCount++;
      }
    }
    
    
    int main()
    {
      int a[] = {2, 5, 6, 77, 1, 32, 45, 77, 12, 13, 14, 15};
      mysort(a, sizeof(a)/sizeof(int));
      Counter::Instance().print();
    }

    Ответ написан
    5 комментариев
  • Как реализовать поиск по Linked List?

    myjcom
    @myjcom Куратор тега C++
    Условие
    bool find(node* n, int value)
    {
        node* ptr = n;
        while(ptr != nullptr)
        {
            if(ptr->value == value) return true;
            ptr = ptr->next;
        }
        return false;
    }
    
    node* find(node* n, int value)
    {
        node* ptr = n;
        while(ptr != nullptr)
        {
            if(ptr->value == value) return ptr;
            ptr = ptr->next;
        }
        return ptr;
    }
    
    node* result = find(...);
    if(result)
    {
        //...
    }
    Ответ написан
    2 комментария
  • Алгоритмы и структуры данных для веб разработчика?

    myjcom
    @myjcom
    Первая ссылка в поиске https://habr.com/post/359192/

    есть еще
    Learning JavaScript Data Structures and Algorithms, Second Edition
    Год издания: 2016
    Автор: Groner L.
    Издательство: Packt Publishing
    ISBN: 9781785285493

    Кроме того есть книга
    Алгоритмы: введение в разработку и анализ
    Год издания: 2006
    Автор: Левитин А.В.
    ISBN: 5-8459-0987-2

    ничем не хуже
    Грокаем алгоритмы

    И крайне полезная для относительно быстрого вхождения книга
    Устойчивость супружеских пар и другие комбинаторные задачи: Введение в математический анализ алгоритмов
    Год: 2011
    Автор: Кнут Дональд Эрвин
    Переводчик: Кашина О.А., Лернер Э.Ю.
    Издательство: МЦНМО

    spoiler
    Про Кромэна, Макконнела, Рода, Шеня писать не буду.
    Алгоритмы: разработка и применение. Классика Computers Science
    Год издания: 2016
    Автор: Клейнберг Дж., Тардос Е.
    Переводчик: Е. Матвеева
    Издательство: Питер
    ISBN: 978-5-496-01545-5

    И конечно же
    Дасгупта С., Пападимитриу Х., Вазирани У.

    spoiler

    Есть совсем жесть)))
    Elements of Programming / Начала программирования
    Год издания: 2011
    Автор: Alexander Stepanov, Paul McJones / Александр Степанов, Пол Мак-Джоунс
    Переводчик: Константин Птицын
    Издательство: ООО "И. Д. Вильямс"
    ISBN: 978–5–8459–1708–9


    И algolist.ru
    Ответ написан
    1 комментарий
  • Какой алгоритм шифрования применяется?

    myjcom
    @myjcom
    Все достаточно просто

    IiiEncryptionXor class:
    spoiler
    package primary.utils
    {
       import flash.utils.ByteArray;
       
       public class IiiEncryptionXor
       {
           
          
          public function IiiEncryptionXor()
          {
             super();
          }
          
          public static function encrypt(string:String, key:String) : String
          {
             var barr:ByteArray = new ByteArray();
             barr.writeUTFBytes(Base64.encode(string));
             var xstr:String = xorr(barr,key);
             return Base64.encode(xstr);
          }
          
          public static function decrypt(string:String, key:String) : String
          {
             var barr:ByteArray = Base64.decodeToByteArray(string);
             var xstr:String = xorr(barr,key);
             return Base64.decode(xstr);
          }
          
          private static function xorr(barr:ByteArray, key:String) : String
          {
             var keypos:Number = NaN;
             var keyByteArr:ByteArray = new ByteArray();
             keyByteArr.writeUTFBytes(key);
             var keylen:int = keyByteArr.length;
             var barrlen:int = barr.length;
             var barrNew:ByteArray = new ByteArray();
             for(var i:int = 0; i < barrlen; i++)
             {
                keypos = i % keylen;
                barrNew[i] = barr[i] ^ keyByteArr[keypos];
             }
             return barrNew.toString();
          }
       }
    }

    Key string: (из DataModelBase)
    spoiler
    private const VERY_LONG:String = "some very-very long string without any non-latin characters due to different string representations inside of variable programming languages";


    Base64 class:
    spoiler
    package primary.utils
    {
       import flash.utils.ByteArray;
       
       public class Base64
       {
          
          private static const BASE64_CHARS:String = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
          
          public static const version:String = "1.1.0";
           
          
          public function Base64()
          {
             super();
             throw new Error("Base64 class is static container only");
          }
          
          public static function encode(data:String) : String
          {
             var bytes:ByteArray = new ByteArray();
             bytes.writeUTFBytes(data);
             return encodeByteArray(bytes);
          }
          
          public static function encodeByteArray(data:ByteArray) : String
          {
             var dataBuffer:Array = null;
             var i:uint = 0;
             var j:uint = 0;
             var k:uint = 0;
             var output:String = "";
             var outputBuffer:Array = new Array(4);
             data.position = 0;
             while(data.bytesAvailable > 0)
             {
                dataBuffer = new Array();
                i = 0;
                while(i < 3 && data.bytesAvailable > 0)
                {
                   dataBuffer[i] = data.readUnsignedByte();
                   i++;
                }
                outputBuffer[0] = (dataBuffer[0] & 252) >> 2;
                outputBuffer[1] = (dataBuffer[0] & 3) << 4 | dataBuffer[1] >> 4;
                outputBuffer[2] = (dataBuffer[1] & 15) << 2 | dataBuffer[2] >> 6;
                outputBuffer[3] = dataBuffer[2] & 63;
                for(j = dataBuffer.length; j < 3; j++)
                {
                   outputBuffer[j + 1] = 64;
                }
                for(k = 0; k < outputBuffer.length; k++)
                {
                   output = output + BASE64_CHARS.charAt(outputBuffer[k]);
                }
             }
             return output;
          }
          
          public static function decode(data:String) : String
          {
             var bytes:ByteArray = decodeToByteArray(data);
             return bytes.readUTFBytes(bytes.length);
          }
          
          public static function decodeToByteArray(data:String) : ByteArray
          {
             var j:uint = 0;
             var k:uint = 0;
             var output:ByteArray = new ByteArray();
             var dataBuffer:Array = new Array(4);
             var outputBuffer:Array = new Array(3);
             for(var i:uint = 0; i < data.length; i = i + 4)
             {
                j = 0;
                while(j < 4 && i + j < data.length)
                {
                   dataBuffer[j] = BASE64_CHARS.indexOf(data.charAt(i + j));
                   while(dataBuffer[j] < 0 && i < data.length)
                   {
                      i++;
                      dataBuffer[j] = BASE64_CHARS.indexOf(data.charAt(i + j));
                   }
                   j++;
                }
                outputBuffer[0] = (dataBuffer[0] << 2) + ((dataBuffer[1] & 48) >> 4);
                outputBuffer[1] = ((dataBuffer[1] & 15) << 4) + ((dataBuffer[2] & 60) >> 2);
                outputBuffer[2] = ((dataBuffer[2] & 3) << 6) + dataBuffer[3];
                for(k = 0; k < outputBuffer.length; k++)
                {
                   if(dataBuffer[k + 1] == 64)
                   {
                      break;
                   }
                   output.writeByte(outputBuffer[k]);
                }
             }
             output.position = 0;
             return output;
          }
       }
    }
    Ответ написан
    Комментировать
  • Где ошибка в реализации QuickSort?

    myjcom
    @myjcom
    У Вас условия не проверяются
    quicksort($array, $first, $right);
    quicksort($array, $left, $last);

    А надо
    if ($r > $left) {
    //Если условие true, совершаем рекурсию
    //Передаем массив, исходное начало и текущий конец
    my_sort($array, $left, $r); 
    }
    
    if ($l < $right) {
    //Если условие true, совершаем рекурсию
    //Передаем массив, текущие начало и конец
    my_sort($array, $l, $right);
    }


    https://habr.com/sandbox/33297/
    Ответ написан
    1 комментарий
  • Как по поисковому запросу классифицировать элемент в каталоге?

    myjcom
    @myjcom
    Наибольшая общая подпоследовательность
    https://ru.wikipedia.org/wiki/Наибольшая_общая_под...

    Нахождение наибольшей общей подпоследовательности
    algolist.ru/search/lcs/simple_lcs.php
    Ответ написан
    4 комментария