Results 1 to 16 of 16

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Registered 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++;
    			}
    È ïîñëå äîáàâèõ åäíî ïîäîáðåíèå
    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++;
    			}
    Ïîäîáðåíèåòî ïðîñòî ïðåñêà÷à âñè÷êè ÷èñëà êîèòî íå çàâúðøâàò íà 1,3,7,9 çàùîòî íå ìîæå äà ñà ïðîñòè à òîâà ñà 60% îò ÷èñëàòà íî ñêîðîñòà íà ïðîãðàìàòà ñêî÷è ñàìî ñ 15% â eclipse, êîé çíàå çàùî ?

    Ìîæå áè íå ñàìèòå äåëåíèÿ íàòîâàðâàò ïðîöåñîðà à âúðòåíå íà 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, àà ÷àêàé ìàé íå âñè÷êè ñúêðàùåíèÿ áÿõà çà òóê... Íî ïúê íàëè å ìîäåðíî ñúñ ñúêðàùåíèÿ äà ñå ãîâîðè.

  2. #2
    ɐ-əpoɔᴉu⋂ ɐí íəÔ anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    Çàùîòî ïîëîâèíàòà ñëó÷àè, 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

  3. #3
    Registered 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, àà ÷àêàé ìàé íå âñè÷êè ñúêðàùåíèÿ áÿõà çà òóê... Íî ïúê íàëè å ìîäåðíî ñúñ ñúêðàùåíèÿ äà ñå ãîâîðè.

  4. #4
    ɐ-əpoɔᴉu⋂ ɐí íəÔ anrieff's Avatar
    Join Date: Apr:2004
    Location: Sofia
    Posts: 8,448
    Ïî ïðèíöèï äåëåíèÿòà ñà ïî-áàâíè îò ðàçíèòå ëóóï êîíñòðóêöèè (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

  5. #5
    Registered User
    Join Date: Aug:2016
    Location: Sofia
    Posts: 17
    Äåëåíèåòî å äîñòà áàâíî. Íî â òâîÿ ñëó÷àé ìîæå äà ãî èçáåãíåø.
    Èñêàø äà ïðåñêî÷èø ÷åòíèòå, ò.å. òè òðÿáâà áúðçà ïðîâåðêà çà ÷åòíîñò íà äàäåíî ÷èñëî.
    Èìàéêè ïðåäâèä, ÷å ÷èñëàòà â êðàéíà ñìåòêà ñå ïðåäñòàâÿò â äâîè÷åí âèä, òîãàâà çàùî äà íå ñå íàïðàâè òàêàâà ïðîâåðêà.
    Àêî ïîñëåäíèÿò áèò íà öÿëîòî ÷èñëî å 1, çíà÷è òîâà å íå÷åòíî ÷èñëî, ò.å. çàâúðøâà íà 1, 3, 5, 7 èëè 9.

    Áè áèëî ñóïåð, àêî ïðîáâàø è ñïîäåëèø êàêâà å ðàçëèêàòà âúâ âðåìåòî çà èçïúëíåíèå ìåæäó ðàçëè÷íèòå ðåøåíèÿ.

  6. #6
    Registered User
    Join Date: Jul:2009
    Location: Bulgaria
    Posts: 848
    Quote Originally Posted by dragi19 View Post
    Äåëåíèåòî å äîñòà áàâíî. Íî â òâîÿ ñëó÷àé ìîæå äà ãî èçáåãíåø.
    Èñêàø äà ïðåñêî÷èø ÷åòíèòå, ò.å. òè òðÿáâà áúðçà ïðîâåðêà çà ÷åòíîñò íà äàäåíî ÷èñëî.
    Èìàéêè ïðåäâèä, ÷å ÷èñëàòà â êðàéíà ñìåòêà ñå ïðåäñòàâÿò â äâîè÷åí âèä, òîãàâà çàùî äà íå ñå íàïðàâè òàêàâà ïðîâåðêà.
    Àêî ïîñëåäíèÿò áèò íà öÿëîòî ÷èñëî å 1, çíà÷è òîâà å íå÷åòíî ÷èñëî, ò.å. çàâúðøâà íà 1, 3, 5, 7 èëè 9.

    Áè áèëî ñóïåð, àêî ïðîáâàø è ñïîäåëèø êàêâà å ðàçëèêàòà âúâ âðåìåòî çà èçïúëíåíèå ìåæäó ðàçëè÷íèòå ðåøåíèÿ.
    Íàëè òîâà ñúì íàïðàâèë â îðèãèíàëíèÿ ìè ïîñò,
    if((c==1)||(c==3)||(c==7)||(c==9))
    äàæå íå ñàìî ÷åòíèòå íî è 5 ñúùî ìàõàì çàùîòî íÿìà ïðîñòè ÷èñëà çàâúðøâàùè íà íåãî. Èëè òè äðóãî èìàø â ïðåäâèä ? Òà ñ òàçè äîáàâêà ñ îêîëî 15-16% ñêî÷è ñêîðîñòà íà ïðîãðàìàòà(àìà äåôàêòî òåçè ïðîöåíòè ãè îò÷åòîõ ïðè ÷åòèðè öèôðåíè ÷èñëà à òî êîëêîòî ñà ïî ãîëåìè òîëêîâà ïî ìàëêî âëèÿíèå ùå îêàçâà òàçè ïðîìÿíà íà 7-8 öèôðåíè íèùî ÷óäíî è äî 1% äà ïàäíå), äîñòà ñêðîìíî ñðàâíåíî ñ î÷àêâàíèÿòà ìè è çàòîâà ïóñíàõ òåìàòà äå. Âñå îùå íå ñúì ïðîáâàë òîâà ñâîéñòâî ñ êîðåíà îò ÷èñëîòî äà âèäÿ êàêâî ùå ñå ñëó÷è, ìàëêî ñúì çàåò â ïîñëåäíî âðåìå...
    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, àà ÷àêàé ìàé íå âñè÷êè ñúêðàùåíèÿ áÿõà çà òóê... Íî ïúê íàëè å ìîäåðíî ñúñ ñúêðàùåíèÿ äà ñå ãîâîðè.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Copyright © 1999-2011 Õàðäóåð ÁÃ. Âúçìîæíî å ñúäúðæàíèåòî íà òàçè ñòðàíèöà äà å îáåêò íà àâòîðñêè ïðàâà.
iskamPC.com | mobility.BG | Bloody's Techblog | Êðèïòîâàëóòè è ìàéíèíã | 3D Vision Blog | Ìàãàçèí çà åëåêòðîííè öèãàðè