Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.136.234.163] |
|
Страницы: (3) [1] 2 3 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем привет!
Интересует сабж. Условие есть набор чисел, допустим [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] |
Сообщ.
#2
,
|
|
|
Это НОК, наименьшее общее кратное.
В школе дети раскладывают каждое число на простые множители, затем переписывают в НОК любое число и дополняют недостающими множителями из оставшихся чисел (6 класс). Видимо, есть готовые алгоритмы, но мне как-то не приходилось ими пользоваться. |
Сообщ.
#3
,
|
|
|
swf, сенкс за наводочку Нашел какую-то теорему:
Цитата Пусть даны целые положительные числа a1, a2, …, ak, наименьшее общее кратное mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak). Пока остается вопрос - как уменьшить количество вычислений для нахождения этого числа. |
Сообщ.
#4
,
|
|
|
Есть, наверно, готовые разложения натуральных чисел на простые множители. Сразу пользоваться этими разложениями.
А вот сравнение разложения проверяемого числа на простые множители с разложением НОК'а на предмет недостающих сомножителей зависит от того, как эти разложения хранятся. За счёт увеличения памяти можно ускорить процедуру сравнения. |
Сообщ.
#5
,
|
|
|
Цитата swf @ Есть, наверно, готовые разложения натуральных чисел на простые множители Это, увы, не вариант - слишком большой объем таких данных будет. Но уже два подхода нарисовались - буду тестировать, замерять. |
Сообщ.
#6
,
|
|
|
Цитата JoeUser @ Это, увы, не вариант - слишком большой объем таких данных будет. 1) Это сколько? 2) Каков критерий быстродействия? И самое главное: Если для ускорения вычисления требуется трансформация данных или предварительные расчеты, то их надо, если имеется такая возможность, то производить их в момент чтения данных откуда-то (например, из файла) |
Сообщ.
#7
,
|
|
|
Цитата JoeUser @ найти минимальное число, которое нацело делится на любое из чисел набора... Какие есть ограничения на значения чисел набора? Цитата JoeUser @ не вариант - слишком большой объем таких данных будет. Либо скорость, либо размер. Промежуточный вариант - хранимая таблица простых чисел в диапазоне значений чисел набора. |
Сообщ.
#8
,
|
|
|
Цитата JoeUser @ 1) Это сколько? Цитата Akina @ Какие есть ограничения на значения чисел набора? для реализации для x32: количество чисел в наборе - 1..232 значение числа в наборе - 1..232 для реализации для x64: количество чисел в наборе - 1..232 значение числа в наборе - 1..264 Ну и результат может отсутствовать, если результирующее число не влезает в EAX (x32) / RAX (x64) без переполнения Цитата Black_Dragon @ 2) Каков критерий быстродействия? Ограничений по времени нет, а пожелание есть - меньшее время вычисления. Добавлено Цитата Black_Dragon @ И самое главное: Если для ускорения вычисления требуется трансформация данных или предварительные расчеты, то их надо, если имеется такая возможность, то производить их в момент чтения данных откуда-то (например, из файла) Не вопрос, пусть массив чисел на старте будет отсортирован и не иметь дублей. Добавлено Цитата Akina @ Промежуточный вариант - хранимая таблица простых чисел в диапазоне значений чисел набора. В принципе можно и заценить скорость построения с помощью решета Эратосфена или Аткина. Но опять же - каков объем может получится... |
Сообщ.
#9
,
|
|
|
В общем, пока накидал свой алгоритм, который пользовал в самом первом сообщении на обычном Си:
#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 Пока мне это нравится. Позже попробую алгоритмы от "арифметической классики" |
Сообщ.
#10
,
|
|
|
Сделал программку...
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 Добавлено #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"; } |
Сообщ.
#11
,
|
|
|
Цитата Black_Dragon @ Так что, оптимистические хотелки... Ну да, с большим количеством фэйлов неинтерсно. Попробую замутить типа "программного стенда для теста" на более скромых хотелках |
Сообщ.
#12
,
|
|
|
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 Добавлено Цитата JoeUser @ значение числа в наборе - 1..232 Вообщем перемножение этих чисел почти всегда дает переполнение в 32 бита... Надо занижать лимиты.... |
Сообщ.
#13
,
|
|
|
Цитата Black_Dragon @ Надо занижать лимиты.... Не, мы поборемся И вот что получилось ... Сперва я сделал тестовый массив - 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 Кбайт, скачиваний: 967) |
Сообщ.
#14
,
|
|
|
Реализация на 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, что бы не было переполнения (но для больших чисел может быть ошибка округления) |
Сообщ.
#15
,
|
|
|
Цитата JoeUser @ Не мы поборемся Ни как... 216 * 216 = 232 Т.е. диапазон значений надо уменьшать. Тогда встает вопрос размера данных, либо тоже уменьшать, либо считать, что в данных есть дубликаты и мы принципиально их не удаляем, а используем (для увеличение нагрузки и размера массива) |