دیروز داشتم در اینترنت می گشتم که به سایت خوب زومیت رسیدم در زومیت یک معما ریاضی – هوش مطرح شده که گفته بود:
آیا میتوانید به کمک هشت عدد ۸، به عدد ۱۰۰۰ برسید؟ استفاده از هر نماد ریاضی در این رابطه مجاز است.
اگر به صورت عادی حل کنیم ، بهترین روش روش آزمون خطاست که در در هر بار حدسمون را بهتر می کنیم تا به جواب برسیم .ولی روش آزمون خطا مشکلی که داره خیلی وقت گیره و ممکنه خیلی زود به جواب برسیم یا خیلی دیر به جواب برسیم یا کلا به جواب نرسیم ، در ضمن در صورت سوال آمده آیا می توان ؟ پس یعنی ممکن است جوابی وجود نداشته باشد که روش آزمون خطا خیلی وقت گیر و بی فایده می شود.
من تصمیم گرفتم که برنامه ای بنویسم که تمام حالاتی را رو که می شود هشت رقم هشت را با هم جمع ، تفریق ،ضرب ، توان و رادیکال کرد را حساب کنم .
اول تصمیم گرفتم که رشته ای مانند :
8^8/8+8*8+8-8+8
درست کنم و مقدارش رو حساب کنم و اگر برابر هزار نشد علامت ها رو عوض کنم و دوباره محاسبه کنم .ولی این کار سه مشکل خیلی اساسی داشت :
۱ – بدون شک جواب دارای پرانتز است و پرانتز ترتیب محاسبه را عوض می کند و همین عبارت بالا را به دها روش می شه پرانتز گذاری کرد و پیدا کردن الگوریتمی که همه پرانتز گذاری ها رو برای همه ی عبارات انجام بده کار خیلی سختیه و خیلی خیلی زمان گیر است.
۲ – مشکل بعدی در حساب کردن عبارت است ، عملگر ها دارای تقدم هستند و با توجه به مکان و شرایطشون تو عبارت محاسباتی ، تقدمشون برای محاسبه فرق می کند ، و پیدا کردن و نوشتن کد برای این کار هم سخته و هم زمانگیر از نظر اجرا.
۳ – تولید تمام حالت های عملگر ها مشکل است.
ولی راه حل :
کامپایلر ها برای محاسبه یک عبارت آن عبارت رو با استفاده از گراف نمایش می دهند و بعد محاسبات رو با شکل prefix درخت انجام می دهند .
که بردن عبارت رو ی درخت شرایط خاصی می خواد و هر مرحله از ساخت درخت قرار دادن ریشه برای ساخت درخت می تونه درخت های متفاوتی بسازه.
فرض کنید ما عبارت :
(8+6)/2-4
را روی درخت ببریم و به صورت درخت نمایش دهیم :
آنگاه نمایش Preorder درخت را بدست آوریم که می شود:
preorder یعنی اول ریشه بعد بچه چپ و بعد بچه راست .
-/+8624
خوب کامپایلر ها از عبارت بالا که به دست آوردیم استفاده می کنند کنند و با استفاده از استک مقدار عبارت بالا را به روش زیر حساب می کنند :
همان طوری که می بینید جواب عبارت ۳ شد و اگر خودتان هم به صورت دستی عبارت اولیه را حساب می کردید جواب سه می شد .
ولی روی درخت بردن درخت و شکستن درخت کار مشکلی و هرچه عملگرها و پرانتز ها زیاد می شود تبدیل عبارت به درخت سختر و پیچیده تر می شود .
خوب از اونجایی که ما می خواهیم همه ی حالاتی که هشت رقم هشت را می توان با عملگرهای توان ، تقسیم ، ضرب ، جمع و تفریق و پرانتز ترکیب کرد را حساب کنیم مرحله ساخت عبارت و بردن روی درخت را حذف می کنیم و مستقیم تمام حالت ها ی نمایش prefix ممکن را می سازیم و بعد با استفاده از استک مقدارش را حساب می کنیم!!
مانند :
++/+*+-88888888 *+^*/^+88888888 +*-+^//88888888
ساخت همه ی حالات هم خودش مشکلی برای این کار :
به + مقدار ۰
به – مقدار ۱
به * مقدار ۲
به / مقدار ۳
به ^ (توان) مقدار ۴
را اختصاص می دهیم و بعد از این کار اعداد ۰۰۰۰۰۰۰ تا ۴۴۴۴۴۴۴ را در مبنای ۵ تولید می کنیم که هر کدام از آن اعداد نشان دهده نمایش خاصی از عملگر ها است مانند :
++/+*+-88888888 -->003020188888888 *+^*/^+88888888 -->204234088888888 +*-+^//88888888 -->021043388888888
اینم از این ! وقتی کد اجرا کردم متوجه شدم عملگر جذر را جا گذاشتم ، گرفتن ریشه مثالا پنجم جز عملگر های مد نظر ما نیست چون باید عدد پنج بنویسیم و این دیگر هشت عدد هشت نیست ولی جذر یا همان ریشه دوم مجاز است چون ما در ریاضی قرار داد کردیم دو را ننویسیم از اون جایی که مجموع عدد ۱۰۰۰ می شود پس باید دوتا رادیکال هشت ضرب در هم داشته باشیم ،برای حل این مشکل یک عملگر دیگه تعریف کردم که جذر دو عدد را در هم ضرب کند و کدش را عدد ۵ گذاشتم .
تمام مشکلات حل شد حالا بریم سراغ کد نهایی :
آپدیت : کد من تمام حالت های پرانتز گذاری حساب نمی کرد .یکی از دوستان به اسم نیما کد قبلی اصلاح کرد در واقع کد جدیدی نوشت .
اولی کد منه و دومی کد آقا نیما:
#include <iostream> #include <string> #include <stack> #include <cmath> using namespace std; //این تابع به یک عدد که به صورت رشته است یکی اضافه می کند ، عدد مبنای شیش است void add(string &B) { int temp=0; for(int i=B.size()-1;i>=0;i--) { temp = B[i]-48 + 1; if(temp<=5) { B[i]++; break; } else { B[i]='0'; } } } int main() { string A="88888888";//هشت تا هشت string B="0000000";//عملگرها string C; stack <float>mystack;//استک float temp1; float temp2; float temp3; float sum; float mul; int k; while(B!="5555555")//این حلقه تمام به اندازه تمام حالات اجرا می شود { C = B + A; for(int i=0;i<8;i++) { mystack.push(C[i]-48); } k=8; while(mystack.size()!=1) { mystack.push(C[k]-48);//پوش کردن در استک temp1 = mystack.top();//خواندن خانه آخر استک mystack.pop();//حذف کردن خانه آخر استک temp2 = mystack.top(); mystack.pop(); temp3 = mystack.top(); mystack.pop(); //open-mind.ir switch((int)temp3) { case 0://+ { mystack.push(temp1+temp2); break; } case 1://- { mystack.push(temp2-temp1); break; } case 2://* { mystack.push(temp1*temp2); break; } case 3:// / { mystack.push(temp2/temp1); break; } case 4:// * { mul = (float)pow(temp2,temp1); mystack.push(mul); break; } case 5:// جذر اولی را ضرب در جذر دومی می کند { mul = (float)pow(temp1,0.5)*(float)pow(temp2,0.5); mystack.push(mul); break; } } k++; } //open-mind.ir sum = mystack.top(); mystack.pop(); if (sum == 1000) { for(int i=0;i<7;i++) { cout<<B[i]; } cout<<" "<<sum<<endl; } add(B); //cout<<B<<endl; string C=""; } return 0; } //open-mind.ir
//برنامه توسط نیما // nima.b.92 روی جیمیل #include <iostream> #include <string> #include <stack> #include <cmath> using namespace std; //این تابع به یک عدد که به صورت رشته است یکی اضافه می کند ، عدد مبنای شیش است void calculate (string &C) { stack <float>mystack;//استک stack <string>mystack2; string s1; string s2; string sum2; float temp1; float temp2; float temp3; float sum; float mul; for (int i=0 ; i<15; i++) { temp3=int(C[i]-48); if (temp3==8){ mystack.push(temp3); //mystack2.push(to_string(temp3)); // need c++ 11 library // که در کدبلاکس باید فعالش کرد با چند کلیک mystack2.push("8"); //mystack2.push(""); } else{ temp1 = mystack.top();//خواندن خانه آخر استک s1 = mystack2.top();//خواندن خانه آخر استک mystack.pop();//حذف کردن خانه آخر استک mystack2.pop();//حذف کردن خانه آخر استک temp2 = mystack.top(); s2 = mystack2.top(); mystack.pop(); mystack2.pop(); //mystack.push(temp1+temp2); switch((int)temp3) { case 0://+ { mystack.push(temp1+temp2); mystack2.push("("+s2+"+"+s1+")"); break; } case 1://- { mystack.push(temp2-temp1); mystack2.push("("+s2+"-"+s1+")"); break; } case 2://* { mystack.push(temp1*temp2); mystack2.push("("+s2+"*"+s1+")"); break; } case 3:// / { mystack.push(temp2/temp1); mystack2.push("("+s2+"/"+s1+")"); break; } case 4:// * { mul = (float)pow(temp2,temp1); mystack.push(mul); mystack2.push("("+s2+"^"+s1+")"); break; } case 5:// جذر اولی را ضرب در جذر دومی می کند { mul = (float)pow(temp1,0.5)*(float)pow(temp2,0.5); mystack.push(mul); mystack2.push("(sqrt("+s2+")*sqrt("+s1+")"); break; } } } //cout<<endl<<"------"<<endl; //cout<<mystack.top(); } sum = mystack.top(); sum2 = mystack2.top(); mystack.pop(); mystack2.pop(); //cout<<sum ; if (sum == 1000) { for(int i=0;i<15;i++) { cout<<C[i]; } cout<<" "<<sum<<endl; cout<<sum2<<endl; } //cout<<endl ; } void make_tree(string &A,string &B,string &C,int a,int b){ while (a!=A.size() && b!=B.size()){ if ((a-b)>1){ C[a+b]=A[a]; a++; make_tree (A,B,C,a,b); a--; C[a+b]=B[b]; b++; make_tree (A,B,C,a,b); return; } else { C[a+b]=A[a]; a++; } } for (int i=a;i<A.size();i++){ C[a+b]=A[a]; a++; } for (int i=b;i<B.size();i++){ C[a+b]=B[b]; b++; } /*for(int i=0;i<a+b-2;i++) cout<<C[i] ; cout<<endl; */ calculate(C); } void add(string &B) { int temp=0; for(int i=B.size()-1;i>=0;i--) { temp = B[i]-48 + 1; if(temp<=5) { B[i]++; break; } else { B[i]='0'; } } } int main() { //cout<<"before"; string A="88888888";//هشت تا هشت string B="0000000";//عملگرها string C=A+B; stack <float>mystack;//استک stack <string>mystack2; float temp1; float temp2; float temp3; float sum; float mul; int k; //string test =A+B; //make_tree(A,B,test,0,0); //cout<<test<<endl; //calculate(test); while(B!="5555555")//این حلقه تمام به اندازه تمام حالات اجرا می شود { //cout<<"test" ; make_tree(A,B,C,0,0); add(B); //string test =A+B; //calculate(test); //cout<<B<<endl; //string C=""; } return 0; } //open-mind.ir
وقتی کد را اجرا کردن جواب زیر به دست اومد که اگر به حالت عادی درش بیاوریم این می شود :
پس با هشت تا هشت می شود به عدد هزار رسید این هم بعضی از جواب ها هست:
این هم ران از برنامه(با کلیک عکس را در اندازه اصلی ببینید):
برای اینکه دلیل استفادده از کلمه هک را بدانید به این پست مراجعه کنید: معنای واقعی هک .