سلام دوستان.من تازه شروع کردم به خوندن الگوریتم و یه سوال داشتم:
دیدم توی خیلی کتابا با استقرا سوالا رو حل میکنن به این صورت که مثلا میگن که فرض میکنیم برای n-1 یک الگوریتم داریم که بهمون جواب داده.بعدش میان با یه سری کارا از n به n-1 میرسن و درنتیجه سوال حل میشه طبق فرض استقرا(یا فوقش اینکه بعدا دوباره عدد آخر رو اضافه میکنن و با چندتا حالت بندی و استفاده از این که n-1 جواب داده کار سوال رو تموم میکنن)
این راه ها قابل قبولن؟برای سوالایی که میگن الگوریتم ارائه بدید.آخه ما اومدیم و گفتیم که برای n-1 میشه جواب گرفت(استقرا) ولی خوب همین میشه چطوره؟
منظورم اینه که ما عملا یک الگوریتم ندادیم و فقط سوالو ساده تر کردیم و از استقرا استفاده کردیم.
این جور جوابا قابل قبولن؟(برای مثال سوال ستاره مشهور که توی کتاب طراحی الگوریتم(که کل ایرانو گشتمو پیداش نکردم!) با استقرا حل شده(میدونم الگوریتم جامعشو البته) و یا سوال بزرگترین زیر مجموعه اعداد از یک تابع به طوری که یک به یک باشن و خروجیم تو خودشون باشه در کتاب آشنایی با الگوریتم که اومده گفته برای n-1 فرض میکنیم که جواب گرفتیم و بزرگترین مشخص شده.حالا اون عضوی که ورودیش صفره رو حذف میکنیم و تعداد میشه n-1 و طبق استقرا جواب میگیریم از این حالت پس حل شد!)
من برای این با این جور جوابا مشکل دارم چون به نظرم کاری که ما کردیم اثبات وجود الگوریتمه و خوده الگوریتمو ارائه نکردیم!
درضمن یه سوال هم دارم:یه عده سرباز داریم که هر کی یه طرفه.هر ثانیه هر دو نفری که رو به روی هم باشن روشونو برمیگردونن.الگوریتمی بدید که مدت زمان رو محاسبه کنه(زمانی که آخرش دیگه کسی از جاش تکون نمیخوره)
من جوابم اینه ولی به نظرم خیلی جواب ساده ایه و شاید غیرقابل قبول:
S=0
تا وقتی که دو نفر هستن که رو به روی هم وایستادن(دو نفر که دقیقا کنار هم هستن البته):
بگرد و تموم زوج هایی که رو به روی هم هستن(دو نفر که کنار هم وایستادن البته) رو پیدا کن و به S یه دونه اضافه کن.
این افراد رو عقب گرد کن.
S رو چاپ کن : دی
دیدم توی خیلی کتابا با استقرا سوالا رو حل میکنن به این صورت که مثلا میگن که فرض میکنیم برای n-1 یک الگوریتم داریم که بهمون جواب داده.بعدش میان با یه سری کارا از n به n-1 میرسن و درنتیجه سوال حل میشه طبق فرض استقرا(یا فوقش اینکه بعدا دوباره عدد آخر رو اضافه میکنن و با چندتا حالت بندی و استفاده از این که n-1 جواب داده کار سوال رو تموم میکنن)
این راه ها قابل قبولن؟برای سوالایی که میگن الگوریتم ارائه بدید.آخه ما اومدیم و گفتیم که برای n-1 میشه جواب گرفت(استقرا) ولی خوب همین میشه چطوره؟
منظورم اینه که ما عملا یک الگوریتم ندادیم و فقط سوالو ساده تر کردیم و از استقرا استفاده کردیم.
این جور جوابا قابل قبولن؟(برای مثال سوال ستاره مشهور که توی کتاب طراحی الگوریتم(که کل ایرانو گشتمو پیداش نکردم!) با استقرا حل شده(میدونم الگوریتم جامعشو البته) و یا سوال بزرگترین زیر مجموعه اعداد از یک تابع به طوری که یک به یک باشن و خروجیم تو خودشون باشه در کتاب آشنایی با الگوریتم که اومده گفته برای n-1 فرض میکنیم که جواب گرفتیم و بزرگترین مشخص شده.حالا اون عضوی که ورودیش صفره رو حذف میکنیم و تعداد میشه n-1 و طبق استقرا جواب میگیریم از این حالت پس حل شد!)
من برای این با این جور جوابا مشکل دارم چون به نظرم کاری که ما کردیم اثبات وجود الگوریتمه و خوده الگوریتمو ارائه نکردیم!
درضمن یه سوال هم دارم:یه عده سرباز داریم که هر کی یه طرفه.هر ثانیه هر دو نفری که رو به روی هم باشن روشونو برمیگردونن.الگوریتمی بدید که مدت زمان رو محاسبه کنه(زمانی که آخرش دیگه کسی از جاش تکون نمیخوره)
من جوابم اینه ولی به نظرم خیلی جواب ساده ایه و شاید غیرقابل قبول:
S=0
تا وقتی که دو نفر هستن که رو به روی هم وایستادن(دو نفر که دقیقا کنار هم هستن البته):
بگرد و تموم زوج هایی که رو به روی هم هستن(دو نفر که کنار هم وایستادن البته) رو پیدا کن و به S یه دونه اضافه کن.
این افراد رو عقب گرد کن.
S رو چاپ کن : دی