Results 1 to 16 of 16
Hybrid View
-
1st December 2016 17:26 #1Registered User
Join Date: Jul:2009
Location: Bulgaria
Posts: 848
Çàùî ñå ïðîìåíÿ òàêà åôåêòèâíîñòà íà òàçè ïðîãðàìà (java)
Èçìèñëèõ ñè òàçè ïðîãðàìà çà òúðñåíå íà ïðîñòè ÷èñëà äíåñ äîêàòî ïúòóâàõ è ÿ òåñòâàõ. Íå å ñëîæíà, äåëè b íà âñÿêî ÷èñëî ïî-ìàëêî îò íåãî êàòî çàïî÷âà îò 2 è àêî íå óñïåå äà ãî ðàçäåëè òî÷íî ìè êàçâà ÷å å ïðîñòî è è ìèíàâà íà b+1 è îòíîâî ñúùàòà ïðîöåäóðà.
È ïîñëå äîáàâèõ åäíî ïîäîáðåíèåCode:int i = 2; int b = 10000000; while (b > 2) { while ((i < b) && (b % i != 0)) { if (i == b - 1) { System.out.print(b + ","); } i++; } i=2; b++; }
Ïîäîáðåíèåòî ïðîñòî ïðåñêà÷à âñè÷êè ÷èñëà êîèòî íå çàâúðøâàò íà 1,3,7,9 çàùîòî íå ìîæå äà ñà ïðîñòè à òîâà ñà 60% îò ÷èñëàòà íî ñêîðîñòà íà ïðîãðàìàòà ñêî÷è ñàìî ñ 15% â eclipse, êîé çíàå çàùî ?Code:int i = 2; int b = 10000000; while (b > 2) { int c = b % 10; if((c==1)||(c==3)||(c==7)||(c==9)){ while ((i < b) && (b % i != 0)) { if (i == b - 1) { System.out.print(b + ","); } i++; }} i=2; b++; }
Ìîæå áè íå ñàìèòå äåëåíèÿ íàòîâàðâàò ïðîöåñîðà à âúðòåíå íà while ëîîïîâåòå ?Last edited by atom3; 1st December 2016 at 17:51.
Alienware 17 R4, i7-6700hq, gtx-1060 OC, 16gb ddr4 2667 ram è 256gb NVMe SSD, LSP, MMS, GPRS, UPS, FedEx, ZDR, kopr?, asl, W2F, àà ÷àêàé ìàé íå âñè÷êè ñúêðàùåíèÿ áÿõà çà òóê... Íî ïúê íàëè å ìîäåðíî ñúñ ñúêðàùåíèÿ äà ñå ãîâîðè.
-
1st December 2016 17:49 #2
Çàùîòî ïîëîâèíàòà ñëó÷àè, b å ÷åòíî è ïðîâåðêàòà ñ b % i == 0 ïðåêðàòÿâà âåäíàãà âúòðåøíèÿ öèêúë.
Àêî èñêàø äà óñêîðèø ïîâå÷å ïðîãðàìàòà: çàïî÷òíè îò íå÷åòíî b è ãî ïðîìåíÿé ñ b -= 2;
Èëè, àêî èñêàø äà ÿ óñêîðèø ñåðèîçíî: íàïèøè ñè ðåøåòî íà Åðàòîñòåí.Last edited by anrieff; 1st December 2016 at 17:51.
Åòî òàêà ñå ïëîäÿò òå, êàçâàì ñè àç. Ïîä íîñà òè.
"640K îught to be enough for anybody" - Bill Gates, 1981
Òåñòîâå íà áàòåðèè::Machine specs::Fract::AGG::ÍåÑåÑúðäè×îâå÷å::Baileys::blog::YouTube channel
-
1st December 2016 18:03 #3Registered User
Join Date: Jul:2009
Location: Bulgaria
Posts: 848
 òîçè ñëó÷àé êîå å íàé-îïðåäåëÿùî çà ñêîðîñòà íà ïðîãðàìàòà, äåëåíèÿòà èëè èçïúëíåíèÿòà íà ëóóïà
Last edited by atom3; 1st December 2016 at 18:03.
Alienware 17 R4, i7-6700hq, gtx-1060 OC, 16gb ddr4 2667 ram è 256gb NVMe SSD, LSP, MMS, GPRS, UPS, FedEx, ZDR, kopr?, asl, W2F, àà ÷àêàé ìàé íå âñè÷êè ñúêðàùåíèÿ áÿõà çà òóê... Íî ïúê íàëè å ìîäåðíî ñúñ ñúêðàùåíèÿ äà ñå ãîâîðè.
-
1st December 2016 18:39 #4
Ïî ïðèíöèï äåëåíèÿòà ñà ïî-áàâíè îò ðàçíèòå ëóóï êîíñòðóêöèè (if (...), i++ è ò.í.).
Îïòèìèçàöèÿòà òè íå ïîìàãà ìíîãî, òúé êàòî òÿ ôèëòðèðà ñàìî ÷èñëà, êîèòî áèõà ñå ïðîâåðèëè ìíîãî áúðçî îò b % i, ò.å. ñïåñòÿâà ñå âðåìå îò ñëó÷àèòå, êîèòî è èíà÷å ñà áúðçè.
Àêî èñêàø äà îïòèìèçèðàø íàé-ëîøèÿ ñëó÷àé (ïðîñòèòå ÷èñëà), ìîæåø äà ïîëçâàø äðóãî íàáëþäåíèå: àêî äî SQRT(b) íå ñè íàìåðèë äåëèòåë - òî íÿìà äà íàìåðèø è íàä SQRT(b)
Ò.å. âúòðåøíèÿò òè öèêúë ìîæå äà å îò âèäà for (int i = 2; i*i <= b; i++) ...
Òîâà ïðàâè öåëèÿò àëãîðèòúì ñúñ ñëîæíîñò Î(n3/2) âìåñòî ñåãàøíèÿò, êîéòî å ÷èñòî O(n2).
Ïî ïðèíöèï çà òàêèâà çàäà÷è àëãîðèòìè÷íàòà ñëîæíîñò å ìíîãî ïî-âàæíà îò òåæåñòòà íà îòäåëíè îïåðàöèè êàòî äåëåíèåòî. Àêî èñêàø äà ãî íàïðàâèø íàèñòèíà áúðçî - ðåäóöèðàé ãî äî O(n log log n), ò.å. ðåøåòî íà Åðàòîñòåí.Åòî òàêà ñå ïëîäÿò òå, êàçâàì ñè àç. Ïîä íîñà òè.
"640K îught to be enough for anybody" - Bill Gates, 1981
Òåñòîâå íà áàòåðèè::Machine specs::Fract::AGG::ÍåÑåÑúðäè×îâå÷å::Baileys::blog::YouTube channel
-
3rd December 2016 21:11 #5Registered User
Join Date: Aug:2016
Location: Sofia
Posts: 17
Äåëåíèåòî å äîñòà áàâíî. Íî â òâîÿ ñëó÷àé ìîæå äà ãî èçáåãíåø.
Èñêàø äà ïðåñêî÷èø ÷åòíèòå, ò.å. òè òðÿáâà áúðçà ïðîâåðêà çà ÷åòíîñò íà äàäåíî ÷èñëî.
Èìàéêè ïðåäâèä, ÷å ÷èñëàòà â êðàéíà ñìåòêà ñå ïðåäñòàâÿò â äâîè÷åí âèä, òîãàâà çàùî äà íå ñå íàïðàâè òàêàâà ïðîâåðêà.
Àêî ïîñëåäíèÿò áèò íà öÿëîòî ÷èñëî å 1, çíà÷è òîâà å íå÷åòíî ÷èñëî, ò.å. çàâúðøâà íà 1, 3, 5, 7 èëè 9.
Áè áèëî ñóïåð, àêî ïðîáâàø è ñïîäåëèø êàêâà å ðàçëèêàòà âúâ âðåìåòî çà èçïúëíåíèå ìåæäó ðàçëè÷íèòå ðåøåíèÿ.
-
6th December 2016 16:14 #6Registered User
Join Date: Jul:2009
Location: Bulgaria
Posts: 848
Íàëè òîâà ñúì íàïðàâèë â îðèãèíàëíèÿ ìè ïîñò,
äàæå íå ñàìî ÷åòíèòå íî è 5 ñúùî ìàõàì çàùîòî íÿìà ïðîñòè ÷èñëà çàâúðøâàùè íà íåãî. Èëè òè äðóãî èìàø â ïðåäâèä ? Òà ñ òàçè äîáàâêà ñ îêîëî 15-16% ñêî÷è ñêîðîñòà íà ïðîãðàìàòà(àìà äåôàêòî òåçè ïðîöåíòè ãè îò÷åòîõ ïðè ÷åòèðè öèôðåíè ÷èñëà à òî êîëêîòî ñà ïî ãîëåìè òîëêîâà ïî ìàëêî âëèÿíèå ùå îêàçâà òàçè ïðîìÿíà íà 7-8 öèôðåíè íèùî ÷óäíî è äî 1% äà ïàäíå), äîñòà ñêðîìíî ñðàâíåíî ñ î÷àêâàíèÿòà ìè è çàòîâà ïóñíàõ òåìàòà äå. Âñå îùå íå ñúì ïðîáâàë òîâà ñâîéñòâî ñ êîðåíà îò ÷èñëîòî äà âèäÿ êàêâî ùå ñå ñëó÷è, ìàëêî ñúì çàåò â ïîñëåäíî âðåìå...if((c==1)||(c==3)||(c==7)||(c==9))Last edited by atom3; 6th December 2016 at 16:20.
Alienware 17 R4, i7-6700hq, gtx-1060 OC, 16gb ddr4 2667 ram è 256gb NVMe SSD, LSP, MMS, GPRS, UPS, FedEx, ZDR, kopr?, asl, W2F, àà ÷àêàé ìàé íå âñè÷êè ñúêðàùåíèÿ áÿõà çà òóê... Íî ïúê íàëè å ìîäåðíî ñúñ ñúêðàùåíèÿ äà ñå ãîâîðè.




Reply With Quote

Lenovo ThinkPad 15 èëè IdeaPad 15
5th May 2023, 22:16 in Ìîáèëíè êîìïþòðè