Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में डीरेंजमेंट की गणना (ऐसा क्रमपरिवर्तन जिसमें कोई तत्व अपनी मूल स्थिति में न हो)


डीरेंजमेंट N संख्याओं का एक क्रमपरिवर्तन है जिसमें कोई संख्या अपनी मूल स्थिति पर नहीं आती। उदाहरण के लिए {1,2,3} का एक संभावित डीरेंजमेंट {2,1,3} है। इसमें कोई तत्व अपनी मूल स्थिति पर नहीं है। यहां लक्ष्य N संख्याओं के लिए संभावित डीरेंजमेंट की गणना करना है।

हम इसे रिकर्सिव समाधान का उपयोग करके करेंगे। तत्वों की निम्नलिखित संख्या के लिए:

  • N=0, कोई डीरेंजमेंट नहीं, 1 लौटाएं
  • N=1, केवल एक संख्या, 0 लौटाएं
  • N=2, केवल एक स्थान परिवर्तन संभव, {1,2} → {2,1}, 1 लौटाएं
  • N=3, 2 संभावित क्रमपरिवर्तन जैसे, {1,2,3} → {2,3,1}, {3,1,2} गणना 2
  • N=4, 9 संभावित क्रमपरिवर्तन
  • .......................
  • N, (N-1)*( क्रमपरिवर्तन(N-1) + क्रमपरिवर्तन(N-2) )

सरणी में सभी तत्वों के लिए,

  • इंडेक्स 0 पर तत्व के n-1 स्थान हैं जो वह ले सकता है,
  • यदि इंडेक्स i पर कोई तत्व इंडेक्स 0 पर रखा जाता है तो, arr[i] और arr[0] की अदला-बदली होती है। अब गणना के लिए n-2 तत्व हैं।
  • यदि इंडेक्स i पर तत्व इंडेक्स 0 पर नहीं रखा जाता है तो n-1 तत्वों के लिए n-2 विकल्प हैं।

आरेख

C++ में डीरेंजमेंट की गणना (ऐसा क्रमपरिवर्तन जिसमें कोई तत्व अपनी मूल स्थिति में न हो)

इनपुट

Arr[] = { 1, 2 }

आउटपुट

डीरेंजमेंट की संख्या: 1

व्याख्या: 1 और 2 की स्थितियां इंडेक्स 0 और 1 हैं। वे केवल अपनी मूल स्थितियों की अदला-बदली करके प्राप्त कर सकते हैं। {2,1}

इनपुट

Arr[] = { 1, 2, 3 }

आउटपुट

डीरेंजमेंट की संख्या: 2

व्याख्या: 1,2 और 3 की स्थितियां इंडेक्स 0,1,2 हैं।

1 को इंडेक्स 1 और 2 पर रखा जा सकता है, 2 को इंडेक्स 0 और 3 पर और 3 को इंडेक्स 0 और 1 पर।

{2,3,1} और {3,1,2} 2 डीरेंजमेंट हैं।

प्रयुक्त दृष्टिकोण

  • पूर्णांक Num मौजूद संख्याओं की संख्या संग्रहीत करता है।
  • रिकर्सिव फ़ंक्शन derangements(int N) संख्याओं की संख्या को इनपुट के रूप में लेता है और डीरेंजमेंट की संख्या लौटाता है।
  • N=0,1,2 के लिए रिटर्न स्टेटमेंट बेस केस को संभालते हैं जिनके लिए क्रमपरिवर्तन पहले से ही 1,0 और 1 के रूप में गणना किए गए हैं।
  • जब N>2 हो तो derangements() को फॉर्मूला का उपयोग करके रिकर्सिव कॉल की जाती है, (N-1)* ( derangements(N-1) + derangements(N-2) )।

जब बैकट्रैकिंग शुरू होती है, तो गणना की जाती है और लौटाई जाती है।

उदाहरण कोड

#include <bits/stdc++.h> using namespace std; int derangements(int N){ if (N == 0) return 1; if (N == 1) return 0; if (N == 2) return 1; return (N - 1) * (derangements(N - 1) + derangements(N - 2)); } int main(){ int Numbers=5; cout<<"डीरेंजमेंट की संख्या: "<<derangements(Numbers); }

आउटपुट

डीरेंजमेंट की संख्या: 44

  1. - C++ में संशोधित नाइट द्वारा पहुंच योग्य सभी संभावित स्थितियों की गणना करें

    इस ट्यूटोरियल में, हम संशोधित नाइट द्वारा पहुंच योग्य संभावित स्थितियों की संख्या खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।इसके लिए हमें एक 8*8 शतरंज बोर्ड प्रदान किया जाएगा। हमारा कार्य दिए गए चरणों की संख्या के साथ संशोधित नाइट द्वारा कब्जा की जा सकने वाली स्थितियों की संख्या ढूंढना है।उदाहरण#inc

  1. - न्यूनतम x खोजें जैसे कि (x % k) * (x / k) == n C++ में

    दिए गए दो धनात्मक पूर्णांक n और k, और हमें धनात्मक पूर्णांक x खोजना है, जैसे कि (x % k)*(x / k) n के समान हो। तो यदि n और k क्रमशः 4 और 6 हैं, तो आउटपुट 10 होगा। तो (10 % 6) * (10 / 6) = 4। हम जानते हैं कि x % k का मान [1 से k - 1] की रेंज में होगा (0 शामिल नहीं) यहां हम उस रेंज में संभावित पूर्णांक

  1. - C++ प्रोग्राम: 'k' खोजें जैसे कि प्रत्येक एरे तत्व के साथ इसका मॉड्यूलस समान हो

    इस लेख में, हम एक प्रोग्राम पर चर्चा करेंगे जो एक पूर्णांक k खोजता है, जैसे कि दिए गए एरे के प्रत्येक तत्व के साथ इसका मॉड्यूलस समान हो। उदाहरण के लिए, मान लीजिए हमें एक एरे दिया गया है, arr = {12, 22, 32} तो हमारे पास आउटपुट मान k = 1, 2, 5, 10 होगा। y)। तब हमारे पास (y + अंतर) % k = y % k होगा।