سوال ۳۹ چرا می شه(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
(۲۱ بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)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
چه سوتی دادم خدایا.اخ.راست میگید.سوال ۳۹ چی ؟
(۲۱ بهمن ۱۳۹۱ ۰۹:۲۳ ب.ظ)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 میشه.
شما از ۳۹ مطمئنید ؟لطفا اگه مطمئنید بگین.
(۲۱ بهمن ۱۳۹۱ ۰۹:۰۸ ب.ظ)pouya sal نوشته شده توسط: سوال ۳۹ چرا می شه(logm+1) لطفا با استدلاال قدسی کیه؟با استدلال بگید لطفا؟به نظرم جوابتون درسته.اما من اینطوری تحلیل کردم که برای بدست آوردنش یا باید log n بار الگوریتم selection رو انجام بدیم تا همشون بدست بیاد که میشه n log n یا بیایم کلشو مرتب کنیم که اونم میشه n logn .دوستان میشه توضیح بدن چطور n بدست آوردن ؟
سوال ۴۲
بنابر 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
باشه logn بار selection روی چه اندازه برحسب n فراخوانی میکنید اگه مطالب و دنبال کنین توضیح دادیم
(۲۱ بهمن ۱۳۹۱ ۰۷:۳۳ ب.ظ)mahdiii نوشته شده توسط:منظور از دست کم چی؟حالت خوشبینانه؟یا حداقل زمان کل انجام کار(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
آره برای این مثال (۳ گوی) با یه مقایسه میشه. کلا سوالا غیر استاندارده. باید می گفت تعداد گویها ۳=<
شما برای ۵ و بعد از اون دیگه نمی تونید با n/2 به نتیجه برسید.
به عنوان مثال برای ۵ (شما نمی دونید که ۴ و ۱ هست یا ۳ و ۲) بنابراین باید همون n-1 مقایسه رو انجام بدید حداقل که زمانی هست که گویهای با بار موافق با هم مقایسه می شوند.
(۲۱ بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
(۲۲ بهمن ۱۳۹۱ ۰۱:۲۶ ق.ظ)saho نوشته شده توسط:برای هر تعداد گوی که بگید میشه n-1!چه ۵ تا چه ۳ تا چه هر چی!(22 بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
من واسه ۵تا مثالشوگفتم.نگفتم حواب حتما همینه گفتم واسه ۳تا و۵تا که n-1نشد.وجواب به n/2نزدیکتره
(۲۲ بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:شاید(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
این استدلالم ببینین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۲ بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:واسه ۳تا یکی کافیه.قطعا(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
(۲۲ بهمن ۱۳۹۱ ۰۱:۲۶ ق.ظ)saho نوشته شده توسط:برای هر تعداد گوی که بگید میشه n-1!چه ۵ تا چه ۳ تا چه هر چی!(22 بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
من واسه ۵تا مثالشوگفتم.نگفتم حواب حتما همینه گفتم واسه ۳تا و۵تا که n-1نشد.وجواب به n/2نزدیکتره
به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!
(۲۲ بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ)saho نوشته شده توسط:دوست عزیز شما یه بار اون الگوریتمی که من بالا نوشتم رو بخونی دیگه نمیگی با ۳ میشه n/2!!!(22 بهمن ۱۳۹۱ ۰۱:۳۹ ق.ظ)MR_KH نوشته شده توسط: به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!پس مشکل اینم حل شد.n-1
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!
امابازم میگم با ۳تا میشه n/2
سوالش مشکل داره
(۲۲ بهمن ۱۳۹۱ ۰۲:۰۰ ق.ظ)mohammadjavadkho نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ)saho نوشته شده توسط:دوست عزیز شما یه بار اون الگوریتمی که من بالا نوشتم رو بخونی دیگه نمیگی با ۳ میشه n/2!!!(22 بهمن ۱۳۹۱ ۰۱:۳۹ ق.ظ)MR_KH نوشته شده توسط: به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!پس مشکل اینم حل شد.n-1
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!
امابازم میگم با ۳تا میشه n/2
سوالش مشکل داره
حق باشماست
(۲۲ بهمن ۱۳۹۱ ۰۱:۳۷ ق.ظ)saho نوشته شده توسط:این استدلالی که میگید اومده اینطور حساب کرده که ما میدونیم که تعداد منفی ها یکی کمتر از مثبت ها هست. چنین چیزیو از کجای سوال میشه فهمید؟ما فقط کل و میدونیم دیکه نمیدونیم که هر کدوم چند تاست.و میدونیم که تعداد منفی ها فرد ومثبت ها زوج.(22 بهمن ۱۳۹۱ ۰۱:۲۲ ق.ظ)mohammadjavadkho نوشته شده توسط:شاید(21 بهمن ۱۳۹۱ ۰۷:۱۰ ب.ظ)saho نوشته شده توسط: سوال ۳۷ که ظاهرا ختم بخیرشد.به نظر من میشه n-1 .چون مساله هیچ داده خاصی نداده.فقط گفته منفی ها تعدادشون فرد و مثبت ها تعدادشون زوج. اینم واسه این گفته که در آخر وقتی گوی ها رو به دو گروه تقسیم کردیم بدونیم که گروهی که تعدادش فرد میشه گو ی های منفی و گروهی که تعدادش زوج میشه گوی های مثبت.ما از طریق مقایسه نمیتونیم بفهمیم که کدوم مثبته و کدوم منفی.فقط میتونیم هم نوع بودن یا نبودنشون رو تشخیص بدیم.بعد که با n-1 مقایسه گوی ها رو به دو گروه تقسیم کردیم(یه گوی رو میگیریم و با همه مقایسه میکنیم اونایی که با این گوی نمونه شبیه هستن تو یه گزوه و اونایی هم که شبیه نیستن تو یه گروه دیگه) گروهی که تعدادش فرد میشه منفی ها و گروه زوج هم میشه مثبت ها.
درمورد سوال گوی های مثبت منفی نظرتون چیه؟
من هرطور حساب میکنم n-1نمیشه
یه مثال ساده داشتن ۳ گوی که مسلما دوتاش مثبته وبهترین حالتشه اینکه اول همین دوتا را نزدیک هم کنیم .
پس بایک بار امتحان که به n/2نزدیکتره.(سوال گفته دست کم)
این استدلالم ببینین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۲ بهمن ۱۳۹۱ ۰۱:۵۱ ق.ظ)saho نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۱:۳۹ ق.ظ)MR_KH نوشته شده توسط: به نظر من هم سوال گوی ها n-1 میشه با اینکه خودم n/2 زدم!پس مشکل اینم حل شد.n-1
الان که دوباره سوالو می خونم مبینم که در بهترین حالت میشه در n/2 تعداد گوی های مثبت و منفی رو تشخیص داد و در n-1 بار هر گوی از نظر مثبت منفی. یه اشتباه دیگه! من همه ی امیدم به این ساختمان بود!
امابازم میگم با ۳تا میشه n/2
سوالش مشکل داره
اگه ۳ تا گوی داشته باشیم دوتای اول رو امتحان مکنیم اگه جذب کردن پس حتما مثبت داریم و دوتا هم داریم و یه منفی ولی هنوز نمیدونیم کدوم چه باری داره که با امتحان کردن یکی از دو گوی اول با گوی سوم مشخص میشه، اگر هم دو گوی اول همدیگرو دفع کردن یا مثبت نداریم یا دوتا داریم که همین دو گوی دفع شده هستن و منفی ها یا سه تا هستن یا یکی که بازهم با امتحان یکی از دو گوی اول با گوی سوم بار گوی ها مشخص میشه
درسته n-1
باید کلید بیاد این دست کم ایهام داشت ،من خودم n-1 زدم نمدونم چرا اما تجربه ام می گه n/2 میشه!!!.احساس میکنم این ازون سوال مزخرفاست که اخر سر حالم و میگیره.
(۲۲ بهمن ۱۳۹۱ ۰۱:۲۵ ب.ظ)pouya sal نوشته شده توسط: باید کلید بیاد این دست کم ایهام داشت ،من خودم n-1 زدم نمدونم چرا اما تجربه ام می گه n/2 میشه!!!.احساس میکنم این ازون سوال مزخرفاست که اخر سر حالم و میگیره.نه بنظرمیاد همون n-1میشه
خداییش این چه کنکوریه که این همه ادم بعدکلی خوندن نمیتونن سر یه گزینه به تفاهم برسن.
اخه من به سازمان سنجش چی بگم با این سوالاش؟؟؟؟؟؟؟؟؟؟؟؟؟؟