हेलो, हेब्र!

एक बार, कुख्यात डेटा विज्ञान पर एक और पुस्तक का अध्ययन करने के बाद, मैं इस निष्कर्ष पर पहुंचा कि संचित ज्ञान को व्यवहार में लाने और विश्लेषिकी विभाग के जीवन को अपनी आँखों से देखने का समय होगा। सौभाग्य से, यैंडेक्स ने उचित दिशा में छह महीने की इंटर्नशिप के लिए चयन शुरू किया, और मैं इसके माध्यम से पास नहीं हो सका। अनुप्रयोगों की स्वीकृति 2020 पहले ही समाप्त हो चुकी है, इसलिए इस लेख में, मैं स्पष्ट विवेक के साथ, उन कार्यों का विश्लेषण करूंगा जो यांडेक्स ने पहले चरण में आवेदकों के लिए हल करने का प्रस्ताव दिया था। इसमें पायथन कोड होगा। Spoiler: मुश्किल, लेकिन दिलचस्प।

कार्य 1. समय सीमा

काम

नौसिखिया विश्लेषक समस्या को हल करने की कोशिश कर रहा है। यदि समस्या हल नहीं हो सकी, तो वह प्रेरणा खो देता है, और अगले प्रयास में सफलता की संभावना गिर जाती है। एक प्रयास में एक दिन लगता है, और कार्य की समय सीमा 90 दिन है। यह संभावना है कि विश्लेषक i-th प्रयास से समस्या का समाधान करेगा:

$\frac{1}{(i+1)}$
$\frac{1}{(i+1)^2}$

समय सीमा से पहले विश्लेषक समस्या को हल करने की कितनी संभावना है?

फेसला

आप टाइपिंग के लिए पहले ही पहुँच गए होंगे: "@nice_one, आपने कहा कि यह मुश्किल होगा, लेकिन यह क्या है?" धैर्य, दोस्तों, यह वार्म अप करने के लिए एक सरल कार्य है, लेकिन अगर आप हालत के बारे में नहीं सोचते हैं तो कुछ याद करना है। आइए हम पहले पैराग्राफ के उदाहरण की जांच करें। कुल संभावना की गणना करना आवश्यक है कि विश्लेषक रिजर्व में उपलब्ध किसी भी 90 दिनों में समस्या का समाधान करेगा, जबकि प्रत्येक आई-वें दिन सफलता की संभावना दी गई है। एक आकर्षक विकल्प, i और add के बजाय 1 से 90 तक की संख्या में अभिव्यक्ति का विकल्प लग सकता है, लेकिन यह सच नहीं है। यह अभिव्यक्ति एक विशेष i-day पर सफलता की संभावना को इंगित करती है, लेकिन उस i-day को प्राप्त करने के लिए, विश्लेषक को पिछले (i - 1) दिनों में विफल होना चाहिए। यदि i-th दिन सफलता की संभावना है

\frac{1}{(i + 1)}

$\frac{1}{(i+1)}$ , तो इस दिन विफलता की संभावना इसलिए बराबर है

1 - \frac{1}{(i + 1)} = \frac{i}{i + 1}

$1 - \frac{1}{(i+1)} = \frac{i}{i+1}$ । जैसा कि आप जानते हैं, कई घटनाओं की एक साथ होने की संभावना को खोजने के लिए, प्रत्येक घटना की संभावना को गुणा करना आवश्यक है। इस प्रकार, संभावना है कि विश्लेषक वास्तव में n दिनों में सामना कर सकता है

(\prod_{k = 1}^{n - 1} \frac{k}{k + 1}) \cdot \frac{1}{n + 1}

$\biggl(\prod\limits_{k=1}^{n-1}\frac{k}{k+1}\biggr)\cdot\frac{1}{n+1}$ ।

कार्य के चिन्ह के नीचे खड़े सदस्य पहले प्रत्येक में विफलता के लिए जिम्मेदार हैं

(n - 1)

$(n - 1)$ दिन, फिर आपको एन-वें दिन सफलता की संभावना से उत्पाद को गुणा करना होगा।
इसलिए, किसी भी संख्या में, हम इस अवधि के लिए सफलता की संभावना जानते हैं। हम अधिकतम 90 दिनों तक की प्रत्येक संभावित अवधि के लिए सफलता की कुल संभावना में रुचि रखते हैं। अब आप संख्याओं को 1 से 90 तक प्रतिस्थापित कर सकते हैं, लेकिन पहले से ही परिणामी सूत्र में। सबसे आसान तरीका कुछ अजगर में एक लूप लिखना है जो संभावनाओं की गणना और जोड़ देगा, जो मैंने किया।

कोड

import numpy as np

n = 90

probs = []

for i in range(1, n+1): #   

    prob_now = 1/(i+1) #      

    prob_not_before = []
    
    for k in range(1, i): #      
        prob_not_before.append(k/(k+1))
        
    prob_not_before = np.array(prob_not_before).prod() # 

    probs.append(prob_not_before * prob_now)

s = sum(probs) #   

print(s)

दूसरे पैराग्राफ का निर्णय पूरी तरह से पहले के समान है, केवल सूत्र अलग है। मैं दूसरे बिंदु को हल करने वाला कोड छोड़ दूंगा - मुझे लगता है कि सबकुछ स्पष्ट हो जाएगा।

बिंदु 2

import numpy as np

n = 90

probs = []

for i in range(1, n+1): #   

    prob_now = 1/((i+1)**2) #      

    prob_not_before = []
    
    for k in range(1, i): #      
        prob_not_before.append(1 - (1/((k+1)**2)))
        
    prob_not_before = np.array(prob_not_before).prod() 

    probs.append(prob_not_before * prob_now)

s = sum(probs) #   

print(s)

टास्क 2. हम्सटर का भाग्य

काम

सर्दियों में जीवित रहने के लिए, लालची भूखे हम्सटर ने अपने छेद से 1000 मीटर दूर एक अखरोट के कारखाने को लूटने का फैसला किया। कारखाने में 3,000 नट बचे थे। हम्सटर के गाल पर अधिकतम 1000 नट रखे जाते हैं। हर जगह और कोई फर्क नहीं पड़ता कि हम्सटर किसके साथ जाता है, हर मीटर पर उसे 1 अखरोट के साथ प्रबलित करने की आवश्यकता होती है। हम्सटर पहले से ही कारखाने में है और खतरनाक है। वह कितने प्रकार के नट को स्टॉक कर सकता है? उत्तर को निकटतम पूर्णांक तक गोल किया जाना चाहिए।

फेसला

जीप के कार्य की दृढ़ता से याद दिलाता है, ऐसा नहीं है? तो यह है, हमारे सामने इसकी अगली किस्म है। सामान्य स्थिति में, एक वाहन (इस मामले में, एक हम्सटर) जीप समस्या में दिखाई देता है, जिसे ईंधन कंटेनर (हैम्स्टर गाल) की सीमित क्षमता की स्थितियों में एक निश्चित दूरी की यात्रा करने की आवश्यकता होती है। इस वर्ग की किसी भी समस्या के समाधान में निहित विचार - जिस तरह से, आप ईंधन की आपूर्ति छोड़ सकते हैं, साथ ही एक नए के लिए वापस आ सकते हैं। अन्यथा, एक एकल समाधान एल्गोरिथ्म मौजूद नहीं है, क्योंकि प्रारंभिक शर्तें और लक्ष्य बहुत अलग हो सकते हैं। यहां प्रस्तावित विकल्प दिलचस्प है क्योंकि यह न केवल कारखाने से छेद तक जाने के लिए आवश्यक है (जो प्राथमिक है, क्योंकि हैम्स्टर बिल्कुल 1000 नट पकड़ सकता है, जो 1000 मीटर के लिए पर्याप्त है), लेकिन इसके लिए जितना संभव हो उतना पागल हस्तांतरण करें। आरेख बनाना सबसे अच्छा है,कारखाने में 1000 मीटर की लंबाई और नट्स का एक स्टॉक दर्शाया गया है, और यह सोचें कि हम्सटर को कैसे काम करना है यदि वह छेद में 3000 नट्स को ट्रांसपोर्ट करना चाहता है, जितना संभव हो उतना कम खाना, यानी, कुल दूरी जितनी कम हो। आइए कई यात्राओं पर आपके साथ सभी 3000 नट्स को स्थानांतरित करते हुए, सबसे छोटे चरणों, 1 मीटर प्रत्येक पर जाने की कोशिश करें।

जाहिर है, किसी भी बिंदु पर 3000 नट्स को स्थानांतरित करने के लिए, हम्सटर को कम से कम 3 बार पिछले एक पर लौटना होगा। जब 2000 नट रहते हैं और बाकी रास्ते में खाए जाते हैं, तो हम्सटर को उन्हें एक नए स्थान पर ले जाने के लिए पिछले बिंदु पर 2 यात्राओं की आवश्यकता होगी। जब ईंधन 1000 इकाइयों से कम हो, तो आपको वापस नहीं जाना होगा, यह सब हम्सटर के गाल में फिट होता है। इस प्रकार, नट्स को स्थानांतरित करने की प्रक्रिया को तीन संगत चरणों में विभाजित किया जा सकता है। आइए देखें कि हम्सटर में प्रत्येक पर "ईंधन की खपत" क्या होगी। जब 2,000 से अधिक नट होते हैं, तो 1 मीटर चलने के लिए हम्सटर को निम्न करना होगा:

नट्स का पूरा गाल उठाएं और 1 मीटर चलें
998 नट्स उतारें (रास्ते में 1 खाया, 1 वापस जाने के लिए छोड़ दिया)
अखरोट स्टॉक पर फिर से 1 मीटर वापस जाएं
दूसरे हज़ार नटों के लिए चरण 1-3 दोहराएं
अंतिम हजार लें और इसके साथ 1 मीटर आगे जाएं

इस प्रकार, सभी शिकार के साथ 1 मीटर विस्थापन में एक हम्सटर 5 नट्स की लागत होती है। जब पागल <2000 हो जाते हैं, और यह 200 मीटर की गति के बाद होता है, तो एल्गोरिथ्म निम्नानुसार होगा:

नट्स का पूरा गाल उठाएं और 1 मीटर चलें
998 नट्स उतारें (रास्ते में 1 खाया, 1 वापस जाने के लिए छोड़ दिया)
अखरोट स्टॉक पर फिर से 1 मीटर वापस जाएं
अंतिम हजार लें और इसके साथ 1 मीटर आगे जाएं

1 मीटर विस्थापन में एक हम्सटर 3 नट का खर्च होता है। जब वह 534 मीटर तक पहुंच जाता है, तो कुल 2001 नट्स खाए जाएंगे, और हम्सटर को आखिरी 999 नट्स लेने होंगे और शांति से शेष 466 मीटर अपने छेद में जाना होगा। जब वह वहां पहुंच जाएगा, तो 533 नट गाल में रहेंगे - यह समस्या का जवाब होगा।

मैं यह नोट करना चाहता हूं कि एल्गोरिदम के सिद्धांत के साथ-साथ बड़ी कंपनियों में साक्षात्कार में इस वर्ग के कार्य काफी लोकप्रिय हैं। उन्हें हल करने का तरीका सीखने का सबसे अच्छा तरीका अभ्यास है। इसे हल करने के लिए एक भी तंत्र नहीं है (अच्छी तरह से, या उसने मुझे पिछले में घुमाया), लेकिन यह उन पर हाथ पाने और रचनात्मक सोच विकसित करने के लिए काफी संभव है।

कार्य 3. विश्लेषणात्मक वितरण

काम

यैंडेक्स बनाना चाहता है

M

$M$ विश्लेषकों की टीम। काम पर रखने पर, प्रत्येक विश्लेषक बेतरतीब ढंग से अपने लिए एक समूह चुनता है जहाँ वह काम करेगा। टीम लीडर यह पता लगाना चाहता है कि हज़ारों विश्लेषकों की न्यूनतम संख्या कितनी है ताकि वह अपने समूह की अधिक संभावना रख सके

P

$P$ कोई कम नहीं था

N

$N$ व्यक्ति?

आपको एक पायथन प्रोग्राम लिखना होगा जो स्वीकार करता है

N

$N$ ,

M

$M$ तथा

P

$P$ एक पंक्ति में, और आउटपुट हजारों विश्लेषकों की संख्या देता है।

1 \leq N \leq 100

$1 \leq N \leq 100$ ,

1 \leq M \leq 100000

$1 \leq M \leq 100000$ ,

0 \leq P \leq 1

$0 \leq P \leq 1$

फेसला

ठीक है, आंकड़ों का ज्ञान, अर्थात् द्विपद वितरण , काम आया । हम यांडेक्स द्वारा काम पर रखे गए विश्लेषकों की संख्या को निरूपित करते हैं

X

$X$ । काम पर रखा विश्लेषकों में से प्रत्येक एक टीम चुनता है। हमारी टीम के नेता के दृष्टिकोण से, काम के लिए एक विश्लेषक को काम पर रखना दो परिणामों के साथ एक प्रयोग है: या तो एक नवागंतुक हमारी टीम में आता है या नहीं। हिट संभावना बराबर होती है

\frac{1}{M}

$\frac{1}{M}$ विश्लेषक की संभावना क्रमशः दूसरे समूह को चुनने की है

\frac{M - 1}{M}

$\frac{M-1}{M}$ । कुल मिलाकर, टीम की पसंद के साथ ऐसे प्रयोग होंगे

X

$X$ । हमारी टीम में हिट की संख्या

n

$n$ का

X

$X$ विश्लेषकों का चुनाव द्विपदीय रूप से वितरित किया जाता है , वितरण समारोह निम्न के बराबर होता है:

P (n ⩽ N) = \sum_{k = 0}^{N} (\binom{X}{k}) (\frac{1}{M})^{k} (\frac{M - 1}{M})^{X - k}

$\mathbb{P}(n \leqslant N) = \sum\limits_{k=0}^{ N} \binom{X}{k}\, \biggl(\frac{1}{M}\biggr)^k \biggl(\frac{M-1}{M}\biggr)^{X-k}$

यह फ़ंक्शन इस संभावना को दर्शाता है कि हिट की संख्या निर्दिष्ट से कम या बराबर होगी

N

$N$ । हम इस संभावना में रुचि रखते हैं कि हिट की संख्या दी गई एक से अधिक या उसके बराबर होगी, इसलिए कार्य इस तरह दिखता है:

X : 1 - P_{x} (n ⩽ N) = P; X - ?

$X: 1 - \mathbb{P_x}(n \leqslant N) = P; X-?$

यही है, आपको काम पर रखे गए विश्लेषकों की संख्या खोजने की आवश्यकता है

X

$X$ जिस पर टीम कम से कम हो जाती है

N

$N$ किसी दिए गए प्रायिकता के लिए व्यक्ति

P

$P$ ।

खैर, हमने गणित निकाला - अब इसे कैसे खोजना है

X

$X$ ? पर्दाफाश। आप एक चक्र लिख सकते हैं जो काम पर रखे गए विश्लेषकों की संख्या के माध्यम से क्रमबद्ध होगा, इसे बढ़ाकर कम से कम प्राप्त करने की संभावना तक

N

$N$ विश्लेषक संतोषजनक नहीं होंगे।

कोड

def c(n, k): #   ,    
    if 0 <= k <= n:
        nn = 1
        kk = 1
        for t in range(1, min(k, n - k) + 1):
            nn *= n
            kk *= t
            n -= 1
        return nn // kk
    else:
        return 0

def bin_prob(trials, k, m): #      

    return c(trials, k) * ((1/m)**k) * ((1 - 1/m)**(trials - k))

def cdf(maximum, trials, m): #   
    value = 0
    for i in range(maximum + 1):
        value += bin_prob(trials, i, m)
    return value

n, m, p = [(float(i)) for i in input().split()] #       
n = int(n)
m = int(m)


x = 1000 
while (1 - cdf(n, x, m)) < p: #      
    x += 1000 #   

print(int(x / 1000)) #

कार्य 4. उपहार अनुसंधान

काम

सांता क्लॉज़ ने अनास्तासिया को 100 उपहार लाए और उन्हें क्रिसमस ट्री के नीचे रखा। पेड़ बड़ा और शराबी है, इसलिए अनास्तासिया को इसके नीचे नेविगेट करना मुश्किल है। अनास्तासिया इस तरह से उपहारों की जांच करती है: गलती से पेड़ के यादृच्छिक पक्ष से यादृच्छिक सीमा तक पहुंच जाती है, उपहार लेती है, उसकी जांच करती है और उसे वापस रखती है। यह पता चलता है कि हर बार अनस्तासिया पेड़ के नीचे झूठ बोलने वालों से कोई उपहार ले सकती है। उपहारों की हिस्सेदारी की उम्मीद खोजें जो अनस्तासिया 100 यादृच्छिक स्ट्रेच के लिए विचार करेगी?

फेसला

पहली नज़र में, कार्य बहुत सरल लगता है, यहां तक कि आत्मविश्वास भी प्रकट होता है कि कुछ प्राथमिक सूत्र द्वारा एक समाधान पाया जा सकता है, लेकिन सब कुछ इतना सरल नहीं है। इतना आसान नहीं। मैंने इस कार्य पर बहुत समय बिताया है, विकल्पों को चित्रित करने और एक सूत्र प्राप्त करने की कोशिश कर रहा हूं, लेकिन मैं सफल नहीं हुआ। फिर मैं Google पर गया और अपने आश्चर्य के लिए, मुझे मंचों में गहरी खुदाई करनी पड़ी, इससे पहले कि मैं सामान्य मामले का हल ढूंढता । इसलिए, अगर हम एक सेट से बेतरतीब ढंग से रिटर्न के साथ तत्वों का चयन करते हैं, तो संभावना है

n

$n$ से चयन

m

$m$ सेट के तत्व बिल्कुल बाहर खींचते हैं

k

$k$ अलग बराबर:

P (m, k, n) = \frac{(\binom{m}{k}) \cdot k! \cdot S_{2} (n, k)}{m^{n}}

$P(m, k, n) = \frac{\binom{m}{k}\cdot k! \cdot S_2(n, k)}{m^n}$

कहाँ पे

S_{2}

$S_2$ वहाँ दूसरी तरह के एक स्टर्लिंग संख्या से सेट की अव्यवस्थित विभाजन की संख्या -

n

$n$ पर आइटम

k

$k$ nonempty सबसेट। खैर, अपेक्षा को खोजने के लिए, इस उपहार द्वारा गणना की गई संभावनाओं को अद्वितीय उपहारों के प्रत्येक संभावित अंश के लिए जोड़ना आवश्यक है - एक सौवें से एक पूरे तक। यह पायथन में एक लूप का उपयोग करके किया जा सकता है।

कोड

import math
import numpy as np
import sys
import sympy #     -   

sys.setrecursionlimit(10**9)

def c(n, k): # C

    return (math.factorial(n))/(math.factorial(k) * math.factorial(n-k))

def s(n, k): #      

    return sympy.functions.combinatorial.numbers.stirling(n, k)

    
def p(m, k, n): #    k

    return c(m, k) * math.factorial(k) * s(n, k) / (m**n)


pr = []
#      ,    ...
for j in range(1, 101): 
    pr.append(p(100, j, 100))
    
pr = np.array(pr)
#...    100
frac = np.array([i for i in range(1, 101)]) / 100


print(sum(pr*frac)) #

कार्य 5. सुगम यात्री

काम

यात्री दो-आयामी ग्रिड के किनारों के साथ पूरी तरह से सही या ऊपर की ओर बढ़ना शुरू कर देता है। वह एक बिंदु से आगे बढ़ता है

(0, 0)

$(0, 0)$ बिल्कुल सही

(100, 100)

$(100, 100)$ । शुरू और अंत बिंदुओं को जोड़ने वाली एक सीधी रेखा में एक नदी को पार करने की कितनी संभावना है, अगर हम मानते हैं कि सभी संभावित मार्ग समान रूप से संभावित हैं? यह माना जाता है कि यात्री नदी को पार करता है यदि वह नदी के ऊपर और नीचे उसी मार्ग में था। एक नदी के प्रवेश को एक चौराहा नहीं माना जाता है।

फेसला

हम शास्त्रीय दृष्टिकोण को पार करने की संभावना पाते हैं - हम संभावित मार्गों की कुल संख्या से चौराहे के साथ मार्गों की संख्या को विभाजित करते हैं। रहने दो

n

$n$ - वर्ग ग्रिड के किनारों की लंबाई। फिर संभावित मार्गों की कुल संख्या:

N = \frac{(2 n!)}{(n!)^{2}}

$N = \frac{(2n!)}{(n!)^2}$

सूत्र की व्युत्पत्ति यहाँ वर्णित है । लेकिन प्रत्येक के लिए नदी पार मार्गों की संख्या का पता कैसे लगाया जाए

n

$n$ ? इस प्रश्न से हैरान होने के बाद, मैंने कुछ छोटे ग्रिड की लंबाई लेने, खेतों को खींचने और मैन्युअल रूप से गणना करने का निर्णय लिया कि कितने मार्ग नदी को पार करते हैं, आश्रितता का पता लगाने की उम्मीद करते हैं (मैं अत्यधिक अनुशंसा करता हूं कि आप भी अब कागज और एक कलम ले लें और छोटे ग्रिड और रास्तों का उपयोग करें)।

आज्ञा देना ग्रिड का आकार 3 से 3 कोशिकाएं होती हैं। ग्रिड के साइड विकर्ण पर नदी का कब्जा है, यात्री निचले बाएं कोने में है।

चित्र

ड्राइंग सही नहीं है, लेकिन मैंने कोशिश की, ईमानदारी से

जैसे ही मैंने ड्राइंग बनाई, मुझे एहसास हुआ कि उन मार्गों को ट्रैक करना बहुत आसान होगा जो नदी पार नहीं करते हैं, अर्थात् नदी के नीचे के मार्ग। फिर उनकी संख्या को 2 से गुणा करना संभव होगा, इस प्रकार नदी के ऊपर दर्पण पथों को ध्यान में रखा जाएगा। चूंकि हम मार्गों की कुल संख्या भी जानते हैं, इसलिए हम नदी पार करने वाले लोगों की संख्या पाते हैं। लेकिन मुख्य कार्य पर वापस - हमें एक रिश्ते की आवश्यकता है

n

$n$ और नदी पार पथों की संख्या।

3x3 के मामले के लिए ऊपर दिए गए आंकड़े में, मैंने नीले रंग में कुछ "भूमि" मार्गों को यात्री के लिए सुलभ चिह्नित किया है: चिह्नित मार्ग 2 के क्षैतिज समन्वय के साथ कोशिकाओं के किनारों से गुजरते हैं, यात्री पहले कोशिकाओं के बाएं और ऊपरी किनारों में प्रवेश नहीं करता है। 3 ऐसे मार्ग हैं, अर्थात्

n

$n$ । अब कॉलम 1 में सेल से गुजरने वाले मार्गों का पता करते हैं।

चित्र

मैंने नए रास्तों को लाल रंग में चिह्नित किया। तो, यह स्पष्ट है कि यदि कोई यात्री बाईं ओर मुड़ता है और फिर सेल के ऊपरी किनारे (1, 0), तो कोशिकाओं के माध्यम से तीन रास्तों में से केवल 2 का क्षैतिज समन्वय उसके लिए सुलभ होगा, क्योंकि आप केवल ऊपर और दाईं ओर जा सकते हैं - तीसरा मार्ग नीचे है। । इस प्रकार, कॉलम 1 से मार्ग में एक नया सेल जोड़ते हुए, हमने कॉलम 2 की कोशिकाओं से गुजरने वाले मार्गों की संख्या से पथों की कुल संख्या में वृद्धि की, जो हमारे नए सेल से कम नहीं हैं।

4 बाय 4 ग्रिड लें और उलझन को उजागर करना जारी रखें। यह स्पष्ट हो गया कि एक नए सेल को एक कॉलम में जोड़ने से मार्गों की संख्या बढ़ जाती है जो अगले कॉलम से गुजरता है, अतिरिक्त सेल के शीर्ष किनारे से कम नहीं। मैं रंगों के साथ मार्गों को चिह्नित नहीं करूंगा, मैं खुद को एक पाठ्य विवरण तक सीमित कर दूंगा, लेकिन यदि आप इसे आवश्यक मानते हैं, तो हल करें - हल करने की प्रक्रिया में मैंने एक दर्जन अलग-अलग ग्रिडों को आकर्षित किया इससे पहले कि मैं आत्मविश्वास से निर्भरता का प्रबंधन करूं।

चित्र

सबसे दाहिना स्तंभ फिर से हमें देता है

n

$n$ मार्गों। सेल का ऊपरी किनारा (2, 0) हमें जोड़ देगा

n - 1

$n-1$ मार्ग। सेल के शीर्ष किनारे (2, 1) जोड़ देगा

n - 2

$n-2$ मार्ग। सेल के शीर्ष किनारे (1, 0) के रूप में कई मार्गों को जोड़ने के रूप में कोशिकाओं (2, 0) और (2, 1) एक साथ जोड़ा जाएगा। यदि आप चाहें, तो आप एक बड़ा ग्रिड बना सकते हैं और उसी एल्गोरिथ्म के साथ मार्गों पर विचार करना जारी रख सकते हैं। हमारा काम 100x100 ग्रिड के लिए मार्गों की गणना करना है। ऐसा करने के लिए, आप एक प्रोग्राम लिख सकते हैं जो इनपुट को स्वीकार करेगा

n

$n$ और एक मैट्रिक्स का निर्माण

n \times n

$n\times n$ कॉलम से शुरू

n

$n$ और फिर पिछले कॉलम के प्रत्येक सेल के लिए, पिछले कॉलम के डेटा के आधार पर सेल द्वारा जोड़े गए रास्तों की संख्या की गणना करता है। इस प्रकार, गैर-नदी पार करने वाले रास्तों की संख्या मिल जाएगी।

कोड

import numpy as np
import math

def routes_total(n): #   
    return math.factorial(2*n) / (math.factorial(n)**2)

def fill_matrix(n): #  ,       
    net = np.zeros((n, n)) 
    net[0, 0] = n #    n 
    for i in range(n-2):
        net[1, i] = n - i - 1 

    for i in range(2, n):
        for j in range(n - i - 1): 
            net[i, j] = 0
            for g in range(j, n - i + 1):
                net[i, j] += net[i - 1, g]
    
    #      2,     
    return (2 * sum(sum(net))) 

#      -    1
print(1  - fill_matrix(100) / routes_total(100))

कार्य 6. रैखिक वितरण की स्थिति

काम

रैखिक वितरण राज्य शहरों की एक भीड़ है, जिनमें से कुछ सड़कों द्वारा जुड़े हुए हैं।

एक बार राज्य के राजा को यह ज्ञात हो गया कि ब्रेकपॉइंट के लोग अपनी सीमाओं पर आक्रमण करने वाले थे। चूंकि राज्य रक्षा के लिए तैयार नहीं था, इसलिए राजा ने एक कठिन निर्णय लिया - राज्य को कई छोटे लोगों में विभाजित करने के लिए, जिनमें से प्रत्येक स्वतंत्र रूप से अपनी सीमाओं की रक्षा करेगा।

यह तय किया गया था कि दो शहरों को एक राज्य में छोड़ा जा सकता है और अगर एक शहर दूसरे में पहुंचा जा सकता है, भले ही ब्रेकप्वाइंट के लोग रैखिक वितरण राज्य के किसी भी दो शहरों के बीच एक सड़क को जब्त कर लें। अन्य सभी मामलों में, शहरों को अलग-अलग राज्यों में होना चाहिए।

प्रत्येक सड़क पर जो किसी भी दो नए राज्यों की सीमा को पार करेगी, एक गढ़ लगाना आवश्यक है। यह आवश्यक है कि इनमें से एक राज्य को पीपुल्स ऑफ ब्रेकप्वाइंट द्वारा कब्जा कर लिया गया है। तब दूसरा अपनी सीमाओं की रक्षा करना जारी रख सकेगा। दूसरे शब्दों में, गढ़ को विभिन्न राज्यों से शहरों को जोड़ने वाली सड़क पर रखा जाएगा।

राजा ने आपको उन सड़कों की एक सूची देने के लिए कहा, जिन पर आपको गढ़ लगाने की आवश्यकता है।

कार्यक्रम इनपुट और आउटपुट स्वरूप

इनपुट प्रारूप

n

$n$

m

$m$ — .

(1 \leq n \leq 20000, 1 \leq m \leq 200000)

$(1 \leq n \leq 20000, 1 \leq m \leq 200000)$ . m . i

b_{i}, e_{i}

$b_i, e_i$ — ,

(1 \leq b_{i}, e_{i} \leq n)

$(1 \leq b_i, e_i \leq n)$

b — , . b — , , . , .

, , , , — .

फेसला

और यहाँ ग्राफ सिद्धांत पर समस्या है। रैखिक वितरण के राज्य के भाग्य के बारे में लंबी कहानियों के लिए, ड्राफ्टर्स ने एक ग्राफ में पुलों को खोजने के बजाय दिलचस्प काम को छुपाया जिनके नोड्स शहर हैं और किनारों की सड़कें हैं। संक्षेप में, एक पुल एक ग्राफ का ऐसा किनारा है, जिसे हटाने से इस ग्राफ का एक निश्चित हिस्सा अन्य कोने से कट जाएगा। यह सड़क पर कब्जा करने का विचार है - यदि पुल पर कब्जा कर लिया जाता है, तो कुछ शहरों के बीच संचार टूट जाएगा, अन्यथा शहरों के बीच हमेशा एक वैकल्पिक सड़क होगी, इसलिए यह पुल है जो राज्यों को विभाजित करते हैं, पुलों पर गढ़ डालना आवश्यक है।

ब्रिज खोज एल्गोरिथ्म गहराई खोज के आधार पर(गहराई-पहली खोज, डीएफएस) - एक ग्राफ ट्रैवर्सल विधि जिसमें प्रारंभिक शीर्ष से आने वाले सभी किनारों की जांच की जाती है, और यदि किनारे एक शीर्ष पर जाता है जिसे अभी तक नहीं माना गया है, तो एल्गोरिथ्म तुरंत अपने शीर्ष से पुनरावृत्ति शुरू करता है। निम्नलिखित तथ्य पुलों की खोज में मदद करेंगे:

मान लीजिए कि हम गहराई में देख रहे हैं, अब शीर्ष से सभी किनारों को देख रहे हैं। तब यदि वर्तमान किनारे (V, U) ऐसा है, जो कि शीर्ष से U और उसके किसी भी वंश से पेड़ के नीचे के पेड़ पर है, तो कोई उलटा नहीं है। वी या उसके पूर्वजों के शिखर के लिए रास्ता, माना जाता है कि एक पुल है।

इस तथ्य को वर्टेक्स V के लिए कैसे सत्यापित किया जाए, यह जानने के लिए, हम शीर्ष डिस्क में प्रवेश के समय का परिचय देते हैं [V](अंग्रेजी से) की खोज की। इस चर में, एल्गोरिथ्म का चरण जिस पर शीर्ष को संसाधित किया गया है, रिकॉर्ड किया जाएगा। इसके अलावा, प्रत्येक शीर्ष V के साथ, सबसे कम [V] वैरिएबल जुड़ा होगा , जिसमें हम सबसे शुरुआती यू के प्रवेश का समय लिखते हैं, जिसे वर्टेक्स V से पहुँचा जा सकता है। वर्टेक्स के प्रारंभिक प्रसंस्करण के दौरान सबसे कम [V] = डिस्क (V) (पहले की तुलना में शीर्ष पर) आप अपने आप को नहीं पाते हैं), लेकिन बाद में गहराई से खोज करने की प्रक्रिया में हम कुछ बेटे वी को ढूंढ सकते हैं, जिनके किनारों में से एक वी के पूर्वज की ओर जाता है (चलो उसे एस कहते हैं)। इस स्थिति में, हम सबसे कम [V]: निम्नतम [V] = डिस्क [S] को अपडेट करेंगे।। और हम पुल को हुक कब कर सकते हैं? फिर, जब हम गहराई से खोज करते हैं, तो हम शीर्ष पर पहुंच जाते हैं, जिसका कोई पुत्र नहीं है जिसे अभी तक नहीं माना गया है (फिर, हम इसे यू कहते हैं)। इस स्थिति में, हम यह जाँच करेंगे कि कौन सा सबसे पहला शीर्ष U से पहुँचा जा सकता है, और यदि यह सबसे पुराना शीर्ष U के तत्काल माता-पिता की तुलना में बाद में होता है (यह संभव है, उदाहरण के लिए, जब U का कोई पुत्र नहीं है, तो निम्नतम [U] = डिस्क [U] ] ), तो माता-पिता के साथ यू का संबंध एक पुल है।

टिप्पणियों के साथ कार्यान्वित एल्गोरिथ्म का कोड नीचे संलग्न है। प्रत्येक वर्टेक्स के डिस्क और निम्नतम के लिए अलग-अलग वैरिएबल न बनाना सुविधाजनक है , लेकिन प्रत्येक वैल्यू के लिए एरेज़ को रखना है, जहां इंडेक्स उस शीर्ष की संख्या है जिसके लिए मान है।

कोड

import sys
from collections import Counter
import numpy as np
sys.setrecursionlimit(10**6) 

n, m = [int(i) for i in input().split()]
roads = [None] #    -    
graph = {}  #      ,    
for i in range(1, n+1):
    graph[i] = []
for i in range(1, m+1):
    twns = [int(j) for j in input().split()]
    graph[twns[0]].append(twns[1])
    graph[twns[1]].append(twns[0])
    roads.append(frozenset([j for j in twns]))
    
disc = [0] * (n+1) #  discovered
lowest = disc.copy() #  lowest
used = disc.copy() #  used. ,    
c = Counter(roads)

timer = 0 #   
nbridges = 0 #  
bridges = [] #  

def dfs(v, parent): #    ,    
    
    global timer
    global nbridges
    global bridges
    
    timer += 1 #   
    disc[v] = timer 
    lowest[v] = timer
    used[v] = True #     
    for u in graph[v]: #      
        if u == parent:
            continue #      ,    ,    
        if used[u]: #  ,    ,  
            lowest[v] = min(lowest[v], disc[u]) # ,       ;  lowest 
        else: #   
            dfs(u, v) #      
            #           cc  U:
            lowest[v] = min(lowest[v], lowest[u])  
            if lowest[u] > disc[v]: #   u    v   ,   
                twns = [] # ,  
                twns.append(u)
                twns.append(v)
                if c[frozenset(twns)] > 1: #     ,  ,    
                    continue
                nbridges += 1
                bridges.append(roads.index(set(twns)))

dfs(1, 0) #      

print(nbridges)
bridges = np.sort(bridges)
for bridge in bridges:
    print(bridge)

निम्नलिखित स्रोत ने मुझे कई तरीकों से समस्या से निपटने में मदद की , इसलिए मैं इसके लिए एक लिंक छोड़ना आवश्यक समझता हूं। यह देखने लायक है और यहाँ यह वीडियो है - एल्गोरिथ्म का एक अच्छा एनीमेशन है।

निष्कर्ष

ये ऐसे कार्य हैं जो यैंडेक्स में इंटर्नशिप के लिए आवेदन करने वाले विशेषज्ञ को आत्मविश्वास से हल करना चाहिए। कार्यों के उपरोक्त सेट को 5 घंटे दिए गए थे - काफी कम समय, मेरी राय में, लेकिन हर कोई अपनी गति से काम करता है।

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

मैं हर किसी के लिए खुद के लिए एक स्थिति खोजने की कामना करता हूं!

यैंडेक्स में विश्लेषक इंटर्नशिप: परीक्षण कार्यों का विश्लेषण

कार्य 1. समय सीमा

काम

फेसला

टास्क 2. हम्सटर का भाग्य

काम

फेसला

कार्य 3. विश्लेषणात्मक वितरण

काम

फेसला

कार्य 4. उपहार अनुसंधान

काम

फेसला

कार्य 5. सुगम यात्री

काम

फेसला

कार्य 6. रैखिक वितरण की स्थिति

काम

इनपुट प्रारूप

फेसला

निष्कर्ष

More articles: