Поиск минимального числа при условии

Всем привет!

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

Условие

есть набор чисел, допустим [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]

Это НОК, наименьшее общее кратное.
В школе дети раскладывают каждое число на простые множители, затем переписывают в НОК любое число и дополняют недостающими множителями из оставшихся чисел (6 класс).
Видимо, есть готовые алгоритмы, но мне как-то не приходилось ими пользоваться.

Сообщение отредактировано: swf - 07.07.20, 18:55

swf, сенкс за наводочку Нашел какую-то теорему:

Цитата

Пусть даны целые положительные числа a1, a2, …, ak, наименьшее общее кратное mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

Пока остается вопрос - как уменьшить количество вычислений для нахождения этого числа.

Есть, наверно, готовые разложения натуральных чисел на простые множители. Сразу пользоваться этими разложениями.
А вот сравнение разложения проверяемого числа на простые множители с разложением НОК'а на предмет недостающих сомножителей зависит от того, как эти разложения хранятся.
За счёт увеличения памяти можно ускорить процедуру сравнения.

Цитата swf @ 07.07.20, 21:45

Есть, наверно, готовые разложения натуральных чисел на простые множители

Это, увы, не вариант - слишком большой объем таких данных будет.
Но уже два подхода нарисовались - буду тестировать, замерять.

Цитата JoeUser @ 07.07.20, 22:19

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

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

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

Цитата JoeUser @ 07.07.20, 18:36

найти минимальное число, которое нацело делится на любое из чисел набора...

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

Цитата JoeUser @ 07.07.20, 22:19

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

Либо скорость, либо размер. Промежуточный вариант - хранимая таблица простых чисел в диапазоне значений чисел набора.

Цитата JoeUser @ 07.07.20, 22:19

1) Это сколько?

Цитата Akina @ 08.07.20, 04:22

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

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

для реализации для x64:
количество чисел в наборе - 1..2³²
значение числа в наборе - 1..2⁶⁴

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

Цитата Black_Dragon @ 08.07.20, 02:37

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

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

Добавлено 08.07.20, 06:59

Цитата Black_Dragon @ 08.07.20, 02:37

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

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

Добавлено 08.07.20, 07:02

Цитата Akina @ 08.07.20, 04:22

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

В принципе можно и заценить скорость построения с помощью решета Эратосфена или Аткина. Но опять же - каков объем может получится...

В общем, пока накидал свой алгоритм, который пользовал в самом первом сообщении на обычном Си:

#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

Пока мне это нравится. Позже попробую алгоритмы от "арифметической классики"

Сделал программку...
64 битка.
Значение чисел 2¹⁵ (int rand())
Массив 100тыс. рандомов

nok = 15375599254564976780
time = 0.0202832
но в основном: fail, из-за

Цитата JoeUser @ 08.07.20, 06:50

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

Так что, оптимистические хотелки...

Цитата

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

для реализации для x64:
количество чисел в наборе - 1..2³²
значение числа в наборе - 1..2⁶⁴

Добавлено 08.07.20, 08:36

#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";
}

Цитата Black_Dragon @ 08.07.20, 08:34

Так что, оптимистические хотелки...

Ну да, с большим количеством фэйлов неинтерсно. Попробую замутить типа "программного стенда для теста" на более скромых хотелках

JoeUser
ошибка у меня логическая.

    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

Добавлено 08.07.20, 09:11

Цитата JoeUser @ 08.07.20, 06:50

значение числа в наборе - 1..2³²

Вообщем перемножение этих чисел почти всегда дает переполнение в 32 бита...
Надо занижать лимиты....

Сообщение отредактировано: Black_Dragon - 08.07.20, 09:11

Цитата Black_Dragon @ 08.07.20, 08:54

Надо занижать лимиты....

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

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

Программа генерации наборов

Скрытый текст

#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;
}

Получившийся набор

Скрытый текст

{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}

Моя программа тестирования алгоритмов

Скрытый текст

#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 результата.
На моем компе это получилось вот так:

Скрытый текст

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 Кбайт, скачиваний: 965)

Реализация на VBA:
Вычисление НОК на базе НОД

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 @ 08.07.20, 10:45

Не мы поборемся

Ни как...
2¹⁶ * 2¹⁶ = 2³²
Т.е. диапазон значений надо уменьшать.
Тогда встает вопрос размера данных, либо тоже уменьшать, либо считать, что в данных есть дубликаты и мы принципиально их не удаляем, а используем (для увеличение нагрузки и размера массива)