परियोजना यूलर # 14

Question

मैं वर्तमान को सुलझाने कर रहा हूँ, Project Euler problem 14:

निम्नलिखित पुनरावृत्ति अनुक्रम सकारात्मक पूर्णांकों का सेट के लिए परिभाषित किया गया है:

n → n/2 (n is even) 
n → 3n + 1 (n is odd) 

Using the rule above and starting with 13, we generate the following sequence: 
       13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 

Which starting number, under one million, produces the longest chain? 

मैं हल करने के लिए निम्नलिखित एल्गोरिथम तैयार समस्या:

• के बजाय ईए के लिए श्रृंखला की खोज ch संख्या अलग से, जिसमें बहुत सी अनावश्यक गणना होगी, मैं श्रृंखला को पीछे से आगे विकसित करने का प्रयास करता हूं। यानी, संख्या से शुरू करें और इससे पहले तत्व की भविष्यवाणी करें।
• चूंकि कई श्रृंखलाएं उत्पन्न की जा सकती हैं, इसलिए एक लिंक की गई सूची का उपयोग करके सभी श्रृंखलाओं की हाल की संख्या को स्टोर करें। (विचार केवल उन तत्वों को स्टोर करना है जिनमें लंबी श्रृंखला है।)
• मैं इसे लूप कर दूंगा, जब तक कि मुझे दी गई सीमा के तहत सभी संख्याएं न मिलें; सीमा के तहत अंतिम संख्या में सबसे लंबी श्रृंखला होगी।

  void series_generate(long num) 
  { 
      long n = 1; 
      addhead(n);    //add 1 to list. 
      while (n < num) 
      { 
        series *p; 
        for (p = head; p != NULL; p = p->next) 
        { 
          long bf = p->num - 1; 
          if (p->num%2 == 0 && bf != 0 && bf%3 == 0) { 
            bf /= 3; 
            if (bf != 1) 
              addhead(bf); 
            if (bf < num) 
              n++; 
          } 
          p->num *= 2; 
          if (p->num < num) 
            n++; 
  
        }  
      }  
  } 
  

  Here is the link to complete code. हालांकि, मैं जवाब के रूप में मैं उम्मीद नहीं मिलता:

यहाँ मेरी कोड है। क्या कोई यह बता सकता है कि यह एल्गोरिदम क्यों काम नहीं करेगा?

Answer 1

आप प्रति स्तर स्तर, कोलात्ज़ पेड़ को पीछे की ओर बनाने की कोशिश कर रहे हैं। इस प्रकार k-आंतरिक लूप के पुनरावृत्ति के बाद, सूची में शामिल है (जबकि कोई ओवरफ़्लो नहीं हुआ) सभी संख्याओं को उनके कोलेट्स अनुक्रम में 1 तक पहुंचने के लिए k चरणों की आवश्यकता है।

उस दृष्टिकोण में दो गंभीर समस्याएं हैं।

1. स्तरों का आकार तेजी से बढ़ता है, आकार लगभग हर तीन स्तरों पर दोगुना हो जाता है। आप स्तर k में बहुत ज्यादा नहीं 100
2. से अधिक सबसे बड़ा सदस्य अतीत की दुकान के स्तर के लिए पर्याप्त स्मृति नहीं है 2 ^{कश्मीर} है। num सदस्य के लिए प्रयुक्त प्रकार के आधार पर, आप स्तर 31, 32, 63 या 64 पर ओवरफ्लो प्राप्त करते हैं। फिर, यदि आप एक हस्ताक्षरित प्रकार का उपयोग करते हैं, तो आपके पास सूची में अनिश्चित व्यवहार, शायद नकारात्मक संख्याएं हैं, और सभी हायरवायर चलाते हैं। यदि आप बिना हस्ताक्षर किए गए प्रकारों का उपयोग करते हैं, तो आपकी सूची में 0 होता है, और सभी खराब हो जाते हैं।

चूंकि 27 को 1 तक पहुंचने के लिए 111 चरणों की आवश्यकता है, इसलिए num > 27 पर आपको अतिप्रवाह होता है, इसलिए आपको गलत परिणाम मिलते हैं।