آمار پرسش:
- پرسیده شده: 2015-07-11 07:49:05 -0600
- مشاهده شده: 494 بار
- بروز شده: 2015-07-13 13:51:06 -0600
پرسش‌های مشابه:
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
تعداد دکامینوهایی که در یک مستطیل ۳ در ۴ جا می‌گیرند
تعداد راههای انتخاب nشی از 2n+1 شی متمایز و n شی یکسان
تعداد راههای حرکت قورباغه روی یک شبکه‌ی ۵ در ۸
تعداد رنگ‌آمیزی‌های هم‌ارز در صفحه های شطرنجی 7*7
تعداد جدول ها دارای عدد زینی (شمارش)
اثبات وجود مربع 2*2 با تعداد خانه های فرد هم رنگ
ازمون مرحله یک سی و سومین المپیاد ریاضی سوال 25 (کد 2)
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
ثابت کنید تعداد زیر دنباله های عجیب از اعداد ۱ تا $n$، نمایی نیست!
به یه دنباله مثل $a_1, a_2, ..., a_k$ عجیب میگیم اگه به ازای هر $1 \le i < k$ داشته باشیم $a_i | a_{i + 1}$.
مثلن دنباله ی $<2, 4, 8, 16>$ عجیبه ولی $<2, 4, 6>$ عجیب نیست!
تعداد زیردنباله های عجیب از دنباله ی $<1, 2, 3, ..., n>$ رو میگیم $f(n)$. (زیر دنباله دیگه... لازم نیست پشت سر هم باشن!)
الف) عدد ثابت $k$ ارائه کنید که داشته باشیم $f(n) = O(n^k)$.
ب) $\Theta(f(n))$ را بدست آورید!
تعاریف $O$ و $\Theta$:
Big O notation Theta notation
2015-07-11 07:49:05 -0600
محمد مهدی 1955 ● 5 ● 12 ● 40
نظرات
1 پاسخ
واقعا حسش نیست توضیح بدم که چرا:
$$ g(n)=g(n/2)+g(n/3)+...+g(n/n) $$ $$ f(n)=\Theta(g(n)) $$ حالا استقرا میزنیم که $g(n)<=n^2$
$$ g(n)=g(n/2)+g(n/3)+...+g(n/n)<= (n^2/4+n^2/9+...+n^2/n^2) $$ $$ g(n)<= n^2(1/4+1/9+...+1/n^2) $$
خوب حالا اینو ببینید
یعنی که تهش 1/4 + 1/9 +... یه چیزه کمتر از یک پس هی کمتر میشه وکلا اثبات میشه که: $$ g(n)<=n^2(1/4+1/9+...+1/n^2)<= n^2 * K<= n^2 $$ $$ g(n)=O(n^2) $$ $$ f(n)=\Theta(g(n)) $$ $$ f(n)=O(n^2) $$
یه کران خوب برای $f(n)$ پیدا کردم :) (با همین راه میتونید بدست بیارید)
$$ \Omega(x^{1.7287})=f(n)=O(x^{1.7288}) $$
2015-07-12 12:13:18 -0600
حمیدرضاه 2979 ● 20 ● 26 ● 52
نظرات
میشه به راحتی اثبات کرد که f(x) از تتای هیچ x^k ی نیست از طرفی نمایی هم نیست کلا خیلی چیزه عجیبیه D:
2015-07-12 16:20:23 -0600 حمیدرضاه