मेरे पास एक समस्या कथन है - n दिया गया है, n के योग वाले पूर्ण वर्ग संख्याओं की न्यूनतम संख्या ज्ञात करें।

कुछ कारणों से, मैं सूत्र के आधार पर कम से कम कुशल पाशविक बल दृष्टिकोण का प्रयास कर रहा था -

PerfectSquaresRequired(n) = (perfectSquaresRequired(n-k) + 1) सभी k के लिए जो पूर्ण वर्ग है<=n

मैंने इसे जावा में लागू करने के लिए एक पुनरावर्ती कार्य लिखा था। यहां numSquares फंक्शन कॉल किया जा रहा है और getSteps वह फंक्शन है जो रिकर्सन लॉजिक को लागू करता है।

Set<Integer> squares;    
public int numSquares(int n) {
    squares = new HashSet();
    for (int i=1; i*i<=n; i++)
        squares.add(i*i);
    
    return getSteps(n);
}

public int getSteps(int k) {
    if (squares.contains(k))
        return 1;
    int min=Integer.MAX_VALUE, cur;
    for (Integer square : squares) {
        if (square>k)
            break;
        cur = getSteps(k-square) + 1;
        min = Math.min(cur, min);
    }
    return min;
}

समस्या यह है कि मुझे इस कोड से बेतुका मूल्य मिल रहा है। हालाँकि अगर मैं Integer.MAX_VALUE के अलावा किसी भी अन्य कथन int min = Integer.MAX_VALUE का उपयोग करता हूं, यानी 2147483647 (यहां तक ​​​​कि 2147483646) से छोटा कोई भी मूल्य, मुझे सही उत्तर मिल रहा है।

मैं अभी केवल एक महीने से डीएसए सीख रहा हूं। क्या कोई समझा सकता है कि ऐसा क्यों हो रहा है?

2
Sparsh 13 फरवरी 2021, 08:52

2 जवाब

सबसे बढ़िया उत्तर
for (Integer square : squares) {
    if (square>k)
        break;
    ...
}

यह लूप उम्मीद करता है कि वर्गों को सबसे छोटे से सबसे बड़े तक पुनरावृत्त किया जाएगा। समस्या यह है कि एक HashSet का कोई पूर्वानुमेय क्रम नहीं है। यदि एक बड़ा वर्ग जल्दी सामने आता है तो अन्य सभी छोटे वर्गों पर विचार करने से पहले लूप टूट जाता है।

आदेश सुनिश्चित करने के लिए आपको SortedSet का उपयोग करना होगा। TreeSet पर स्विच करने से प्रोग्राम ठीक हो जाता है:

squares = new TreeSet<>();

साइड नोट, मैं दृढ़ता से सुझाव देता हूं कि आप अधिक memoization जोड़ें। जब n बढ़ता है तो getSteps को समान मान के लिए बार-बार कॉल करने की बहुत होती है। यदि आपके पास getSteps प्रत्येक k के लिए इसके रिटर्न मानों को कैश करता है और महंगे लूप में जाने से पहले कैशे को कॉल करने पर परामर्श करता है, तो आपको पर्याप्त गति प्राप्त होगी।

3
John Kugelman 13 फरवरी 2021, 09:07

अतिप्रवाह!

त्रुटि होने लगती है यदि गणना करने के लिए मान >=17 है।

आपका परिणाम -2147483648 है, जो है....हां, Integer.MAX_VALUE+1 यहां छवि विवरण दर्ज करें

रिकर्सिव ऑपरेशन नंबर t+1 में:

 for (Integer square : squares) {
      if (square>k)
           break;
    cur = getSteps(k-square) + 1;
    min = Math.min(cur, min);
 }
return min;

cur ऑपरेशन नंबर t के अनुसार, min को Integer.MAX_VALUE के मान के साथ लौटा दिया गया था।

यह बनाता है

cur = Integer.MAX_VALUE + 1 // --> -2147483648

वहां से, Math.min(cur,min) को अपना अंतिम मान मिल गया: -2147483648

यह केवल एक बार होता है, इसलिए यदि आप Integer.MAX_VALUE-1 को min के रूप में सेट करते हैं, तो विफल नहीं होता क्योंकि यह अतिप्रवाह नहीं होगा (और इस रूप में नहीं चुना जाएगा न्यूनतम मान न तो)।


सस्ता समाधान: long

यदि आप उस कोड को बनाए रखना चाहते हैं/चाहते हैं, तो यह एक समाधान होगा।

नहीं, बस ऐसा मत करो। जैसा कि जॉन ने नीचे टिप्पणी की है, यह विफलता को कम स्पष्ट बनाता है

उनका जवाब शुरू से ही सही समाधान था



प्रविष्टि आदेश सुरक्षित रखें

squares को पुनः प्राप्त करते समय सम्मिलन आदेश का सम्मान किया जाना चाहिए। यही कुंजी है, जैसा कि जॉन सही कहता है। दो प्रकार के सेट हैं जो इसका सम्मान करते हैं: LinkedHashSet और TreeSet

इस परिदृश्य के लिए दोनों खराब हैं, लेकिन विशेष रूप से TreeSet केवल भयानक है।

TreeSet, add, contains और remove के लिए मतलब ~O(log(N))। यहाँ कोई मज़ाक नहीं है, बस इसे numSquares(99) क्रियान्वित करने का परीक्षण करें। यह एक कम संख्या है, लेकिन मैंने देखा कि कुछ मूल्यों (55-60) के बाद समय तेजी से बढ़ा। तो 99 इसकी पुष्टि करने के लिए पर्याप्त से अधिक है।

मैंने 3 घंटे (असली के लिए) इंतजार किया और वह बात खत्म नहीं हुई। यह आपको विश्वास दिलाता है कि आपके कंप्यूटर की संसाधन क्षमता 90 के दशक के मध्य के LCD videoconsoles से कम है।

यह भी जॉन के उत्तर द्वारा सही ढंग से इंगित किया गया था।


मेरी पूरी कोशिश

परीक्षण के बाद, सबसे अच्छा प्रदर्शन एक मिश्रित दृष्टिकोण वाला कोड था जिसमें HashSet और एक ArrayList का उपयोग किया गया था। तंत्र में फिर से शुरू किया जा सकता है:

  • तत्वों को ArrayList में जोड़ें (यह प्रविष्टि आदेश का सम्मान करेगा)
  • आह्वान HashSet.addAll(ArrayList)
  • HashSet.contains कंडीशन चेक है
  • for (Integer square : ArrayList) लूप मैकेनिज्म है

यह कोड है:

 Set<Integer> sqSet;  
 List<Integer> sqArr;
 //...
 public int numSquares(int n)
 {
     sqSet = new HashSet<>((n/10)+2);
     sqArr = new ArrayList<>((n/10)+2);  //avoids grow()

     for (int i=1; i*i<=n; i++)
         sqArr.add(i*i);
    
     sqSet.addAll(sqArr);
     return getSteps(n);
 }

 public int getSteps(int k) 
 {
    if (sqSet.contains(k))
       return 1;
    int min=Integer.MAX_VALUE;
    int cur;
    for (Integer square : sqArr) 
    { 
       if (square>k)
         break;
       cur = getSteps(k-square) + 1;
       min = Math.min(cur, min);
     }   
     return min;
  }
3
aran 19 फरवरी 2021, 05:29