Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3835253 Sun, 26 Jul 2020 08:31:59 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3835253 Цитата scrum0fscrums @
Буду за деньги преобразовывать любой говнокод в эффективные линейные программы.

За сколько преобразуете венгерский алгоритм для задачи о назначениях?]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3835196 Sat, 25 Jul 2020 01:18:59 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3835196 НОК(a,b)*НОД(a,b) = a*b]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834029 Wed, 08 Jul 2020 16:38:11 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834029 JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834026 Wed, 08 Jul 2020 14:41:43 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834026
Цитата JoeUser @
для реализации для x32:
количество чисел в наборе - 1..232
значение числа в наборе - 1..232

То, что я показал выше, неплохая такая оптимизация, позволяющая не юзать длинную арифметику там, где она нафиг не нужна.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834025 Wed, 08 Jul 2020 14:21:30 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834025 Цитата OpenGL @
У тебя частный случай - нахождение нод, когда один из операндов вмещается в int.

Ты не заметил, что там нет int?]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834024 Wed, 08 Jul 2020 13:47:42 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834024 Цитата JoeUser @
BigInteger Nod(BigInteger a, BigInteger b) {
while (a != 0 and b != 0) if (a > b) a %= b; else b %= a;
return a+b;
}

У тебя частный случай - нахождение нод, когда один из операндов вмещается в int. Так что быстрее будет так:
    int gcd_int(int a, int b)
    {
        while(b != 0)
        {
            int t = a;
            a = b;
            b = t % b;
        }
        return a;
    }
     
    int gcd(BigInteger a, int b)
    {
        // b не должно быть равно 0
        return gcd_int(b, a % b);
    }
     
    BigInteger lmc(BigInteger a, int b)
    {
        if(b == 0) return a;
        return a * (b / gcd(a, b));
    }
]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834023 Wed, 08 Jul 2020 13:22:15 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834023 Цитата JoeUser @
Да, конечно цифры получаются большими.

Давай что-нибудь практическое придумаем... :whistle:]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834022 Wed, 08 Jul 2020 13:07:18 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834022
Скрытый текст
    #include <iostream>
    #include <vector>
    #include <chrono>
    #include "BigIntegerLibrary.hh"
     
    std::vector<BigInteger> R;
     
    BigInteger Nod(BigInteger a, BigInteger b) {
      while (a != 0 and b != 0) if (a > b) a %= b; else b %= a;
      return a+b;
    }
     
    BigInteger Nok(BigInteger a, BigInteger b) {
      return a/Nod(a,b)*b;
    }
     
     
    void YouTest(std::vector<int> &V) {
      BigInteger M;
      for(size_t i=0; i+1<V.size(); i++) {
        if (i==0) M = Nok(V[0],V[1]); else M = Nok(M,V[i+1]);
      }
      R.push_back(M);
    }
     
    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);
      auto start = std::chrono::high_resolution_clock::now();
      for(int i=0; i<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;
    }

вывод:
Скрытый текст
    Elapsed: 1378 ms
    9588669098580
    527825598300
    43129446360
    12539627100
    3920127120
    382604040
    11695320
    1667842296120
    16778770800
    1411408313640
    216377700
    4602752280
    2380775276880
    4957680
    3795870312
    1086891960
    29506021776
    280390927320
    1964784521700
    7351344
    140581978992
    175670352
    10308555180
    28354122720
    1661926200
    3544795800
    119253420
    10828263600
    3978365160
    83765501820
    22179437280
    10538866800

А для второго набора с большими числами изначально
Скрытый текст
    std::vector<std::vector<int>> Arr = {
        {0x7cd45dd6,0x7cfb2c2f,0x7d17697c,0x7d1c4aed,0x7d1e29e1,0x7d5766ed,0x7dee7bbd,0x7dff2159,0x7e007b27,0x7e045db9},
        {0x7d710637,0x7d720e66,0x7d8a5328,0x7dae46b1,0x7de0429c,0x7df70761,0x7e072d36,0x7e146be0,0x7e320e0b,0x7e51405c},
        {0x7d59173e,0x7d5b6f43,0x7d5f73af,0x7d651a54,0x7d7555e4,0x7d7f206d,0x7dab0f4f,0x7db11276,0x7dbd4b37,0x7ddc79ad},
        {0x7d0125e7,0x7d191867,0x7d1d42f9,0x7d226efd,0x7d2b223a,0x7d357524,0x7d5c17e8,0x7d8e5293,0x7d9e6e53,0x7ddd7053},
        {0x7d6550cf,0x7dd00b81,0x7de6495f,0x7df4279c,0x7e042f64,0x7e461e67,0x7e482342,0x7e7e3c7d,0x7e866b20,0x7e9c1d10},
        {0x7e113111,0x7e1f2a68,0x7e252112,0x7e2902f2,0x7e5f78a4,0x7e784d46,0x7ebe3d96,0x7ec82d4e,0x7ecb53c4,0x7edf4c73},
        {0x7d26032a,0x7d2b20c6,0x7d3a5c2e,0x7d5354ee,0x7d882b72,0x7d921cc1,0x7d9b4027,0x7e032f12,0x7e6c09d3,0x7e7d7ed5},
        {0x7bf657d5,0x7c014a70,0x7c4506a2,0x7cd329f0,0x7ce56aa7,0x7ce81d34,0x7d1716f4,0x7d194dc6,0x7d23131a,0x7d5e3664},
        {0x7d496f5d,0x7d4c0f41,0x7d606b1a,0x7d6461d0,0x7d6c6be0,0x7d717a80,0x7e096d25,0x7e106047,0x7e780539,0x7e937878},
        {0x7d24062e,0x7d2c6b82,0x7d827250,0x7da12d0c,0x7dc12285,0x7dc63b60,0x7dc822c7,0x7dd41f99,0x7e0f3c28,0x7e456330},
        {0x7c6f6e37,0x7c9f7469,0x7ca94be5,0x7ccb31bb,0x7ce2198d,0x7ceb40b5,0x7d0267e9,0x7d524e46,0x7d6f0ba7,0x7d7f0a37},
        {0x7d2c3397,0x7d2c38bd,0x7dd62c04,0x7dd67b90,0x7df64421,0x7e0c6b08,0x7e227887,0x7e3e7bed,0x7e410fc6,0x7e477b3c},
        {0x7cc30907,0x7cd60b0b,0x7cef020a,0x7d03001c,0x7d2c64a3,0x7d350179,0x7d4b41e5,0x7d856488,0x7d9c0c74,0x7dd54e69},
        {0x7c1f748c,0x7c21175f,0x7c6238fb,0x7c82171b,0x7cad08ed,0x7cb24149,0x7ce94757,0x7d036ae4,0x7d214b58,0x7d6f0a3d},
        {0x7d416876,0x7d690162,0x7d7015c9,0x7d88180b,0x7dc04b25,0x7dd363fa,0x7df9418e,0x7e094c2a,0x7e26677c,0x7e55473c},
        {0x7d345112,0x7d397f62,0x7d537af7,0x7d58312a,0x7d6727d4,0x7d9e59aa,0x7dcd116d,0x7dcf192c,0x7dd95b41,0x7df76402},
        {0x7d5c2fb5,0x7d863062,0x7d995475,0x7da67b0b,0x7dcf14ae,0x7df00bfb,0x7e042300,0x7e2b1ab9,0x7e477f1e,0x7e725a93},
        {0x7dfc4f7f,0x7e037475,0x7e1c3261,0x7e2f60e1,0x7e3d3d85,0x7e421fcc,0x7e6540de,0x7e67531a,0x7e7d6cc7,0x7e7f0789},
        {0x7d057a8c,0x7d07099d,0x7d14041a,0x7d207534,0x7d2b1875,0x7d4e32c8,0x7d5112ea,0x7d64127d,0x7dc1228e,0x7dd0732e},
        {0x7d664f54,0x7db1778d,0x7dda61a7,0x7de51343,0x7df63b84,0x7e0605db,0x7e081bda,0x7e184611,0x7e624928,0x7e640832},
        {0x7e7842b9,0x7e9f4ad6,0x7ea64ecc,0x7eb7125d,0x7ebc47b1,0x7ecc3d4a,0x7ed53815,0x7edc2062,0x7edc276d,0x7eee4861},
        {0x7d014c60,0x7d0b0920,0x7d3554bd,0x7d627ca5,0x7d6415ac,0x7d647a60,0x7d9f722a,0x7dfc3598,0x7e213d60,0x7e3a2b78},
        {0x7cd92864,0x7d33706f,0x7d8e2363,0x7dc10eb5,0x7dd55002,0x7e2c7cd1,0x7e447327,0x7e457cbe,0x7e6d6f27,0x7e73533e},
        {0x7cf01896,0x7d172b41,0x7d5a79b3,0x7d89255c,0x7deb4f3f,0x7df974e4,0x7dff01cd,0x7e5c1595,0x7e7279d5,0x7e7c2d05},
        {0x7c926328,0x7ca004e9,0x7cad57ec,0x7ce9775f,0x7cf7135d,0x7d07453c,0x7d084c8b,0x7d0f6b4c,0x7d454c67,0x7d4f3a45},
        {0x7e2e57f8,0x7e3f6b7b,0x7e5370c3,0x7e764d44,0x7e8a5f0c,0x7e8c3417,0x7ea060b4,0x7eab0a71,0x7ec4369d,0x7ecd2d1a},
        {0x7cad0fb7,0x7cc477d0,0x7cc74a4c,0x7ce71c30,0x7d20003c,0x7d2b1b78,0x7d735951,0x7d9741d6,0x7da77b9f,0x7dc90f2e},
        {0x7c9d3798,0x7c9e535f,0x7ca844b9,0x7cad10b6,0x7cb56f5a,0x7d0209d0,0x7d1b40c7,0x7d1b617b,0x7d710abf,0x7d722c3e},
        {0x7d847bb6,0x7de5361b,0x7e1e6471,0x7e223fd8,0x7e340c2b,0x7e5c4c1a,0x7e7445c6,0x7e760312,0x7e7f2cce,0x7e894d2e},
        {0x7d493a94,0x7d4f528a,0x7d7f3e2f,0x7d875f25,0x7dbd50a8,0x7de851c6,0x7e335209,0x7e385ccc,0x7e482cc0,0x7e48798a},
        {0x7c7c1b24,0x7cf13502,0x7d534047,0x7d584c31,0x7d5b53c6,0x7d6b5ee1,0x7daa4f8f,0x7de2717a,0x7dea4786,0x7dff7af7},
        {0x7d1871a4,0x7d2018bd,0x7d2815cd,0x7d774b76,0x7d841cd9,0x7d895b6d,0x7dd76085,0x7df34d8b,0x7dfe45d9,0x7dfe4d99}
      };

Получился вот такой результат:
Скрытый текст
    Elapsed: 7813 ms
    8365952198818774082761182752826492709705353472768857783518932270943615384126743225484220
    6320784966646816085566075372050288774163083533310223412067630401536400391507483003360
    372965641708056343100671012886426814882051314151484963188075362084382390495188874300
    152046970479457502245073922096275168909385354426662178417039241800071420492281361373952680
    126527352355773471721414839256668398843177001156445305761310662173112181954910210287456
    103173769752087961922560643530764147207112796208249628740374208211004747481026394897960
    97580947841540309585744501944268707806192013625089179078240251275199492717354127494050410
    658424750501043684868086106460183123310519659236268731747507021965953665328766603600
    219526365178587019702964440217431588833431189719850964824263190628965911597070052480
    5896282002515888839350031734886929524119790897492373106113264797010617740512533627939040
    12147216871546784182869018501023272553426670323282399316976611747028891817282129272967380170
    106296206725973511003071955573025894114919643976191842733704315889020489983063580280240
    5167872557586608191948556334010077457643088059745349539962505228671962363637573060206920
    446224936219092299774695846181984522639964926306878449710518868824542371977224101649099720
    440123142671612922643968887481816571303358017322824654791040478709721423143801134896260
    9119713839306100061487001655155324259599019842429627086510112885658955607460594927316
    290517572508361811488661447420828423401260402380137586777930494515519844500267299116800
    50520924027731474619464147641100856895295982212232157980554181149167031553624724765871315172
    4328567320666505347271561328359181982055970787586959933970942463427025802943796550596760
    12952281244141561307406306392058785642677315080032779441231055316800005185073173244452600
    276394662419827287242992857333387035616294952602445960883488304840638048759071430885333500
    696504066204039086504093430337009155728188927832176955004778788831336847216836079200
    6615279929305400025297732430650553553078662258832596392260358097614118819200154375784100
    43878260208418628823156222649970651587385088857268281774469306331890408122270063159410006740
    218787285695220121127373807803078072214370551512233159301622720209468796642905853420158760
    51055566993622631458771818230502965458972847923195223488796602092223024703817681371880
    20141264573928462505142539000000831107750484193507850672036969242867600868875150143440
    156834931714649030815630944760386489262784627499294812061727382540624786877284828530800
    69087642384679507706012918384628597974549327733541898202352422921110101087636970883000
    2694163307667579202220636480509744380958601600596803923780055098580309018684009954974016
    13749346721233841734887885146491926944389137693673390982571052279064803140884657724910260
    148293055169307720833926985648257182289595114441389459016963339316768729714260354703849300

Да, конечно цифры получаются большими.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834020 Wed, 08 Jul 2020 12:06:37 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834020
Вначале нумеруем простые числа (помещаем простые числа в массив)/
p -> NUM[p]
Затем создаём массив НОК точно такой же длины, в к-м будем хранить кратности (степени) простых чисел, входящих в разложение.
Первоначально там нули.

Читаем первое число.
1. Проверяем, делится ли оно на 4.
Если да, то уменьшаем число N:= N div 4; НОК[NUM[2]]:= НОК[NUM[2]]+2 и повторяем этот шаг.
Если нет, то проверяем делимость на 2.
Если делится на 2, то N:= N div 2; НОК[NUM[2]]:= НОК[NUM[2]]+2
Переход на шаг 2.

2. Проверяем, делится ли число на 9.
Аналогично шагу 1.
...
Перенесли первое число в НОК.
Читаем второе число.
Аналогично. Но если степень простого числа p оказывается больше, чем записано в НОК[NUM[p]], то переписываем НОК[NUM[p]]]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834019 Wed, 08 Jul 2020 11:39:02 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834019 Цитата m-ch @
Для указанных чисел НОК значительно меньше, должно получится:

Все верно - у меня косяк! :'(]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834018 Wed, 08 Jul 2020 11:19:40 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834018 Количество прогонов 1 048 576
Elapsed: 10901 ms
Скрытый текст
Nok 0 = 9588669098580
Nok 1 = 527825598300
Nok 2 = 43129446360
Nok 3 = 12539627100
Nok 4 = 3920127120
Nok 5 = 382604040
Nok 6 = 11695320
Nok 7 = 1667842296120
Nok 8 = 16778770800
Nok 9 = 1411408313640
Nok 10 = 216377700
Nok 11 = 4602752280
Nok 12 = 2380775276880
Nok 13 = 4957680
Nok 14 = 3795870312
Nok 15 = 1086891960
Nok 16 = 29506021776
Nok 17 = 280390927320
Nok 18 = 1964784521700
Nok 19 = 7351344
Nok 20 = 140581978992
Nok 21 = 175670352
Nok 22 = 10308555180
Nok 23 = 28354122720
Nok 24 = 1661926200
Nok 25 = 3544795800
Nok 26 = 119253420
Nok 27 = 10828263600
Nok 28 = 3978365160
Nok 29 = 83765501820
Nok 30 = 22179437280
Nok 31 = 10538866800


Добавлено
+
OpenMP по циклу прогона повторов (i7-4770 4C/8T).
Elapsed: 1711 ms]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834016 Wed, 08 Jul 2020 11:06:14 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834016 Цитата JoeUser @
Пока остается вопрос - как уменьшить количество вычислений для нахождения этого числа.

Смысла большого нет. НОК(a, b) = a / НОД(a, b) * b, а НОД считается очень быстро (за логарифм, и это в самом неудачном случае). Если это окажется слишком медленным, то только разложением на простые множители делать. И не забыть про переполнение, которое в твоей задаче возникнет как нефиг делать.

Добавлено
Цитата OpenGL @
а НОД считается очень быстро (за логарифм, и это в самом неудачном случае)

Да, делается это алгоритмом Евклида.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834015 Wed, 08 Jul 2020 11:02:02 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834015 Цитата JoeUser @
На моем компе это получилось вот так:

Для указанных чисел НОК значительно меньше, должно получится:
Скрытый текст
9588669098580
527825598300
43129446360
12539627100
3920127120
382604040
11695320
1667842296120
16778770800
1411408313640
216377700
4602752280
2380775276880
4957680
3795870312
1086891960
29506021776
280390927320
1964784521700
7351344
140581978992
175670352
10308555180
28354122720
1661926200
3544795800
119253420
10828263600
3978365160
83765501820
22179437280
10538866800
]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834014 Wed, 08 Jul 2020 11:00:01 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834014
Новый набор
Скрытый текст
    std::vector<std::vector<int>> Arr = {
        {0xff03,0xff04,0xff0d,0xff17,0xff1b,0xff1d,0xff21,0xff22,0xf1d2,0xf1d6},
        {0xff01,0xff0b,0xff0c,0xff0d,0xff0e,0xff12,0xff19,0xff1d,0xf1bd,0xf1c6},
        {0xff01,0xff0d,0xff0e,0xff15,0xff23,0xff28,0xff2c,0xff2e,0xf1d2,0xf1d5},
        {0xff06,0xff0b,0xff12,0xff15,0xff19,0xff1c,0xff1f,0xff27,0xf1b2,0xf1c1},
        {0xff03,0xff09,0xff0d,0xff0e,0xff10,0xff12,0xff13,0xff15,0xf1d5,0xf1d6},
        {0xff07,0xff09,0xff0f,0xff18,0xff1a,0xff1c,0xff1e,0xff28,0xf1ca,0xf1cb},
        {0xff04,0xff08,0xff11,0xff14,0xff18,0xff1b,0xff1e,0xff28,0xf1b9,0xf1ba},
        {0xff08,0xff11,0xff24,0xff27,0xff31,0xff37,0xff38,0xff3c,0xf1b5,0xf1bd},
        {0xff03,0xff04,0xff06,0xff0a,0xff0b,0xff10,0xff13,0xff19,0xf1bf,0xf1c1},
        {0xff05,0xff06,0xff09,0xff0c,0xff1f,0xff27,0xff28,0xff2f,0xf1c1,0xf1cd},
        {0xff03,0xff04,0xff06,0xff07,0xff16,0xff19,0xff1c,0xff1d,0xf1db,0xf1dc},
        {0xff02,0xff09,0xff0c,0xff12,0xff13,0xff14,0xff18,0xff1f,0xf1b9,0xf1bb},
        {0xff0d,0xff10,0xff17,0xff1e,0xff1f,0xff21,0xff23,0xff2d,0xf1c3,0xf1c4},
        {0xff02,0xff05,0xff07,0xff0a,0xff0e,0xff10,0xff14,0xff15,0xf1c6,0xf1c7},
        {0xff01,0xff02,0xff09,0xff0d,0xff13,0xff18,0xff1a,0xff24,0xf1cd,0xf1cf},
        {0xff08,0xff0b,0xff0f,0xff14,0xff16,0xff1c,0xff21,0xff29,0xf1c5,0xf1c8},
        {0xff07,0xff0b,0xff0e,0xff10,0xff12,0xff16,0xff25,0xff2e,0xf1d8,0xf1dd},
        {0xff07,0xff08,0xff0f,0xff11,0xff22,0xff28,0xff2b,0xff36,0xf1c1,0xf1c4},
        {0xff03,0xff19,0xff21,0xff22,0xff29,0xff31,0xff34,0xff36,0xf1bf,0xf1c2},
        {0xff02,0xff04,0xff06,0xff0d,0xff10,0xff11,0xff12,0xff15,0xf1cb,0xf1ce},
        {0xff01,0xff07,0xff0d,0xff12,0xff22,0xff24,0xff2a,0xff2f,0xf1cf,0xf1d0},
        {0xff01,0xff02,0xff08,0xff09,0xff0b,0xff0c,0xff0d,0xff10,0xf1c1,0xf1c8},
        {0xff0b,0xff0e,0xff0f,0xff15,0xff1b,0xff1d,0xff21,0xff23,0xf19c,0xf19f},
        {0xff02,0xff04,0xff0f,0xff12,0xff15,0xff16,0xff1f,0xff20,0xf1b6,0xf1c4},
        {0xff02,0xff06,0xff08,0xff0b,0xff19,0xff32,0xff37,0xff3a,0xf1c8,0xf1c9},
        {0xff01,0xff05,0xff08,0xff09,0xff0d,0xff11,0xff12,0xff13,0xf1d5,0xf1db},
        {0xff01,0xff03,0xff04,0xff05,0xff0b,0xff12,0xff14,0xff1a,0xf1c3,0xf1c4},
        {0xff01,0xff0b,0xff10,0xff1d,0xff21,0xff28,0xff2a,0xff36,0xf1c1,0xf1c2},
        {0xff02,0xff08,0xff0b,0xff0e,0xff0f,0xff13,0xff1f,0xff21,0xf1d9,0xf1dc},
        {0xff04,0xff09,0xff11,0xff1c,0xff1d,0xff27,0xff29,0xff33,0xf1cc,0xf1ce},
        {0xff03,0xff0c,0xff0d,0xff16,0xff17,0xff1a,0xff1b,0xff20,0xf1be,0xf1c7},
        {0xff08,0xff0c,0xff0e,0xff10,0xff17,0xff19,0xff1c,0xff1d,0xf1a2,0xf1b0}
      };

Новый результат
Скрытый текст
    Elapsed: 441 ms
    1267181565169635425462863626561526344973096267680
    1265590721868154745738295203429428311872292813600
    1268092707958795420632098493907650308667795513600
    1266349051990390548480339990387472650745527926880
    1266214933755942035226746963525434649171259169920
    1267044933820491982921741146506920591675277568000
    1266174529475152210573573826827313055198474240000
    1269065168672279046348206506985745801150907008000
    1264967440304829035101760176767215706006657964800
    1267095474333011259746076094424917508966100523200
    1266673650925208243619540344921441031968007955200
    1265516555345870866142337767256950747693612275200
    1267670400889602029097375441972460375582659120000
    1265252559262830116127528091951631771778153600000
    1266237671401813706617080051969013882214634805632
    1266861780356304491009262066714412626559487232000
    1267544698108113485608581332247488057193474484224
    1267473951388862396897399764122010398600308659200
    1268809442232034164457312628368527394478455624800
    1265536637971779144334666224152595250187508759552
    1267618222216795097900633967552670043612397221376
    1264725204774598971749322444468379305150606974976
    1265319624029702628095242472125781110471552983000
    1265833045511143680440607015689548306199703429120
    1267661221289163842304514694545742008902136704000
    1265871193008340467265414534585362453427564376400
    1264994241649546059982131267989135324163440736000
    1267588260553839183231644888365738255825843123200
    1266807347805406433602161868733263696054245809280
    1267904103159507471093606398113129732929541564800
    1266310173940555867207588984770344723619411901440
    1265208797332832056986562970768988271418020331520

Дааа ... числа хорошо растут! :-?]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834012 Wed, 08 Jul 2020 10:58:18 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834012 Цитата JoeUser @
Не мы поборемся

Ни как...
216 * 216 = 232
Т.е. диапазон значений надо уменьшать.
Тогда встает вопрос размера данных, либо тоже уменьшать, либо считать, что в данных есть дубликаты и мы принципиально их не удаляем, а используем (для увеличение нагрузки и размера массива)]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834011 Wed, 08 Jul 2020 10:51:29 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834011 Вычисление НОК на базе НОД

    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, что бы не было переполнения (но для больших чисел может быть ошибка округления)]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834010 Wed, 08 Jul 2020 10:45:47 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834010 Цитата Black_Dragon @
Надо занижать лимиты....

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

Сперва я сделал тестовый массив - 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 (, : 1029) ]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834007 Wed, 08 Jul 2020 08:54:23 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834007 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 бита...
Надо занижать лимиты....]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834006 Wed, 08 Jul 2020 08:49:46 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834006 Цитата Black_Dragon @
Так что, оптимистические хотелки...

Ну да, с большим количеством фэйлов неинтерсно. Попробую замутить типа "программного стенда для теста" на более скромых хотелках :)]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834004 Wed, 08 Jul 2020 08:34:50 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834004 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";
    }
]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834003 Wed, 08 Jul 2020 08:34:03 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834003
    #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

Пока мне это нравится. Позже попробую алгоритмы от "арифметической классики" :)]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833999 Wed, 08 Jul 2020 06:50:44 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833999 Цитата JoeUser @
1) Это сколько?

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


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

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

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

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

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

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

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

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

В принципе можно и заценить скорость построения с помощью решета Эратосфена или Аткина. Но опять же - каков объем может получится...]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833988 Wed, 08 Jul 2020 04:22:11 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833988 Цитата JoeUser @
найти минимальное число, которое нацело делится на любое из чисел набора...

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

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

Либо скорость, либо размер. Промежуточный вариант - хранимая таблица простых чисел в диапазоне значений чисел набора.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833987 Wed, 08 Jul 2020 02:37:19 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833987 Цитата JoeUser @
Это, увы, не вариант - слишком большой объем таких данных будет.

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

И самое главное:
Если для ускорения вычисления требуется трансформация данных или предварительные расчеты, то их надо, если имеется такая возможность, то производить их в момент чтения данных откуда-то (например, из файла)]]> Black_Dragon Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833984 Tue, 07 Jul 2020 22:19:18 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833984 Цитата swf @
Есть, наверно, готовые разложения натуральных чисел на простые множители

Это, увы, не вариант - слишком большой объем таких данных будет.
Но уже два подхода нарисовались - буду тестировать, замерять.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833983 Tue, 07 Jul 2020 21:45:33 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833983 А вот сравнение разложения проверяемого числа на простые множители с разложением НОК'а на предмет недостающих сомножителей зависит от того, как эти разложения хранятся.
За счёт увеличения памяти можно ускорить процедуру сравнения.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833968 Tue, 07 Jul 2020 19:00:51 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833968 swf, сенкс за наводочку :) Нашел какую-то теорему:
Цитата
Пусть даны целые положительные числа a1, a2, …, ak, наименьшее общее кратное mk этих чисел находится при последовательном вычислении m2=НОК(a1, a2), m3=НОК(m2, a3), …, mk=НОК(mk−1, ak).

Пока остается вопрос - как уменьшить количество вычислений для нахождения этого числа.]]> JoeUser Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833967 Tue, 07 Jul 2020 18:54:26 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833967 В школе дети раскладывают каждое число на простые множители, затем переписывают в НОК любое число и дополняют недостающими множителями из оставшихся чисел (6 класс).
Видимо, есть готовые алгоритмы, но мне как-то не приходилось ими пользоваться.]]> swf Алгоритмы https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833966 Tue, 07 Jul 2020 18:36:19 +0000 Поиск минимального числа при условии https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3833966
Интересует сабж.

Условие

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