Printable View
دردود بر شما
مساله اینه:
100 تومان پول داریم که میخوایم اونو به سکه های 2 ، 5 ، 10 ،20 و 50 تومانی خرد کنیم.
به چند حالت میتونیم این کار رو انجام بدیم؟؟:41:
برنامه ای که من نوشتم 196 حالت پیدا کرد ولی بازم شک دارم لطفا اگه راهی برای حل این مسئله وجود داره کمکم کنید:11:
درود!نقل قول:
سوال وقتگیری هستش و طبیعتا بهترین راه برای محاسبه، استفاده از برنامه نویسی در 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 را اختیار کند.
....... دیگه حوصله ندارم حساب کنم :31:
موفق باشین.
90/12/24
سلام
تعداد حالتها همون 196 میشه.
شاید دو نکته در کم کردن محاسبات کمک کنه.این راه حل:
کد:http://ir2up.ir/up1/13317268381.jpg
حسابی افتادید تو زحمت...
من فکر کردم یه فرومولی چیزی داره وگرنه راضی به این همه زحمتتون نبودم.
بازم تشکر لطف کردید:40::11:
سلام vahid جاننقل قول:
برای اطلاعات بیشتر می توانید به کتاب ریاضیات انتخاب از مرکز نشر دانشگاهی فصل 7 مراجعه نمایید.
davy jones فکر نکنم این قدر راه حلش طولانی باشد.
موفق باشید
ممنون از راهنماییتون ولی دوستمون ali_hp تو راه حلشون کامل توضیح دادند و با سواد ریاضی من هم کاملا قابل فهم بود. عکسی که آپلود کردند رو نگاه کنیدنقل قول:
سلام
جاااااان!!!!!!!!!!!!!
بابا دمت گرم داداش. خیلی حال دارین. چند خط کد ساده کافی بود تا به عددش برسین!!!
واقعا مرسی به حوصله تون
لطفا" اون چند خطو بنویس برامون؟:20:نقل قول:
منظور سوالتون رو نمی فهمم که حالت ها رو برای چی می خواهید.چون باید مشخص کنید
که از بین این سکه ها طول انتخابی به چه اندازه داریم مثلا انتخاب به طول 2 یا ... اگر منظورتون این هستش که از هر 5 سکه انتخاب به طول 5 داریم اونوقت 5 به توان 5 خواهد بود که 3125 می شه. در کل باید طول انتخابی مشخص بشه.
برای خرد کردن پول برای اینکه بیشترین سود در میان باشه و کمترین زمان برده بشه از
الگوریتم حریصانه استفاده می شه مثل الگوریتم پریم.
مثلا همین 100 تومان رو اگر دو تا 50 تومان انتخاب بشه سود بیشتری داره. 50+50=100 دو سکه انتخاب شد.بهترین حالت.
و یا اینکه اگر حق انتخاب سکه 50 تومانی به تعداد یک بار باشه به این صورت می شه
50+20+20+10 چهار سکه انتخاب در بهترین حالت تا بیشترین سود در میان باشه.
مثلا 50+10+10+10+10+10=100 شش سکه انتخاب شد این حالت خیلی بد هست و سود کمی رو داره
اگر از سکه 5 تومانی استفاده بشه بدتر از این حالت می شه.
قبلا به دلیل کمبود حافظه هم زمان و حافظه بیشتر مدنظر هر طراح الگوریتم برای به کار بردن در برنامه نویسی بود
ولی الان بیشتر طراحی ها برای کاهش زمان اجرا هستش(تعداد مقایسه ها) تا سرعت بالاتر و پاسخگویی بالایی رو داشته باشه.
هر چه تعداد مقایسه کمتر باشه زمان کمتری می بره و تعداد دستورات انجام شده در عمل توسط پردازنده کاهش می یابه
و زمان پاسخگویی به کاربر در بهترین حالت قرار می گیره.
همون کارهایی که در دستگاه های خودپرداز برای پرداخت پول به صورت هوشمندانه انجام می شه.
سلام دوست عزیزنقل قول:
من خیلی سال پیش C پاس کردم و الان به دلیل استفاده ی خیلی کم، همه اش پریده!!!!:5:
اما الان MATLAB کار می کنم. خدا بخواد می نویسم میفرستم. به دردتون میخوره حالا؟
سلام مجدد
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]
متغیر n تعداد حالتهای ممکن رو ذخیره می کنه و متغیر states خود حالتهارو
امیدوارم مفید باشه
ممنون دوست عزیز ماله تمرینات نوروزی بود که دادم رفت و نمرشم گرفتم...!نقل قول:
ممنون از توضیحاتتون ولی زیاد سر در نیاوردم!!نقل قول:
کدی که من نوشتم و فرستادم طولش مهم نبود و از هر طولی می ساخت که مجموعش از 196 حالت تجاوز نمی کرد شاید شما اشتباه می کنید.
[PHP]//daniyal javani
//tamrin 2 3ke
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int a[6],i,j,k,l,m,s,n=0;
a[0]=2;
a[1]=5;
a[2]=10;
a[3]=20;
a[4]=50;
a[5]=0;
for(i=0;i<51;i++)
{
for(j=0;j<51;j++)
{
for(k=0;k<51;k++)
{
for(l=0;l<51;l++)
{
for(m=0;m<51;m++)
{
s=i*2+j*5+k*10+l*20+m*50;
if(s==100)
{
n++;
if(i !=0) cout<<i <<"*2\t";
if(j !=0) cout<<j <<"*5\t";
if(k !=0) cout<<k <<"*10\t";
if(l !=0) cout<<l <<"*20\t";
if(m !=0) cout<<m <<"*50\t";
cout<<endl;
}
s=0;
}
}
}
}
}
cout<<"\n \n \nnumber is : "<<n;
getch();
return 0;
}[/PHP]
سلام دوست عزیزنقل قول:
خواهش می کنم
درسته، کد MTLAB من هم 196 حالتو میده. (راستی یادم رفت بگم اگه MATLAB ندارید با Notepad هم میتونید فایل با پسود m رو باز کنید.)
موفق باشید
اون مطلبی که گفتم به صورت ازایه خطی بود که شما اعداد رو برای خانه ها فرض می کنید و حالت ها رو بدست می اورید.نقل قول:
که هر کدوم تشکیل یک دنباله از خانه ها رو می ده.
برای انتخاب هایی مثل همین پول خرد از الگوریتم های گریدی یا همون حریص استفاده می شه.
برای مسئله سکه ها اگر عنوان زیر رو سرچ کنید به مطالب جالبی در مورد همین مسئله سکه می رسید.
a greedy algorithm for the coin problem