انجمنصفحه اولجستجوی انجمن

[pouya sal]

سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟

---

سوال ۴۲
بنابر selection
n/2=o(n
n/4=o(n/2
n/8=o(n/4
.
.
n+n/2+n/8+...=n(1+1/2+1/4
میشه nln=nlogn

[mahdiii]

(۲۱ بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)pouya sal نوشته شده توسط:  سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟

---

سوال ۴۲
بنابر selection
n/2=o(n
n/4=o(n/2
n/8=o(n/4
.
.
n+n/2+n/8+...=n(1+1/2+1/4
میشه nln=nlogn

سوال ۴۲ غلط نوشتین.
n+n/2+n/8+...=n(1+1/2+1/4 میشه حداکثر ۲n
اون عبارت داخل پرانتز که یه جمع دنباله هندسی هست که اگه تا بینهایت بره میشه [tex]\frac{a_{1}}{1-q}[/tex]
خوب جمله اول یکه و q هم ۰/۵ . پس میشه ۲n. تازه اینجا تا بینهایت نمیره. در آخر گزینه دو درسته

---

(۲۱ بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)pouya sal نوشته شده توسط:  سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟

---

سوال ۴۲
بنابر selection
n/2=o(n
n/4=o(n/2
n/8=o(n/4
.
.
n+n/2+n/8+...=n(1+1/2+1/4
میشه nln=nlogn

شما با این دنباله اشتباه کردی
۱+۱/۲+۱/۳+۱/۴+... که میشه log

[pouya sal]

چه سوتی دادم خدایا.اخ.راست میگید.سوال ۳۹ چی ؟

---

(۲۱ بهمن ۱۳۹۱ ۰۹:۲۳ ب.ظ)mahdiii نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)pouya sal نوشته شده توسط:  سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟

---

سوال ۴۲
بنابر selection
n/2=o(n
n/4=o(n/2
n/8=o(n/4
.
.
n+n/2+n/8+...=n(1+1/2+1/4
میشه nln=nlogn

سوال ۴۲ غلط نوشتین.
n+n/2+n/8+...=n(1+1/2+1/4 میشه حداکثر ۲n
اون عبارت داخل پرانتز که یه جمع دنباله هندسی هست که اگه تا بینهایت بره میشه [tex]\frac{a_{1}}{1-q}[/tex]
خوب جمله اول یکه و q هم ۰/۵ . پس میشه ۲n. تازه اینجا تا بینهایت نمیره. در آخر گزینه دو درسته

---

(۲۱ بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)pouya sal نوشته شده توسط:  سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟

---

سوال ۴۲
بنابر selection
n/2=o(n
n/4=o(n/2
n/8=o(n/4
.
.
n+n/2+n/8+...=n(1+1/2+1/4
میشه nln=nlogn

شما با این دنباله اشتباه کردی
۱+۱/۲+۱/۳+۱/۴+... که میشه log

راست میگین من اشتباه کردم.چه اشتباهی .

---

(۲۱ بهمن ۱۳۹۱ ۰۲:۲۲ ب.ظ)osho نوشته شده توسط:  سوال ۴۵ طراحی الگوریتم زیر دنباله مشترک از مرتبه n^2 و از روش برنامه ریزی پویا است کسی نظری نداره این سوال مستقیما تو کتاب طراحی هادی یوسفی است.

---

سوال ۴۳ طراحی الگوریتم
باید n بار dfs بزنی که مرتبه آن از فلوید که n^ 3 کمتر است.
سوال ۴۲ n+klogk و قسمت دوم n میشه
سوال ۳۹ تو کتاب جدید قدسی است که میشه n\2,m\2 +log(m)+1 میشه.

شما از ۳۹ مطمئنید ؟لطفا اگه مطمئنید بگین.

---

[mohammadjavadkho]

(۲۱ بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)pouya sal نوشته شده توسط:  سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟

---

سوال ۴۲
بنابر selection
n/2=o(n
n/4=o(n/2
n/8=o(n/4
.
.
n+n/2+n/8+...=n(1+1/2+1/4
میشه nln=nlogn

به نظرم جوابتون درسته.اما من اینطوری تحلیل کردم که برای بدست آوردنش یا باید log n بار الگوریتم selection رو انجام بدیم تا همشون بدست بیاد که میشه n log n یا بیایم کلشو مرتب کنیم که اونم میشه n logn .دوستان میشه توضیح بدن چطور n بدست آوردن ؟

[pouya sal]

باشه logn بار selection روی چه اندازه برحسب n فراخوانی میکنید اگه مطالب و دنبال کنین توضیح دادیم

---

(۲۱ بهمن ۱۳۹۱ ۰۷:۳۳ ب.ظ)mahdiii نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

آره برای این مثال (۳ گوی) با یه مقایسه میشه. کلا سوالا غیر استاندارده. باید می گفت تعداد گویها ۳=<
شما برای ۵ و بعد از اون دیگه نمی تونید با n/2 به نتیجه برسید.
به عنوان مثال برای ۵ (شما نمی دونید که ۴ و ۱ هست یا ۳ و ۲) بنابراین باید همون n-1 مقایسه رو انجام بدید حداقل که زمانی هست که گویهای با بار موافق با هم مقایسه می شوند.

منظور از دست کم چی؟حالت خوشبینانه؟یا حداقل زمان کل انجام کار

[mohammadjavadkho]

(۲۱ بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.

---

(۲۲ بهمن ۱۳۹۱ ۰۱:۲۶ ق.ظ)saho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.

من واسه ۵تا مثالشوگفتم.نگفتم حواب حتما همینه گفتم واسه ۳تا و۵تا که n-1نشد.وجواب به n/2نزدیکتره

برای هر تعداد گوی که بگید میشه n-1!چه ۵ تا چه ۳ تا چه هر چی!

[saho]

(۲۲ بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.

شاید
این استدلالم ببینین

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

---

(۲۲ بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.

---

(۲۲ بهمن ۱۳۹۱ ۰۱:۲۶ ق.ظ)saho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.

من واسه ۵تا مثالشوگفتم.نگفتم حواب حتما همینه گفتم واسه ۳تا و۵تا که n-1نشد.وجواب به n/2نزدیکتره

برای هر تعداد گوی که بگید میشه n-1!چه ۵ تا چه ۳ تا چه هر چی!

واسه ۳تا یکی کافیه.قطعا

[MR_KH]

به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!

[mohammadjavadkho]

(۲۲ بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ)saho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۳۹ ق.ظ)MR_KH نوشته شده توسط:  به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!

پس مشکل اینم حل شد.n-1
امابازم میگم با ۳تا میشه n/2
سوالش مشکل داره

دوست عزیز شما یه بار اون الگوریتمی که من بالا نوشتم رو بخونی دیگه نمیگی با ۳ میشه n/2!!!

[saho]

(۲۲ بهمن ۱۳۹۱ ۰۲:۰۰ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ)saho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۳۹ ق.ظ)MR_KH نوشته شده توسط:  به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!

پس مشکل اینم حل شد.n-1
امابازم میگم با ۳تا میشه n/2
سوالش مشکل داره

دوست عزیز شما یه بار اون الگوریتمی که من بالا نوشتم رو بخونی دیگه نمیگی با ۳ میشه n/2!!!

حق باشماست

[mohammadjavadkho]

(۲۲ بهمن ۱۳۹۱ ۰۱:۳۷ ق.ظ)saho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:  

(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط:  سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)

به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.

شاید
این استدلالم ببینین

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

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

[MR_KH]

(۲۲ بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ)saho نوشته شده توسط:  

(22 بهمن ۱۳۹۱ ۰۱:۳۹ ق.ظ)MR_KH نوشته شده توسط:  به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!

پس مشکل اینم حل شد.n-1
امابازم میگم با ۳تا میشه n/2
سوالش مشکل داره

اگه ۳ تا گوی داشته باشیم دوتای اول رو امتحان مکنیم اگه جذب کردن پس حتما مثبت داریم و دوتا هم داریم و یه منفی ولی هنوز نمیدونیم کدوم چه باری داره که با امتحان کردن یکی از دو گوی اول با گوی سوم مشخص میشه، اگر هم دو گوی اول همدیگرو دفع کردن یا مثبت نداریم یا دوتا داریم که همین دو گوی دفع شده هستن و منفی ها یا سه تا هستن یا یکی که بازهم با امتحان یکی از دو گوی اول با گوی سوم بار گوی ها مشخص میشه

[mahdiii]

درسته n-1

[pouya sal]

باید کلید بیاد این دست کم ایهام داشت ،من خودم n-1 زدم نمدونم چرا اما تجربه ام می گه n/2 میشه!!!.احساس میکنم این ازون سوال مزخرفاست که اخر سر حالم و میگیره.

[saho]

(۲۲ بهمن ۱۳۹۱ ۰۱:۲۵ ب.ظ)pouya sal نوشته شده توسط:  باید کلید بیاد این دست کم ایهام داشت ،من خودم n-1 زدم نمدونم چرا اما تجربه ام می گه n/2 میشه!!!.احساس میکنم این ازون سوال مزخرفاست که اخر سر حالم و میگیره.

نه بنظرمیاد همون n-1میشه
خداییش این چه کنکوریه که این همه ادم بعدکلی خوندن نمیتونن سر یه گزینه به تفاهم برسن.
اخه من به سازمان سنجش چی بگم با این سوالاش؟؟؟؟؟؟؟؟؟؟؟؟؟؟