Премини към съдържанието

Архивирана тема

Темата е твърде стара и е архивирана. Не можете да добавяте нови отговори в нея, но винаги можете да публикувате нова тема, в която да продължи дискусията. Регистрирайте се или влезте във вашия профил за да публикувате нова тема.

boy1

Оптимизация на алгоритъм за намиране на делителите на число

Препоръчан отговор


Здравейте! Опитвам се да намеря всички делители на дадено число, но проблемът ми е, че се налага да използвам число с 15 цифри. Сигурно се досещате, че отнема доста време, ако използваме стандартния начин за търсене, който съм приложил:

void List::Deliteli(long long m)      {        int t = 0;        for(long long i = 2; i <= m/2; i++)          {            if(m%i == 0)               {                cout << i << endl;                       t = 1;              }          }                   if(t == 0) cout << "Prime number!" << endl;                  }

Бих искал да Ви попитам дали има по-оптимален алгоритъм? Търсих в Гугъл, но не успях да намеря нищо :/.

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

... не съм прочел въпроса правилно, извинявам се за отговора

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Здравейте! Опитвам се да намеря всички делители на дадено число, но проблемът ми е, че се налага да използвам число с 15 цифри. Сигурно се досещате, че отнема доста време, ако използваме стандартния начин за търсене, който съм приложил:

void List::Deliteli(long long m)      {        int t = 0;        for(long long i = 2; i <= m/2; i++)          {            if(m%i == 0)               {                cout << i << endl;                       t = 1;              }          }                   if(t == 0) cout << "Prime number!" << endl;                  }

Бих искал да Ви попитам дали има по-оптимален алгоритъм? Търсих в Гугъл, но не успях да намеря нищо :/.

АМи няма прост начин, иначе RSA базираната криптография щеше да е разбита отдавна. И не е ли по-лесно да търсите простите множители и след това да ги комбинирате. Така ще се налага да смятате само до корен квадратен от числото и можете да започнете от 3 със стъпка две

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Привет !

 

Ето и от мен няколко идеи за забързване на написаният алгоритъм:

 

1) Идея за "ловене" на два делителя с една проверка: 

Плюсове: Написаният от колегата boy1 алгоритъм ще цикли до около числото N = m/4.

Минуси: Извеждането на делителите няма да има наредба, а ако искаме такава, трябва да помислим за заделяне на памет + операция за сортиране + извеждане

т.е. ако ги искаме сортирани, ще получим време: O(m/4 + t*log(t) + t), където t е броя намерени делители.

 

Минуса мисля, че може да се разреши с използването на рекурсия и по - точно с обръщение към метода в момента, когато сме извели първия множител и преди да изведем втория. Ще е малко извратена рекурсия, но мисля, че е възможно.

 

Идея: При намиране на делител R на числото m, то числото m/R също е делител. В случая, R <= m/R <= m/2. Това означава, че с нарастване на R, то m/R ще намалява и ще се отдалечава от m/2, което пък води до идеята, цикъла да прави корекция до кое число да бъде изпълняван, като това число е < m/R, вместо m/2.

 

Като пример: С оригиналния алгоритъм, за числото 15 ще се направя 6 цъкъла (от 2 до 7 включително), докато с оптимизацията, те ще са 3 (от 2 до 5, без 5, защото вече е намерен делител още при проверката на 3).

 

2) Идеята за прости множители (Идеята на capnemo) 

Както колегата сподели, може да се опитаме да намерим всички прости множители на числото - това ще гарантира, че цикъла ще извърти до числото sqrt(m), но ще се наложи получените числа да се пазят. Самите делители ще са комбинация от 1, 2 или повече числа, запазени в тази памет, и генерирането им може и да отнеме някакво време, което може и да доста голямо за голям набор от множители. В случая по-полезни ще са Ви самите намерени прости множители в тази форма.

 

Поздрави !

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Начин за ускорение на работата на алгоритъма, е и реализирането му чрез използването на няколко нишки, работещи паралелно, които претърсват различни интервали.


Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Начин за ускорение на работата на алгоритъма, е и реализирането му чрез използването на няколко нишки, работещи паралелно, които претърсват различни интервали.

Това само на пръв поглед изглежда ефективно. И то само ако можем да пуснем всяка нишка на отделно ядро.

Но ако намираме прости множители няма как да стане със спаралеляване. Но за сметка на това операциите ще са по-малко от sqrt(n)/2, където n е числото

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

1) Идея за "ловене" на два делителя с една проверка: 

Мерси за съвета. Преработих алгоритъма малко и сега наистина се забелязва подобрение в скоростта. Ето това направих водейки се по съветите Ви.

void List::Deliteli(long long m)      {        int t = 0;        for(long long i = 2; i <= sqrt(m); i++)          {            if(m%i == 0)               {                cout << i << " ";                 cout << m/i << endl;                       t = 1;              }          }                   if(t == 0) cout << "Prime number!" << endl;                  }
2) Идеята за прости множители (Идеята на capnemo)

Сега ще опитам да напиша и този алгоритъм. Дано да нямам ядове с намирането на простите множители :D. И доколкото схванах, после просто комбинирам всеки с всеки нали? Примерно намерил съм 5, 7, 11 и умножовам 5*7, 5*11, 7*11? :)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Сега ще опитам да напиша и този алгоритъм. Дано да нямам ядове с намирането на простите множители :D. И доколкото схванах, после просто комбинирам всеки с всеки нали? Примерно намерил съм 5, 7, 11 и умножовам 5*7, 5*11, 7*11? :)

не само, всички делители на числото ще са:

5,7,11, 5*7, 5*11, 7*11, 5*7*11

П.П. и една забележка: мислите ли че в нормалните типове на езика ще можете да съберете число в 15 цифри? Мисля си че трябва да си потърсите библиотека за работа с големи числа

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

не само, всички делители на числото ще са:

5,7,11, 5*7, 5*11, 7*11, 5*7*11

П.П. и една забележка: мислите ли че в нормалните типове на езика ще можете да съберете число в 15 цифри? Мисля си че трябва да си потърсите библиотека за работа с големи числа

Мисля, че използвайки long long ще успее да събере такова число.

Все пак колегата е добре да провери и коя версия използва на компютъра си, но при мен лично няма проблеми да се изведе и съхрани число с деветнадесет (19) символа.

Използвам VS 2012 върху 64-bit платформа.

Евентуално полезно инфо: 32-bit , 64-bit

 

Поздрави !

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Поразрових се и намерих този алгоритъм:

void List::Deliteli(long long m)      {        int t = 0;        while(m%2 == 0)          {            cout << 2 << " ";            m = m/2;                  }                for(int i = 3; m > 1;)          {            if(m%i > 0) i = i+2; //Ето тук в един момент не става ли 9, което не е просто число?            else              {                cout << i << " ";                m = m/i;              }                }         }

Наистина се забелязва още по-бърза скорост. Мислех си да направя същото и аз, но като видях този алгоритъм забелязах нещо: На първия ред от втория цикъл, в даден момент, числото не става ли 9? А 9 не е просто число. Въпреки това всичко си е нормално.

 

И само да спомена, че съм на 32 битова платформа и ползвам Dev-C++ 4.9.9.2. Иначе и аз нямам проблем с числа до 19 цифри, ако ползвам long long. :)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Болят ме очите да следя алгоритъма, но идеята е следната

Създаваш си масив в който в началото има само числото две

проверяваш дали числото се дели на две като го делиш и проверяваш резултата докато спре да се дели като ако се дели поне веднъж маркираш две като просто множител

след това правиш while по някаква променлива

дефинираш делителя като 3

проверяваш дали числото се дели на 3 като го делиш и проверяваш резултата докато спре да се дели като ако се дели поне веднъж маркираш 3 като просто множител

увеличаваш делителя с две

проверяваш дали е просто число (дали се дели на числата от масива по-горе) При първото делене се маркира като съставно и се връщаш на горната точка

Ако резултата е по-малък от 3 вдигаш флаг за край на while

 

Ох, стана малко оплетено, но си мисля че това е най-простия и бърз начин :D 

Само една забележка: след като провериш дали се дели на две и се дели точно нататък числото става n/2

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Поразрових се и намерих този алгоритъм:

Наистина се забелязва още по-бърза скорост. Мислех си да направя същото и аз, но като видях този алгоритъм забелязах нещо: На първия ред от втория цикъл, в даден момент, числото не става ли 9? А 9 не е просто число. Въпреки това всичко си е нормално.

 

Алгоритъма е доста хитро написан. За съжаление обаче се влияе от входа - т.е. от стойността на числото m. Ето защо:

- Алгоритъма ще е много бърз, ако m има много на брой, еднакви и малки като стойност прости делители - Пример: за 1024, ще се извършат 10 операции, което е < sqrt(1024) = 32

В този случай множителите ще са 10 броя 2-ки т.е. 2^10. Подобно нещо се случва и за 1000 = 2^3*5^3, което са 6-7 операции. 

- Алгоритъма ще се забави, ако m има малко на брой множители и/или множителите му са големи числа - Пример 34042 

Числото има два делителя 2 и 17021 и съответно алгоритъма прави >8500 операции, докато sqrt(34042) < 185

- Алгоритъма ще е еквивалентен на първият Ви алгоритъм в началото, ако m е просто число. - Пример 47093 - с целия си късмет, това се оказа просто число, което автоматически докара броя операции до 23546 (m/2) 

 

Равносметка: Базирайки се на данните, които получих при опитите, както и кода, който се изпълнява, броя операции е доста сложен да се изчисли - изключително много зависи от входните данни. Но прилагайки наблюденията за числа m, клонящи към безкрайност имаме следните изводи:

1) С увеличаване на m, шанса за среща на прости числа намалява драстично

2) С увеличаване на m, се увеличава шанса да се наложи да се проверяват все повече и повече числа, като прага е някъде около m/2 брой проверки.

3) Алгоритъма дава от добри до много добри резултати за относително малко количество от числа, докато метода за проверка до sqrt(m) е гарантиран да изведе правилен резултат, с гарантиран брой операции ~O(sqrt(m))

 

Според мен, оригиналният алгоритъм ще се представи по-добре за повече на брой проверки и за по-голяма гама от числа.

 

P.S. Не е проблем алгоритъма да "провери" и за 9, въпреки, че то не е просто число. В случая, ние сме преминали вече през 3-ката, което означава, че числото m е делено с 3, докато вече не може да се раздели. Визирайки, че 9 = 3*3 , 27 = 3*3*3, то проверката ще мине през тях, но реално няма да промени резултата в израза m = m/i, защото остатъка от числото няма да се дели без остатък нито на 9, нито на 27 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

  • Разглеждащи това в момента   0 потребители

    Няма регистрирани потребители разглеждащи тази страница.

  • Горещи теми в момента

  • Подобни теми

    • от Plamy Gerova
      Здравейте, може ли помощ за курсовата ми задача?
      съставете програма с функции за:
      а) въвеждане от клавиатурата във файл и в масив( чрез добавяне) данни за морски пътувания (до 25)- Морска гара Варна: маршрут, кораб-име, име на капитан, цени на билетите- I,II класа, брой пасажери в съответната класа, обща сума на продадените билети- през избран месец от годината.Извеждане текущото съдържание на масива(файла) на екрана.
      б) извеждане на екран данните за превозите на кораб по въведено от клавиатурата име на кораб(със запитване за справка)
      в) извеждане на екран данните за морско пътуване с най- голяма обща сума на продадени билети.
      Главна функция main()- с меня за избор на функции и проверка за състоянието та данните.Използване на локални променливи и функции с предаване на параметри. 
       
    • от Десислава Нешева
      Здравейте на всички. Имам въпрос, свързан с програмата си++. Имам матрица, на която търся сума от отрицателните елементи. Въпроса ми е как ще стане това нещо да се запише във файл, искам резултата да се показва само във файла, а не цялата матрица. Ето моя код:

      #include <iostream>

      #include<fstream>

      int main()

      {

      int a[10][10],m,n;

      int sum=0;

      std::cout<<"rows= ";

      std::cin>>m;

      std::cout<<"cols= ";

      std::cin>>n;

      for (int i=0; i<m; i++)

      for (int j=0; j<n; j++)

      {

      std::cout<<"a["<<i<<"]["<<j<<"]= ";

      std::cin>>a[j];

          if(a[j]<0) sum=sum+a[j];

      std::cout<<"sum= "<<sum;}

      return 0;

      }

      Благодаря, предварително !!!
    • от Boqn Tzonev
      #include <iostream> #include <iomanip> #include <string> #include <fstream> using namespace std; const int N = 5; struct player { string ime; string familia; string otbor; int nomer; int vk_golove; } igrachi[N], podredba; // Prototypes. int add_player(player a[]); void search_by_number(player a[], int &nomer_na_igracha); void search_by_team(player a[], string & ime_na_otbora); void klasirane(player a[]); void actual(player a[], int &nomer_na_igracha, string & ime_na_otbora); //********************************************** fstream igrachi_file; //********************************************** int add_player(player a[]) { int br; igrachi_file.open("igrachi.txt", ios::out | ios::app); // <--- As an "fstream" this needs to know if it is input or output. do { //cout << "\n Broi igrachi:"; cout << "\n Number of players:"; cin >> br; } while (br <= 0 || br > N); if (igrachi_file.fail()) { cout << "Error. The file is missing."; exit(1); } for (int i = 0; i < br; i++) { //cout << "Vuvedi ime na igrach:"; cout << " Enter player's first name: "; cin >> a[i].ime; igrachi_file << a[i].ime << endl; //cout << "Vuvedi familia na igrach:"; cout << " Enter a player's last name :"; cin >> a[i].familia; igrachi_file << a[i].familia << endl; //cout << "Vuvedi otbor na igracha:"; cout << " Enter a player's team: "; cin >> a[i].otbor; igrachi_file << a[i].otbor << endl; //cout << "Vuvedi nomer na igracha:"; cout << " Enter the player number: "; cin >> a[i].nomer; if (a[i].nomer > 99 || a[i].nomer < 1) { do { //cout << "Vuvedete nomer ot 1 do 99. \n"; cout << "Enter number 1 to 99. \n"; cin >> a[i].nomer; } while (a[i].nomer > 99 || a[i].nomer < 1); } igrachi_file << a[i].nomer << endl; //cout << "Vuvedi vkarani golove na igracha:"; cout << " Enter player goals scored: "; cin >> a[i].vk_golove; if (a[i].vk_golove < 0) { do { //cout << "Vuvedete golove >= 0 \n"; cout << "Enter goals >= 0 \n"; cin >> a[i].vk_golove; } while (a[i].vk_golove < 0); } igrachi_file << a[i].vk_golove << endl; } igrachi_file.close(); } void search_by_number(player a[], int &nomer_na_igracha) { int flag = 0; igrachi_file.open("igrachi.txt", ios::in); igrachi_file.seekg(0); if (igrachi_file.fail()) { cout << "Fail to open the file"; exit(1); } for (int i = 0; i < N; i++) { igrachi_file >> a[i].ime; igrachi_file >> a[i].familia; igrachi_file >> a[i].otbor; igrachi_file >> a[i].nomer; igrachi_file >> a[i].vk_golove; if (nomer_na_igracha == a[i].nomer) { cout << "Igrach: " << a[i].ime << " " << a[i].familia << "\nOtbor: " << a[i].otbor << "\nNomer: " << a[i]. nomer << "\nVkarani golove: " << a[i].vk_golove << endl; flag++; } } if (!flag) cout << endl << "Nqma takuv igrach!" << endl; igrachi_file.close(); } void search_by_team(player a[], string & ime_na_otbora) { int flag = 0; igrachi_file.open("igrachi.txt", ios::in); igrachi_file.seekg(0); if (igrachi_file.fail()) { cout << "Fail to open the file"; exit(1); } for (int i = 0; i < N; i++) { igrachi_file >> a[i].ime; igrachi_file >> a[i].familia; igrachi_file >> a[i].otbor; igrachi_file >> a[i].nomer; igrachi_file >> a[i].vk_golove; if (ime_na_otbora == a[i].otbor) { cout << "Igrach: " << a[i].ime << " " << a[i].familia << "\nOtbor: " << a[i].otbor << "\nNomer: " << a[i]. nomer << "\nVkarani golove: " << a[i].vk_golove << endl << endl; flag++; } } if (!flag) cout << endl << "Nqma takuv otbor!" << endl; igrachi_file.close(); } void klasirane(player a[]) { igrachi_file.open("igrachi.txt", ios::in); igrachi_file.seekg(0); // <--- Not needed as the file pointer is already at the beginning from the open statement. for (int i = 0; i < N; i++) { igrachi_file >> a[i].ime; igrachi_file >> a[i].familia; igrachi_file >> a[i].otbor; igrachi_file >> a[i].nomer; igrachi_file >> a[i].vk_golove; } cout << "ime" << setw(15) << "familia" << setw(15) << "otbor" << setw(15) << "nomer" << setw(15) << "vkarani golove" << endl; for (int i = 0; i < N; i++) { cout << a[i].ime << right << setw(15) << a[i]. familia << right << setw(15) << a[i]. otbor << right << setw(15) << a[i]. nomer << right << setw(15) << a[i].vk_golove << endl; } igrachi_file.close(); } int main() { int choice; int nomer_na_igracha; string ime_na_otbora, familia_na_igracha; player a[N]; do { cout << "\n================================================================================" << endl; cout << "\t\tMenu\n\n"; //cout << "= Izberete:\n"; cout << " Choose:\n"; //cout << "= 1. Dobavqne na igrachi\n"; cout << " 1. Add players\n"; //cout << "= 2. Spisuk s igrachite\n"; cout << " 2. List of players\n"; //cout << "= 3. Spravka za igrach po nomer\n"; cout << " 3. Reference for player by number\n"; //cout << "= 4. Spravka za igrach po otbor\n"; cout << " 4. Player report by team\n"; //cout << "= 5. Aktualizirane\n"; cout << " 5. Update\n"; //cout << "= 6. Krai\n"; cout << " 6. End\n"; cout << "\n================================================================================" << endl; cin >> choice; switch (choice) { case 1: { add_player(a); break; } case 2: { klasirane(a); break; } case 3: { cout << "Tursene po nomer: "; cin >> nomer_na_igracha; search_by_number(a, nomer_na_igracha); break; } case 4: { cout << "Tursene po otbor: "; cin >> ime_na_otbora; search_by_team(a, ime_na_otbora); break; } case 5: { cout<< "Update:"; cin>> nomer_na_igracha, ime_na_otbora; } break; } } while (choice != 6); } Здравейте имам нужда от малко помощ с моята курсова задача.Остана ми да направя единствено актуализацията ,но не мога да се справя. Ето и какво съм направил по актуализацията.Ще го постна като отговор долу.

      void actual(player a[], int nomer_na_igracha, string ime_na_otbora) { int i{}; fstream igrachi_file; igrachi_file.open("igrachi.txt", ios::in); while (getline(igrachi_file, a[i].familia)) // <--- Changed. { igrachi_file >> a[i].vk_golove; igrachi_file.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // <--- Requires header file <limits>. getline(igrachi_file, a[i].otbor); i++; } igrachi_file.close(); //cout << "Vuvedete igrachite chiqto informaciq iskate da redaktirate: "; cout << "Enter the players whose information you want to edit: "; //cin >> num; // <--- Not defined or used. //cout << "\n Ime: "; cout << "\n Name: "; std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // <--- Requires header file <limits>. getline(cin, a[i].familia); //cout << "\n Golove: "; cout << "\n Goals: "; cin >> a[i].vk_golove; // <--- goals. cin.get(); cout << endl << endl; } Кодът не е правилен.Да се види до къде съм стигнал.
    • от kirilov_philip
      Моля за помощ!!!
      Задача: Даден е двумерен масив A с m реда и n стълба. Да се напише програма на C++, която създава нов масив B, като стойността на елемента Bi(i e долен индекс) е равна на индекса на най-малката стойност в i-ия ред на A.
      Стигнах дотук.
      #include <iostream>
      #include <stdlib.h>
      using namespace std;
      int main()
      {
          int m, n;
          cout << "m="; cin >> m;
          cout << "n="; cin >> n;
          int A[100][100];
          int i, j;
          for(i=0;i<m;i++)
              for (j = 0; j < n; j++)
              {
                  cout << "A[" << i << "][" << j << "]="; cin >> A[j];
              }
      }
    • от georgi999
      здравейте надявам се да ми помогнете. 4 пъти ме късат на този изпит . На notepad ++ трябва да го направя .наистина не ми се отдава. моляви не ме критикувайте просто искам да взема изпита,разберете ме. Трябва да направя уеб сайт .ще кача файла за да видите там е обеснено подробно .моляви за помощ.благодаря предварително .  

  • Дарение

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.