उन संख्याओं का क्रम उत्पन्न करें जिनके k-वें अंक बाएँ से और दाएँ योग से सभी k . के लिए १० हो जाते हैं

Question

एक पायथन कोडिंग अभ्यास एक फ़ंक्शन f बनाने के लिए कहता है जैसे कि f (k) k-वें नंबर है, जैसे कि इसका k-वें अंक बाईं ओर से और दाईं ओर से सभी k के लिए १० है। उदाहरण के लिए 5, 19, 28, 37 अनुक्रम की पहली कुछ संख्याएँ हैं।

मैं इस फ़ंक्शन का उपयोग करता हूं जो स्पष्ट रूप से जांचता है कि संख्या 'एन' संपत्ति को संतुष्ट करती है या नहीं:

def check(n):

    #even digit length
    if len(str(n)) % 2 == 0:

        #looping over positions and checking if sum is 10
        for i in range(1,int(len(str(n))/2) + 1):

            if int(str(n)[i-1]) + int(str(n)[-i]) != 10:

                return False

    #odd digit length
    else:

        #checking middle digit first
        if int(str(n)[int(len(str(n))/2)])*2 != 10:

            return False

        else:
            #looping over posotions and checking if sum is 10
            for i in range(1,int(len(str(n))/2) + 1):

                if int(str(n)[i-1]) + int(str(n)[-i]) != 10:

                    return False

    return True

और फिर मैं अनुक्रम उत्पन्न करने के लिए सभी नंबरों पर लूप करता हूं:

for i in range(1, 10**9):

    if check(i):
        print(i)

हालांकि अभ्यास एक फ़ंक्शन f(i) चाहता है जो i-th ऐसी संख्या को 10 सेकंड से कम में लौटाता है। स्पष्ट रूप से, मेरा बहुत अधिक समय लेता है क्योंकि यह गणना करने के लिए संख्या 'i' से पहले पूरे अनुक्रम को उत्पन्न करता है। क्या ऐसा फ़ंक्शन बनाना संभव है जिसमें सभी पूर्व संख्याओं की गणना न हो?

python sequence digits

2

Mike 21 जुलाई 2019, 21:31

Answer 1

प्रत्येक प्राकृतिक संख्या का परीक्षण करना एक खराब तरीका है। प्राकृतिक संख्याओं के केवल एक छोटे से अंश में ही यह गुण होता है, और जैसे-जैसे हम बड़ी संख्या में आते हैं, अंश तेज़ी से घटता जाता है। मेरी मशीन पर, नीचे दिए गए साधारण पायथन प्रोग्राम को 1,000वां नंबर (2,195,198) खोजने में 3 सेकंड और 2,000वें नंबर (15,519,559) को खोजने में 26 सेकंड से अधिक का समय लगा।

# Slow algorithm, only shown for illustration purposes

# '1': '9', '2': '8', etc.
compl = {str(i): str(10-i) for i in range(1, 10)}

def is_good(n):
    # Does n have the property
    s = str(n)
    for i in range((len(s)+1)//2):
        if s[i] != compl.get(s[-i-1]):
            return False
    return True

# How many numbers to find before stopping
ct = 2 * 10**3

n = 5
while True:
    if is_good(n):
        ct -= 1
        if not ct:
            print(n)
            break
    n += 1

स्पष्ट रूप से, अधिक कुशल एल्गोरिदम की आवश्यकता है।

हम अंक स्ट्रिंग की लंबाई पर लूप कर सकते हैं, और उसके भीतर, संख्यात्मक क्रम में संपत्ति के साथ संख्याएं उत्पन्न कर सकते हैं। छद्म कोड में एल्गोरिथ्म का स्केच:

for length in [1 to open-ended]:
    if length is even, middle is '', else '5'
    half-len = floor(length / 2)
    for left in (all 1) to (all 9), half-len, without any 0 digits:
        right = 10's complement of left, reversed
        whole-number = left + middle + right

अब, ध्यान दें कि प्रत्येक लंबाई के लिए संख्याओं की गणना आसानी से की जाती है:

Length    First    Last     Count
1         5        5        1
2         19       91       9
3         159      951      9
4         1199     9911     81
5         11599    99511    81

सामान्य तौर पर, यदि बाएँ-आधे में n अंक हैं, तो गिनती 9**n होती है।

इस प्रकार, हम केवल अंकों की गणना के माध्यम से पुनरावृति कर सकते हैं, यह गिनते हुए कि कितने समाधान मौजूद हैं, उनकी गणना किए बिना, जब तक कि हम वांछित उत्तर वाले कोहोर्ट तक नहीं पहुंच जाते। तब यह गणना करना अपेक्षाकृत सरल होना चाहिए कि हम कौन सी संख्या चाहते हैं, फिर से, हर संभावना के माध्यम से पुनरावृति किए बिना।

उपरोक्त रेखाचित्र से कुछ विचार उत्पन्न होने चाहिए। मेरे द्वारा लिखे जाने के बाद अनुसरण करने के लिए कोड।

कोड:

def find_nth_number(n):
    # First, skip cohorts until we reach the one with the answer
    digits = 1
    while True:
        half_len = digits // 2
        cohort_size = 9 ** half_len
        if cohort_size >= n:
            break
        n -= cohort_size
        digits += 1

    # Next, find correct number within cohort

    # Convert n to base 9, reversed
    base9 = []
    # Adjust n so first number is zero
    n -= 1
    while n:
        n, r = divmod(n, 9)
        base9.append(r)
    # Add zeros to get correct length
    base9.extend([0] * (half_len - len(base9)))
    # Construct number
    left = [i+1 for i in base9[::-1]]
    mid = [5] * (digits % 2)
    right = [9-i for i in base9]
    return ''.join(str(n) for n in left + mid + right)

n = 2 * 10**3

print(find_nth_number(n))

2

Tom Zych 21 जुलाई 2019, 22:58

Answer 2

यह एक ऐसा फ़ंक्शन है जो उस पैटर्न का फायदा उठाता है जहां 10 की आसन्न शक्तियों के बीच "वैध" संख्याओं की संख्या 9 की शक्ति है। यह हमें बहुत से संख्याओं को छोड़ने की अनुमति देता है।

def get_starting_point(k):
    i = 0
    while True:
        power = (i + 1) // 2
        start = 10 ** i
        subtract = 9 ** power
        if k >= subtract:
            k -= subtract
        else:
            break
        i += 1
    return k, start

मैंने इसे आपके द्वारा परिभाषित विधि के साथ जोड़ा है। मान लीजिए कि हम ४५वें नंबर में रुचि रखते हैं, यह दिखाता है कि खोज १००० से शुरू होती है, और हमें केवल १००० के बाद होने वाली २६ वीं "वैध" संख्या को खोजना है। यह १०००० से कम होने की गारंटी है। बेशक, यह सीमा बदतर हो जाती है और इससे भी बदतर, और आप इस पद पर समुदाय के अन्य सदस्यों द्वारा सुझाई गई तकनीकों को नियोजित करना चाहेंगे।

k = 45
new_k, start = get_starting_point(k)
print('new_k: {}'.format(new_k))
print('start at: {}'.format(start))
ctr = 0
for i in range(start, 10**9):
    if check(i):
        ctr += 1
        if ctr == new_k:
            break
print(i)

आउटपुट:

new_k: 26
start at: 1000
3827

ऐसा लगता है कि 45वां नंबर 3827 है।

1

brentertainer 21 जुलाई 2019, 22:45

उन संख्याओं का क्रम उत्पन्न करें जिनके k-वें अंक बाएँ से और दाएँ योग से सभी k . के लिए १० हो जाते हैं

2 जवाब

संबंधित सवाल

नए सवाल

python