یه الگوریتم که مخ انیشتین رو می خواد

[m_mov_sia3]

سلام به مهندسین و بر و بچ!
یه الگوریتم رو می خوام پیاده کنم ولی حسابی تووش موندم
این برنامه باید یه عدد مثلاً از 1 تا 1000 از ورودی بگیره و با اعداد (1 تا 9 ) با انواع حالتهای (+ و - و * و / ) بگه که چه جوری اوون عدد ورودی ساخته می شه.
مثلا اگه بهش بدیم 14، تمام حالتهایی که 14 با اعداد زیر 1000 تولید میشه رو بهمون بده:
شبیه این حالتها:
14=4+2*5
14=6-5*4
...

خدایی خودم که گیج شدم دیگه :ناراحت:
اگه کسی بلده و یگه بزرگترین ثواب دنیا رو کرده !!

[alireza643]

برای ضربش اگر من میخواستن انجام بدم این کار رو میکردم اول همه مقسوم علیه های عدد رو به دست میآوردم.
مثلا برای 14 میشه 1و2و7و14 بعد حاصل ضرب رو مینوشتم.
1*14 = 14
2 * 7 = 14
بعد این کار رو تو یه حلقه به این شکل ادامه میدادم که شرع میکردم یکی یکی از عدد کم میکردم و مقسوم علیه های اون عدد رو بدست می آوردم و حاصل ضرب اون ها رو به علاوه ی عدد کم شده میکردم.
مثلا برای 14 برای تکرار اول حلقه 14 - 1 = 13 میشه و میدونید که 13 فقط به خودش بخش پذیره پس میشه
13 * 1 + 1 = 14
برای تکرار دوم حلقه باید 14-2 = 12 بشه و مقسوم علیه های 12 اعداد 1و2و3و4و6و12 هست که برای این عدد داریم
12 * 1 + 2 = 14
2 * 6 + 2 = 14
3 * 4 + 2 = 14
حالا این حلقه تا صفر ادامه پیدا میکنه و تمام راه های به دست اومدن اون عدد با اعداد کوچک تر از خودش به دست میآد.
حالا یه حلقه افزایشی درست کن و همین کار رو برای اعداد بزرگتر ولی انجام بده ولی به جای جمع کردن این بار تفریق کن.
مثلا 14 + 1 = 15 که مقسوم علیه های 15 اعداد 1و3و5و15 هستن حالا داریم
15 * 1 - 1 = 14
3 * 5 + 1 = 14
بار دوم و عد 16 که مقسوم علیه های اون 1 و 2 و 4 و8 16 هستن
1*16 - 2 = 14
2 * 8 - 2 = 14
4 * 4 - 2 = 14
این حلقه هم تا 1000 ادامه پیدا میکنه.
امید وارم یه کمی از مشکلاتت حل بشه.

[ne0l3oy]

سلام

خوب یه مقداری سوالتون مبهم چون نگفتین اعداد تکراری هم می تونن بیان یا اینکه هر تعداد جمع و تفریق می شده استفاده کرد یا نه ؟‌ مثلا بی نهایت بار می شه جمع و تفریق کرد تا بخوایم اون عدد و بسازیم اما خوب اگه استفاده محدود باشه یا اینکه اعداد غیر تکراری باشن اولین راه بدیهی برای این مساله BackTracking‌ هستش که شما اعداد 1 تا 9 رو تمام حالات مختلفشو بررسی می کنین ،‌اما اگه مساله محدودتر بشه احتمالا با راه حل های ساده تری مثل داینامیک زدن و .... حلش کرد . . . البته بهتره یه رجوعی به کتاب CLRS بکنین .

موفق باشین

[alireza643]

با انواع حالتهای (+ و - و * و / ) بگه که چه جوری اوون عدد ورودی ساخته می شه.

این جا که عملگر ها رو معرفی کردن محدودیت نگذاشتن پس احتمالا محدودیت تو استفاده از نوع و تعداد عملگر ها نداریم.
جایی که ابهام هست اینجاست که گفتن


با اعداد (1 تا 9 )

و خط بعدی گفتن:


تمام حالتهایی که 14 با اعداد زیر 1000 تولید میشه رو بهمون بده

اینجا نفهمیدم با اعداد 1 تا 9 یا با هر عددی زیر هزار.


‌اما اگه مساله محدودتر بشه احتمالا با راه حل های ساده تری مثل داینامیک زدن و .... حلش کرد .

میشه یکی از این همه راه حل رو که به جاش ... نقطه گذاشتید رو دربارش یه کم توضیح بدید ؟
قصد جسارت ندارم این سوال رو پرسیدم فقط به این خاطر که این مسئله یه مقدار سخته و فکر نمیکنم که این همه راه حل داشته باشه و تو کتاب هم اومده باشه.

[eyes_shut_number1]

دیدی! بچه ها از انیشتین هم خفن ترن!
منم موافقم با این

[alireza643]

با کدوم موافقی؟ با این که مسئله راه حل های زیادی داره و میشه به روش های خیلی ساده اون رو حل کرد؟

[Arman_1367]

سلام به مهندسین و بر و بچ!
یه الگوریتم رو می خوام پیاده کنم ولی حسابی تووش موندم
این برنامه باید یه عدد مثلاً از 1 تا 1000 از ورودی بگیره و با اعداد (1 تا 9 ) با انواع حالتهای (+ و - و * و / ) بگه که چه جوری اوون عدد ورودی ساخته می شه.
مثلا اگه بهش بدیم 14، تمام حالتهایی که 14 با اعداد زیر 1000 تولید میشه رو بهمون بده:
شبیه این حالتها:
14=4+2*5
14=6-5*4
...

خدایی خودم که گیج شدم دیگه :ناراحت:
اگه کسی بلده و یگه بزرگترین ثواب دنیا رو کرده !!
به نظر من بهترین راه اینه که اول از همه عدد را تجزیه کنی بعد با توجه به توانها و اعداد پایه با یک حلقه خیلی کوچیکتر از 1000 دور اعداد کوچکتر را به دست آوردی .
اما به دست آوردن جمع ها و تفریق ها کافی بعد از مراحل فوق یک حلقه بنویسی که هر دفعه یک واحد به عدد اضافه کنه تا در آخر 9 واحد اضافه کرده باشه و برای تمام آنها تمام این حالات ضرب را حساب کنی و در آخر برای رسیدن به عدد مورد نظر به اندازه اضافه شده از حاصل ضرب کم کنی و برای جمع ها کافیه از 1 تا 9 ازش کم بشه بعد مقادیر حساب بشه به اندازه مقدار کم شده به حاصل هر ضرب اضافه کنی همین.کار زیاد سختی نیست.
و اما
برای اعداد بزرگتر هم کافیه اعدادی که بر عدد مورد نظر بخش پذیر هستند را بیابی الگریتمهای سریع زیادی وجود داره اما آقای شل دو یا سه تا الگریتم خیلی خفن داره حالشو ندارم توضیح بدم.بعد حالت های تقسیم برابر این اعداد تقسیم بر خارج قسمت آنها بر عدد اولیه می شود فکر کنم بهتر از این باشه که بخواهیم با حلقه ها ی طولانی این کار را بکنیم.

[alireza643]

خوب شما که میگید به حلقه ی هزار تایی نیاز نیست همون کار بالا رو دارید تکرار میکنید با این تفاوت که اول اعداد رو دست بندی میکنید بعد همون عملیات بالا رو روی تمامشون انجام میدید. مثلا برای 15 اول عدد رو تجزیه میکنی که میشه 1و3و5 بعد همون عملیات بالا رو برای این اعداد انجام میدی اینطوری اگر در مجموع تعداد حلقه ها شمرده بشه همون هزار دوره فقط کاری که انجام شده اضافه شدن مرحله ی تجزیه کردن اعداد.
کاری که شما کردید از 1 تا 3 سه بار تکرار. از 3 تا 5 دو بار تکرار از 5 تا 15 هم 10 بار تکرار که در مجموع میشه 15.
چیزی هم که من گفتم برای هر عدد در هر صورت حلقه 1000 تایی میشد. یعنی برای اعداد کوچکتر به تعداد خود عدد و برای بزرگترها به تعداد 1000 منهای عدد.

[Arman_1367]

اگر کد هر دو را بنویسید بعد از اجرا متوجه می شید که روش شما خیلی وقت گیره دوم اینکه شما گفتید یکی یکی عدد را با 1 جمع کنیم تا به هزار برسیم من گفتم تا 9 واحد اضافه بشه چون من مبنا را بر این گذاشتم که اعداد کوچکتر مساوی 9 باشه پس در مجموع 18 دور داریم که در 9 تا یک واحد کم میشه و در 9 تا دیگه یک واحد به عدد اصلی اضافه می شه نه هزار دور برای اعداد بزرگتر هم که من طبق فرضی اعداد کوچکتر از 9 اصلاً عملی را در نظر نگرفتم و فقط به یک توضیح در صورتی که نیاز داشتن اکتفا کردم. در ضمن من که کلکل نمی کنم. اگه اسرار دارید روش شما بهتره خوب کد همون روش را استفاده کنید.

[alireza643]

من هم قصد کل کل ندارم فقط من هرچی نوشته های خودم و شما رو بررسی میکنم میبینم که از لحاظ زمانی تفاوتی نمیکنه. شاید هم من نمیفهمم منظور شما چی بوده. یه کم بیشتر توضیح میدادی شاید متوجه میشدم.
ببینید شما میگید مبنا رو گذاشتید که اعداد کوچتر از 9 باشن یعنی اعداد زیر هزار اگر تجزیه بشن مقداری بیشتر از 9 ندارن. چون تا جایی که یادمه برای تجزیه اعداد خودمون رو به اعداد اولی که کوچکتر مساوی خودشون بودن تقسیم میکریم. مثلا برای 111 یکی از اعدادی که به دست میاد 3 و دیگری 37 خوب الان 37 از 9 بزرگتره و تجزیه پذیر هم نیست. برای این باید چی کار کرد؟

[someCoder]

اگر کد هر دو را بنویسید بعد از اجرا متوجه می شید که روش شما خیلی وقت گیره

من هرچی نوشته های خودم و شما رو بررسی میکنم میبینم که از لحاظ زمانی تفاوتی نمیکن
و اینگونه بود که مفهوم Order کشف شد!

[alireza643]

و اینگونه بود که مفهوم Order کشف شد!
گویا شما متوجه شدید که اشکال کار ما کجاست یا اینکه کجا اشتباه داریم که حرف های همدیگه رو متوجه نمیشیم.
خوب یه کم راهنمایی کنید. یه لینکی یه مقاله ای یه دو سه خط توضیح ...
شاید میترسی اون بلوط از دستت بیوفته؟(البته قصد جسارت به اساتید نیست فقط یه شوخی که امید وارم ناراحت نشید)

[Arman_1367]

ببین بزار مسئله را متوجه بشم.

این برنامه باید یه عدد مثلاً از 1 تا 1000 از ورودی بگیره و با اعداد (1 تا 9 ) با انواع حالتهای (+ و - و * و / ) بگه که چه جوری اوون عدد ورودی ساخته می شه.

خوب فرض کن عددی را تجزیه کردیم و تمام اعداد اول حاصله کوچکتر از 9 بود مشکلی که نیست. خوب حالا شروع می کنیم هی 1 واحد 1 واحد کم می کنیم و دوباره تجزیه و ... تا 9 واحد کم شود و بعد هم جمع ها.
در این قسمت هر دو اشتراک نظر داشتیم.
حالا فرض کنید عددی تجزیه شد و یکی از عامل ها بزرگتر از 9 بود . خوب شروع می کنیم از اون عامل 9 واحد به روش قبل ازش کم می کنیم و ... فقط اگر اعدادی که در اثر جمع ها یا تفریق ها به دست می آید اگر اول بود و بزرگتر از 9 دوباره باید همین کار را بکنیم تا تمام حالات را پوشش دهیم و فکر کنم که دیگه حالات اضافی دیگه ای نمونه البته اگر اعداد بزرگ بشه قطعاً برنامه داخل حلقه های بی نهایت می افته.
البته بعد از جمع و تفریق باید در عوامل دیگه ضرب صورت بگیره و ... در ضمن باید توجه داشته باشیم بعد از ضرب نباید اعداد حاصله در جمع و تفریق از 9 بزرگتر بشه.

راستی یکم صبر کن فکر می کنم روش ما غلط باشه باید روش را عوض کنیم بزار تو کتاب هام بگردم.دلیل اینکه اینجوری فکر می کنم اینه که اگر عدد های بزرگتر از 9 زیاد بشن و ... خیلی مشکل پیش می آید. بهر حال بزار ببینم کتاب چی میگه تا وقتی استادان بزرگ این علم هستن من چی دارم بگم.شما چی فکر می کنید؟؟؟؟؟؟؟؟؟؟؟؟؟؟

راستی منظور شما را هم از

و اینگونه بود که مفهوم Order کشف شد!

نفهمیدم اگر لطف کنید توضیح بدبد ممنون میشم.

[alireza643]

من فکر میکنم استادان بزرگ همه از همین جا که ما شروع کردیم شروع کردن و ما اگر بخواهیم همیشه به حرف استادان بزرگ گوش کنیم هیچ وقت استاد بزرگی نمیشیم.
من دارم تلاش میکنم یه روش جدید پیدا کنم. جواب گرفتم خبر میکنم.

[Arman_1367]

تو کتابها چیزی در این رابطه پیدا نکردم برای همین گفتم مسئله با حالیه برای همین بزار روش فکر کنم.
بعد از دیشب تا حالا که فکر کردم به این روش رسیدم.

ابتدا فرض اینه که اعداد باید حتماً از 10 کوچکتر باشند یعنی بین 0 تا 9 خوب مثلاً می خواهیم تمامی حالات را برای عدد 5 انجام بدهیم و عدد اصلی نیز 99 است خوب 99 برابر 11*9 است در صورتی که تجزیه بشه 11 از 10 بزرگتره پس این مورد قابل قبول نیست.
اما کوچکترین عدد بزرگتر از 99 که بر 5 بخش پذیره 100 می شود که حاصل تجزیه آن این است.
4*5*5 خوب این عبارت منهای 1 (100-99) برابر 99 می شود یعنی عبارت (5*5*4)-1 خوب حالا عدد 105 از 100 بزرگتره و بر 5 نیز بخش پذیره که حاصل تجزیه ان 3*7*5 درسته حالا عبارت (5*3*7)-6 به دست می آید این عمل را تا جایی ادامه می دهیم که قسمت تفریق از 10 بزرگتر بشه بعد می رویم و عکس این عمل را ار 95 به پایین انجام می دهیم مثلاً بزرگترین عدد کوچکتر از 99 که بر 5 بخش پذیر باشه می شود 95 که تجزیه شده آن 5*19 است چون 19 از 10 بزرگتره این عبارت را در نظر نمی گیریم . اما 90 بر 5 بخش پذیره و میشه 5*9*2 که باید با اختلاف 90 و 99 جمع بشه تا 99 به دست بیاد اما 9 خودش برابر 3*3 پس عبارت دیگری که همان 2*3*3*5 است به دست آمد پس برای 5 عبارات زیر به دست می آید :


(5*5*4)-1
(5*3*7)-6
(5*9*2)+9
(5*2*3*3)+9

همین فکر کنم الگریتم کاملی باشه چون برای اعداد 2 تا 9 میشه این کار را انجام داد و خیلی هم حلقه طولانی نمیشه فقط یکم باید زیادتر کد نویسی بشه حالا که نه کار دارم فردا کد این الگریتم را هم می زارم.راستی عدد یک تو همون قسمت اول باید چک بشه که آیا اول هست یا نه اگر تجزیه شد و تمام اعداد پایه از 9 کوچکتر باشه اون وقت یک حالت داریم و اما هرجا که اعداد اول در ضرب نداشتیم باید حالت جدیدی از ضرب عوامل آنها بشه مثل 9 که شد 3*3 و در ضمن بعد از این حالان به جای عدد 2 می توانیم 4/2 را جایگزین کنیم و حالت جدید به دست بیاوریم دیگه همین. به هر حال من بازم سر می زنم اگر ایرادی به ذهنتون رسید بگید ممنون می شم.

[someCoder]

برای فهمیدن بیشتر منظورم اینجا رو ببینید: http://en.wikipedia.org/wiki/Big_O_notation
در کل مقایسه دو تا الگوریتم از نظر زمان (و همینطور حافظه) مصرفی راه حل ریاضی مشخص داره که برای این کار چند معیار تعریف میشه و پرکاربردترینش همین Big O است که قبلا هم گفتم و دانشجویان رشته مهندسی کامپیوتر در دروس ساختمان داده ها و طراحی الگوریتم باهش آشنا میشن.
مفهوم O کاری که میکنه اینه که مدت زمان اجرای برنامه رو از نظر ریاضی در بدترین حالت اجرای الگوریتم محاسبه میکنه و اگر برای دو تا الگوریتم مختلف این مقدار محاسبه بشه، راحت میشه اونها رو باهم مقایسه کرد.
الان وقت ندارم که بیشتر توضیح بدم، اما اگر خودتون چیزی پیدا نکردید، بگید تا بعدا براتون با مثال توضیح بدم که چطور محاسبه میشه.

[Arman_1367]

قرار شد نظرتون را در رابطه با الگریتم بگید همین فقط یه نگاه انداختید و رفتید.

جناب somecoder از شما هم ممنون مطلب خیلی مفیدی بود اگر لطف کنید و گاهی از این جور چیزها بذارید ممنون می شم.

[alireza643]

سلام
الگوریتم خوبیه ولی یه نکته ای که داره اینه که گفته تمام حالتهایی که عدد مورد نظر ما تشکیل میشه ولی الگوریتم شما تمام حالات رو با اعداد کوچکتر از 10 پوشش میده مثلا برای عدد 105 این چند تا حالت نمایش داده میشه؟
105 = 895 - 1000
105 = 800 - 905

[Arman_1367]

الگوریتم خوبیه ولی یه نکته ای که داره اینه که گفته تمام حالتهایی که عدد مورد نظر ما تشکیل میشه ولی الگوریتم شما تمام حالات رو با اعداد کوچکتر از 10 پوشش میده مثلا برای عدد 105 این چند تا حالت نمایش داده میشه؟
105 = 895 - 1000
105 = 800 - 905

دوست عزیز فکر می کنم که در اولین تاپیک فرض بر این بوده که اعداد از 10 کوچکتر باشند برای همین این روش را ارائه دادم و اما یک نکته تازه:

هممون قبول داریم که عمل ضرب عمل تقسیم را خنثی می کند مثلاً 4*2/2 همان 4 می شود و عمل جمع و تفریق هم نسبت به هم همین حالت را دارند پس تعداد حالات به بی نهایت میل می کند.

پس شاید بهتر باشه یکم محدودیت سوال را افزایش دهیم.

آخر صفحه اسم نویسنده این تاپیک را نمی بینم برای همین عذر می خواهم اما اگر ایشان از منبعی این سوال را مطرح کرده اند خوب معرفی کنند تا بررسی کنیم سوال صحیح چی هست و اگر هم نمی خواهند متن سوال را اصلاح شده بگزارند برای اینکه با این روش شما می توانید در هر حالت به دست آمده عددی را ضرب و بر همان عدد تقسیم انجام دهید و هر دفعه حالتی جدید بسازید برای جمع هم همینطور پس بهتره محدودیت ها را دقیق بیان کنند.

[alireza643]

درباره محدودیت اعداد خوب تو سوال گفته بودند با اعداد زیر هزار.
درباره محدودیت اعمال جبری هم بعضی از محدودیت ها باگ منطقی به وجود میاره و حتی اگر ذکر هم نشه اصولا این محدودست ها در نظر گرفته میشه مثل حالتی که شما گفتید عمل تقسیمی که ضرب رو خنثی کنه نباید تو محاسبات بیاد واگر نه برای هر عدد بی نهایت راه حل وجود داره.

[Arman_1367]

درباره محدودیت اعداد خوب تو سوال گفته بودند با اعداد زیر هزار.
درباره محدودیت اعمال جبری هم بعضی از محدودیت ها باگ منطقی به وجود میاره و حتی اگر ذکر هم نشه اصولا این محدودست ها در نظر گرفته میشه مثل حالتی که شما گفتید عمل تقسیمی که ضرب رو خنثی کنه نباید تو محاسبات بیاد واگر نه برای هر عدد بی نهایت راه حل وجود داره.

اینو نگاه کن :

این برنامه باید یه عدد مثلاً از 1 تا 1000 از ورودی بگیره و با اعداد (1 تا 9 ) با انواع حالتهای (+ و - و * و / ) بگه که چه جوری اوون عدد ورودی ساخته می شه.

محدودیت مطقی یعنی چی گفته تمام حالات و اینجور چیز ها هم جزو تمام حالات میشه نمی دونم چرا نویسنده تاپیک خودش یک سری نمیزنه تا ببینیم اصل مسئله چی هست ما را انداخته تو یک چاه که ته نداره .:شیطان:

[alireza643]

شما اینجا رو نگاه کن:


مثلا اگه بهش بدیم 14، تمام حالتهایی که 14 با اعداد زیر 1000 تولید میشه رو بهمون بده:

من تو همون صفحه ی اول گفتم که تکلیف رو دقیقا روشن نکردن.