• Как реализовать побитовый сдвиг чисел, которые записаны как строки ( длинные числа хранятся в строках)?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Из комментариев понятно, что это вы так пытаетесь умножение двух длинных чисел через сдвиги реализовывать. Соответственно, у вас сдвиги тоже длинные.

    Можно сдвигать не двоичные цифры, а десятичные. Или вообще любые. Тогда помимо сдвига еще появляется умножение на цифру. Такой сдвиг в строке из цифр - это просто сдвиг всей строки на нужное количество позиций. Саму сдвинутую строку вам не надо и получать, в общем-то.

    Основной цикл будет вроде
    for (int i = 0; i < a.length(); ++i) {
      for (int j = 0; j < b.length(); ++j) {
         c[i+j] += a[i] * b[j];
      }
    }


    В этом коде i+ - это и есть сдвиг. a[i] - это цифра на которую приходится домножать. а b[j] - это собственно само сдвигаемое и прикладываемое число.
    Ответ написан
    Комментировать
  • Как решать задачи на разбиение фигуры на сектора по цветам?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Лемма бернсайда. Гуглите. Но суть в том, что надо подсчитать количество раскрасок, которые не меняются при повороте на какой-то угол. Для всех углов сложить и поделить на количество поворотов.

    Поворот на 1<=i<=42 секторов создает gcd(i,42) циклов, каждый из которых должен быть окрашен целиком в один из 6 цветов. Т.е. получается 6^gcd(i,42) раскрасок, инвариантных для поаорота на i секторов.

    Отсюда ответ к задаче: sum i=1..42 6^gcd(i,42)/42.
    Ответ написан
    2 комментария
  • Как доказать, что если множество (G \ H) ∪ {1} — подгруппа G, то либо H = {1}, либо H = G?

    @Mercury13
    Программист на «си с крестами» и не только
    Обозначим обратный через x*, так писать проще.

    Берём элемент h∈H, ≠1 и другой g∉H, ≠1. Заметим, что:
    • h*∈H, ≠1, а g*∉H, ≠1
    • gh, hg, g*h и т.д. в любых сочетаниях ≠1.

    Вариант первый. x=gh∈H. Множим справа на h*, и получаем xh* = ghh* = g. Слева штуки из H, справа нет — H не замкнута.

    Вариант второй. x=gh∉H. Множим слева на g*, и получаем g*x = g*gh = h. Слева штуки из нашей подгруппы (G \ H) ∪ {1}, справа нет. Так что подгруппа явно не замкнута.

    Для полугрупп с единицей, о которых ты пытался говорить, это НЕ ТАК. Как известно, у любой конечной полугруппы есть идемпотент — тем лучше. Пусть G = B², H={00, 10}, операция — побитовое ИЛИ, E=00. Тогда множество (G\H)∪E={00,01,11} явно замкнуто относительно ИЛИ. (Я пытался вводить ажурные B и единицу, а система стирает.)
    Ответ написан
    Комментировать
  • Как доказать, что группы неизоморфны?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Надо найти какое-то противоречие в структурах групп.
    Например, в C есть элементы {1, i, -1, -i}. Это 4 различных элемента которые при умножении сами на себя дают 1. Если группы изоморфны, то должны быть 4 соответствующих им элемента в R, все - квадратные корни из 1. Но в R таких только 2: {1, -1}.

    Во втором примере можно привязаться к 0. в Q есть 0, умножив на который всегда получится 0. Но нет элемента, прибавив которой всегда получится одно и то же число.

    Опять же, 0 в {Q, *} не имеет аналога в {R, +}
    Ответ написан
    Комментировать
  • Как устроен вывод в задаче?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Минимизируйте стоимость строительства самой дорогой построенной предложенной линии.


    не сумма всех взятых ребер, а стоимость максимального из них.

    1 2 (2) и 2 3 (1) - максимальная стоимость 2 (max(1,2)).

    1 3 (3) - максимальная стоимость 3 max(3). 3 больше 2, значит ответ выше лучше.

    Так задача легче, чем с суммой.
    Ответ написан
    8 комментариев
  • Как сделать ограничение максимума и минимума в генерации случайных чисел с помощью строк?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Во-первых, дополните минимум нулями слева, чтобы две строки были одинаковой длины.

    Потом генерируйте посимвольно, считая, какие значения текущая цифра может принимать. Смотрите, если где-то вы сгенерируете цифру меньше maximum, то дальше может быть вообще что угодно. Ваше сгенеренное число уже меньше максимума. Так же с минимумом. Поэтому, поддерживайте 2 флага: "сгенрированная строка уже меньше максимума" и "сгенерированная строка уже больше минимума". Каждый следующий символ не должен превосходить цифру в максимуме, если не первый флаг. Также он не должен быть меньше минимума, если не второй флаг.

    Что-то вроде этого:
    bool smaller_than_max = false;
    bool bigger_than_min = false;
    for (int i = 0; i < n; ++i) {
       int left = bigger_than_min ? '0' : minimum[i];
       int right = smaller_than_max ? '9' : maximum[i];
       answer[i] = left + rand() % (right - left + 1);
       bigger_than_min |= answer[i] > minimum[i];
       smaller_than_max |= answer[i] < maximum[i];
    }


    Edit: тут все возможные числа не будут равновероятны. Чтобы они были равновероятны придется хорошенько поизвращаться.
    Ответ написан
    Комментировать
  • Как переделать код под ООП?

    @vanyamba-electronics
    По Вашей просьбе оформил в ООП.
    С такими алгоритмами недолго и программистом стать.
    https://onlinegdb.com/q6b6nwNdX
    Ответ написан
    Комментировать
  • Как переделать код под ООП?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Программирование в ООП предполагает что мир состоит из "объектов".
    Например твоя программ (процесс) калькулятор это уже объект. Даже не имея декларации
    она уже является объектом с точки зрения ОС.

    Но если твой преподаватель - такой душный, то сделай

    class Calculator {
       ...
    }

    Можно сделать объектом число и операцию над ним (унарная или бинарная) но это уже немотивированное
    (или слабо мотивированное) действие. Теоретики ООП всегда пишут что введение объекта должно иметь смысл. Иначе так можно
    дойти до абсурда и объявлять объектом любую чепуху, что только усложнит написание кода
    и создаст бюрократию на пустом месте.

    Поясни это преподавателю если он будет сильно настаивать на том что мало объектов.
    Ответ написан
    Комментировать
  • Как переделать код под ООП?

    @code_panik
    Сначала замечу, что нет никакого смысла переписывать код в стиле ООП, потому что класс, назовем его Calculator, не имеет состояния, не хранит данных, состоит только из функций. То есть весь код будет выглядеть как раньше, но придется приписывать в начало операций имя объекта класса типа Calculator, напр. calculator.divide(1, 2);. Достаточно собрать эти функции в нашем пространстве имен my_math, например,
    namespace my_math {
    bool operator<(const std::string& st1, const std::string& st2) {
        size_t len1 = st1.length();
        size_t len2 = st2.length();
        if (len1 != len2) return (len1 < len2);
        long int i = 0;
            // ищем разряд, в котором значения отличаются
        while (i < len1 && st1[i] == st2[i])
        {
            i++;
        }
            // если разряд найден, то меньше число с меньшей цифрой для положительных и с большей цифрой для отрицательных, иначе числа равны
        return (i < len1) && ((st1[i] < st2[i]) );
    }
    bool les(int lhs, int rhs) {
        return lhs <= rhs;
    }
    }
    
    int main() {
        using my_math::operator<; // иначе cout << my_math::operator<(s1, s2) << endl;
        std::string s1 = "1", s2 = "2";
        cout << (s1 < s2) << endl;
    
        int a = 1, b = 2;
        cout << (my_math::les(a, b)) << endl;
        return 0;
    }

    Для ООП можно воспользоваться примером https://godbolt.org/z/rEPzdKe4j. В нем определены два файла: calculator.h и calculator.cpp с объявлением класса и реализацией соответственно.
    Замечу, что в реализациях бинарных операций не следует передавать string по значению, чтобы избежать лишних копирований. Если заменить тип аргумента std::string на ссылочный const std::string&, придется поправить код, чтобы он не изменял значения аргументов.
    Ответ написан
    Комментировать
  • Как превратить строку в многомерный массив?

    Vindicar
    @Vindicar
    RTFM!
    Разбить сначала по символу перевода строки (\n), потом каждый кусок разбить по пробелу.
    Гугли методы строки .split() и .splitlines(). Ну и преобразовать в int или float в конце.
    Ответ написан
    Комментировать
  • Как можно оптимизировать код из задачи ЕГЭ?

    sswwssww
    @sswwssww
    from itertools import combinations
    
    sq = {e**2: e for e in range(1, 5001)}
    maximum = 0
    cmaximum = 0
    count = 0
    
    for a, b in combinations(sq, 2):
        ab = a + b
        if ab in sq:
            count += 1
            tmp_maximum = sq[a] + sq[b] + sq[ab]
            cmaximum, maximum = (sq[ab], tmp_maximum) if tmp_maximum > maximum else (cmaximum, maximum)
    print(count, cmaximum)
    Ответ написан
    6 комментариев
  • Каким образом можно сократить код?

    MinTnt
    @MinTnt
    Если нужно именно сократить, без сильных изменений в самом коде... то придётся пожертвовать временем исполнения...
    (locals().update({'k': 1, 'a': []}), [(a.append([]), [(a[i].append(k), loc.update({'k': k+1})) for j in range(3)]) for loc in [locals()] for i in range(3)], [print(*a[i]) for i in range(3)])

    ...но в принципе это всё возможно.

    Ну а вообще, чтобы сократить написанное, можно
    a = [[k for k in range(x, x+3)] for x in range(1, 10, 3)]
    for i in a:
        print(*a)
    Ответ написан
    Комментировать