کمک در حل مسئله خرد کردن پول

[vahid javani]

دردود بر شما
مساله اینه:
100 تومان پول داریم که میخوایم اونو به سکه های 2 ، 5 ، 10 ،20 و 50 تومانی خرد کنیم.
به چند حالت میتونیم این کار رو انجام بدیم؟؟
برنامه ای که من نوشتم 196 حالت پیدا کرد ولی بازم شک دارم لطفا اگه راهی برای حل این مسئله وجود داره کمکم کنید

[davy jones]

دردود بر شما
مساله اینه:
100 تومان پول داریم که میخوایم اونو به سکه های 2 ، 5 ، 10 ،20 و 50 تومانی خرد کنیم.
به چند حالت میتونیم این کار رو انجام بدیم؟؟
برنامه ای که من نوشتم 196 حالت پیدا کرد ولی بازم شک دارم لطفا اگه راهی برای حل این مسئله وجود داره کمکم کنید

درود!

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

مساله شما در حقیقت معادله ی سیاله ی خطی زیر در مجموعه ی اعداد حسابی (اعداد طبیعی + صفر) هستش:

از بحث های ابتدایی و اثبات وجود جواب به ازای انتخاب هر تعداد از 5 متغیر موجود که بگذریم باید گفت که:

الف) به ازای انتخاب تنها یک متغیر از این 5 متغیر، جواب منحصر به فرد وجود داره. یعنی 100 تومن رو میشه منحصرا به هر کدام از سکه های خرد گفته شده، خرد کرد. پس 100 تومن برابر میشه با:

1- 50 سکه ی 2 تومنی
2- 20 سکه ی 5 تومنی
3- 10 سکه ی 10 تومنی
4- 5 سکه ی 20 تومنی
5- 2 سکه ی 50 تومنی

پس اگه فقط یک متغیر رو ناصفر فرض کنیم و در مجموعه ی اعداد طبیعی بخواهیم جواب رو پیدا کنیم، به یک حالت به جواب میرسیم. پس تا اینجا 5 حالت برای خرد کردن 100 تومن پیدا شد.

=========
ب) اما اینبار فرض میکنیم که دو متغیر از این 5 متغیر ناصفر هستند. یعنی برای خرد کردن 100 تومن از دو نوع سکه ی متفاوت استفاده کنیم. اولا که خود این کار به حالت امکان پذیره که بیایم و 2 متغیر دلخواه رو از بین 5 متغیر انتخاب کنیم. حالا باید حالات زیر رو تک تک بررسی کنیم:

1. فقط از سکه های 2 تومنی و 5 تومنی استفاده کنیم:
مساله تبدیل میشه به حل معادله ی سیاله ی در اعداد طبیعی. چون 5y مضرب 5 هستش پس باید x هم مضرب 5 باشه تا مجموع 5y و 2x هم که شده برابر 100، مضرب 5 باشه چون 100 هم مضرب 5 هستش. همچنین با استدلال مشابه، y هم باید حتما زوج باشه. از اونجایی که x و y نمیتونن صفر باشند پس حداقل مقدار x برابر میشه با 5، , و حداقل مقدار y هم برابر میشه با 2. با اندکی صرف وقت و محاسبه معلوم میشه که مقادیر زوج مرتبهای که در این قسمت صدق میکنند برابره با:

(5,18) , (10,16) , (15,14) , (20,12) , (25,10) , (30,8) , (35,6) , (40,4) , (45,2)

که تعدادشون برابر با 9 حالته.
------
2. فقط از سکه های 2 تومنی و 10 تومنی استفاده کنیم:

در اینجا x و z نمیتونن برابر با صفر باشند و طبق استدلال قسمت قبل، x باید مضرب 5 باشه ولی z محدودیتی نداره. پس حداقل x برابر با 5 و حداقل z برابر با 1 هستش.

زوج مرتب های رو که در معادله ی سیاله ی این قسمت صدق میکنند، مینویسیم:

(5,9) , (10,8) , (15,7) , (20,6) , (25,5) , (30,4) , (35,3) , (40,2) , (45,1)

که تعدادشون برابر با 9 حالته
------
3. فقط از سکه های 2 تومنی و 20 تومنی استفاده کنیم:

x و w نمیتونن صفر باشن و همچنین x باید مضرب 10 باشه. زوج مرتبهای ممکن (x,w) رو برای این حالت مینویسیم:

(10,4) , (20,3) , (30,2) , (40,1)

که تعدادشون برابر با 4 حالته
------
4. فقط از سکه های 2 تومنی و 50 تومنی لستفاده کنیم:

x و t نمیتونن صفر باشند و x باید مضرب 25 باشه. زوج مرتب های ممکن (x,t) رو برای این حالت مینویسیم:

(25,1)

فقط همین یک حالت امکان داره
------
5. فقط از سکه های 5 تومنی و 10 تومنی استفاده کنیم:

y و z نمیتونن برابر با صفر باشند و y هم باید حتما زوج باشه. زوج مرتبهای ممکن (y,z) رو برای این حالت مینویسیم:

(2,9) , (4,8) , .... , (16,2) , (18,1)

که تعدادشون برابر با 9 حالته
------
6. فقط سکه های 5 تومنی و 20 تومنی:

y و w نمیتونن برابر با صفر باشند و y هم باید حتما مضرب 4 باشه. زوج مرتبهای ممکن (y,w) رو برای این حالت مینویسیم:

(4,4) , (8,3) , (12,2) , (16,1)

که تعدادشون برابر با 4 حالته
------
7. فقط سکه های 5 تومنی و 50 تومنی:

y و t نباید برابر با صفر باشند و y هم باید مضرب 10 باشه. پس تنها زوج مرتب ممکن (y,t) در این حالت برابر میشه با (10,1)

------
8. فقط از سکه های 10 تومنی و 20 تومنی استفاده کنیم:

z و w نمیتونن صفر باشند و z هم باید حتما زوج باشه. پس زوج مرتبهای ممکن (z,w) در این حالت میشه:

(2,4) , (4,3) , (6,2) , (8,1)

که تعدادشون برابر با 4 حالته
------
9. فقط از سکه های 10 تومنی و 50 تومنی استفاده کنیم:

z و t نمیتونن صفر باشند و z باید مضرب 5 باشه. پس تنها زوج مرتب ممکن (z,t) در این حالت برابر میشه با (5,1)

------
10. فقط از سکه های 20 تومنی و 50 تومنی استفاده کنیم:

w و t نمیتونن برابر با صفر باشند. همچنین w باید مضرب 5 باشه و t هم باید زوج باشه. پس حداقل w برابر میشه با 5 و حداق مقدار t برابر میشه با 2 که مجموع 5 سکه ی 20 تومنی به علاوه ی 2 سکه ی 50 تومنی میشه 200 تومن. پس در این حالت جواب ممکنی در اعداد طبیعی نداریم.



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

===============
ج) از سه نوع سکه در خرد کردن پول استفاده کنیم. یعنی سه تا متغیر از 5 متغیر ما ناصفر باشند. تعداد حالات انتخاب 3 متغیر دلخواه از بین 5 متغیر برابره با: . پس باید 10 حالت دیگه رو بررسی کنیم:

1- w و t صفر باشند و بقیه ناصفر:

در اینجا هیچکدام از سه متغیر بالا نمیتونن برابر با صفر باشند و نیز طبق استدلالات گذشته، x باید مضرب 5، و y باید مضرب 2 باشه. z محدودیتی نداره. پس حداقل مقدار x برابر میشه با 5، حداقل مقدار y برابر میشه با 2، و حداقل z برابر با 1 هستش. سه تایی های مرتب (x,y,z) رو برای این حالات مینویسیم (در محاسبه از نتایج قسمتهای قبلی برای راحتی میشه استفاده های ضمنی داشت):

(5,2,8)
(5,4,7) , (10,2,7)
(5,6,6) , (10,4,6) , (15,2,6)
(5,8,5) , (10,6,5) , (15,4,5) , (20,2,5)
(5,10,4) , (10,8,4) , (15,6,4) , (20,4,4) , (25,2,4)
(5,12,3) , (10,10,3) , (15,8,3) , (20,6,3) , (25,4,3) , (30,2,3)
(5,14,2) , (10,12,2) , (15,10,2) , (20,8,2) , (25,6,2) , (30,4,2) , (35,2,2)
(5,16,1) , (10,14,1) , (15,12,1) , (20,10,1) , (25,8,1) , (30,6,1) , (35,4,1) , (40,2,1)

تعداد کل حالات این قسمت برابر با 36 حالت میشه
------
2-

علاوه بر اینکه هیچکدام از سه متغیر نمیتونن صفر باشند، باید x مضرب 10 و y مضرب 4 باشند. پس حداقل x برابر با 10 میشه و حداقل y هم برابر با 4 میشه و حداقل مقدار w هم برابر با 1 هستش. سه تایی های مرتب (x,y,w) در این حالت میشه:

(10,4,3)
(10,8,2) , (20,4,2)
(10,12,1) , (20,8,1) , (30,4,1)

که تعداد حالات این قسمت برابر میشه با 6 حالت
------
3-

در اینجا متغیر t تنها میتونه مقدار 1 رو اتخاذ کنه. پس تعداد حالات این قسمت برابر با تعداد حالات معادله ی سیاله ی 2x+5y=50 در مجموعه ی اعداد طبیعی هستش. در اینجا x باید مضرب 5 و y باید مضرب 2 باشد. پس حداقل مقدار x برابر با 5 و حداقل مقدار y برابر با 2 میشه.
پس 3 تایی های مرتب (x,y,t) در این قسمت با اندکی دقت برابر میشن با:

(5,8,1) , (10,6,1) , (15,4,1) , (20,2,1)

که تعدادشون بابر با 4 حالت میشه

------
4-

علاوه بر ناصفر بودن سه متغیر، y باید مضرب 4 باشه و z باید حتما زوج باشه. پس حداقل مقدار y برابر با 4 میشه، حداقل مقدار z برابر با 2 میشه و حداقل مقدار w برابر با 1 هستش. پس سه تایی های مرتب ممکن (y,z,w) در این حالت میشه:

(4,2,3)
(4,4,2) , (8,2,2)
(4,6,1) , (8,4,1) , (12,2,1)

که تعداد حالات این قسمت برابر با 6 حالت میشه
------
5-

بنا بر استدلال و توضیحات داده شده در قسمتهای قبل، مقدار t در این قسمت تنها میتواند مقدار 1 را اختیار کند. بنابراین تعداد جوابهای این قسمت برابر با تعداد حالات جواب معادله ی سیاله ی y+2z=10 در اعداد طبیعی است که تعداد آن برابر است با 4 حالت.
پس 3 تایی های مرتب ممکن (y,z,t) در این حالت برابر میشه با:

(2,4,1) , (4,3,1) , (6,2,1) , (8,1,1)

که تعدادشون برابر با 4 حالت میشه

------
6-

در این حالت هم مشابه حالت قبلی، به علت اینکه t تنها میتواند مقدار 1 را اختیار کند، تعداد حالات برابر با تعداد حالات جوابهای طبیعی معادله ی سیاله ی z+2w=5 خواهد بود که این تعداد برابر با 2 حالت است.
پس 3 تایی های مرتب (z,w,t) در این حالت اینها هستند:

(1,2,1) , (3,1,1)

که تعداد حالات این قسمت هم 2 حالت میشه

------
7-

در محاسبه ی این قسمت راحت تر این است که به w مقدار دهیم. در اینجا w میتواند یکی از اعداد بین 1 تا 4 را اختیار کند.

....... دیگه حوصله ندارم حساب کنم

موفق باشین.
90/12/24

[ali_hp]

سلام
تعداد حالتها همون 196 میشه.
شاید دو نکته در کم کردن محاسبات کمک کنه.این راه حل:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[vahid javani]

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

[Farzam.s]

دردود بر شما
مساله اینه:
100 تومان پول داریم که میخوایم اونو به سکه های 2 ، 5 ، 10 ،20 و 50 تومانی خرد کنیم.
به چند حالت میتونیم این کار رو انجام بدیم؟؟
برنامه ای که من نوشتم 196 حالت پیدا کرد ولی بازم شک دارم لطفا اگه راهی برای حل این مسئله وجود داره کمکم کنید

سلام vahid جان
برای اطلاعات بیشتر می توانید به کتاب ریاضیات انتخاب از مرکز نشر دانشگاهی فصل 7 مراجعه نمایید.
davy jones فکر نکنم این قدر راه حلش طولانی باشد.
موفق باشید

[vahid javani]

سلام vahid جان
برای اطلاعات بیشتر می توانید به کتاب ریاضیات انتخاب از مرکز نشر دانشگاهی فصل 7 مراجعه نمایید.
davy jones فکر نکنم این قدر راه حلش طولانی باشد.
موفق باشید

ممنون از راهنماییتون ولی دوستمون ali_hp تو راه حلشون کامل توضیح دادند و با سواد ریاضی من هم کاملا قابل فهم بود. عکسی که آپلود کردند رو نگاه کنید

[ea2021]

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

[armardeh]

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

لطفا" اون چند خطو بنویس برامون؟

[Karmenwet]

منظور سوالتون رو نمی فهمم که حالت ها رو برای چی می خواهید.چون باید مشخص کنید
که از بین این سکه ها طول انتخابی به چه اندازه داریم مثلا انتخاب به طول 2 یا ... اگر منظورتون این هستش که از هر 5 سکه انتخاب به طول 5 داریم اونوقت 5 به توان 5 خواهد بود که 3125 می شه. در کل باید طول انتخابی مشخص بشه.

برای خرد کردن پول برای اینکه بیشترین سود در میان باشه و کمترین زمان برده بشه از
الگوریتم حریصانه استفاده می شه مثل الگوریتم پریم.
مثلا همین 100 تومان رو اگر دو تا 50 تومان انتخاب بشه سود بیشتری داره. 50+50=100 دو سکه انتخاب شد.بهترین حالت.
و یا اینکه اگر حق انتخاب سکه 50 تومانی به تعداد یک بار باشه به این صورت می شه
50+20+20+10 چهار سکه انتخاب در بهترین حالت تا بیشترین سود در میان باشه.
مثلا 50+10+10+10+10+10=100 شش سکه انتخاب شد این حالت خیلی بد هست و سود کمی رو داره
اگر از سکه 5 تومانی استفاده بشه بدتر از این حالت می شه.
قبلا به دلیل کمبود حافظه هم زمان و حافظه بیشتر مدنظر هر طراح الگوریتم برای به کار بردن در برنامه نویسی بود
ولی الان بیشتر طراحی ها برای کاهش زمان اجرا هستش(تعداد مقایسه ها) تا سرعت بالاتر و پاسخگویی بالایی رو داشته باشه.
هر چه تعداد مقایسه کمتر باشه زمان کمتری می بره و تعداد دستورات انجام شده در عمل توسط پردازنده کاهش می یابه
و زمان پاسخگویی به کاربر در بهترین حالت قرار می گیره.
همون کارهایی که در دستگاه های خودپرداز برای پرداخت پول به صورت هوشمندانه انجام می شه.

[ea2021]

لطفا" اون چند خطو بنویس برامون؟

سلام دوست عزیز
من خیلی سال پیش C پاس کردم و الان به دلیل استفاده ی خیلی کم، همه اش پریده!!!!
اما الان MATLAB کار می کنم. خدا بخواد می نویسم میفرستم. به دردتون میخوره حالا؟