افراز عددی مرتب و نامرتب (قسمت اول)

افراز عددی مرتب و نامرتب (قسمت دوم)

افراز عددی مرتب و نامرتب (قسمت سوم)

افراز عددی مرتب و نامرتب (قسمت چهارم)

افراز عددی مرتب و نامرتب (قسمت پنجم)

پیچیدگی

تمرین‌های هفتهٔ دوم

۱. فرض کنید \(a\) و \(b\) اعداد صحیحی باشند که \(0\leq a\leq b\) برقرار است. تعداد جواب‌های صحیح نامعادلهٔ
\[a\leq\big|x_1\big|+\dots+\big|x_r\big|<b\] را در هر یک از حالت زیر محاسبه کنید.
الف) \(x_i\)ها مخالف صفر باشند.
ب) \(x_i\)ها اعداد صحیح دلخواه باشند.

۲. ثابت کنید تعداد راههای نوشتن \(n\) به صورت مجموعی از جمع‌وندهای \(1\)، \(2\)، و \(3\) بدون مهم بودن ترتیب جمع‌وندها، به‌طوری که هر یک از این جمع‌وندها حداقل یک‌بار مورد استفاده قرار گیرند، برابر عبارت زیر است:
\[1+\Big\lfloor\frac{n(n-6)}{12}\Big\rfloor.\]

۳. ثابت کنید تعداد افرازهای \(n\) به حداکثر \(k\) جزء برابر با تعداد افرازهای \(n+k\) به دقیقاً \(k\) جزء است.

۴. فرض کنید هر کدام از گزاره‌ها، زمان اجرای یک الگوریتم از اندازهٔ ورودی \(n\) باشد. در هر مورد مشخص کنید که کوچک‌ترین کران بالا \((O)\) برای اجرای الگوریتم چیست و با آوردن استدلال آن را اثبات کنید.

\[\begin{aligned}a)\;&5+0.001n^3+0.025n\\b)\;&0.3n+5n^{1.5}+2.5n^{1.75}\\c)\;&n\log_3⁡n+n\log_2⁡n\\d)\;&3\log_8⁡n+\log_2⁡\log_2 \log_2⁡n\\e)\;&2n+n^{0.5}+0.5n^{1.25}\\f)\;&100n\log_3⁡n+n^3+100n\end{aligned}\]

۵. درستی یا نادرستی هر یک از گزاره‌های زیر را مشخص کنید و برای پاسخ‌تان دلیل بیاورید. در صورت غلط بودن، عبارتی صحیح پیشنهاد دهید.
\[\begin{aligned}a)\;&O(f+g)=O(f)+O(g)\\b)\;&O(f\cdot g)=O(f)\cdot O(g)\\c)\;&g=O(f)\;{\rm and}\;h=O(f)\Rightarrow g=O(h)\\d)\;&5n+8n^2+100n^3=O(n^4)\\e)\;&5n+8n^2+100n^3=O(n^2 log⁡ n)\end{aligned}\]

کتاب هوش et

ریاضی تکمیلی

 

ویدئوی هفته

آیا فقط یک عدد چهاررقمی با خاصیت ۶۱۷۴ وجود دارد؟

ارسال پاسخویدئوهای بیشتر

 

مسئلهٔ هفتهٔ بیست‌وششم

مسئلهٔ هشت وزیر. چگونه \(8\) وزیر را در یک صفحهٔ شطرنج قرار دهیم به‌ طوری‌که هیچ‌کدام دیگری را تهدید نکند.

هشت وزیر

ارسال پاسخمسائل بیشتر

کتاب هوش فرازمینی et

0 Comments
Inline Feedbacks
مشاهده همه نظرات