تالار گفتمان مانشت
ساختمان داده-مهندسی کامپیوتر ۸۵ - نسخه‌ی قابل چاپ

ساختمان داده-مهندسی کامپیوتر ۸۵ - Majiid - 05 آبان ۱۳۹۵ ۰۸:۳۰ ب.ظ

سلام.میشه بفرمائید جواب این تست کدوم گزینه ست؟
[attachment=20735]

RE: ساختمان داده-مهندسی کامپیوتر ۸۵ - Behnam‌ - ۰۵ آبان ۱۳۹۵ ۰۹:۱۵ ب.ظ

(۰۵ آبان ۱۳۹۵ ۰۸:۳۰ ب.ظ)Majiid نوشته شده توسط:  سلام.میشه بفرمائید جواب این تست کدوم گزینه ست؟

خب چند تا رشته‌ی پشت سر هم رو بنویسید متوجه می‌شید
۰۰۰۰
۰۰۰۱
۰۰۱۰
۰۰۱۱
۰۱۰۰
۰۱۰۱
۰۱۱۰
۰۱۱۱

بیت شماره‌ی ۰ از سمت راست هر بار تغییر می‌کنه، بیت ۱ (با شروع از ۰) از راست هر دو بار یکی تغییر می‌کنه، بیت ۲ از راست هر ۴ بار یکی تغییر می‌کنه و ..
به طور کلی، بیت شماره‌ی i، هر [tex]2^i[/tex] یکی تغییر می‌کنه. پس بعد از [tex]n=2^k[/tex] بار افزایش، بیت صفرم n بار، بیت یکم n/2 بار، بیت شماره‌ی دو [tex]\frac{n}{4}[/tex] بار و ... که میشه گزینه‌ی ۳/
گزینه‌ی ۱، خود n رو شامل نمی‌شه پس اشتباه هست

RE: ساختمان داده-مهندسی کامپیوتر ۸۵ - DANEiL - 12 آبان ۱۳۹۵ ۰۹:۰۳ ق.ظ

میشه لطفا این سوال رو بیشتر توضیح بدین؟
مخصوصا نحوه محاسباتش رو؟
خیلی ممنونم.

RE: ساختمان داده-مهندسی کامپیوتر ۸۵ - Pure Liveliness - 17 آبان ۱۳۹۵ ۰۴:۴۰ ب.ظ

(۱۲ آبان ۱۳۹۵ ۰۹:۰۳ ق.ظ)DANEiL نوشته شده توسط:  میشه لطفا این سوال رو بیشتر توضیح بدین؟
مخصوصا نحوه محاسباتش رو؟
خیلی ممنونم.
سلام.
شمارنده از صفر شروع میکنه و به ترتیب اعداد زیر رو میشماره. فرض میکنیم میتونه تا ۱۵ بشماره یعنی ۴ بیت. حالا بیشتر هم میتونه باشه و فرقی نداره.
گفته شمارنده ی k بیتی هست و [tex]۲^k[/tex] بار افزایشش میدیم. یعنی اگه ۴ بیتی باشه. ۱۶ بار افزایشش میدیم. تا برسه به [tex]۲^k[/tex] یعنی ۱۶. یعنی بشه k+1 بیتی که بیت پرارزشش ۱ و مابقی صفر هستن. و چون k بیت رو میتونه بشماره از بیت آخر صرف نظر میکنیم.
۰۰۰۰
۰۰۰۱
۰۰۱۰
۰۰۱۱
۰۱۰۰
۰۱۰۱
۰۱۱۰
۰۱۱۱
۱۰۰۰
۱۰۰۱
۱۰۱۰
۱۰۱۱
۱۱۰۰
۱۱۰۱
۱۱۱۰
۱۱۱۱
۱۰۰۰۰
مشاهده میکنیم که بیت کم ارزش تر با هر بار عمل increment عوض میشه. یعنی ما [tex]2^k-1[/tex]بار inc کنیم. کم ارزش ترین بیت هم [tex]2^k-1[/tex] بار تغییر میکنه.
دومین بیت از سمت راست هر دو بار یک بار تغییر میکنه. یعنی اگه [tex]2^k-1[/tex]بار عمل inc رو انجام بدیم بیت دوم از راست [tex]2^{k-1}-1[/tex] بار تغییر میکنه.
سومین بیت از سمت راست هر چهار بار یک بار تغییر میکنه. یعنی اگه [tex]n=2^k-1[/tex] بار عمل inc رو انجام بدیم بیت سوم از راست [tex]2^{k-2}-1[/tex] بار تغییر میکنه.
پرارزش ترین بیت هر هشت بار یک بار تغییر میکنه. یعنی اگه [tex]n=2^k-1[/tex] بار عمل inc رو انجام بدیم، پرارزش ترین بیت [tex]2^{k-3}-1[/tex] بار تغییر میکنه.
یه بارم که عدد حاوی k تا ۱ به [tex]۲^k[/tex] تبدیل میشه، k بیت ۱ تبدیل میشه به ۰.
پس در مجموع واسه شمارنده ی k بیتی:
تغییر کم ارزش ترین بیت: [tex]۲^k-1[/tex]
تغییر بیت دوم از راست: [tex]۲^{k-1}-1[/tex]
تغییر بیت سوم از راست: [tex]۲^{k-2}-1[/tex]
.
.
.
تغییر بیت k ام (پرارزش ترین بیت): [tex]۲^{k-(k-1)}=2^1-1[/tex]
یه بارم که عدد حاوی k تا ۱ به [tex]۲^k[/tex] تبدیل میشه، k بیت ۱ تبدیل میشه به ۰….