जाहिर है कुछ लोगों को बाइनरी खोज एक विभाजन और जीत एल्गोरिथ्म पर विचार, और कुछ नहीं हैं। मैं जल्दी से तीन संदर्भ googled (सभी शिक्षा से संबंधित तो लग) है कि यह एक डी & सी एल्गोरिथ्म फोन: http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf http://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/DivConq.htm http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html
मुझे लगता है कि यह आम सहमति है कि एक डी & सी एल्गोरिथ्म कम से कम पहले दो चरणों होना चाहिए इन तीन में से:
- विभाजन, यानी यह तय कर लें पूरी समस्या उप समस्याओं में अलग किया जाता है;
- जीत है, यानी स्वतंत्र रूप से उप-समस्याओं में से प्रत्येक को हल;
- [वैकल्पिक] गठबंधन है, यानी एक साथ मर्ज स्वतंत्र संगणना का परिणाम है।
दूसरे चरण - जीत - रिकर्सिवली व्यवहार में भी छोटे उप उप समस्याओं में विभाजित करके subproblem हल करने के लिए उसी तकनीक लागू करना चाहिए, और आदि, हालांकि, अक्सर कुछ सीमा पुनरावर्ती सीमित करने के लिए प्रयोग किया जाता है दृष्टिकोण, छोटे आकार की समस्याओं के लिए एक अलग दृष्टिकोण तेजी से हो सकता है। उदाहरण के लिए, त्वरित सॉर्ट कार्यान्वयन अक्सर उपयोग करते हैं उदा। बुलबुला सॉर्ट जब सॉर्ट भाग का आकार छोटा हो जाता है।
तीसरे चरण हो सकता है नो-सेशन, और मेरी राय में यह डी & सी एक सामान्य उदाहरण के रूप में एक एल्गोरिथ्म को अयोग्य घोषित नहीं करता है एक for -loop स्वतंत्र डेटा आइटम के साथ विशुद्ध रूप से कार्य कर रहे सभी पुनरावृत्तियों के साथ की पुनरावर्ती अपघटन (है यानी किसी भी रूप में कोई कमी नहीं)। यह नज़र में बेकार लग सकता है, लेकिन वास्तव में यह बहुत शक्तिशाली तरीका है उदा। समानांतर में लूप निष्पादित करें, और सिल्क और इंटेल के टीबीबी के रूप में इस तरह के ढांचे द्वारा उपयोग किया जाता है।
int search(int value, int* a, int begin, int end) {
// end is one past the last element, i.e. [begin, end) is a half-open interval.
if (begin < end)
{
int m = (begin+end)/2;
if (value==a[m])
return m;
else if (value<a[m])
return search(value, a, begin, m);
else
return search(value, a, m+1, end);
}
else // begin>=end, i.e. no valid array to search
return -1;
}
यहाँ डिवाइड हिस्सा int m = (begin+end)/2; और है:;:
मूल प्रश्न पर वापस लौटते हुए (खेद है इस भाषा आप के साथ सहज हैं नहीं है मैं सी का उपयोग ++) के कुछ कोड है कि एल्गोरिथ्म को लागू करता है पर विचार करते हैं बाकी सब जीतने का हिस्सा है। एल्गोरिदम स्पष्ट रूप से एक रिकर्सिव डी & सी रूप में लिखा गया है, भले ही शाखाओं में से केवल एक ही लिया गया हो। हालांकि, यह भी एक पाश रूप में लिखा जा सकता है:
int search(int value, int* a, int size) {
int begin=0, end=size;
while(begin<end) {
int m = (begin+end)/2;
if (value==a[m])
return m;
else if (value<a[m])
end = m;
else
begin = m+1;
}
return -1;
}
मुझे लगता है कि यह काफी एक आम तरीका है एक पाश के साथ द्विआधारी खोज को लागू करने के है; मैंने जानबूझकर वही वैरिएबल नामों को रिकर्सिव उदाहरण के रूप में उपयोग किया, ताकि समानता को देखना आसान हो। इसलिए हम कह सकते हैं कि, फिर, मध्यबिंदु की गणना करना विभाजन भाग है, और शेष लूप बॉडी भाग जीतने वाला है।
लेकिन निश्चित रूप से अगर आपके परीक्षकों अलग तरह से सोचने, यह उन्हें समझाने के लिए यह विकास & है सी मुश्किल हो सकता है
अद्यतन: सिर्फ एक विचार है कि अगर मैं एक डी & सी एल्गोरिथ्म के एक सामान्य कंकाल कार्यान्वयन विकसित करने के लिए थे, मैं निश्चित रूप से द्विआधारी खोज एपीआई उपयुक्तता परीक्षणों में से एक के रूप में है कि क्या एपीआई पर्याप्त शक्तिशाली करते हुए भी संक्षिप्त है की जाँच करने के लिए उपयोग होता था । बेशक यह कुछ भी साबित नहीं करता है :)
जीत भाग वह जगह है जहां आप समस्या का समाधान करते हैं। मुझे यकीन नहीं है कि उन्होंने क्यों कहा कि यह विभाजन और जीत नहीं था। ये चीजें हैं जिन्हें आप अपने परीक्षकों से पूछना सुनिश्चित कर सकते हैं! वे केवल वे हैं जो वे जो जवाब ढूंढ रहे थे उसे जानते हैं। –
ठीक है, आप केवल एक आधे में खोजते हैं। तो हाँ, आप समस्या को विभाजित करते हैं। लेकिन नहीं, आप दोनों हिस्सों को जीत नहीं पाते हैं, केवल एक (कम से कम जब आप स्मार्ट होते हैं .-)) –
क्या यह घटता है और जीतता है? विकिपीडिया से उद्धरण यहां दिया गया है। "सिंगल-सबप्रोबलेम क्लास के लिए नाम कम हो गया है और जीत का प्रस्ताव दिया गया है" http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms#Decrease_and_conquer – arun8