विभाजक को अधिकतम करने के लिए divisor कैसे खोजें?

Question

दो नंबर n और k दिए गए, x, 1 <= x <= k खोजें जो शेष n % x को अधिकतम करता है।

उदाहरण के लिए, एन = 20 और के = 10 समाधान x = 7 है क्योंकि शेष 20% 7 = 6 अधिकतम है।

---

इस मेरे समाधान है:

int n, k; 
cin >> n >> k; 
int max = 0; 
for(int i = 1; i <= k; ++i) 
{ 
    int xx = n - (n/i) * i; // or int xx = n % i; 
    if(max < xx) 
    max = xx; 
} 
cout << max << endl; 

लेकिन मेरे समाधान O(k) है। क्या इसके लिए कोई और अधिक कुशल समाधान है?

Answer 1

असीम रूप से तेज़, लेकिन तेज नहीं, बस पीछे की ओर जाकर और जब आप जानते हैं कि आप बेहतर नहीं कर सकते हैं तो रोकना।

मान लें kn से कम है (अन्यथा केवल आउटपुट k)।

int max = 0; 
for(int i = k; i > 0 ; --i) 
{ 
    int xx = n - (n/i) * i; // or int xx = n % i; 
    if(max < xx) 
    max = xx; 
    if (i < max) 
    break; // all remaining values will be smaller than max, so break out! 
} 
cout << max << endl; 

(यह आगे जब तक i > max के रूप में पाश के लिए कर रही है, इस प्रकार एक सशर्त बयान को नष्ट करने से सुधार किया जा सकता है, लेकिन मैं इसे और अधिक स्पष्ट बनाने के लिए इस तरह से लिखा है) यह भी

, जाँच Garey और जॉनसन के कंप्यूटर और इंट्रैक्टिबिलिटी बुक यह सुनिश्चित करने के लिए कि यह एनपी-पूर्ण नहीं है (मुझे यकीन है कि मुझे उस पुस्तक में कुछ समस्या याद है जो इस तरह दिखती है)। मैं बेहतर समाधान के साथ आने की कोशिश करने पर बहुत अधिक प्रयास करने से पहले ऐसा करूँगा।

Answer 2

अच्छी छोटी पहेली!

दो मामूली मामलों से शुरू करना।

n < k के लिए: x s.t. n < x <= k हल करता है।

n = k के लिए: x = floor(k/2) + 1 हल करता है।

मेरे प्रयास।

n > k के लिए

:

x = n 
while (x > k) { 
    x = ceil(n/2) 
} 

^---- काम नहीं किया था।

1. x = floor(float(n)/(floor(float(n)/k) + 1)) + 1
2. x = ceil(float(n)/(floor(float(n)/k) + 1)) - 1

^---- "बंद" (जो कुछ भी है कि इसका मतलब है), लेकिन काम नहीं किया।

मेरे गर्व मुझे पतला है कि मैं सबसे बड़ी k -bounded हार्मोनिक, द्वारा 1.

समाधान दिया उपयोग करने के लिए पहली बार था उल्लेख करने के लिए।

अन्य जवाब के साथ इनलाइन मैं बस nk से भी कम समय के हार्मोनिक्स (@ColonelPanic की अवधि सौजन्य से) की जाँच, वर्तमान अधिकतम मूल्य (@TheGreatContini के सौजन्य से) द्वारा सीमित है। यह दोनों दुनिया में सबसे अच्छा है और मैंने सफलता के साथ 0 और 10000000 के बीच यादृच्छिक पूर्णांक के साथ परीक्षण किया है।

int maximalModulus(int n, int k) { 
    if (n < k) { 
     return n; 
    } 
    else if (n == k) { 
     return n % (k/2 + 1); 
    } 
    else { 
     int max = -1; 
     int i = (n/k) + 1; 
     int x = 1; 
     while (x > max + 1) { 
      x = (n/i) + 1; 
      if (n%x > max) { 
       max = n%x; 
      } 
      ++i; 
     } 
     return max; 
    } 
} 

प्रदर्शन परीक्षण: http://cpp.sh/72q6

नमूना उत्पादन:

Average number of loops: 
bruteForce: 516 
theGreatContini: 242.8 
evgenyKluev: 2.28 
maximalModulus: 1.36 // My solution 

Answer 3

मुझे यकीन है कि के लिए गलत हूँ, लेकिन यह मेरे लिए लग रहा है कि यह अगर n < k या नहीं पर निर्भर करता है।

मेरा मतलब है, अगर n < k, n%(n+1) आपको अधिकतम देता है, तो x = (n+1)।

ठीक है, दूसरे हाथ पर, आप j = k से शुरू कर सकते हैं और वापस n%j का मूल्यांकन जब तक यह n के बराबर है, इस प्रकार x = j है आप के लिए क्या देख रहे जाने के लिए और आप अधिकतम k चरणों में मिल जाएगा ... बहुत ज्यादा , क्या यह?

Answer 4

लहरों हाथ के आसपास

x का कोई मूल्य जो n का एक पहलू अधिकतम n%x का उत्पादन कर सकते है, क्योंकि अगर xn तो n%x=0 का एक पहलू है।

इसलिए, आप ऐसी प्रक्रिया चाहेंगे जो x पर विचार करने से बचाती है जो n का कारक है। लेकिन इसका मतलब है कि आप जानना चाहते हैं कि x एक कारक है या नहीं। यदि यह संभव था तो आप एक आसान प्रमुख कारक बनाने में सक्षम होंगे।

चूंकि is not प्रमुख कारक बनाने का एक ज्ञात आसान तरीका आपकी समस्या को हल करने के लिए एक "आसान" तरीका नहीं हो सकता है (मुझे नहीं लगता कि आपको एक सूत्र मिल जाएगा, किसी प्रकार की खोज आवश्यक होगी)।

यह कहा गया है कि प्रमुख कारककरण साहित्य में निष्पक्ष खोज के सापेक्ष कारकों को जल्दी से प्राप्त करने के चालाक तरीके हैं, इसलिए शायद इसे आपके प्रश्न का उत्तर देने के लिए लीवरेज किया जा सकता है।

Answer 5

के लिए> समस्या समस्या तुच्छ है (x = n + 1 ले लो)।

के < एन के लिए, रहने वाले n% x के ग्राफ के बारे में सोचें। यह सभी एन के लिए समान दिखता है: रहने वाले एन: एन/2, एन/3, एन/4 के हार्मोनिक्स पर शून्य पर गिरते हैं, जिसके बाद वे कूदते हैं, फिर अगले हार्मोनिक की तरफ आसानी से कमी करते हैं।

समाधान नीचे का सबसे स्थानीय स्थानीय अधिकतम है। एक सूत्र के रूप में x = n//((n//k)+1)+1 (जहां // पूर्णांक विभाजन है)।

Answer 6

यह समस्या दी गई श्रेणी में समारोह f(x)=n%x की अधिकतम पाने के लिए बराबर है।चलो देखते हैं कि यह कैसे समारोह की तरह दिखता है:

यह हम अधिकतम जल्दी ही मिल सकता है कि अगर हम x=k के साथ शुरू और फिर x कमी है, जबकि यह कोई मतलब (x=max+1 तक) बनाता है स्पष्ट है। इसके अलावा यह चित्र दिखाता है कि xsqrt(n) से बड़ा है, हमें अनुक्रमिक रूप से x को कम करने की आवश्यकता नहीं है। इसके बजाय हम तुरंत स्थानीय अधिकतम से पहले कूद सकते हैं।

int maxmod(const int n, int k) 
{ 
    int max = 0; 

    while (k > max + 1 && k > 4.0 * std::sqrt(n)) 
    { 
     max = std::max(max, n % k); 
     k = std::min(k - 1, 1 + n/(1 + n/k)); 
    } 

    for (; k > max + 1; --k) 
     max = std::max(max, n % k); 

    return max; 
} 

जादू निरंतर 4.0 पहले (महंगा) पाश की पुनरावृत्तियों की संख्या को कम करके प्रदर्शन में सुधार करने की अनुमति देता है।

सबसे खराब मामला जटिलता का अनुमान लगाया जा सकता है ओ (न्यूनतम, के, वर्ग (एन)))। लेकिन काफी बड़े k के लिए यह अनुमान शायद निराशावादी है: हम अधिकतम तेज़ी से पा सकते हैं, और यदि ksqrt(n) से काफी अधिक है तो हमें इसे खोजने के लिए केवल 1 या 2 पुनरावृत्तियों की आवश्यकता है।

मैं निर्धारित करने के लिए कितने पुनरावृत्तियों n के विभिन्न मूल्यों के लिए सबसे खराब स्थिति में जरूरत है कुछ परीक्षण किया:

n  max.iterations (both/loop1/loop2) 
10^1..10^2 11 2 11 
10^2..10^3 20 3 20 
10^3..10^4 42 5 42 
10^4..10^5 94 11 94 
10^5..10^6 196 23 196 
up to 10^7 379 43 379 
up to 10^8 722 83 722 
up to 10^9 1269 157 1269 

वृद्धि दर काफ़ी ओ (sqrt (एन)) से बेहतर है।