۱- مزایا و معایب نسبی استفاده از [tex]O^{\infty }[/tex] (اوی بی نهایت) نسبت به O برای مشخص کردن زمان اجرای برنامه ها را مشخص کنید.
۲- درستی و نادرستی رابطه های زیر را بیابید. [tex]g\left ( n \right )\in O(R(n))[/tex] و [tex]f\left ( n \right )\in O(S(n))[/tex]
الف ) [tex]f\left ( n \right )-g(n)\in O(S(n)-R(n))[/tex]
ب) [tex]f\left ( n \right )\div g(n)\in O(S(n)\div R(n))[/tex]
۳- گیریم در کشوری عجیب پنج نوع سکه وجود داشته باشد ۶۷و ۴۱و ۲۹و ۲۳و ۱۵سنتی، ترکیبی از این سکه ها بیابید که با آن بشود مبلغ ۱۸ دلار و ۸ سنت(۱۸۰۸ سنت) را پرداخت کرد.(از همه سکه ها به تعداد کافی در جیبتان وجود دارد.)
۴- فهرست اعداد زیر را در نظر بگیرید کار شما این است که تا جای ممکن تعداد کم تری از آنها را پاک کنید بطوری که اعداد باقی مانده صعودی باشد.
۹ ۴۴ ۳۲ ۱۲ ۷ ۴۲ ۳۴ ۹۲ ۳۵ ۳۷ ۴۱ ۸ ۲۰ ۲۷
۸۳ ۶۴ ۶۱ ۲۸ ۳۹ ۹۳ ۲۹ ۱۷ ۱۳ ۱۴ ۵۵ ۲۱ ۶۶ ۷۲
۲۳ ۷۳ ۹۹ ۱ ۲ ۸۸ ۷۷ ۳ ۶۵ ۸۳ ۸۴ ۶۲ ۵ ۱۱
۷۴ ۶۸ ۷۶ ۷۸ ۶۷ ۷۵ ۶۹ ۷۰ ۲۲ ۷۱ ۲۴ ۲۵ ۲۵
دوستان اگر لطف کردن پاسخ دادن، بگن چه جوری به جواب رسیدن ، می خوام یاد بگیرم خودم حل کنم اما الان واقعا نمی دونم چه جوری باید فکر کنم تا به جواب برسم
ممنون از زمانی که صرف می کنید
در مورد سوال ۲ قسمت "ب" :
فرض کنیم داریم :[tex]f(n)=n^{2},g(n)=n,S(n)=R(n)=n^{3}[/tex] حال در معادله قرار دیم به صورت زیر در می آید :
[tex]f(n)/g(n)=n^{2}/n=n,,,S(n)/R(n)=n^{3}/n^{3}=1\Rightarrow n \notin O(1)[/tex] که غلط هستش و همیشه برقرار نیست
در مورد قسمت "الف" هم همینطور :
[tex]f(n)- g(n)=n^{2} - n \notin O(S(n) - R(n)= n^{3}-n^{3}=0)[/tex] اینم اشتباه هستش یعنی همیشه برقرار نیست
در مورد سوال ۳ مثالی در کتاب راهیان اومده خلاصه برات میگم فرضا سکه های ۱ و ۲ و ۵ و ۱۰ و ۲۵ و ۵۰ رو داریم از هر کدام حداقل یک نمونه داریم می خواهیم طوری مبلغ ۳۶ هزار تومان را محاسبه کنیم تا از حداقل سکه ها استفاده شود :
راه حل حریصانه و بهینه ترین راه حل و کمترین تعداد سکه{۳۶} و بعدش {۱۸و۱۸} که این سکه ها موجود نیست لذا به این نتیجه می رسیم که روش حریصانه همواره جواب بهینه را نمیدهد لذا از بین سکه ها سراغ بزرگترین سکه میرویم (سکه ۵۰) اگر حاصل از ۳۶ بزرگتر باشد آن را کنار میگذاریم ولی اگر کوچکتر بود آن سکه بخشی از جواب میشود لذا سراغ سکه ۲۵ میرویم و چون کمتر از ۳۶ هست بخشی از جواب هست {۲۵} حال دوباره با سکه ۲۵ مقایسه می کنیم ۲۵+۲۵=۵۰ لذا چون بیشتر است از سکه ۲۵ عبور می کنیم حال سکه ۱۰ تومانی با سکه ۲۵ جمع کنیم می شود ۳۵ چون کمتر از ۳۶ هست پس جواب {۲۵و۱۰} حال سراغ سکه ۲ رویم میشه ۳۷ بیشتر از ۳۶ هستش لذا سراغ سکه ۱ میرویم و دقیقا معادل ۳۶ هست لذا جواب بهینه {۲۵و۱۰و۱} می باشد اما بهینه ترین نیست در مورد سوال شما همین رویه و الگوریتم رو ادامه بدید تا به جواب برسید