एक पूर्णांक एनआई दो पूर्णांकों ए और बी है कि संतुष्ट एक × बी निम्नलिखित शर्तों के साथ ≥ एन लगाना चाहते हैं को देखते हुए ग्रिड निर्माण

Question

के लिए दो में एक पूर्णांक विघटित करने के लिए:

1. एक × बी के बीच का अंतर और एन जितना संभव हो उतना कम है।
2. ए और बी के बीच का अंतर जितना संभव हो उतना कम (वर्ग तक पहुंचने के लिए) है।

उदाहरण: 23 संभावित समाधान 3 × 8, 6 × 4, 5 × 5. 6 × 4 सबसे अच्छा है, क्योंकि यह ग्रिड में सिर्फ एक खाली जगह छोड़ देता है और 3 से × 8 "कम" आयताकार है

एक और उदाहरण: 21. समाधान 3 × 7 और 4 × 6. 3 × 7 वांछित है।

एक ब्रूट फोर्स समाधान आसान है। मैं देखना चाहता हूं कि एक चालाक समाधान संभव है या नहीं।

Answer 1

आसान।

स्यूडोकोड

a = b = floor(sqrt(N)) 

if (a * b >= N) return (a, b) 

a += 1 
if (a * b >= N) return (a, b) 

return (a, b+1) 

में और यह हमेशा समाप्त हो जाएगी, a और b के बीच की दूरी पर सबसे केवल 1.

यदि आप दूसरी बाधा आराम बहुत कठिन होगा, लेकिन है कि एक और सवाल है।

संपादित करें: जैसा कि ऐसा लगता है कि पहली स्थिति अधिक महत्वपूर्ण है, आपको समस्या को थोड़ा अलग तरीके से हमला करना है। आपको खराबता मापने के लिए कुछ विधि निर्दिष्ट करने की आवश्यकता है, जो कि चौकोर पर्याप्त = दूसरी स्थिति नहीं है, क्योंकि यहां तक ​​कि प्राइम संख्याओं को 1*number के रूप में कारक बनाया जा सकता है, और हम पहली शर्त को पूरा करते हैं। मान लें कि हमारे पास एक बुरी तरह का कार्य है (a >= b && a <= 2 * b कहें), फिर N को कारगर बनाएं और सर्वोत्तम संयोजन खोजने के लिए विभिन्न संयोजनों को आजमाएं। यदि कोई अच्छा पर्याप्त नहीं है, तो N+1 और इसी तरह से प्रयास करें।

EDIT2: थोड़ा सोच के बाद और अधिक मैं इस समाधान के साथ आते हैं, पायथन में:

from math import sqrt 

def isok(a, b): 
    """accept difference of five - 2nd rule""" 
    return a <= b + 5 

def improve(a, b, N): 
    """improve result: 
    if a == b: 
     (a+1)*(b-1) = a^2 - 1 < a*a 
    otherwise (a - 1 >= b as a is always larger) 
     (a+1)*(b-1) = a*b - a + b - 1 =< a*b 

    On each iteration new a*b will be less, 
    continue until we can, or 2nd condition is still met 
    """ 
    while (a+1) * (b-1) >= N and isok(a+1, b-1): 
    a, b = a + 1, b - 1 

    return (a, b) 

def decomposite(N): 
    a = int(sqrt(N)) 
    b = a 

    # N is square, result is ok 
    if a * b >= N: 
    return (a, b) 

    a += 1 

    if a * b >= N: 
    return improve(a, b, N) 

    return improve(a, b+1, N) 

def test(N): 
    (a, b) = decomposite(N) 

    print "%d decomposed as %d * %d = %d" % (N, a, b, a*b) 

[test(x) for x in [99, 100, 101, 20, 21, 22, 23]] 

जो आउटपुट

99 decomposed as 11 * 9 = 99 
100 decomposed as 10 * 10 = 100 
101 decomposed as 13 * 8 = 104 
20 decomposed as 5 * 4 = 20 
21 decomposed as 7 * 3 = 21 
22 decomposed as 6 * 4 = 24 
23 decomposed as 6 * 4 = 24 

Answer 2

A = B = ceil (sqrt N) 

Answer 3

मुझे लगता है कि यह काम कर सकते हैं (अपनी शर्तों कुछ हद तक अस्पष्ट हैं)। यह समाधान कुछ हद तक समान है, मूल रूप से आयताकार मैट्रिक्स का उत्पादन करता है जो लगभग वर्ग है। आप अगर पहली शर्त प्रमुख है (और दूसरी शर्त नहीं किया जाता है) साबित होता है कि ए + 2 इष्टतम स्थिति नहीं है

A0 = B0 = ceil (sqrt N) 
A1 = A0+1 
B1 = B0-1 
if A0*B0-N > A1*B1-N: return (A1,B1) 
return (A0,B0) 

इस समाधान है आवश्यकता हो सकती है

A0 = B0 = ceil (sqrt N) 
if A0*B0==N: return (A0,B0) 
return (N,1) 

अन्य शर्तें रूपों में हो जाएगा