На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (3) [1] 2 3  все  ( Перейти к последнему сообщению )  
> Поиск минимального числа при условии
    Всем привет!

    Интересует сабж.

    Условие

    есть набор чисел, допустим [1,2,3,4,5,6,7,8,9,10,11,12], нужно найти минимальное число, которое нацело делится на любое из чисел набора...

    Мое решение

    Очевидное число, удовлетворяющее условию D=1*2*3*4*5*6*7*8*9*10*11*12 = 479001600, и оно явно избыточное
    Тогда я стал из произведения убирать множители:

    1) 6, если число делится на 12, значит будет делится и на 6
    2) 5, если число делится на 10, значит будет делится и на 5
    3) 4, если число делится на 12, значит будет делится и на 4
    4) 3, если число делится на 12, значит будет делится и на 3
    5) 2, если число делится на 12, значит будет делится и на 2
    6) 1, ну тут понятно

    Итого получилось: Dmin = 7*8*9*10*11*12 = 665280

    Вопросы

    Я действительно нашел минимальное число, удовлетворяющее условию?
    Как формализовать алгоритм нахождения такого минимального числа для произвольного набора чисел? Например [2,3,17,4,3,3]
    Мои программные ништякиhttps://majestio.info
      Это НОК, наименьшее общее кратное.
      В школе дети раскладывают каждое число на простые множители, затем переписывают в НОК любое число и дополняют недостающими множителями из оставшихся чисел (6 класс).
      Видимо, есть готовые алгоритмы, но мне как-то не приходилось ими пользоваться.
      Сообщение отредактировано: swf -
        swf, сенкс за наводочку :) Нашел какую-то теорему:
        Цитата
        Пусть даны целые положительные числа a1, a2, …, ak, наименьшее общее кратное mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

        Пока остается вопрос - как уменьшить количество вычислений для нахождения этого числа.
        Мои программные ништякиhttps://majestio.info
          Есть, наверно, готовые разложения натуральных чисел на простые множители. Сразу пользоваться этими разложениями.
          А вот сравнение разложения проверяемого числа на простые множители с разложением НОК'а на предмет недостающих сомножителей зависит от того, как эти разложения хранятся.
          За счёт увеличения памяти можно ускорить процедуру сравнения.
            Цитата swf @
            Есть, наверно, готовые разложения натуральных чисел на простые множители

            Это, увы, не вариант - слишком большой объем таких данных будет.
            Но уже два подхода нарисовались - буду тестировать, замерять.
            Мои программные ништякиhttps://majestio.info
              Цитата JoeUser @
              Это, увы, не вариант - слишком большой объем таких данных будет.

              1) Это сколько?
              2) Каков критерий быстродействия?

              И самое главное:
              Если для ускорения вычисления требуется трансформация данных или предварительные расчеты, то их надо, если имеется такая возможность, то производить их в момент чтения данных откуда-то (например, из файла)
              MS Visual Studio 2019 (C++)
                Цитата JoeUser @
                найти минимальное число, которое нацело делится на любое из чисел набора...

                Какие есть ограничения на значения чисел набора?

                Цитата JoeUser @
                не вариант - слишком большой объем таких данных будет.

                Либо скорость, либо размер. Промежуточный вариант - хранимая таблица простых чисел в диапазоне значений чисел набора.
                Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
                Есть претензии ко мне как к участнику? да ради бога.
                Не нравятся мои ответы? не читайте их.
                В общем, берегите себя. Нервные клетки не восстанавливаются.
                  Цитата JoeUser @
                  1) Это сколько?

                  Цитата Akina @
                  Какие есть ограничения на значения чисел набора?


                  для реализации для x32:
                  количество чисел в наборе - 1..232
                  значение числа в наборе - 1..232

                  для реализации для x64:
                  количество чисел в наборе - 1..232
                  значение числа в наборе - 1..264

                  Ну и результат может отсутствовать, если результирующее число не влезает в EAX (x32) / RAX (x64) без переполнения

                  Цитата Black_Dragon @
                  2) Каков критерий быстродействия?

                  Ограничений по времени нет, а пожелание есть - меньшее время вычисления.

                  Добавлено
                  Цитата Black_Dragon @
                  И самое главное:
                  Если для ускорения вычисления требуется трансформация данных или предварительные расчеты, то их надо, если имеется такая возможность, то производить их в момент чтения данных откуда-то (например, из файла)

                  Не вопрос, пусть массив чисел на старте будет отсортирован и не иметь дублей.

                  Добавлено
                  Цитата Akina @
                  Промежуточный вариант - хранимая таблица простых чисел в диапазоне значений чисел набора.

                  В принципе можно и заценить скорость построения с помощью решета Эратосфена или Аткина. Но опять же - каков объем может получится...
                  Мои программные ништякиhttps://majestio.info
                    В общем, пока накидал свой алгоритм, который пользовал в самом первом сообщении на обычном Си:

                    ExpandedWrap disabled
                      #include <stdio.h>
                      #include <string.h>
                       
                      const int Size = sizeof(unsigned int);
                      unsigned int A[] = {1,2,3,4,5,6,7,8,9,10,11,12};
                       
                      void PrintArray(unsigned int *X, int len) {
                        int Res = 1;
                        for (int i=0; i<len; i++) {
                          printf("%d ",*(X+i));
                          Res *= *(X+i);
                        }
                        printf("\nRes: %d\n",Res);
                      }
                       
                      int main(void) {
                       
                        int Len = sizeof(A)/Size;
                        int End = Len-1;
                        int Cur = End-1;
                        int Cnt = 0;
                        while (End>0) {
                          Cnt++;
                          if (A[End] % A[Cur] == 0) {
                            memmove((A+Cur),(A+Cur+1),(Len-Cur)*Size);
                            Len--;
                            End--;
                          }
                          Cur--;
                          if (Cur<0) {
                            End--;
                            Cur = End-1;
                          }
                        }
                        /* Печать результирующего набора и полученное число */
                        PrintArray(A,Len);
                        /* Печать количества итераций */
                        printf("%d",Cnt);
                        return 0;
                      }


                    Получилось следующее

                    Для набора [1,2,3,4,5,6,7,8,9,10,11,12]:

                    Оставшийся набор = 7 8 9 10 11 12
                    Полученное число = 665280
                    Циклов = 23

                    Для набора [17,19,23,29,31,37,41,43,47,53]:

                    Оставшийся набор = 17 19 23 29 31 37 41 43 47 53
                    Полученное число = 2085895579
                    Циклов = 45

                    Пока мне это нравится. Позже попробую алгоритмы от "арифметической классики" :)
                    Мои программные ништякиhttps://majestio.info
                      Сделал программку...
                      64 битка.
                      Значение чисел 215 (int rand())
                      Массив 100тыс. рандомов

                      nok = 15375599254564976780
                      time = 0.0202832
                      но в основном: fail, из-за
                      Цитата JoeUser @
                      Ну и результат может отсутствовать, если результирующее число не влезает в EAX (x32) / RAX (x64) без переполнения


                      Так что, оптимистические хотелки...
                      Цитата
                      для реализации для x32:
                      количество чисел в наборе - 1..232
                      значение числа в наборе - 1..232

                      для реализации для x64:
                      количество чисел в наборе - 1..232
                      значение числа в наборе - 1..264


                      Добавлено
                      ExpandedWrap disabled
                        #include <fcntl.h>
                        #include <io.h>
                        #include <wchar.h>
                        #include <locale>
                        #include <iostream>
                         
                        #ifdef _MSC_VER
                        #define NOMINMAX
                        #include <windows.h>
                         
                        __forceinline double time()
                        {
                            LARGE_INTEGER counter, frequency;
                            QueryPerformanceCounter(&counter);
                            QueryPerformanceFrequency(&frequency);
                            return double(counter.QuadPart) / double(frequency.QuadPart);
                        }
                        #else
                        #include <sys/time.h>
                         
                        inline __attribute__((always_inline)) double time()
                        {
                            timeval t1;
                            gettimeofday(&t1, NULL);
                            return t1.tv_sec + t1.tv_usec * 0.000001;
                        }
                        #endif
                         
                        using m_type = UINT64;
                         
                        m_type nod1(m_type a, m_type b) {
                            return b ? nod1(b, a % b) : a;
                        }
                         
                        m_type nod2(m_type a, m_type b) {
                            while (b) {
                                a %= b;
                                std::swap(a, b);
                            }
                            return a;
                        }
                         
                        m_type MmM = std::numeric_limits<m_type>::max();
                        m_type nok1(m_type a, m_type b)
                        {
                            unsigned long long val = (a * b) / nod2(a, b);
                            return (val > MmM) ? (0) : (m_type(val));
                        }
                         
                        const m_type count = 100000;
                         
                        //u_int arr[count] = { 2, 5, 17, 24, 9, 35, 11, 42, 29, 18 };
                         
                        //#define _PRN
                         
                        int wmain()
                        {
                            _setmode(_fileno(stdout), _O_U8TEXT);
                            std::wcout << L"Search NOK!\n";
                            srand((unsigned)time(0));
                            m_type *arr = new m_type[count];
                            for (m_type i = 0; i < count; ++i)
                            {
                                arr[i] = rand();
                        #ifdef _PRN
                                std::wcout << i << L" = " << arr[i] << L"\n";
                        #endif
                            }
                            bool fail = false;
                            m_type nok = arr[0];
                            double t_s = time();
                            for (u_int i = 1; i < count; ++i)
                            {
                                nok = nok1(nok, arr[i]);
                                if (nok == 0)
                                {
                                    fail = true;
                                    break;
                                }
                            }
                            double t_e = time();
                            delete[] arr;
                            if (fail) std::wcout << L"Nok fail!\n";
                            else  std::wcout << L"nok = " << nok << L"\n";
                            std::wcout << L"time = " << (t_e - t_s) << L"\n";
                        }
                      MS Visual Studio 2019 (C++)
                        Цитата Black_Dragon @
                        Так что, оптимистические хотелки...

                        Ну да, с большим количеством фэйлов неинтерсно. Попробую замутить типа "программного стенда для теста" на более скромых хотелках :)
                        Мои программные ништякиhttps://majestio.info
                          JoeUser
                          ошибка у меня логическая.
                          ExpandedWrap disabled
                                for (m_type i = 0; i < count; ++i)
                                {
                                    rand_s(arr + i);
                                    if (arr[i] == 0) arr[i] = 1;
                            #ifdef _PRN
                                    std::wcout << i << L" = " << arr[i] << L"\n";
                            #endif
                                }

                          Но!!!
                          1) нужен генератор большого диапазона, виндовый максимум x32
                          2) UINT64 = unsigned long long, надо усложнять проверку на переполнение при x64.

                          щас потестю на x32 + OpenMP

                          Добавлено
                          Цитата JoeUser @
                          значение числа в наборе - 1..232

                          Вообщем перемножение этих чисел почти всегда дает переполнение в 32 бита...
                          Надо занижать лимиты....
                          Сообщение отредактировано: Black_Dragon -
                          MS Visual Studio 2019 (C++)
                            Цитата Black_Dragon @
                            Надо занижать лимиты....

                            Не, мы поборемся :lol: И вот что получилось ...

                            Сперва я сделал тестовый массив - 32 набора, в каждом по 10 случайных чисел в диапазоне 1..512

                            Программа генерации наборов
                            Скрытый текст
                            ExpandedWrap disabled
                              #include <algorithm>
                              #include <iostream>
                              #include <iomanip>
                              #include <vector>
                               
                              int main() {
                                std::vector<std::vector<int>> A;
                                std::srand(43453524);
                                A.reserve(32);
                                for (int i=0; i<32; i++) {
                                  A.push_back(std::vector<int>());
                                  A[i].reserve(1024);
                                  for (int j=0; j<126; j++) {
                                    A[i].push_back(std::rand() % 512+1);
                                  }
                                  std::sort(A[i].begin(),A[i].end());
                                  A[i].erase(std::unique(A[i].begin(), A[i].end()), A[i].end());
                                  if (A[i].size()>10) {
                                    A[i].erase(A[i].begin()+8,A[i].end()-14);
                                    std::cout << "{";
                                    for(int a=0; a<10; a++) {
                                      std::cout << "0x" << std::setfill('0') << std::setw(4) << std::right << std::hex << A[i][a];
                                      if (a<9) std::cout << ",";
                                    }
                                    std::cout << "}";
                                    if (i<31) std::cout << ",";
                                    std::cout << std::endl;
                                  } else {
                                    std::cout << "Беда!" << std::endl;
                                    return 1;
                                  }
                                }
                                return 0;
                              }


                            Получившийся набор
                            Скрытый текст
                            ExpandedWrap disabled
                              {0x0003,0x0004,0x000d,0x0017,0x001b,0x001d,0x0021,0x0022,0x01d2,0x01d6},
                              {0x0001,0x000b,0x000c,0x000d,0x000e,0x0012,0x0019,0x001d,0x01bd,0x01c6},
                              {0x0001,0x000d,0x000e,0x0015,0x0023,0x0028,0x002c,0x002e,0x01d2,0x01d5},
                              {0x0006,0x000b,0x0012,0x0015,0x0019,0x001c,0x001f,0x0027,0x01b2,0x01c1},
                              {0x0003,0x0009,0x000d,0x000e,0x0010,0x0012,0x0013,0x0015,0x01d5,0x01d6},
                              {0x0007,0x0009,0x000f,0x0018,0x001a,0x001c,0x001e,0x0028,0x01ca,0x01cb},
                              {0x0004,0x0008,0x0011,0x0014,0x0018,0x001b,0x001e,0x0028,0x01b9,0x01ba},
                              {0x0008,0x0011,0x0024,0x0027,0x0031,0x0037,0x0038,0x003c,0x01b5,0x01bd},
                              {0x0003,0x0004,0x0006,0x000a,0x000b,0x0010,0x0013,0x0019,0x01bf,0x01c1},
                              {0x0005,0x0006,0x0009,0x000c,0x001f,0x0027,0x0028,0x002f,0x01c1,0x01cd},
                              {0x0003,0x0004,0x0006,0x0007,0x0016,0x0019,0x001c,0x001d,0x01db,0x01dc},
                              {0x0002,0x0009,0x000c,0x0012,0x0013,0x0014,0x0018,0x001f,0x01b9,0x01bb},
                              {0x000d,0x0010,0x0017,0x001e,0x001f,0x0021,0x0023,0x002d,0x01c3,0x01c4},
                              {0x0002,0x0005,0x0007,0x000a,0x000e,0x0010,0x0014,0x0015,0x01c6,0x01c7},
                              {0x0001,0x0002,0x0009,0x000d,0x0013,0x0018,0x001a,0x0024,0x01cd,0x01cf},
                              {0x0008,0x000b,0x000f,0x0014,0x0016,0x001c,0x0021,0x0029,0x01c5,0x01c8},
                              {0x0007,0x000b,0x000e,0x0010,0x0012,0x0016,0x0025,0x002e,0x01d8,0x01dd},
                              {0x0007,0x0008,0x000f,0x0011,0x0022,0x0028,0x002b,0x0036,0x01c1,0x01c4},
                              {0x0003,0x0019,0x0021,0x0022,0x0029,0x0031,0x0034,0x0036,0x01bf,0x01c2},
                              {0x0002,0x0004,0x0006,0x000d,0x0010,0x0011,0x0012,0x0015,0x01cb,0x01ce},
                              {0x0001,0x0007,0x000d,0x0012,0x0022,0x0024,0x002a,0x002f,0x01cf,0x01d0},
                              {0x0001,0x0002,0x0008,0x0009,0x000b,0x000c,0x000d,0x0010,0x01c1,0x01c8},
                              {0x000b,0x000e,0x000f,0x0015,0x001b,0x001d,0x0021,0x0023,0x019c,0x019f},
                              {0x0002,0x0004,0x000f,0x0012,0x0015,0x0016,0x001f,0x0020,0x01b6,0x01c4},
                              {0x0002,0x0006,0x0008,0x000b,0x0019,0x0032,0x0037,0x003a,0x01c8,0x01c9},
                              {0x0001,0x0005,0x0008,0x0009,0x000d,0x0011,0x0012,0x0013,0x01d5,0x01db},
                              {0x0001,0x0003,0x0004,0x0005,0x000b,0x0012,0x0014,0x001a,0x01c3,0x01c4},
                              {0x0001,0x000b,0x0010,0x001d,0x0021,0x0028,0x002a,0x0036,0x01c1,0x01c2},
                              {0x0002,0x0008,0x000b,0x000e,0x000f,0x0013,0x001f,0x0021,0x01d9,0x01dc},
                              {0x0004,0x0009,0x0011,0x001c,0x001d,0x0027,0x0029,0x0033,0x01cc,0x01ce},
                              {0x0003,0x000c,0x000d,0x0016,0x0017,0x001a,0x001b,0x0020,0x01be,0x01c7},
                              {0x0008,0x000c,0x000e,0x0010,0x0017,0x0019,0x001c,0x001d,0x01a2,0x01b0}

                            Моя программа тестирования алгоритмов
                            Скрытый текст
                            ExpandedWrap disabled
                              #include <iostream>
                              #include <vector>
                              #include <chrono>
                              #include "BigIntegerLibrary.hh"
                               
                              std::vector<BigInteger> R;
                               
                              void YouTest(std::vector<int> &V) {
                                int Len = 10;
                                int End = 9;
                                int Cur = 0;
                                while (End>0) {
                                  if (V[End] % V[Cur] == 0) {
                                    V.erase(V.begin()+Cur);
                                    Len--;
                                    End--;
                                  }
                                  Cur--;
                                  if (Cur<0) {
                                    End--;
                                    Cur = End-1;
                                  }
                                }
                                BigInteger Tmp = 1;
                                for(auto &&i:V) Tmp*=i;
                                R.push_back(Tmp);
                              }
                               
                              void Func() {
                                std::vector<std::vector<int>> Arr = {
                                  {0x0003,0x0004,0x000d,0x0017,0x001b,0x001d,0x0021,0x0022,0x01d2,0x01d6},
                                  {0x0001,0x000b,0x000c,0x000d,0x000e,0x0012,0x0019,0x001d,0x01bd,0x01c6},
                                  {0x0001,0x000d,0x000e,0x0015,0x0023,0x0028,0x002c,0x002e,0x01d2,0x01d5},
                                  {0x0006,0x000b,0x0012,0x0015,0x0019,0x001c,0x001f,0x0027,0x01b2,0x01c1},
                                  {0x0003,0x0009,0x000d,0x000e,0x0010,0x0012,0x0013,0x0015,0x01d5,0x01d6},
                                  {0x0007,0x0009,0x000f,0x0018,0x001a,0x001c,0x001e,0x0028,0x01ca,0x01cb},
                                  {0x0004,0x0008,0x0011,0x0014,0x0018,0x001b,0x001e,0x0028,0x01b9,0x01ba},
                                  {0x0008,0x0011,0x0024,0x0027,0x0031,0x0037,0x0038,0x003c,0x01b5,0x01bd},
                                  {0x0003,0x0004,0x0006,0x000a,0x000b,0x0010,0x0013,0x0019,0x01bf,0x01c1},
                                  {0x0005,0x0006,0x0009,0x000c,0x001f,0x0027,0x0028,0x002f,0x01c1,0x01cd},
                                  {0x0003,0x0004,0x0006,0x0007,0x0016,0x0019,0x001c,0x001d,0x01db,0x01dc},
                                  {0x0002,0x0009,0x000c,0x0012,0x0013,0x0014,0x0018,0x001f,0x01b9,0x01bb},
                                  {0x000d,0x0010,0x0017,0x001e,0x001f,0x0021,0x0023,0x002d,0x01c3,0x01c4},
                                  {0x0002,0x0005,0x0007,0x000a,0x000e,0x0010,0x0014,0x0015,0x01c6,0x01c7},
                                  {0x0001,0x0002,0x0009,0x000d,0x0013,0x0018,0x001a,0x0024,0x01cd,0x01cf},
                                  {0x0008,0x000b,0x000f,0x0014,0x0016,0x001c,0x0021,0x0029,0x01c5,0x01c8},
                                  {0x0007,0x000b,0x000e,0x0010,0x0012,0x0016,0x0025,0x002e,0x01d8,0x01dd},
                                  {0x0007,0x0008,0x000f,0x0011,0x0022,0x0028,0x002b,0x0036,0x01c1,0x01c4},
                                  {0x0003,0x0019,0x0021,0x0022,0x0029,0x0031,0x0034,0x0036,0x01bf,0x01c2},
                                  {0x0002,0x0004,0x0006,0x000d,0x0010,0x0011,0x0012,0x0015,0x01cb,0x01ce},
                                  {0x0001,0x0007,0x000d,0x0012,0x0022,0x0024,0x002a,0x002f,0x01cf,0x01d0},
                                  {0x0001,0x0002,0x0008,0x0009,0x000b,0x000c,0x000d,0x0010,0x01c1,0x01c8},
                                  {0x000b,0x000e,0x000f,0x0015,0x001b,0x001d,0x0021,0x0023,0x019c,0x019f},
                                  {0x0002,0x0004,0x000f,0x0012,0x0015,0x0016,0x001f,0x0020,0x01b6,0x01c4},
                                  {0x0002,0x0006,0x0008,0x000b,0x0019,0x0032,0x0037,0x003a,0x01c8,0x01c9},
                                  {0x0001,0x0005,0x0008,0x0009,0x000d,0x0011,0x0012,0x0013,0x01d5,0x01db},
                                  {0x0001,0x0003,0x0004,0x0005,0x000b,0x0012,0x0014,0x001a,0x01c3,0x01c4},
                                  {0x0001,0x000b,0x0010,0x001d,0x0021,0x0028,0x002a,0x0036,0x01c1,0x01c2},
                                  {0x0002,0x0008,0x000b,0x000e,0x000f,0x0013,0x001f,0x0021,0x01d9,0x01dc},
                                  {0x0004,0x0009,0x0011,0x001c,0x001d,0x0027,0x0029,0x0033,0x01cc,0x01ce},
                                  {0x0003,0x000c,0x000d,0x0016,0x0017,0x001a,0x001b,0x0020,0x01be,0x01c7},
                                  {0x0008,0x000c,0x000e,0x0010,0x0017,0x0019,0x001c,0x001d,0x01a2,0x01b0}
                                };
                                for (auto &&i:Arr) YouTest(i);
                              }
                               
                              int main() {
                                R.reserve(32*1024*1024);
                                auto start = std::chrono::high_resolution_clock::now();
                                for(int i=0; i<1024*1024; i++) Func();
                                auto stop = std::chrono::high_resolution_clock::now();
                                std::cout << "Elapsed: "
                                        << std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count()
                                        << " ms"
                                        << std::endl;
                                for(int i=0; i<32; i++) std::cout << R[i] << std::endl;
                                std::cout << std::endl;
                                return 0;
                              }

                            Ну и краткое описание
                            Тест запускается 1024*1024 раза на весь набор из 32 элементов. Собственно это время обработки и считается. Чтобы избежать переполнения при умножении - задействовал библиотечку BigInteger. Что тут может немного повлиять на валидность результата - то, что я собираю в вектор результаты. Т.е. работа с вектором может (или не может) вносить значимые поправки. В принципе, если это убрать - будет точнее. Ну как есть ...

                            После отработки программы выдается затраченное время и первые 32 результата.
                            На моем компе это получилось вот так:
                            Скрытый текст
                            ExpandedWrap disabled
                              Elapsed: 139626 ms
                              230128058365920
                              63339071796000
                              2366944016236800
                              22119902204400
                              4610069493120
                              39668386867200
                              2576712902400
                              42029625862224000
                              1006726248000
                              50810699291040
                              24234302400
                              994194492480
                              47139350482224000
                              19434105600
                              91100887488
                              51649105939200
                              33990937085952
                              67293822556800
                              31829509251540000
                              16672848192
                              6747934991616
                              50593061376
                              681910925157000
                              24497962030080
                              33238524000
                              673511202000
                              1908054720
                              280668592512000
                              7352018815680
                              126653438751840
                              27679937725440
                              16187699404800


                            Файл проекта под qmake прилагается, если кому интересно.
                            Прикреплённый файлПрикреплённый файлtesto_testo.7z (20,21 Кбайт, скачиваний: 19)
                            Мои программные ништякиhttps://majestio.info
                              Реализация на VBA:
                              Вычисление НОК на базе НОД

                              ExpandedWrap disabled
                                Sub main()
                                    Dim arr, x, myLCD As Double
                                    arr = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12) 'массив значений
                                    myLCD = 1
                                    For Each x In arr
                                        myLCD = myLCD * x / myGCD(myLCD, x)
                                    Next
                                    Debug.Print myLCD 'наименьшее общее кратное
                                End Sub
                                 
                                Sub main2()
                                    Dim arr, x, myLCD As Double
                                    arr = Array(2, 3, 17, 4, 3, 3)
                                    myLCD = 1
                                    For Each x In arr
                                        myLCD = myLCD * x / myGCD(myLCD, x)
                                    Next
                                    Debug.Print myLCD 'наименьшее общее кратное
                                End Sub
                                 
                                Sub main3()
                                    Dim arr, x, myLCD As Double
                                    arr = Array(17, 19, 23, 29, 31, 37, 41, 43, 47, 53)
                                    myLCD = 1
                                    For Each x In arr
                                        myLCD = myLCD * x / myGCD(myLCD, x)
                                    Next
                                    Debug.Print myLCD 'наименьшее общее кратное
                                End Sub
                                 
                                Function myGCD(ByVal a As Double, ByVal b As Double) As Double 'функция расчета наибольшего общего делителя
                                    Dim t As Double
                                    If a < b Then t = a: a = b: b = t
                                    While b
                                        t = b
                                        b = myMOD(a, b)
                                        a = t
                                    Wend
                                    myGCD = a
                                End Function
                                 
                                Function myMOD(a As Double, b As Double) As Double 'остаток от деления для чисел типа Double
                                    myMOD = a - Fix(a / b) * b
                                End Function

                              Результат для примеров
                              27720
                              204
                              1,08522006251049E+15
                              Работает с типом данных Double, что бы не было переполнения (но для больших чисел может быть ошибка округления)
                                Цитата JoeUser @
                                Не мы поборемся

                                Ни как...
                                216 * 216 = 232
                                Т.е. диапазон значений надо уменьшать.
                                Тогда встает вопрос размера данных, либо тоже уменьшать, либо считать, что в данных есть дубликаты и мы принципиально их не удаляем, а используем (для увеличение нагрузки и размера массива)
                                MS Visual Studio 2019 (C++)
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1595 ]   [ 16 queries used ]   [ Generated: 8.08.20, 03:44 GMT ]