जावा प्रोग्रामिंग: सीढ़ियों पर गतिशील प्रोग्रामिंग उदाहरण

Question

एक आदमी एन चरणों के साथ सीढ़ी चला रहा है, और एक समय में 1 कदम, 2 कदम, या 3 कदम जा सकता है। अब यह जानने के लिए एक कार्यक्रम लिखें कि बच्चे सीढ़ियों को कितने संभावित तरीके से चला सकता है।

दिया कोड की तरह

नीचे

public static int countDP(int n, int[] map) { 
if (n<0) 
    return 0; 
else if (n==0) 
    return 1; 
else if (map[n]>-1) 
    return map[n]; 
else { 
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 
    return map[n]; } 
} 

मैं C और C++ पता है, नहीं जावा है। यह कोडिंग साक्षात्कार पुस्तक क्रैकिंग से है। किसी

1. क्यों की व्याख्या कर सकते कर सकते हैं और कैसे वह समारोह नक्शा यहाँ कार्यरत हैं? यहां नक्शा सही है?

2. मुझे नक्शा सरणी में इनपुट सहेजने के लिए कोई लाइन नहीं दिखाई देती है लेकिन यह कुछ कैसे वापस लाएगी?

3. किसी को भी इस कोड का सी ++ या सी संस्करण का विचार है? इस कोड को समझना मुश्किल है। शायद जावा व्याकरण की वजह से नहीं, बल्कि गतिशील प्रोग्रामिंग की अंतर्निहित संरचना।

4. इस एल्गोरिदम की समय जटिलता क्या होगी? यह ओ (3^एन) से छोटा होना चाहिए?

मैं इसकी सराहना करता हूं।

धन्यवाद, लोग

Answer 1

ठीक है, कोड क्या करता है।

`if (n<0)` 
    `return 0;` 

यदि पर्याप्त कदम शेष नहीं हैं, तो इसे गिनें मत। उदाहरण के लिए, यदि दो चरण शेष हैं, लेकिन उपयोगकर्ता तीन चरणों को लेने की कोशिश कर रहा है, तो यह संभावित संयोजन के रूप में नहीं गिना जाता है।

else if (n==0) return 1;

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

else if (map[n]>-1) return map[n];

यहाँ गतिशील प्रोग्रामिंग हिस्सा है। मान लें कि सरणी में सभी मानों का मान -1 था। इसलिए, यदि संख्या -1 से अधिक है, तो इसे पहले ही हल कर लिया गया है, इसलिए इसे हल करने के बजाय चरण संख्या n से संयोजनों की कुल संख्या वापस कर दें।

`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);` 

return map[n]; }

अंत में, इस हिस्से कोड को हल करती है। संभावित संयोजनों की संख्या उपयोगकर्ता द्वारा प्राप्त किए जा सकने वाले संभावित संयोजनों की संख्या के बराबर होती है यदि वह 1 कदम + संभव संयोजनों की संख्या लेता है, यदि उपयोगकर्ता 2 कदम उठाता है + यदि संभव हो तो उपयोगकर्ता संभवतः संभावित संयोजनों की संख्या ले सकता है तीन कदम

एक उदाहरण, मान लीजिए 5 कदम

एक साधारण रन कैसा दिखेगा देखते हैं:

//The number of solutions from the fifth step 

countDp(5) = countDp(4)+countDp(3)+countDp(2); 

//Number of solutions from the fourth step 

countDP(4) = countDp(3)+countDp(2)+countDp(1); 

//Number of solutions from the third step 

countDp(3) = countDp(2)+countDp(1)+countDp(0); 
//Number of solutions from the second step 
countDp(2) = countDp(1)+countDp(0)+countDp(-1); 
//Number of solutions from the first step 
countDp(1) = countDp(0) + countDp(-1)+countDp(-2); 
//Finally, base case 
countDp(0) = 1; 

countDp(-1)= 0; 
countDp(-2)= 0; 
countDp(1) = 1+0+0 = 1; 
countDp(2) = 1+1+0 = 2; //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1] 
countDp(3) = 2+1+1 = 4; //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2] 
countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1] 
countDp(5)= 2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2] 

Answer 2

क्यों और कैसे वह समारोह नक्शा यहाँ कार्यरत हैं?

पुस्तक memoization नामक गतिशील प्रोग्रामिंग तकनीक दिखाती है। इसका उपयोग उसी नंबर की गणना करने से बचने के लिए किया जाता है: यदि तत्व -1 नहीं है, तो इसे फिर से गणना की गई है, और फिर इसकी गणना करने से इसका मतलब बहुत सी CPU चक्रों को बर्बाद कर देगा। डीपी एक बार मान की गणना करता है, और उसके बाद मूल्य की आवश्यकता होने पर हर बार इसे वापस कर देता है।

मानचित्र यहाँ सरणी सही है?

सही, map एक सरणी प्रकार का है।

मुझे नक्शा सरणी में इनपुट सहेजने के लिए कोई लाइन नहीं दिखाई दे रही है लेकिन यह कुछ कैसे वापस आएगी?

कि नीचे से तीसरी पंक्ति में काम होगा:

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 

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

दाएं, डीपी और ज्ञापन को उपयोग करने के लिए कुछ समय लगता है। पेपर और पेंसिल के साथ एक छोटी संख्या के लिए एक बार इस एल्गोरिदम के माध्यम से चलाएं, कहें, 10. यह आपको दिखाएगा कि उत्तर का इष्टतम प्रतिस्थापन इस एल्गोरिदम को इतनी तेजी से उत्तर के साथ कैसे मदद करता है।

इस एल्गोरिदम की समय जटिलता क्या होगी? यह ओ (3^एन) से छोटा होना चाहिए?

बिल्कुल! प्रत्येक आइटम की गणना एक बार की जाती है, और प्रत्येक आइटम गणना करने के लिए O(1) को मिश्रित करता है, इसलिए इस कोड की समग्र जटिलता O(N) है। यह प्रतिकूल हो सकता है, जैसा कि आप देखते हैं कि countDP(K) की गणना करने के लिए रिकर्सिव इनवोकेशन की श्रृंखला O(K) पुनरावर्ती आमंत्रण लेती है। हालांकि, प्रत्येक आमंत्रण Kmap के आइटमों की गणना समाप्त करता है (ध्यान दें कि map एक तरफा सड़क है: एक बार जब आप किसी सेल में गैर-ऋणात्मक मान सेट करते हैं, तो यह हमेशा के लिए गैर-ऋणात्मक रहेगा, इसलिए पुनः कंप्यूटिंग किसी भी अन्य आमंत्रण पथ के माध्यम से एक ही मूल्य O(1) समय ले जाएगा।

Answer 3

1.) नक्शा एक पूर्णांक सरणी है। जावा में नोटेशन यह है कि मानचित्र [n] अनुक्रमणिका एन पर पूर्णांक मान देता है।

2.) वापसी एक पूर्णांक है क्योंकि नक्शा [एन] सूचकांक एन पर पूर्णांक मान देता है। केवल समय एक मूल्य सरणी में सहेजा जाता है

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 

पर यह एक पुनरावर्ती कॉल के लिए सभी संभव 1, 2, और 3 संयोजनों की गणना के द्वारा दिए गए चरणों का योग मिल रहा है है।

3.)

int countDP(int n, int map[]) 
{ 
if (n<0) 
    return 0; 
else if (n==0) 
    return 1; 
else if (map[n]>-1) 
    return map[n]; 
else { 
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 
    return map[n]; 
} 


} 

4.) हाँ जटिलता हे (3^n) की तुलना में बहुत तेजी से किया जाएगा।

Answer 4

जावास्क्रिप्ट समाधान: (पुनरावृत्ति)

function countPossibleWaysIterative(n) { 
    if (n < 0){ 
    return -1; // check for negative, also might want to check if n is an integer 
    } if (n === 0) { 
    return 0; // for case with 0 stairs 
    } else if (n === 1) { 
    return 1; // for case with 1 stairs 
    } else if (n === 2) { 
    return 2; // for case with 2 stairs 
    } else { 

    var prev_prev = 1; 
    var prev = 2; 
    var res = 4; // for case with 3 stairs 

    while (n > 3) { // all other cases 
     var tmp = prev_prev + prev + res; 
     prev_prev = prev; 
     prev = res; 
     res = tmp; 
     n--; 
    } 
    } 
    return res; 
} 

Answer 5

/** 
* Created by mona on 3/3/16. 
*/ 
import java.util.Hashtable; 
public class StairCount { 
    /* 
    A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, 
     or 3 steps at a time. count how many possible ways the child can run the stairs. 
    */ 
    static Hashtable<Integer, Long> ht=new Hashtable<>(); 

    public static long stairs(int n){ 
     if (!ht.containsKey(1)){ 
      ht.put(1, (long) 1); 
     } 
     if (!ht.containsKey(2)){ 
      ht.put(2, (long) 2); 
     } 
     if (!ht.containsKey(3)){ 
      ht.put(3, (long) 4); 
     } 

/* 
     if (!ht.containsKey(n)){ 
      ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3)); 
     } 
*/ 
     if (!ht.containsKey(n)){ 
      ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3)); 
     } 
     return ht.get(n); 
    } 
    public static void main(String[] args){ 
     System.out.println(stairs(4)); 

    } 
} 

// जवाब 4 के लिए 14 है और 5 के लिए 27 है। जिस पंक्ति पर टिप्पणी की गई है। क्या कोई टिप्पणी कर सकता है कि मेरी विचार प्रक्रिया गलत क्यों थी?