पायथन

Question

में हल करने की पहेली मुझे एक पहेली मिली और मैं इसे पायथन का उपयोग करके हल करना चाहता हूं।

पहेली:

एक व्यापारी एक 40 किलो वजन जो वह अपने दुकान में प्रयोग किया जाता है। एक बार, यह अपने हाथों से गिर गया और 4 टुकड़ों में तोड़ दिया गया था। लेकिन आश्चर्य की बात है, अब के संयोजन के साथ इन 4 टुकड़ों के संयोजन के साथ 1 किलो से 40 किलोग्राम के बीच वजन कम कर सकते हैं।

तो सवाल यह है कि, उन 4 टुकड़ों के वजन क्या हैं?

अब मैं इसे पायथन में हल करना चाहता था।

केवल बाधा मैं पहेली से मिला 4 टुकड़े की है कि राशि 40. इसी के साथ मैं फ़िल्टर कर सकते हैं सभी 4 मानों जिसका योग के सेट 40.

import itertools as it 

weight = 40 
full = range(1,41) 
comb = [x for x in it.combinations(full,4) if sum(x)==40] 

length of comb = 297

अब है है मुझे comb में मानों के प्रत्येक सेट को जांचने और संचालन के सभी संयोजनों को आजमाने की आवश्यकता है।

जैसे (a,b,c,d)comb में मानों का पहला सेट है, मुझे a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........ और इसी तरह की जांच करने की आवश्यकता है।

मैंने बहुत कोशिश की, लेकिन मैं इस चरण में फंस गया हूं, यानी 4 मानों के प्रत्येक सेट में गणना के इन सभी संयोजनों को कैसे जांचें।

प्रश्न:

1) मुझे लगता है कि मैं एक सूची [a,b,c,d] and [+,-] के सभी संभव संयोजन पाने के लिए की जरूरत है।

2) क्या किसी के पास एक बेहतर विचार है और मुझे बताएं कि यहां से आगे कैसे जाना है?

इसके अलावा, मैं इसे बाहरी पुस्तकालयों की सहायता के बिना पूरी तरह से करना चाहता हूं, केवल पायथन के मानक पुस्तकालयों का उपयोग करने की आवश्यकता है।

EDIT: देर से जानकारी के लिए खेद है। इसका जवाब है (1,3, 9, 27), जिसे मैंने कुछ साल पहले पाया था। मैंने जवाब की जांच की है और सत्यापित किया है।

संपादित करें: वर्तमान में, fraxel का उत्तर time = 0.16 ms के साथ सही काम करता है। एक बेहतर और तेज़ दृष्टिकोण हमेशा स्वागत है।

सादर

ARK

Answer 1

इससे पहले चलने के माध्यम से anwswer:

हम सब x के लिए पता a*A + b*B + c*C + d*D = x 0 और 40 के बीच, और a, b, c, d-1, 0, 1 तक सीमित हैं। स्पष्ट रूप से A + B + C + D = 40।

A + B + C = 39, तो D = 1, neccessity द्वारा: अगले मामले x = 39 है, इसलिए स्पष्ट रूप से छोटी से छोटी चाल एक तत्व को दूर करने के लिए है (यह तभी संभव कदम कि सफलतापूर्वक 39 के खिलाफ संतुलन में परिणाम सकता है)।

अगले:

A + B + C - D = 38

अगले:

A + B + D = 37, तो C = 3

तो:

A + B = 36

तो:

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31, तो A = 9

इसलिए B = 27

01,235,

तो वजन 1, 3, 9, 27

वाकई इस तथ्य यह है कि वे सभी के गुणकों में होना चाहिए से तुरंत निष्कर्ष निकाला जा सकता है 3.

दिलचस्प अद्यतन:

तो यहाँ के लिए कुछ अजगर कोड है किसी भी गिराए गए वजन के लिए वजन का न्यूनतम सेट ढूंढें जो अंतरिक्ष को फैलाएगा:

def find_weights(W): 
    weights = [] 
    i = 0 
    while sum(weights) < W: 
     weights.append(3 ** i) 
     i += 1 
    weights.pop() 
    weights.append(W - sum(weights)) 
    return weights 

print find_weights(40) 
#output: 
[1, 3, 9, 27] 

आगे बढ़ने के लिए इस व्याख्या को चित्रित करें, कोई समस्या संख्या [0, 40] को स्थानांतरित करने के लिए वजन की न्यूनतम संख्या के रूप में समस्या पर विचार कर सकता है। यह स्पष्ट है कि प्रत्येक वजन के साथ आप जो चीजें कर सकते हैं वह ट्रिनरी/टर्नरी है (वजन बढ़ाएं, वजन हटाएं, दूसरी तरफ वजन रखें)।

ABCD: Ternary: 
40: ++++  0000 
39: +++0  0001 
38: +++-  0002 
37: ++0+  0010 
36: ++00  0011 
35: ++0-  0012 
34: ++-+  0020 
33: ++-0  0021 
32: ++--  0022 
31: +0++  0100 
etc. 

मैं के साथ 9 0 से त्रिगुट गिनती डाल दिया है, वर्णन करने के लिए है कि हम एक trinary संख्या प्रणाली में प्रभावी रूप से कर रहे हैं: तो अगर हम हमारे (अज्ञात) अवरोही क्रम में वजन (A, B, C, D) लिखते हैं, हमारे चाल के रूप में संक्षेप किया जा सकता है (आधार 3)। हमारा समाधान हमेशा इस प्रकार लिखा जा सकता है:

3**0 + 3**1 +3**2 +...+ 3**N >= Weight 

न्यूनतम एन के लिए यह सच है। न्यूनतम समाधान हमेशा इस फॉर्म का होगा।

इसके अलावा, हम आसानी से बड़ी वजन के लिए समस्या का समाधान और अंतरिक्ष को पार करने वाली टुकड़े की न्यूनतम संख्या पा सकते हैं:

एक आदमी एक ज्ञात वजन डब्ल्यू चला जाता है, यह टुकड़ों में टूट जाता है। उनके नए वजन उन्हें डब्ल्यू तक वजन कम करने की इजाजत देते हैं। कितने वजन हैं, और वे क्या हैं?

#what if the dropped weight was a million Kg: 
print find_weights(1000000) 
#output: 
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839] 

एक बड़ी वजन और टुकड़े की अज्ञात संख्या के लिए क्रमपरिवर्तन उपयोग करने का प्रयास !!

Answer 2

यहाँ एक जानवर बल itertools समाधान है:

import itertools as it 

def merchant_puzzle(weight, pieces): 
    full = range(1, weight+1) 
    all_nums = set(full) 
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight] 
    funcs = (lambda x: 0, lambda x: x, lambda x: -x) 
    for c in comb: 
     sums = set() 
     for fmap in it.product(funcs, repeat=pieces): 
      s = sum(f(x) for x, f in zip(c, fmap)) 
      if s > 0: 
       sums.add(s) 
       if sums == all_nums: 
        return c 

>>> merchant_puzzle(40, 4) 
(1, 3, 9, 27) 

यह कैसे काम करता है की एक विवरण के लिए, the answer Avaris gave चेक करें, इस एक ही एल्गोरिथ्म के एक कार्यान्वयन है ।

Answer 3

आप करीब हैं, बहुत करीब :)।

चूंकि यह एक पहेली है जिसे आप हल करना चाहते हैं, मैं केवल पॉइंटर्स दूंगा।इस भाग के लिए:

जैसे अगर (ए, बी, सी, डी) कंघी में मूल्यों का पहला सेट है, मैं जांच करने की आवश्यकता ए, बी, सी, डी, ए + बी, एबी,। ................ ए + बी + सीडी, ए-बी + सी + डी ........ और इसी तरह।

इस पर विचार करें: प्रत्येक वजन को एक पैमाने पर, दूसरे या न तो रखा जा सकता है। तो a के मामले के लिए, इस [a, -a, 0] के रूप में प्रतिनिधित्व किया जा सकता है। अन्य तीनों के साथ ही। अब आपको प्रत्येक वजन के लिए इन 3 संभावनाओं के साथ सभी संभावित जोड़ों की आवश्यकता है (संकेत: itertools.product)। फिर, एक जोड़ी के संभावित मापने (कहते हैं कि करने देता है: (a, -b, c, 0)) केवल इन (a-b+c+0) का योग है।

कार्य शेष है सिर्फ अगर तुम सकता है 'उपाय' सभी आवश्यक वजन जाँच कर रहा है। set यहां आसान हो सकता है।

पुनश्च: के रूप में यह टिप्पणी में कहा गया था, सामान्य स्थिति के लिए, यह आवश्यक नहीं है कि इन विभाजित वजन अलग होना चाहिए हो सकता है (इस समस्या के लिए यह है)। आप itertools.combinations पर पुनर्विचार कर सकते हैं।

Answer 4

मैं जानवर दूसरे भाग से बाहर नरक मजबूर कर दिया।

इस पर क्लिक करें यदि आप इस सवाल का जवाब देखने के लिए नहीं करना चाहती है। जाहिर है, अगर मैं क्रमपरिवर्तन में बेहतर था, इस के लिए आवश्यक है | बहुत कम काट/चिपका खोज/बदल देते हैं:

http://pastebin.com/4y2bHCVr

Answer 5

मुझे पायथन वाक्यविन्यास नहीं पता है, लेकिन हो सकता है कि आप इस स्कैला कोड को डीकोड कर सकें; के लिए लूप 2 के साथ शुरू:

def setTo40 (a: Int, b: Int, c: Int, d: Int) = { 

val vec = for (
    fa <- List (0, 1, -1); 
    fb <- List (0, 1, -1); 
    fc <- List (0, 1, -1); 
    fd <- List (0, 1, -1); 
    prod = fa * a + fb * b + fc * c + fd * d; 
    if (prod > 0) 
) yield (prod) 

    vec.toSet 
} 

for (a <- (1 to 9); 
    b <- (a to 14); 
    c <- (b to 20); 
    d = 40-(a+b+c) 
    if (d > 0)) { 
    if (setTo40 (a, b, c, d).size > 39) 
     println (a + " " + b + " " + c + " " + d) 
    } 

Answer 6

वजन के साथ

[2, 5, 15, 18] आप भी 1 और 40 किलो के बीच सभी वस्तुओं है, हालांकि उनमें से कुछ परोक्ष रूप से मापा जा करने की आवश्यकता होगी माप सकते हैं। उदाहरण के लिए, ऑब्जेक्ट वेटिंग 39 किग्रा को मापने के लिए, आप इसकी तुलना 40 किलोग्राम के साथ करेंगे और शेष 40 किलो ग्राउंड (क्योंकि 39 < 40) पर पेंड करेगा, लेकिन फिर यदि आप 2 किलो वजन निकाल देते हैं तो यह दूसरी तरफ पेंड करेगा (क्योंकि 39> 38) और इस तरह आप ऑब्जेक्ट वजन 39 किलो वजन समाप्त कर सकते हैं।

अधिक दिलचस्प बात, वजन [2, 5, 15, 45] के साथ आप सभी वस्तुओं को 67 किलो तक माप सकते हैं।

Answer 7

किसी कॉम्बो/perms आयात करने के लिए एक पुस्तकालय आयात करने के लिए नहीं चाहता है, यह सब संभव 4-कदम रणनीतियों उत्पन्न होगा ...

# generates permutations of repeated values 
def permutationsWithRepeats(n, v): 
    perms = [] 
    value = [0] * n 
    N = n - 1 
    i = n - 1 

    while i > -1: 
     perms.append(list(value)) 

     if value[N] < v: 
      value[N] += 1 
     else: 
      while (i > -1) and (value[i] == v): 
       value[i] = 0 
       i -= 1 

      if i > -1: 
       value[i] += 1 
       i = N 

    return perms 

# generates the all possible permutations of 4 ternary moves 
def strategy(): 
    move = ['-', '0', '+'] 
    perms = permutationsWithRepeats(4, 2) 

    for i in range(len(perms)): 
     s = '' 

     for j in range(4): 
      s += move[perms[i][j]] 

     print s 

# execute 
strategy()