ম্যাজিক স্কয়ার জেনারেট করার এলগরিদম

ম্যাজিক স্কয়ার জেনারেট করার এলগরিদম

শর্তসমূহঃ

১। ডাইমেনশন অবশ্যই বিজোড় হতে হবে। যেমন n  যদি ডাইমেনশন হয় তাহলে ৩*৩, ৫*৫, ৭*৭  এইরকম হতে হবে।

২। ডাইমেনশন n হলে উপাদানগুলোর যোগফল হবে=  (১ থেকে n*n পর্যন্ত যোগফল)/n
যেমনঃ উপরের চিত্রে সংখ্যাগুলোর যোগফল ১৫ ।

(১ থেকে n*n পর্যন্ত যোগফল) বের করার নিয়ম ঃ

ধরি, m=n*n

(১ থেকে n*n পর্যন্ত যোগফল) = m*(m+1)/2

n*n পর্যন্ত মানগুলোর পজিশন বের করতে হবে।

৩। প্রথমে ১ এর পজিশন হবে = (n/2,n-1)=(i,j)

৪। পরবর্তী নম্বরগুলোর রো ও কলাম পজিশন হবে= (i-1,j+1)

৫। যদি সারির পজিশন -১ হয় তাহলে আসল পজিশন হবে   i=n-1

৬। যদি কলামের পজিশন n এর সমান হয় তাহলে আসল পজিশন হবে   j=n-n=0

৭। যদি (i,j) এর মান লিস্ট এ অলরেডি এক্সিস্ট থাকে তাহলে পজিশন হবে = (i+1,j-2)

৮। যদি  একই সাথে সারির পজিশন -১ হয় এবং কলামের পজিশন n এর সমান হয় তাহলে

আসল পজিশন হবে = (0,n-2)

এখন ৩*৩ এর ম্যাজিক স্কয়ার জেনারেট করব এই নিয়মে ঃ

উপাদানগুলোর যোগফল ঃ      (১ থেকে n*n পর্যন্ত যোগফল)/n=45/3=15

 নম্বর ১ এর পজিশন = (n/2,n-1)=(3/2,3-1)=(1,2)

 নম্বর ২ এর পজিশন = (i-1,j+1)=(1-1,3+1)=(0,3)

       

যেহেতু j=n তাই j=3-3=0

নম্বর ২ এর পজিশন = (i,n-n)=(0,3-3)=(0,0)

 নম্বর ৩ এর পজিশন = (i-1,j+1)=(0-1,0+1)=(-1,1)

যেহেতু i=-1 তাই i=n-1=3-1=2

নম্বর ৩ এর পজিশন = (n-1,j)=(2-1,1)=(2,1) 

অর্থাৎ i=-1 যখন হয়েছিলো তখন j এর মান যা ছিল তাই থাকবে। 

নম্বর ৪  এর পজিশন= (i-1,j+1)=(2-1,1+1)=(1,2)

যেহেতু  (1,2) অলরেডি এক্সিস্ট তাই

নম্বর ৪  এর পজিশন  i=i+1 , j=j-2 , (i,j)= (1+1,2-2)=(2,0)

নম্বর ৫  এর পজিশন= (i-1,j+1)=(2-1,0+1)=(1,1)

নম্বর ৬  এর পজিশন= (i-1,j+1)=(1-1,1+1)=(0,2)

নম্বর ৭  এর পজিশন= (i-1,j+1)=(0-1,2+1)=(-1,3)

যেহেতু i=-1 এবং j=n তাই i=0, j=n-2=3-2=1

নম্বর ৭ এর পজিশন = (0,n-2)=(0,3-2)=(0,1)

নম্বর ৮ এর পজিশন = (i-1,j+1)=(0-1,1+1)=(-1,2)

যেহেতু i=-1 তাই i=n-1=3-1=2

নম্বর ৮ এর পজিশন = (n-1,j)=(2-1,2)=(2,2)

নম্বর ৯ এর পজিশন = (i-1,j+1)=(2-1,2+1)=(1,3)

যেহেতু j=n তাই j=3-3=0

নম্বর ৯ এর পজিশন = (i,n-n)=(1,3-3)=(1,0)

৩*৩=৯ পর্যন্ত মান বের করা শেষ। এখন ম্যাজিক স্কয়ার এ মানগুলো পজিশন অনুযায়ী বসিয়ে পাই

 UVA 1266 নম্বর প্রব্লেম এ ম্যাজিক স্কয়ার জেনারেট করতে বলা হয়েছে । ম্যাজিক স্কয়ার জেনারেট

 করার সি++ কোড টি  এখানে  http://shawonruet.blogspot.com/2016/06/uva-1266-magic-square.html

 পাওয়া যাবে। এই এলগরিদম দিয়েই সল্ভ করা হয়েছে ।

Download Coding Interview Book and Get More Tutorials for Coding and Interview Solution: Click Here

Download System Design Interview Book and Get More Tutorials and Interview Solution: Click Here

Do you need more Guidance or Help? Then Book 1:1 Quick Call with Me: Click Here

Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge. Learn More: Click Here