یک معمای ریاضی و یک هک ساده!
شرح معما
دیروز داشتم در اینترنت می گشتم که به سایت خوب زومیت رسیدم در زومیت یک معما ریاضی – هوش مطرح شده که گفته بود:
آیا می‌توانید به کمک هشت عدد ۸، به عدد ۱۰۰۰ برسید؟ استفاده از هر نماد ریاضی در این رابطه مجاز است.
اگر به صورت عادی حل کنیم ، بهترین روش روش آزمون خطاست که در در هر بار حدسمون را بهتر می کنیم تا به جواب برسیم .ولی روش آزمون خطا مشکلی که داره خیلی وقت گیره و ممکنه خیلی زود به جواب برسیم یا خیلی دیر به جواب برسیم یا کلا به جواب نرسیم ، در ضمن در صورت سوال آمده آیا می توان ؟ پس یعنی ممکن است جوابی وجود نداشته باشد که روش آزمون خطا خیلی وقت گیر و بی فایده می شود.
من تصمیم گرفتم که برنامه ای بنویسم که تمام حالاتی را رو که می شود هشت رقم هشت را با هم جمع ، تفریق ،ضرب ، توان و رادیکال کرد را حساب کنم .
اول تصمیم گرفتم که رشته ای مانند :
1 | 8^8/8+8*8+8-8+8 |
درست کنم و مقدارش رو حساب کنم و اگر برابر هزار نشد علامت ها رو عوض کنم و دوباره محاسبه کنم .ولی این کار سه مشکل خیلی اساسی داشت :
۱ – بدون شک جواب دارای پرانتز است و پرانتز ترتیب محاسبه را عوض می کند و همین عبارت بالا را به دها روش می شه پرانتز گذاری کرد و پیدا کردن الگوریتمی که همه پرانتز گذاری ها رو برای همه ی عبارات انجام بده کار خیلی سختیه و خیلی خیلی زمان گیر است.
۲ – مشکل بعدی در حساب کردن عبارت است ، عملگر ها دارای تقدم هستند و با توجه به مکان و شرایطشون تو عبارت محاسباتی ، تقدمشون برای محاسبه فرق می کند ، و پیدا کردن و نوشتن کد برای این کار هم سخته و هم زمانگیر از نظر اجرا.
۳ – تولید تمام حالت های عملگر ها مشکل است.
راه حل معما !
ولی راه حل :
کامپایلر ها برای محاسبه یک عبارت آن عبارت رو با استفاده از گراف نمایش می دهند و بعد محاسبات رو با شکل prefix درخت انجام می دهند .
که بردن عبارت روی درخت شرایط خاصی می خواد و هر مرحله از ساخت درخت قرار دادن ریشه برای ساخت درخت می تونه درخت های متفاوتی بسازه.
فرض کنید ما عبارت :
1 | (8+6)/2-4 |
را روی درخت ببریم و به صورت درخت نمایش دهیم :
آنگاه نمایش Preorder درخت را بدست آوریم که می شود:
preorder یعنی اول ریشه بعد بچه چپ و بعد بچه راست .
1 | -/+8624 |
خوب کامپایلر ها از عبارت بالا که به دست آوردیم استفاده می کنند کنند و با استفاده از استک مقدار عبارت بالا را به روش زیر حساب می کنند :
همان طوری که می بینید جواب عبارت ۳ شد و اگر خودتان هم به صورت دستی عبارت اولیه را حساب می کردید جواب سه می شد .
ولی روی درخت بردن درخت و شکستن درخت کار مشکلی و هرچه عملگرها و پرانتز ها زیاد می شود تبدیل عبارت به درخت سختر و پیچیده تر می شود .
خوب از اونجایی که ما می خواهیم همه ی حالاتی که هشت رقم هشت را می توان با عملگرهای توان ، تقسیم ، ضرب ، جمع و تفریق و پرانتز ترکیب کرد را حساب کنیم مرحله ساخت عبارت و بردن روی درخت را حذف می کنیم و مستقیم تمام حالت ها ی نمایش prefix ممکن را می سازیم و بعد با استفاده از استک مقدارش را حساب می کنیم!!
مانند :
1 2 3 | ++/+*+-88888888 *+^*/^+88888888 +*-+^//88888888 |
ساخت همه ی حالات هم خودش مشکلی برای این کار :
به + مقدار ۰
به – مقدار ۱
به * مقدار ۲
به / مقدار ۳
به ^ (توان) مقدار ۴
را اختصاص می دهیم و بعد از این کار اعداد ۰۰۰۰۰۰۰ تا ۴۴۴۴۴۴۴ را در مبنای ۵ تولید می کنیم که هر کدام از آن اعداد نشان دهده نمایش خاصی از عملگر ها است مانند :
1 2 3 | ++/+*+-88888888 -->003020188888888 *+^*/^+88888888 -->204234088888888 +*-+^//88888888 -->021043388888888 |
اینم از این ! وقتی کد اجرا کردم متوجه شدم عملگر جذر را جا گذاشتم ، گرفتن ریشه مثلاً پنجم جز عملگر های مد نظر ما نیست چون باید عدد پنج بنویسیم و این دیگر هشت عدد هشت نیست ولی جذر یا همان ریشه دوم مجاز است چون ما در ریاضی قرار داد کردیم دو را ننویسیم از اون جایی که مجموع عدد ۱۰۰۰ می شود پس باید دوتا رادیکال هشت ضرب در هم داشته باشیم ،برای حل این مشکل یک عملگر دیگر تعریف کردم که جذر دو عدد را در هم ضرب کند و کدش را عدد ۵ گذاشتم .
تمام مشکلات حل شد حالا بریم سراغ کد نهایی!
پیاده سازی کد
آپدیت : کد من تمام حالت های پرانتز گذاری حساب نمی کرد .یکی از دوستان به اسم نیما کد قبلی اصلاح کرد در واقع کد جدیدی نوشت .
اولی کد منه و دومی کد آقا نیما:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | #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 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | //برنامه توسط نیما // 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 |
وقتی کد را اجرا کردن جواب زیر به دست اومد که اگر به حالت عادی درش بیاوریم این می شود :
پس با هشت تا هشت می شود به عدد هزار رسید این هم بعضی از جواب ها هست:
برای اینکه دلیل استفاده از کلمه هک را بدانید به این پست مراجعه کنید: معنای واقعی هک .
سلام داداشای هکر و خواهرهای(هکر)😂
من جوابم با شما احساس میکنم فرق میکنه تازه من اصلا از این کد ها استفاده نکردم😐
جواب
پرانتز باز هشت*هشت*هشت*جذر ششم هشت*هشت پرانتز بسته منهای پرانتز باز هشت+هشت+هشت پرانتز بسته
عالی بود داداش فکرت عالی بود موفق باشی
خیلی جالب بود. اگر اجازه دهید یک معمای مشابه را معرفی کنم که کمی سخت تر است و در کتاب هوش مصنوعی راسل و نورویش نوشته شده :
فرض کنید دنباله ای از چند عدد داریم مثل ۱،۳،۵،۷،۹ . یک روش جستجوی مناسب طراحی و پیاده سازی کنید که ضابطه عمومی دنباله ای را بیابد که این اعداد را تولید میکند. مثلا ضابطه عمومی دنباله فوق برابر است با:
f(n) = 2*n-1
خوشم اومد!
من با یه سرچ ساده توی گوگول زیر ۳۰ ثانیه جواب رو پیدا کردم! 🙂
۱۰۰۰=۸+۸+۸+۸۸+۸۸۸
تشکر 😀
روش شما هم درسته .از عملگر ترکیب استفاده کردید.
منم از تو راحتتر به نتیجه رسیدم کاری نداره طبق قوانین زبان ماشین ۱۰۰۰ همان دودویی عدد ۸ می باشد نیازی به سرچ نیست
avarin!
vali algoritmesh ziad booooood!
banabarin nakhondam 😀
این کد تغییر یافته‌ی کد خود شما هست که همه‌ی حالات پرانتز گذاری (همه‌ی prefix ها ) را حساب میکند. تابع make_tree() همه‌ی prefix ها را میسازد و تابع calculate() با stack نتیجه را حساب میکند … (برنامه کمی سنگین هست که فکر میکنم از تعداد زیاد prefix ها به ازای هر رشته‌ی عملگر ها باشه (۴۲۹ تا هست)
———————————-
کدی که اینجا گذاشتی همون کد خودمه فکر کنم هنگامی می خواستی کپی پیست کنی کد قبلی رو کپی کردی ، خیلی ممنون می شم کدت رو بدی بذارم.
فدایی داری 🙂
😀 😀
+me
۱۰۲۴ منهای ۲۴ میشه ۱۰۰۰
۲۴ که جمع ۳ تا ۸ است
۱۰۲۴ هم که ۲ به توان ۱۰ یا به عبارتی ۲به توان ۴ ضربدر ۲ به توان ۶
۲ به توان ۴ که برابر جمع ۲ تا ۸ است
۲ به توان ۶ هم که برابر ضرب ۲ تا ۸ است
در نتیجه
(۸+۸+۸) – ((۸+۸)*۸*۸)
یعنی همونی که شما بهش رسیدی
درسته .هر دو مون یک کار رو کردیم، شما حساب کردید که با هفتا هشت به عدد هزار هشت برسید و یک هشت ازش کم کردید که شده هشت تا هشت و عدد هزار ،من هم تقریبا همچین کاری کردم یعنی حساب کردم با هفت تا هشت به هزار برسم و بعد یکی از هشتا رو نوشتم رادیکال هشت ضرب در رادیکال هشت .
ولی جواب شما زیبا تر است.
جناب دلیرانی سایت بسیار خوبی داری . . . ماهم همکار و هم رشته شما هستیم . . . مطالب خوبتون رو دنبال خواهم کرد
تشکر آقای علیرضا ، از اینکه ما رو قابل دونستید که مطالبمون رو دنبال کنید.
واسم یه سوال پیش اومده.
شما میای A و B رو با هم جمع میکنی. مثلا داری: ۰۰۰۰۰۰۰۸۸۸۸۸۸۸۸
توی عملیات ریاضی prefix سه تا عملوند (عدد) کنار هم قرار نمیگیره شما الان ۸ تا عملوند رو کنار هم گذاشتی.
برای اینکه این مشکل رو دور بزنی اومدی از k و آرایه‌ی C استفاده کردی. و از توی آرایه‌ی C یک عملگر رو هر بار داخل پشته push میکنی و بعد pop میکنی. در واقع اصلا از پشته! و prefix هیچ استفاده‌ای نکردی.
نکته‌ی بعد هم اینه که شما گفتی که یکی از مشکلات هم استفاده از پرانتز‌ها بوده، در حالی که وقتی combination تمام حالات ریاضی رو برای ۸ عدد مشابه بخوای حساب کنی، اصلا پرانتز مطرح نمیشه.
موفق باشی.
http://open-mind.ir/wp-content/uploads/2014/04/DSC_1021.jpg
در نمایش پرفیکس محدودیتی برای کنار هم قرار گرفتن عملوندها نیست و می شه به تعداد عملگر ها عملوند کنار هم گذاشت در عکسی که گذاشتم یا از نمایش ها prefix سه عملوند کنار هم است .
همین طور تو عکس نحوه کار کرد استک کشیدم که دقیقا برنامه هم همون کار را می کند .
تشکر از نظر خوبتون.
این دوست ما تا اندازه‌ای حق داره … هر جایگشتی از عملگر ها و عملوندها یک محاسبه‌ی جدید هست در حالی که شما فقط یک حالت پرانتزگذاری را در نظر گرفتید (یک نوع درخت دودویی) به عنوان مثالی نقض عبارت :
((۸*۸)*(۸+۸))*((۸*۸)+(۸+۸)) = ۸۱۹۲۰
در الگوریتم شما جواب ندارد (شما فقط یک نوع پرانتز گذاری را در نظر گرفتید)
نیما من نگفتم که دوستمون اشتباه می گه ، گفتم که می شه تو پرقیکس بیش از دو عدد کنار هم قرار بگیره .و نحوه کار با استک رو نوشتم .بله شما درست می گویی کد من فقط پرانتز گذاری های خاصی حساب می کند. اگه اجازه بدی کد جدید رو جایگزین کنم؟
ایول حاجی 😀
تشکر
سلام، از چه IDE استفاده کردید؟
این بار استثنا از Code::blocks ( همیشه از ویژوال استدیواستفاده می کنم).
خیلی بی کاری 😀
خیلی خوب بود ،آفرین !
تشکر