تالار گفتمان مانشت

سوالو ضمیمه کردم

جواب گزینه ۱ میباشد.

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

(21 خرداد 1391 03:33 ب.ظ)reyhaneh64 نوشته شده توسط: [ -> ]سوالو ضمیمه کردم

جواب گزینه ۱ میباشد.

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

سوالش بیشتر شبیه تست هوش بود!!
ساده فکر کن.
ما می دونیم ۱۰۰ تا حلقه رو تو 100^2 تا حر کت میدیم از میله اول به سوم.حالا ما اومدیم به ۲ تا بخش تقسیمش کردیم.تو فرمول بازگشتیش فرض میکردیم که n-1 رو انقال دادیم حالا اون ۱ دونه رو انتقال میدیم.اینجام همینه.[tex]100-n[/tex]تا رو انتقال دادیم و n تاش مونده.پس کلا ۱ حرکت و خودش انجام داده.پس از 100^2 jتا حرکت فقط ۱ایشو انجام داده.

فکر می کنم گزینه ی 1 درست هست.
فصل دوم ساختمان داده کتاب پوران یوسفی.
----------------
[tex]2^0 2^1 ... 2^{n-1}=\frac{a(q^n-1)}{q-1}=\frac{1(2^n-1)}{2-1}=2^n-1\Rightarrow 2^{100}-1[/tex]