की गणना करने में ज्ञापन का उपयोग कैसे करें मुझे एक प्रोग्राम दिया गया है, जिसके लिए मुझे मैट्रिक्स के लिए पिछले राज्य की संख्या की गणना करने की आवश्यकता है।बड़ी संख्या में मैट्रिक्स
दिए गए मैट्रिक्स एक बूलियन मैट्रिक्स है। कार्यक्रम की व्याख्या करने के लिए false के लिए true और 0 का उपयोग करूंगा।
एक मैट्रिक्स में एक सेल के अगले राज्य 1 है अगर, इन चार कोशिकाओं पर विचार:
- सेल ही
- यह करने के लिए सही सेल
- इसके नीचे
- सेल इसके नीचे सेल, और इसके दाएं,
इन सभी 4 कोशिकाओं में केवल एक 1 है, मैं एई, इन 4 कोशिकाओं में बिल्कुल 3 0 एस और बिल्कुल 1 1 हैं।
अगर दिया मैट्रिक्स (एम) है:
1 1 0 0 0 0 0 1 0 0 1 0
तो पहले सेल के लिए (एम [0] [0]), पर विचार किया जा करने के लिए चार कोशिकाएं होती हैं एम [0] [0], एम [0] [1], एम [1] [0] और एम [1] [1]। तो, पहले सेल का अगला राज्य 0 है, क्योंकि हमारे पास इन 4 कोशिकाओं में 2 1 है।
दूसरे सेल (एम [0] [1]) के लिए, चार कोशिकाओं को माना जाना चाहिए एम [0] [1], एम [0] [2], एम [1] [1], एम [1] [2]। तो इस सेल के लिए अगला राज्य 1 है क्योंकि इन चार कक्षों में केवल 1 1 है।
इस तरह, इस मैट्रिक्स (एम) के लिए अगले राज्य जा रहे हैं मैट्रिक्स (एन) होगा:
0 1 1 0 1 0
अगले राज्य, जाहिर है, 1 पंक्ति और 1 स्तंभ से कम होगी पिछला राज्य
1 0 1 0 1 0 0 0 1 1 0 0
भी अगले राज्य एन
मैं गिनती करने के लिए है होगा: इस प्रकार, मैट्रिक्स की दी गई राज्य मैट्रिक्स एम, यह देखते हुए मैट्रिक्स के साथ पिछले कई राज्यों, उदाहरण के लिए हो सकता है पिछले राज्यों की संख्या जो एक दिए गए मैट्रिक्स में है।
public class Answer2 {
static boolean[][] main_array,answer_array; // answer_array is the 2D array given to me. main_array is the 2D array which I recurse through, and then find its solution to compare with answer_array.
static int c; // counter
static int answer_array_height,answer_array_width; // matrix height and matrix width
public static int answer(boolean[][] boolean_array)
{
answer_array = boolean_array;
main_array = new boolean[answer_array.length+1][answer_array[0].length+1];
c=0;
answer_array_height = answer_array.length;
answer_array_width = answer_array[0].length;
recurse(1,1);
main_array[0][0] = true;
recurse(1,1);
return c;
}
public static String pad(String s, int l){ //Add 0's to the beginning of the string till its length equals l
for(int i=s.length(); i<l; i++)
s='0'+s;
return s;
}
public static void recurse(int w, int h){
if(w==answer_array_width+1 && h==answer_array_height+1){
c++;
return;
}
//System.out.println(java.util.Arrays.deepToString(main_array).replace("],","],\n").replace("true","1").replace("false","0"));
if(h==answer_array_height+1 || h>=w){//Add column
int x = 0;
for(int i=0; i<h; i++) x+=(int)Math.pow(2,i); //This will give me the integer representation of max value(whose binary representation will be used to put values in the matrix) to handle.
for(int i=0; i<=x; i++){
String str = pad(Integer.toBinaryString(i),h);
for(int j=0; j<h; j++){
main_array[j][w]= str.charAt(j)=='1'; //set main_array[j][w] true wherever the binary representation of i has 1. This recurses through all the combinations.
}
if(check(w+1,h,false)){
recurse(w+1, h);
}else{
for(int j=0; j<h; j++){
main_array[j][w]=false;
}
}
}
}else{//Add row
int x = 0;
for(int i=0; i<w; i++) x+=(int)Math.pow(2,i);
for(int i=0; i<=x; i++){
String str = pad(Integer.toBinaryString(i),w);
for(int j=0; j<w; j++){
main_array[h][j]= str.charAt(j)=='1';
}
if(check(w,h+1,true)){
recurse(w, h+1);
}else{
for(int j=0; j<w; j++){
main_array[h][j]=false;
}
}
}
}
}
// w is the effective width, h is the effective height, height_was_increased is true if height was increased, false if width was increased.
//height_was_increased helps to shorten the time used for comparison as the matrix was correct before the width or height was increased. So it just needs to check the increased portion.
public static boolean check(int w, int h, boolean height_was_increased){
if(height_was_increased){
for(int j=0; j<w-1; j++){
//I know this part is complex. It just finds out the answer of the four cells to be considered and matches it with the given matrix.
if(answer_array[h-2][j] != (main_array[h-2][j]^main_array[h-2+1][j]^main_array[h-2][j+1]^main_array[h-2+1][j+1] && !(main_array[h-2][j] && main_array[h-2+1][j]) && !(main_array[h-2][j+1] && main_array[h-2+1][j+1]))) return false;
}
}else{
for(int i=0; i<h-1; i++){
if(answer_array[i][w-2] != (main_array[i][w-2]^main_array[i+1][w-2]^main_array[i][w-2+1]^main_array[i+1][w-2+1] && !(main_array[i] [w-2] && main_array[i+1][w-2]) && !(main_array[i][w-2+1] && main_array[i+1][w-2+1]))) return false;
}
}
return true;
}
}
यह मूल रूप से क्या करता है, यह है कि यह (अपनी अगली राज्य मैट्रिक्स के लिए कहा देने के लिए के लिए उपयुक्त आकार के) एक खाली मैट्रिक्स के साथ शुरू होता है और से शुरू होता है:
मैं निम्नलिखित कोड लिखा है शीर्ष बाएं कोने, वैकल्पिक चौड़ाई और ऊंचाई को 1 से वैकल्पिक रूप से बढ़ाकर, और जांच कर रहा है कि अब तक मैट्रिक्स की अगली स्थिति, दी गई स्थिति से मेल खाती है। यदि नहीं, तो यह शेष मैट्रिक्स को छोड़ देता है। फिर, यदि ऐसा मैट्रिक्स पाया जाता है, जिसका अगला राज्य दिए गए राज्य के समान होता है, तो यह काउंटर को 1.
यह कोड छोटे मैट्रिस के लिए काम करता है (कक्ष < 40 से अधिक नहीं), लेकिन इसमें बहुत कुछ लगता है बड़े matrices के लिए समय।मैट्रिक्स की अधिकतम चौड़ाई 50 हो सकती है और अधिकतम ऊंचाई 9 हो सकती है। तो, यह कोड उस उद्देश्य के लिए काफी उपयुक्त नहीं है।
मुझे पता है कि मुझे यहां यादों का उपयोग करना है (c++ कर रहा है हजारों बार सही नहीं है!) लेकिन मैं कल्पना नहीं कर सकता कि इसका उपयोग कैसे करें। मैंने पहले गतिशील प्रोग्रामिंग का उपयोग करके प्रोग्राम लिखे हैं, लेकिन मुझे पता नहीं है कि इसका उपयोग यहां किया जाएगा। किसी भी सहायता की सराहना की जाएगी।
संपादित करें: प्रस्तुत करने की समय सीमा को पार कर गया है, और मैं इस सवाल का जवाब प्रस्तुत नहीं कर सका। : '(
लेकिन, मैं अभी भी जवाब जानना चाहता हूं ताकि मैं भविष्य में ऐसे कार्यक्रमों को हल कर सकूं। मुझे पूरा कोड की आवश्यकता नहीं है, लेकिन आगे बढ़ने के बारे में कुछ मदद भी होगी! :)
जब आप ने कहा, "इस तरह से जा रहे हैं, इस सेल के लिए अगले राज्य मैट्रिक्स (एन) होगा" तुम मुझे खो दिया है। * सेल * ए * मैट्रिक्स * की अगली स्थिति कैसी है? –
@ मार्टिन ब्रॉडहर्स्ट मुझे बहुत खेद है। मेरा कहना था "इस तरह से जा रहा है, इस मैट्रिक्स (एम) के लिए अगला राज्य मैट्रिक्स (एन) होगा"। मैंने इसे अभी संपादित किया है। – Hackerdarshi
ठीक है, यह जानने के लिए कुछ समय लगा कि आप क्या हासिल करने का प्रयास करते हैं। दुर्भाग्य से प्रदान किया गया कोड केवल भयानक है, क्योंकि यह पैरामीटर/चर/विधियों के उद्देश्य पर कोई जानकारी प्रदान नहीं करता है। यह सब अर्थहीन नामों और संक्षेपों से छिपा हुआ है। साथ ही, आप पहले ही देख चुके हैं, कि एक पूर्णांक सरणी के साथ काम करते समय समझना आसान हो जाता है। आप उस ज्ञान को अपने कोड पर क्यों लागू नहीं करते? –