मैं निम्नलिखित समस्या को हल करने की कोशिश कर रहा हूँ:सबसे छोटा एन-बिट पूर्णांक ग कश्मीर 1-बिट है और है कि छ दो एन-बिट पूर्णांकों का योग है, ज बिट्स 1 (गतिशील प्रोग्रामिंग) के लिए सेट
छोटी से छोटी n-बिट पूर्णांक ग कश्मीर 1-बिट है और है कि जी, एच बिट्स 1. जी, एच सेट दो एन-बिट पूर्णांकों का योग है कि पता लगाएं, k < = n
प्रारंभ करने के लिए, यहां एन-बिट पूर्णांक का अर्थ है कि हम सभी n
बिट्स, यानी अधिकतम उपयोग कर सकते हैं। ऐसे पूर्णांक का मान 2^n - 1
है। वर्णित पूर्णांक बिल्कुल मौजूद नहीं हो सकता है। यह स्पष्ट है कि k > g + h
में कोई समाधान नहीं है और g + h = k
के लिए उत्तर केवल 2^k - 1
है (पहले k
बिट्स 1-बिट्स, k - n
सामने में शून्य हैं)।
कार्यक्रम करने के लिए माना जाता है के कुछ उदाहरण दिए के लिए के रूप में:
g = h = k = 4, n = 10 :
0000001111 + 0000001111 = 0000011110
15 + 15 = 30 (30 should be the output)
(4, 6, 5, 10):
0000011110 + 0000111111 = 0001011101
30 + 63 = 93
(30, 1, 1, 31):
1 + (2^30 - 1) = 2^30
मैं इसके बारे में लगता है के रूप में, यह एक गतिशील प्रोग्रामिंग समस्या है और मैं निम्नलिखित दृष्टिकोण चुन लिया है: dp[g][h][k][n][c]
होने दो वर्णित पूर्णांक और c
ले जाने के लिए एक वैकल्पिक बिट है। मैं निम्नतम आदेश बिट्स के आधार पर संभावित रकम का पुनर्निर्माण करने का प्रयास करता हूं। तो, dp[g][h][k][n + 1][0]
(0, 0): dp[g][h][k][n][0]
(0, 0): 2^n + dp[g][h][k - 1][n][1]
(1, 0): 2^n + dp[g - 1][h][k - 1][n][0]
(0, 1): 2^n + dp[g][h - 1][k - 1][n][0]
इसी तरह के कम से कम है, dp[g][h][k][n + 1][1]
(1, 1): dp[g - 1][h - 1][k][n][0]
(1, 1): dp[g - 1][h - 1][k - 1][n][1] + 2^n
(1, 0): dp[g - 1][h][k][n][1]
(0, 1): dp[g][h - 1][k][n][1]
की न्यूनतम विचार यह है कि मुश्किल नहीं है, लेकिन मैं वास्तव में इस तरह की चीजों और मेरे एल्गोरिथ्म नहीं करता है के साथ अनुभव नहीं कर रहा हूँ सरल मामलों के लिए भी काम नहीं करते हैं। मैंने टॉप-डाउन दृष्टिकोण चुना है। मेरे लिए सभी कोने के मामलों पर विचार करना मुश्किल है। मुझे वास्तव में पता नहीं है कि मैंने सही ढंग से रिकर्सन का आधार चुना है, आदि। मेरा एल्गोरिदम g = h = k = 1, n = 2
(उत्तर 01 + 01 = 10
) के लिए सबसे बुनियादी मामले के लिए भी काम नहीं करता है। g = h = k = 1, n = 1
के लिए उत्तर नहीं होना चाहिए लेकिन एल्गोरिदम 1
देता है (जो मूल रूप से 2
के बजाय 1
का उत्पादन करता है)।
int solve(int g, int h, int k, int n, int c = 0) {
if (n <= 0) {
return 0;
}
if (dp[g][h][k][n][c]) {
return dp[g][h][k][n][c];
}
if (!c) {
if (g + h == k) {
return dp[g][h][k][n][c] = (1 << k) - 1;
}
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g + h > k && k <= n - 1) {
a1 = solve(g, h, k, n - 1, 0);
}
if (g + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g, h, k - 1, n - 1, 1);
}
if (g - 1 + h >= k - 1 && k - 1 <= n - 1) {
a3 = (1 << (n - 1)) + solve(g - 1, h, k - 1, n - 1, 0);
}
if (g + h - 1 >= k - 1 && k - 1 <= n - 1) {
a4 = (1 << (n - 1)) + solve(g, h - 1, k - 1, n - 1, 0);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
} else {
int min, a1, a2, a3, a4;
min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
if (g - 2 + h >= k && k <= n - 1) {
a1 = solve(g - 1, h - 1, k, n - 1, 0);
}
if (g - 2 + h >= k - 1 && k - 1 <= n - 1) {
a2 = (1 << (n - 1)) + solve(g - 1, h - 1, k - 1, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a3 = solve(g - 1, h, k, n - 1, 1);
}
if (g - 1 + h >= k && k <= n - 1) {
a4 = solve(g, h - 1, k, n - 1, 1);
}
min = std::min({a1, a2, a3, a4});
return dp[g][h][k][n][c] = min;
}
}
अच्छा सवाल। लेकिन मेरा मानना है कि आप गलत निष्कर्ष (गतिशील प्रोग्रामिंग का उपयोग करके) के लिए बहुत तेजी से कूदते हैं। मैं एक और रचनात्मक दृष्टिकोण की तलाश में हूं। कुछ मामलों को हल करके, 1 <= k, g, h <= 3, हाथ से, आप एक पैटर्न देख सकते हैं। नाइटपिक: "इस तरह के पूर्णांक का अधिकतम मूल्य' 2^(एन + 1) - 1' "है - यह वास्तव में' 2^n - 1' है। – Gassa
@ गासा। यदि आप संकेत दे रहे हैं कि जी + एच = के + 1 के लिए समाधान 10 + के हैं, तो जी + एच = के + 2 के लिए यह 110 + के हैं और इसी तरह, आप गलत हैं। सबसे पहले, जी + एच - के> के लिए थोड़ा अधिक कॉम्प्लेक्स पैटर्न है। दूसरा, दोनों में गिनती है! – Atin
क्षमा करें, मेरे पास दिमाग में एक विशिष्ट पैटर्न नहीं है। इसके बजाय, एक सामान्य जांच विधि जो पैटर्न - या इसके अस्तित्व को प्रकट करेगी, अगर वास्तव में यह मामला है। – Gassa