नकली सिक्का भारित कार्यों को हल करना

सभी खाबरोवियों को शुभ दिन ।

मैं टीके के लिए प्रोग्रामिंग ज्ञान को गहरा करने के लिए दूसरे दिन देख रहा था और नकली की पहचान करने के लिए सिक्कों को तौलने की समस्या पर एक साइट पर ठोकर खाई।

इस कार्य की कई किस्में हैं:
1) नकली सिक्के की पहचान करने के लिए तौल की संख्या निर्धारित करें (यह हल्का या भारी है)
2) वजन एल्गोरिथ्म निर्धारित करें
3) एक भारी या हल्के नकली सिक्के की परिभाषा
खैर, किस्मों का लेआउट।


यह Google के लिए संभव था, लेकिन कुछ के साथ उसने मुझे झुका दिया, और रात के कई घंटों के परिणामों के बाद, मैं निम्नलिखित प्राप्त करने में कामयाब रहा:

1. तौल की संख्या निर्धारित करें

• 3 में से 1 सिक्के को एक तौल में निर्धारित किया जा सकता है (यह या तो तौलने वालों में से एक होगा, या संतुलन में होगा)
• 2 तौल में 9 सिक्कों का निर्धारण किया जा सकता है
  
• 27 में से - 3 तौल आदि के लिए।
  

कुल मिलाकर, वजन की संख्या निर्धारित करने के लिए - ए - ए के लिए - सिक्कों की संख्या, निम्नलिखित शर्तों को पूरा करना चाहिए:
3 ⁿ > = A, या logA / log3 <= n,
जहाँ

• A सिक्कों की संख्या है,
• n - वज़न की संख्या (पूर्णांक तक गोल)
• लॉग दशमलव लघुगणक है।

उदाहरण के लिए:

• 26 सिक्कों के लिए आपको log26 / log3 = 2.966, n = 3 वज़न चाहिए
• 1563 सिक्कों के लिए - log1563 / log3 = 6.694 n = 7 वजन

2. वेटिंग एलगोरिदम

अब मैं एक सिक्के को तौलने के लिए सामान्य एल्गोरिदम दिखाऊंगा (बिंदु 1 को स्पष्ट करने के लिए) और मैं किसी प्रकार की एल्गोरिथम भाषा का उपयोग करूंगा। आपको बता दें कि एक नकली सिक्का भारी / हल्का होता है

1) हम तौल की संख्या निर्धारित करते हैं। एक नियम के रूप में, कार्य यह निर्धारित करते हैं कि नकली सिक्के को निर्धारित करने के लिए कितने वजन हैं, लेकिन इस तरह से हम यह जांच करेंगे कि समस्या का समाधान है या नहीं। अनुच्छेद 1 के अनुसार, हम संख्या n प्राप्त करते हैं।

logA / log3 <= n

2) अगला, हम सिक्कों को 2 समूहों में बांटते हैं

यदि वांछित संख्या विषम है
बी = ए - ३ ^{(एन - १)}

यदि वांछित संख्या सम है
बी = ए - 3 ^{(एन - 1)} + १

और दूसरा समूह

सी = ए - बी

3) समूह बी - हम सेक्स को दो समूहों (बाएं समूह - एलजी, सही समूह पीजी) में विभाजित करते हैं। हमें तीन समूह मिले

एलएच, पीजी, सी।

4) समूह एलजी, पीजी - एक नकली सिक्के (डी) के साथ समूह को तौला और निर्धारित किया। 3 विकल्प हैं:
a) तराजू पर सिक्कों का बायां समूह (LG) भारी / हल्का है (D = LG)
ख) तराजू पर सिक्कों का सही समूह (PG) भारी / हल्का है (D = PG)
ग) तराजू पर सिक्कों के समूह समान हैं, फिर शेष (डी = सी) में एक नकली सिक्का।

5) चरण 4 में पाए गए समूह के लिए, चरण 1-4 (ए = डी) दोहराएं, जबकि सिक्कों की संख्या 2 (ए> 2) से अधिक है

6) अगर 2 सिक्के बचे हैं, तो अंतिम वेट-इन (LG = 1 और PG = 1) करें

7) एक नकली सिक्का मिला है।

स्पष्टता के लिए कार्य पर विचार करें, इसे उसी साइट से होने दें: आपको 3 वज़न के लिए 12 सिक्कों को विभाजित करने की आवश्यकता है, एक नकली सिक्का आसान है।
1) वजन की संख्या
log12 / log3 = 2.261
n = 3 (ठीक है, समस्या का हल है)
2) समूहों में विभाजित करें
बी = 12 - 3 ^{(3 - 1)} + 1 = 4
सी = 12 - 4 = 8
3) हम समूह बी को आधे में विभाजित करते हैं:
एलजी = 2, पीजी = 2, शेष सी = 8

4) वजन एलएच और जीएचजी।

1 तौल के बाद विकल्प
a) एलजी = 2 - एक नकली सिक्के के साथ (चरण 6 पर जाएं)
ख) पीजी = 2 - एक नकली सिक्के के साथ (चरण 6 पर जाएं)
c) शेष (C = 8) - एक नकली सिक्के के साथ। 8 सिक्कों के लिए चरण 1-4 दोहराएं
ए = 8
1) वजन की संख्या
log8 / log3 = 1.893
n = 2
2) समूहों में विभाजित करें
बी = 8 - 3 ^{(2 - 1)} + 1 = 6
सी = 8 - 6 = 2
3) हम समूह बी को आधे में विभाजित करते हैं:
एलजी = 3, पीजी = 3, शेष सी = 2

2 वें वजन के बाद विकल्प
a) LG = 3 - एक नकली सिक्के के साथ (3 सिक्कों A = 3 के लिए चरण 1-4 दोहराएं)
ख) पीजी = 3 - एक नकली सिक्के के साथ (दोहराएँ चरण १-४ के लिए ३ सिक्के ए = ३)
c) शेष (C = 2) - एक नकली सिक्के के साथ। चरण 6 पर जाएं)

खैर, तीसरा वजन - नकली का निर्धारण करने के लिए 2 या 3 सिक्कों से, और 3 सिक्कों के लिए नियम भी काम करेगा।

25 सिक्कों के लिए एक और उदाहरण
1) एन = 2.93 = 3
2) बी = 25 - 3 ^{(3 - 1)} = 16
सी = 25 - 16 = 9
3) एलजी = 8, पीजी = 8, सी = 9
1 तौल के बाद विकल्प
a) D = LG = 8
b) D = PG = 8
c) D = C = 9
8 सिक्कों का वजन पिछले उदाहरण में दिखाया गया है (ठीक है, यह अनुकूल रूप से मेल खाता है), मैं 9 के लिए दिखाऊंगा।
ए = ९
1) एन = 2
2) बी = 9 - 3 ^{(2 - 1)} = 6
सी = 9 - 6 = 3
3) एलजी = 3, पीजी = 3, सी = 3
खैर, और 2 और वज़न (समूह को निर्धारित करने और सिक्के को निर्धारित करने के लिए)।

3. भारी या हल्के नकली सिक्के की परिभाषा

कार्य का तीसरा बिंदु बना रहा - कठिन नकली सिक्का या आसान निर्धारित करना।
एक अलग लेख इस निर्णय के लिए समर्पित होगा (ठीक है, मुझे लगता है कि होगा)।