algorithm - हरण - पूर्णांक की एक सीमा में प्रत्येक अंक की गणना कैसे करें?




सबसे बड़ी ऋणात्मक पूर्णांक संख्या (8)

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

  • 1 से 100 रु
  • 51 से 300 रु
  • बाईं ओर शून्य के साथ 1 से 2,000

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

मुझे आश्चर्य है कि अगर पूरे पूर्णांक सीमा के माध्यम से लूप के बिना, इसे हल करने का एक बेहतर तरीका है।

किसी भी भाषा या छद्म भाषा में समाधान का स्वागत है।

संपादित करें:

उत्तर की समीक्षा
जॉन एट कैशकॉम्स एंड वेन कॉनराड टिप्पणी करते हैं कि मेरा वर्तमान दृष्टिकोण काफी अच्छा और तेज है। मुझे एक मूर्खतापूर्ण सादृश्य का उपयोग करने दें: यदि आपको शतरंज बोर्ड में चौकों को 1 मिनट से कम समय में गिनने का काम दिया गया है, तो आप एक-एक करके वर्गों की गिनती करके कार्य को पूरा कर सकते हैं, लेकिन एक बेहतर उपाय यह है कि पक्षों की गिनती करें और एक गुणन करें, क्योंकि आपको बाद में एक इमारत में टाइलें गिनने के लिए कहा जा सकता है।
एलेक्स रीजनर एक बहुत ही दिलचस्प गणितीय कानून की ओर इशारा करता है, दुर्भाग्य से, इस समस्या के लिए प्रासंगिक नहीं लगता है।
एंड्रेस वही एल्गोरिदम सुझाता है जिसका मैं उपयोग कर रहा हूं, लेकिन सब्सट्रिंग के बजाय% 10 संचालन के साथ अंक निकालना।
CashCommons और phord में जॉन आवश्यक अंकों की पूर्व-गणना और उन्हें लुकअप तालिका में संग्रहीत करने का प्रस्ताव देते हैं या, कच्ची गति, एक सरणी के लिए। यह एक अच्छा समाधान हो सकता है अगर हमारे पास एक पूर्ण, अचूक, पत्थर में सेट, अधिकतम पूर्णांक मूल्य है। मैंने उनमें से एक को कभी नहीं देखा।
उच्च-प्रदर्शन मार्क और स्ट्रेनर ने विभिन्न श्रेणियों के लिए आवश्यक अंकों की गणना की। एक मिलन के लिए परिणाम इंगित करता है कि एक अनुपात है, लेकिन अन्य संख्या के परिणाम भिन्न अनुपात दिखाते हैं।
छलनी में कुछ सूत्र पाए गए जिनका उपयोग अंकों की गणना के लिए किया जा सकता है जो कि दस की शक्ति हैं। रॉबर्ट हार्वे को MathOverflow में प्रश्न पोस्ट करने का एक बहुत ही दिलचस्प अनुभव था। गणित के लोगों में से एक ने गणितीय संकेतन का उपयोग करके एक समाधान लिखा।
गणित के उपयोग से समाधान का अध्ययन और विश्लेषण एरोनियट ने किया। इसे पोस्ट करने के बाद उन्होंने मैथ ओवरफ़्लो से उत्पन्न फ़ार्मुलों की समीक्षा की और उसमें एक दोष पाया (स्टैकओवरफ़्लो को इंगित करते हुए :)।
noahlavine ने एक एल्गोरिथ्म विकसित किया और इसे स्यूडोकोड में प्रस्तुत किया।

एक नया उपाय
सभी उत्तरों को पढ़ने के बाद, और कुछ प्रयोग करने के बाद, मैंने पाया कि 1 से 10 n -1 तक पूर्णांक की सीमा के लिए:

  • अंक 1 से 9 के लिए, n * 10 (n-1) टुकड़ों की आवश्यकता होती है
  • अंक 0 के लिए, यदि अग्रणी शून्य का उपयोग नहीं कर रहे हैं, तो n * 10 n-1 - ((10 n -1) / 9) की आवश्यकता है
  • अंक 0 के लिए, यदि अग्रणी शून्य का उपयोग कर रहे हैं, n * 10 n-1 - n की आवश्यकता है

पहला सूत्र छलनी (और शायद दूसरों द्वारा) पाया गया था, और मुझे परीक्षण और त्रुटि के द्वारा अन्य दो मिले (लेकिन वे अन्य उत्तरों में शामिल हो सकते हैं)।

उदाहरण के लिए, यदि n = 6, रेंज 1 से 999,999 है:

  • 1 से 9 अंकों के लिए हमें प्रत्येक की 6 * 10 5 = 600,000 की आवश्यकता है
  • अंक 0 के लिए, अग्रणी शून्य के बिना, हमें 6 * 10 5 - (10 6 -1) / 9 = 600,000 - 111,111 = 488,889 की आवश्यकता है
  • अंक 0 के लिए, अग्रणी शून्य के साथ, हमें 6 * 10 5 - 6 = 599,994 चाहिए

इन नंबरों को उच्च-प्रदर्शन मार्क परिणामों का उपयोग करके जांचा जा सकता है।

इन सूत्रों का उपयोग करते हुए, मैंने मूल एल्गोरिथ्म में सुधार किया। यह अभी भी पूर्णांक की सीमा में पहली से अंतिम संख्या तक लूप करता है, लेकिन, अगर यह एक संख्या पाता है जो दस की शक्ति है, तो यह 1 से 9 की पूरी श्रृंखला के लिए अंकों की गणना के लिए सूत्रों को जोड़ने के लिए सूत्र का उपयोग करता है या 1 से 99 या 1 से 999 इत्यादि। यहाँ पेस्डोडकोड में एल्गोरिथ्म है:

integer First,Last //First and last number in the range
integer Number     //Current number in the loop
integer Power      //Power is the n in 10^n in the formulas
integer Nines      //Nines is the resut of 10^n - 1, 10^5 - 1 = 99999
integer Prefix     //First digits in a number. For 14,200, prefix is 142
array 0..9  Digits //Will hold the count for all the digits

FOR Number = First TO Last
  CALL TallyDigitsForOneNumber WITH Number,1  //Tally the count of each digit 
                                              //in the number, increment by 1
  //Start of optimization. Comments are for Number = 1,000 and Last = 8,000.
  Power = Zeros at the end of number //For 1,000, Power = 3
  IF Power > 0                       //The number ends in 0 00 000 etc 
    Nines = 10^Power-1                 //Nines = 10^3 - 1 = 1000 - 1 = 999
    IF Number+Nines <= Last            //If 1,000+999 < 8,000, add a full set
      Digits[0-9] += Power*10^(Power-1)  //Add 3*10^(3-1) = 300 to digits 0 to 9
      Digits[0]   -= -Power              //Adjust digit 0 (leading zeros formula)
      Prefix = First digits of Number    //For 1000, prefix is 1
      CALL TallyDigitsForOneNumber WITH Prefix,Nines //Tally the count of each 
                                                     //digit in prefix,
                                                     //increment by 999
      Number += Nines                    //Increment the loop counter 999 cycles
    ENDIF
  ENDIF 
  //End of optimization
ENDFOR  

SUBROUTINE TallyDigitsForOneNumber PARAMS Number,Count
  REPEAT
    Digits [ Number % 10 ] += Count
    Number = Number / 10
  UNTIL Number = 0

उदाहरण के लिए, श्रेणी 786 से 3,021 के लिए, काउंटर को बढ़ाया जाएगा:

  • 1 से 786 से 790 (5 चक्र)
  • ९ from ९ से 7 ९९ तक (१ चक्र)
  • 799 से 800 तक 1
  • 99 से 800 से 899 तक
  • 1 से 899 से 900 तक
  • ९९ से ९ ०० से ९९९ तक
  • 1 से 999 से 1000 तक
  • 1000 से 1999 तक 999 रु
  • 1999 से 2000 तक 1
  • 999 से 2000 से 2999 तक
  • 1 से 2999 से 3000 तक
  • 1 से 3000 से 3010 (10 चक्र)
  • 9 से 3010 से 3019 (1 चक्र) तक
  • 3019 से 3021 तक 1 (2 चक्र)

कुल: अनुकूलन के बिना 28 चक्र: 2,235 चक्र

ध्यान दें कि यह एल्गोरिथ्म अग्रणी शून्य के बिना समस्या को हल करता है। अग्रणी शून्य के साथ इसका उपयोग करने के लिए, मैंने एक हैक का उपयोग किया:

यदि अग्रणी शून्य के साथ 700 से 1,000 की सीमा की आवश्यकता है, तो 10,700 से 11,000 के लिए एल्गोरिथ्म का उपयोग करें और फिर अंक 1 की गिनती से 1,000 - 700 = 300 को प्रतिस्थापित करें।

बेंचमार्क और सोर्स कोड

मैंने इन परिणामों के साथ मूल दृष्टिकोण,% 10 का उपयोग करते हुए और कुछ बड़ी श्रेणियों के लिए नए समाधान का परीक्षण किया:

Original             104.78 seconds
With %10              83.66
With Powers of Ten     0.07

बेंचमार्क एप्लिकेशन का स्क्रीनशॉट:
alt text http://clarion.sca.mx/images/stories/digitsbench.png

यदि आप पूर्ण स्रोत कोड देखना चाहते हैं या बेंचमार्क चलाना चाहते हैं, तो इन लिंक का उपयोग करें:

स्वीकृत उत्तर

Noahlavine समाधान सही हो सकता है, लेकिन l बस छद्म कोड का पालन नहीं कर सकता, मुझे लगता है कि कुछ विवरण गायब हैं या पूरी तरह से समझाया नहीं गया है।

Aaronaught समाधान सही प्रतीत होता है, लेकिन कोड मेरे स्वाद के लिए बहुत जटिल है।

मैंने तनावपूर्ण उत्तर को स्वीकार कर लिया, क्योंकि उनके विचार की लाइन ने मुझे इस नए समाधान को विकसित करने के लिए प्रेरित किया।


आप प्रत्येक अंक को अलग कर सकते हैं ( उदाहरण के लिए यहां देखें ), 0..9 से प्रविष्टियों के साथ एक हिस्टोग्राम बनाएं (जो गिनेंगे कि कितने अंक एक संख्या में दिखाई दिए) और 'संख्या' की संख्या से गुणा करें।

लेकिन अगर आपको वह नहीं मिल रहा है, तो क्या आप एक बेहतर उदाहरण दे सकते हैं?

संपादित:

अब मुझे लगता है कि मुझे समस्या है। मुझे लगता है कि आप इस पर भरोसा कर सकते हैं (छद्म सी):

int histogram[10];
memset(histogram, 0, sizeof(histogram));

for(i = startNumber; i <= endNumber; ++i)
{
    array = separateDigits(i);
    for(j = 0; k < array.length; ++j)
    {
        histogram[k]++;
    }
}

अलग-अलग अंक लिंक में फ़ंक्शन को लागू करते हैं।

हिस्टोग्राम की प्रत्येक स्थिति में प्रत्येक अंक की मात्रा होगी। उदाहरण के लिए

histogram[0] == total of zeros
histogram[1] == total of ones

...

सादर


आपका दृष्टिकोण ठीक है। मुझे यकीन नहीं है कि आपने जो कुछ भी वर्णित किया है उससे कहीं अधिक तेज़ी से आपको कभी भी आवश्यकता क्यों होगी।

या, यह आपको एक तात्कालिक समाधान देगा: इससे पहले कि आपको वास्तव में इसकी आवश्यकता हो, गणना करें कि आपको 1 से कुछ अधिकतम संख्या की आवश्यकता क्या होगी। आप प्रत्येक चरण में आवश्यक संख्याओं को संग्रहीत कर सकते हैं। यदि आपके पास अपने दूसरे उदाहरण की तरह एक सीमा है, तो यह 1 से 300 के लिए आवश्यक है, शून्य से 1 से 50 के लिए क्या आवश्यक है।

अब आपके पास एक लुकअप टेबल है जिसे वसीयत में बुलाया जा सकता है। 10,000 तक करने में केवल कुछ MB लगेगा और, क्या, कुछ मिनटों की गणना करने के लिए, एक बार?


किसी संख्या से अंकों को पुनः प्राप्त करने के लिए, हमें कभी भी एक महंगा स्ट्रिंग रूपांतरण करने की आवश्यकता होगी यदि हम एक मॉड कर सकते हैं, तो अंकों को सबसे जल्दी से इस तरह एक नंबर पर धकेल दिया जा सकता है:

feed=number;
do
{ digit=feed%10;
  feed/=10; 
  //use digit... eg. digitTally[digit]++;
  }
while(feed>0)

वह लूप बहुत तेज़ होना चाहिए और अंकों को पूरा करने के लिए सबसे सरल तरीके से संख्याओं के अंत तक लूप के अंदर रखा जा सकता है।

संख्याओं की बड़ी रेंज के लिए तेजी से जाने के लिए, 0 से नंबर * 10 ^ महत्व (मुझे शुरू से अंत तक मुझे चकाचौंध करने के लिए) सभी अंकों को मिलान करने की एक अनुकूलित विधि की तलाश में।

यहाँ एक तालिका है जो कुछ एकल महत्वपूर्ण अंकों की संख्या को दर्शाती है .. ये 0 के समावेशी हैं, लेकिन स्वयं का शीर्ष मान नहीं है, लेकिन यह एक ओवरसाइट था, लेकिन इसके पैटर्न को देखने के लिए थोड़ा आसान है (शीर्ष मान वाले अंक अनुपस्थित हैं) इन ऊंचाइयों में शून्य ट्रेल्स शामिल नहीं हैं,

  1 10 100 1000 10000 2 20 30 40 60 90 200 600 2000  6000

0 1 1  10  190  2890  1  2  3  4  6  9  30 110  490  1690
1 0 1  20  300  4000  1 12 13 14 16 19 140 220 1600  2800
2 0 1  20  300  4000  0  2 13 14 16 19  40 220  600  2800
3 0 1  20  300  4000  0  2  3 14 16 19  40 220  600  2800
4 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
5 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
6 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
7 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
8 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
9 0 1  20  300  4000  0  2  3  4  6  9  40 120  600  1800

संपादित करें: मेरे मूल विचारों को साफ़ करना:

ब्रूट फोर्स टेबल से 0 (सम्‍मिलित) से लेकर पावरपोइंट (notinc) तक की ऊँचाई दिखाते हुए, यह दिखाई दे रहा है कि टेनपॉवर का एक प्रमुख स्रोत:

increments tally[0 to 9] by md*tp*10^(tp-1)
increments tally[1 to md-1] by 10^tp
decrements tally[0] by (10^tp - 10) 
(to remove leading 0s if tp>leadingzeros)
can increment tally[moresignificantdigits] by self(md*10^tp) 
(to complete an effect)

यदि ये टैली समायोजन प्रत्येक महत्वपूर्ण अंक के लिए लागू किए गए थे, तो टैली को संशोधित किया जाना चाहिए, हालांकि 0 से एंड -1 तक गिना जाता है

समायोजन पूर्ववर्ती सीमा (आरंभ संख्या) को हटाने के लिए उल्टा किया जा सकता है

आपके पूर्ण और परीक्षित उत्तर के लिए धन्यवाद हारून।


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

यह वास्तव में काफी सरल है लेकिन व्याख्या करना आसान नहीं है।

यदि आप पहले n नंबर को सूचीबद्ध करते हैं

     1
     2
     3

     .
     .
     .


     9
    10
    11

सामान्य तौर पर स्टार्ट रूम नंबर से लेकर एंड रूम नंबर से लेफ्ट से राइट फैशन में गिनने के लिए अंकों की गिनती शुरू करना आम बात है, इसलिए ऊपर के लिए हमारे पास एक 1, 2 2, एक 3 ... एक 9, दो 1 का एक शून्य है। , चार 1 इत्यादि अधिकांश समाधान मैंने इस दृष्टिकोण का उपयोग कुछ अनुकूलन के साथ इसे गति देने के लिए किया है।

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

यदि आप संख्याओं को लिखने के लिए एक्सेल का उपयोग करते हैं लेकिन संख्या के प्रत्येक अंक के लिए एक अलग कॉलम का उपयोग करते हैं तो कल्पना करना आसान है

     A    B    C
     -    -    -
     0    0    1  (assuming room numbers do not start at zero)
     0    0    2
     0    0    3
     .
     .
     .
     3    6    4
     3    6    5
     .
     .
     .

     6    6    9
     6    7    0
     6    7    1

     ^
     sum in columns not rows

इसलिए अगर उच्चतम कक्ष संख्या 671 है तो सैकड़ों कॉलम में 100 शून्य होंगे, उसके बाद 100 और इतने पर 71 छक्के होंगे, 100 शून्य की उपेक्षा करें यदि आवश्यक हो तो हमें पता है कि ये सभी अग्रणी हैं।

फिर दसियों तक वापस जाएं और एक ही ऑपरेशन करें, हमें पता है कि 10 जीरो होंगे जिसके बाद 10 लोग होंगे आदि, छह बार दोहराया गया, फिर अंतिम समय 2 सेवन्स तक। फिर से पहले 10 शून्य को अनदेखा कर सकते हैं क्योंकि हम जानते हैं कि वे अग्रणी हैं। अंत में निश्चित रूप से इकाइयों को पहले शून्य की आवश्यकता के रूप में अनदेखा करते हैं।

तो कोई लूप नहीं हैं सब कुछ विभाजन के साथ गणना की जाती है। मैं कॉलम को "ऊपर" यात्रा करने के लिए पुनरावृत्ति का उपयोग करता हूं, जब तक कि अधिकतम एक (इस मामले में सैकड़ों) तक नहीं पहुंच जाता है और फिर वापस चला जाता है।

मैंने इसे C # में लिखा था और यदि कोई दिलचस्पी रखता है तो कोड पोस्ट कर सकता है, किसी भी बेंचमार्क समय पर नहीं किया है, लेकिन यह अनिवार्य रूप से 10 ^ 18 कमरों तक के मूल्यों के लिए तत्काल है।

इस दृष्टिकोण का उल्लेख यहां या कहीं और नहीं किया जा सकता है इसलिए सोचा कि यह किसी के लिए उपयोगी हो सकता है।


मैंने मैथ ओवरफ्लो पर यह प्रश्न पूछा , और इस तरह के एक साधारण प्रश्न को पूछने के लिए प्रेरित हुआ। उपयोगकर्ताओं में से एक ने मुझ पर दया की और कहा कि अगर मैंने इसे द आर्ट ऑफ़ प्रॉब्लम सॉल्विंग में पोस्ट किया, तो वह इसका जवाब देगा; तो मैंने किया।

यहाँ वह जवाब पोस्ट किया गया है:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

शर्मनाक ढंग से, मेरे गणित-फू को समझने में अपर्याप्त है कि उसने क्या पोस्ट किया है (लड़का 19 साल का है ... जो इतना निराशाजनक है)। मुझे वास्तव में कुछ गणित कक्षाएं लेने की आवश्यकता है।

उज्ज्वल पक्ष पर, समीकरण पुनरावर्ती है, इसलिए इसे गणित को समझने वाले किसी व्यक्ति द्वारा कोड की कुछ पंक्तियों के साथ पुनरावर्ती कार्य में बदलना एक साधारण मामला होना चाहिए।


यदि "बेहतर" का अर्थ "स्पष्ट" है, तो मुझे संदेह है। अगर इसका मतलब "तेज़" है, तो हाँ, लेकिन मैं एक स्पष्ट आवश्यकता के बिना एक स्पष्ट के स्थान पर एक तेज एल्गोरिथ्म का उपयोग नहीं करूंगा।

#!/usr/bin/ruby1.8

def digits_for_range(min, max, leading_zeros)
  bins = [0] * 10
  format = [
    '%',
    ('0' if leading_zeros),
    max.to_s.size,
    'd',
  ].compact.join
  (min..max).each do |i|
    s = format % i
    for digit in s.scan(/./)
      bins[digit.to_i] +=1  unless digit == ' '
    end
  end
  bins
end

p digits_for_range(1, 49, false) 
# => [4, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 49, true)
# => [13, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 10000, false)
# => [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]

रूबी 1.8, एक भाषा जिसे "डॉग स्लो" कहा जाता है, उपरोक्त कोड 0.135 सेकंड में चलता है। जिसमें दुभाषिया लोड करना शामिल है। जब तक आपको अधिक गति की आवश्यकता न हो, एक स्पष्ट एल्गोरिथ्म न छोड़ें।


यह आपके सटीक प्रश्न का उत्तर नहीं देता है, लेकिन बेनफोर्ड के कानून के अनुसार पहले अंकों के वितरण पर ध्यान देना दिलचस्प है। उदाहरण के लिए, यदि आप यादृच्छिक पर संख्याओं का एक सेट चुनते हैं, तो उनमें से 30% "1" से शुरू होंगे, जो कुछ हद तक काउंटर-सहज ज्ञान युक्त है।

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


यहाँ एक बहुत बुरा जवाब है, मुझे इसे पोस्ट करने में शर्म आ रही है। मैंने गणितज्ञ से 1 से 1,000,000 तक सभी अंकों में प्रयुक्त अंकों को मिलान करने के लिए कहा, कोई प्रमुख 0 नहीं। यहाँ मुझे क्या मिला है:

0   488895
1   600001
2   600000
3   600000
4   600000
5   600000
6   600000
7   600000
8   600000
9   600000

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







clarion