سلام دوستان
من هرچی تلاش میکنم نمیتونم صورت این الگوریتم رو برای زبان C بنویسم...
این یک تمرین بر پایه تمرینات CLRS و الگوریتم هست
شما میتونید کد رو بنویسید:
((میخواهیم یک ماشین بستنی فروشی را تحت کنترل کامپیوتر بسازیم.
طرز کار : مشتری به ماشین بستنی فروشی مراجعه کرده و تعدد بستی های درخواتی را وارد میکند.
ماشین با توجه به قیمت واحد بستنی با پیغامی مناسب قیمت یک عدد بستنی و مجموع پولی که مشتری باید پرداخت کند ،را اعلام میکند.
مشتری مبلغ پرداختی را با سکه های ۵۰۰۰ ، ۲۰۰۰ ، ۲۵۰ ، ۵۰ و ۱ ریالی پرداخت میکند.
درصورتی که مشتری مبلغ کمتری نسبت به بستنی های درخواستی پرداخت کرده باشد ، ماشین بطور خودکار از میزان سفارش کم کرده و اینکار را با پیغام مناسب به اطلاع مشتری میرساند.
ولی درصورتی که مبلغ پرداختی مشتری بیشتر از مبلغ میزان سفارش باشد ، ماشین مابقی پول مشتری را با حداقل سکه به او باز میگرداند و این عملیات تا زمانی که میزان سفارش صفر یا منفی وارد شود ،ادامه میابد.
مبلغ ۰ به عنوان پایان ورود سکه میباشد.))
سلام
برنامه خیلی سختی نیست ولی چند تا سوال پیش میاد، اولآ بفرمائید که فرمت گرفتن سکه ها چجوریه ؟
به طور مثال : "اگر هر بستنی ۵۰۰ تومان باشه و طرف ۱۰ تا سفارش داده باشه. برنامه بهش میگه که ۵۰۰۰ پرداخت کن و طرف با وارد کردن این سری از اعداد ۲۵۰،۲۰۰۰،۲۰۰۰،۲۵۰،۲۵۰،۵۰،۵۰،۵۰،۵۰،۵۰،۰ به ماشین سکه میدهد ؟ "
تو مثال که من زدم بعد از اتمام سکه ها عدد صفر آمده که به برنامه حالی کنه که سکه ها تموم شد.
آیا منظور شما هم همین بود ؟
قالب گرفتن اطلاعات به مشتری چطوری باید باشه ؟
یه مثال عددی و جامع بزن من سه سوت برنامشو برات مینویسم ولی تا برای خودم مفهوم نباشه نمیشه برنامه رو نوشت.
(۱۸ خرداد ۱۳۹۱ ۰۹:۱۲ ق.ظ)naderx نوشته شده توسط: سلامخوب مشتری که سکه ۵۰۰۰ تومانی میده.
برنامه خیلی سختی نیست ولی چند تا سوال پیش میاد، اولآ بفرمائید که فرمت گرفتن سکه ها چجوریه ؟
به طور مثال : "اگر هر بستنی ۵۰۰ تومان باشه و طرف ۱۰ تا سفارش داده باشه. برنامه بهش میگه که ۵۰۰۰ پرداخت کن و طرف با وارد کردن این سری از اعداد ۲۵۰،۲۰۰۰،۲۰۰۰،۲۵۰،۲۵۰،۵۰،۵۰،۵۰،۵۰،۵۰،۰ به ماشین سکه میدهد ؟ "
مشکل وقتیه که مثلا ۴۱۰۰ تومان قیمت بستنی ها بشه و مشتری ۵۰۰۰ تومان بده اونوقت ماشین باید ابتدا تعدادی ۲۵۰ تومانی بده (۷ تا) بعد هم ۳ تا ۵۰ تومانی.
چون سکه ۱ ریالی داریم همیشه میتونیم باقیمانده پول مشتری رو کامل پس بدیم. اما باید تعداد سکه ها حداقل باشه پس از الگوریتم حریصانه استفاده میکنیم.(مساله coin changing)
یکمی این شبه کد رو تغییر بدین فکر کنم شبه کدی که میخواین بدست بیاد :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این مسئله همون مسئله خرد کردن سکه ها وقتی w1=1 (ارزش کم ارزشترین سکه) و همچنین مسئله کوله پشتی وقتی w1=1 (وزن سبکترین کالا) است.
راهی که به ذهن من میرسه : مقدار سکه ها رو به ترتیب نزولی توی آرایه بگذارید باقیمانده رو با مقدار خانه اول مقایسه کنید اگر کوچکتر بود به اندازه مقدار آرایه از باقیمانده کم کنید دوباره مقایسه کنید اگر باقیمانده بزرگتر از خانه اول بود باز به اندازه خانه اول کم کنید و اگر بزرگتر بود به خانه بعدی آرایه بروید.
میتوانید یک آرایه دیگر برای مشخص کردن سکه های استفاده شده بکار برید هربار که به اندازه مقدار خانه i ام آرایه A از باقیمانده کم می کنید یک واحد به محتوای خانه i ام آرایه B اضافه کنید.
وقتی باقیمانده صفر شد مقدار خانه های آرایه B نشان دهنده تعداد سکه هایی است که باید برگردانده شود.
مثلا اگر B[1] =2 بود یعنی ۲ عدد از پرارزشترین سکه (۵۰۰۰ تومانی) باید داده شود.
بهتره واسه خودتون مثال بزنید تا بتونید سوال رو حل کنید.