ماراتن الگوریتم

[Goharshady]

سلام بر همگی
مرحله ی بعدی کامپیوتر برنامه نویسی است. به همین دلیل خیلی لازم بود که ماراتن الگوریتم برگزار شود.
لطفا الگوریتم ها را به صورت مرحله به مرحله بنویسید یا فلوچارت آنها را بکشید.
همچنین ماراتن برنامه نویسی ایجاد شد که امیدوارم این دو تا مفید باشند.
فقط چند تا نکته»
1- تا وقتی سوال حل نشده وجود دارد ، سوال دیگری نگذارید
2-شماره ی سوال را بالای مطلبتان بنویسید
3- از درج الگوریتم ها در تگ کد جدا خودداری کنید
4- شروع و پایان برای الگوریتم خود در نظر بگیرید

 

[Goharshady]

[center:a7743075c3]1[/center:a7743075c3]اینجا هم مانند ماراتن برنامه نویسی از آسان شروع می کنم و همان مسئله ی 1 ماراتن برنامه نویسی را به عنوان مسئله ی 1 ماراتن الگوریتم می نویسم.

الگوریتمی بنویسید که معادله ی درجه ی اول ax+b=c را حل کند.

 

[Olympiad]

اين رو شما بنويسيد تا با نحوه ي نوشتن آشنا بشم....

 

[Goharshady]

این هم الگوریتمش (سعی کنید الگوریتمهاتون تمیز و مرتب باشند)

1-شروع
2-a و b و c را بخوان
3-x را برابر

قرار بده
4- x را چاپ کن
5- پایان

1. Start
2. Read a,b,c
3. 
   = x
4. Print x
5. End

 

[Olympiad]

سوال دو مال خودمه ....
ميدونم آسونه ولي خودتون گفتيد از آسون شروع كنيد ....

سوال : فرض كنيد يك سري از اعداد طبيعي داريم كه پشت سر هم قرار دارند و به ترتيب صعودي . الگوريتمي طراحي كنيد كه عددي از ورودي گرفته و اگر آن عدد وجود داشت ، عدد يك را چاپ كند و در غير اين صورت عدد صفر را چاپ كند.

 

[Goharshady]

2
پیشنهاد می کنم Order الگوریتم را هم تعیین کنید که یک کمی سخت بشه

 

[Olympiad]

2
پیشنهاد می کنم Order الگوریتم را هم تعیین کنید که یک کمی سخت بشه

خوب شما بگيد ....

 

[mahtaaab]

اينجا صعودي بودن اعداد لازمه ؟

 

[Goharshady]

[center:d16d154760]2[/center:d16d154760]اگر Order تعیین نکنند ، لازم نیست
اما من Order تعیین می کنم.
الگوریتمی بنویسید که از

باشد. (n تعداد اعداد است)

مثلا اگر بخواهیم بدون در نظر گرفتن Order یک الگوریتم بنویسیم می توان این را پیشنهاد داد:

0- شروع
1- عدد input را بخوان
2- a را برابر 0 قرار بده
3- برای هر یک از اعداد دنباله مثل x
3-1- اگر x=input
3-1-1- مقدار a را برابر 1 قرار بده
4-a را چاپ کن
5-پایان

 

[Goharshady]

[center:d720d79066]2[/center:d720d79066]ببخشید ولی داره خیلی طول می کشه
الگوریتم درست binary sorted search است. فرض کنید تعداد اعداد n باشد.(n متغیر است)

1-شروع
2- a را برابر 0 قرار بده
3-عدد input را بخوان
4-تعداد اعداد را در n قرار بده
5- اگر n از صفر بزرگتر است:
5-1-input را با

امین عدد مقایسه کن
5-1-1- اگر input بزرگتر بود ، همه ی اعداد قبل از

و خود

را حذف کن و به مرحله ی 4 برو
5-1-2-اگر input کوچکتر بود ، همه ی اعداد بعد از

و خود

را حذف کن و به مرحله ی 4 برو
5-1-3- اگر مساوی بودند ، a را برابر 1 قرار بده و به مرحله ی 6 برو
6-a را چاپ کن
7-پایان

 

[Goharshady]

[center:a74ccabf9f]3[/center:a74ccabf9f][center:a74ccabf9f]این سوال از مرحله ی دوم شانزدهمین المپیاد کامپیوتر ایران است[/center:a74ccabf9f]آیدا قصد دارد جشن تولد بگیرد. متأسفانه به دلیل مشغله ی زیاد، تصمیم گرفته است مسئولیت کلیه ی تدارکات مراسم عروسی را به دوستش آقای « کاف » بدهد! آقای « کاف » پس از جست و جوی فراوان برای تدارکات نور عروسی، موفق به خرید یک « ریسه » ی 100 لامپی (شامل 100 عدد سرپیچ لامپ و 100 عدد لامپ) شده است. ریسه تعدادی سرپیچ متصل به هم است که در صورتی که به آن ها لامپ بسته شود، به زیبایی روشن می شوند. البته فروشنده گفته است که دقیقا 50 تا از لامپ ها سالم و 50 تای بقیه خراب اند. هم چنین دقیقا 50 تا از سرپیچ ها سالم و بقیه خراب اند!

آقای کاف قصد دارد، لامپ ها و سرپیچ های سالم را پیدا کرده و سپس برای به دست آوردن حداکثر نور در جشن تولد، پنجاه لامپ سالم را به پنجاه سرپیچ سالم وصل کند تا پنجاه لامپ روشن در ریسه موجود باشد. برای این منظور آقای کاف ریسه را به برق وصل کرده و شروع به امتحان لامپ ها و سرپیچ ها می کند. از آن جا که او هیچ وسیله ی اضافه ای در اختیار ندارد و لامپ های سالم و خراب و نیز سرپیچ های سالم و خراب کاملا شبیه هم هستند، او می تواند فقط با بستن و باز کردن لامپ ها و سرپیچ ها به یک دیگر، آن ها را بیازماید. می دانیم که یک لامپ اگر به یک سرپیچ بسته شود، تنها در صورتی روشن می شود که هم سرپیچ سالم باشد و هم لامپ.

ضمنا می دانیم که باز کردن یک لامپ از یک سرپیچ دقیقا یک دقیقه طول می کشد ولی از آن جا آقای کاف در بستن لامپ به سرپیچ مهارت زیادی دارد، زمان بستن یک لامپ صفر ثانیه فرض می شود.

الگوریتمی برای آقای کاف بنویسید (یعنی مراحل دقیق انجام کار را مشخص کنید) که در حداقل زمان بتواند لامپ های سالم و نیز سرپیچ های سالم را پیدا کرده و ریسه را با 50 لامپ روشن برای جشن تولد آماده کند. دقت کنید که لزومی ندارد که در انتهای کار تمامی لامپ ها به تمامی سرپیچ ها متصل باشند. یک الگوریتم درست (ولی با زمان بد) چنین است:

1) یکی از لامپ هایی که تا کنون آزموده نشده است را بردار.

2) لامپ برداشته شده را با تمام سرپیچ هایی که خالی هستند امتحان کن، در صورتی که روشن شد، لامپ را در آن سرپیچ رها کرده و گرنه به سراغ سرپیچ بعدی برو.

3) اگر لامپ آزموده نشده ای باقی مانده است به مرحله ی 1 برو.

می توان ثابت کرد این الگوریتم در بدترین حالت، 7550 دقیقه طول می کشد.

الف. الگوریتمی بنویسید که حداکثر در 500 دقیقه، ریسه را با 50 لامپ روشن آماده کند. (15 امتیاز)

ب. الگوریتمی بنویسید که حداکثر در 250 دقیقه، ریسه را با 50 لامپ روشن آماده کند. (15 امتیاز)

توجه: حتما در سطر اول پاسخ نامه، حداکثر زمان الگوریتم خود را بنویسید. در صورتی که فقط قسمت « ب » را به درستی حل کنید، نمره ی کامل این مسئله را خواهید گرفت.

 

[Goharshady]

[center:79e2c8a9b2]3[/center:79e2c8a9b2]اگه سوالو حل نمی کنین لااقل نظرتونو درباره اش بگین.
آخرین مهلت پاسخگویی : فردا (تمدید نخواهد شد)

 

[Goharshady]

[center:fecefbc4ce]3[/center:fecefbc4ce]تمدید که شد ولی جواب نگرفت.
اینجا میگه باید مطلب مورد نظرتون رو با دقت بنویسید!
به همین دلیل جوابو تو وبلاگم گذاشتم.
http://www.goharshady.iranblog.com/
از این به بعد می خواهم ماراتن الگوریتم با ماراتن برنامه نویسی هماهنگ شود.
پس سوال بعدی همان سوال اعداد آرمسترانگ است.

 

[Goharshady]

[center:36d216b844]4[/center:36d216b844]سوال چهارم:

این هم فعلا یه سوال آسون دیگه.
به عددی که برابر با مجموع مکعب ارقامش باشد آرمسترانگ می گوییم. مثلا 371 آرمسترانگ است.
برنامه ای بنویسید که n را از ورودی گرفته و نخستین n عدد آرمسترانگ را در خروجی چاپ کند.

حالا اینجا الگوریتمشو بنویسید.

 

[Goharshady]

[center:0f5348f963]4[/center:0f5348f963]
معنای متغیرها:
n : در صورت سوال تعریف شده است
number: عددی که مورد آزمایش قرار می گیرد
k: تعداد اعداد چاپ شده
copy: متغیری که number را در آن می گذاریم و تغییر می دهیم.
sum : جمع مکعبات ارقام عدد

الگوریتم اصلی (متناظر با تابع main)
1-شروع
2-n را از ورودی بخوان
3- k را برابر 0 و number را برابر 1- قرار بده
4-تا زمانی که k از n کوچکتر است:
4-1- یکی به number اضافه کن
4-2- اگر number آرمسترانگ است (چک کردن با الگوریتم فرعی)
4-2-1- number را چاپ کن
4-2-2- یکی به k اضافه کن
5-پایان

الگوریتمی که آرمسترانگ بودن یک عدد را بررسی می کند. (در برنامه متناظر با تابع armstrong است)
1-شروع
2- number را از تابع فراخوان بگیر
3-مقدار number را در copy بریز و sum را برابر صفر قرار بده
4-تا وقتی copy از صفر بزرگتر است:
4-1- مکعب باقیمانده ی copy بر 10 را به sum اضافه کن
4-2- باقیمانده ی تقسیم copy بر 10 را در copy قرار بده
5-اگر sum با number برابر است:
5-1- مقدار true برگردان
در غیر این صورت:
5-2-مقدار false برگردان

 

[Goharshady]

[center:85fbe936c6]5[/center:85fbe936c6]

این سوال از مسابقات ACM سال 2007 دانشگاه کالیفرنیا انتخاب شده است. Sponsor این مسابقات google بوده است.
طریقه ی ورود و خروج اطلاعات توسط خودم آسان سازی شده است.

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

[center:85fbe936c6]

[/center:85fbe936c6]

همانطور که می بینید همه ی این کلمات با معنی هستند.
برنامه ای بنویسید که از کاربر تعداد دلخواهی واژه به صورت string بگیرد و واژه ای را پیدا کند که بتوان از آن بیشترین تعداد حرف را کم کرد و همینطور مشخص کند که چند حرف می توان حذف کرد.
برای مثال اگر کلمات
ant
boy
a
car
an
cant
any
وارد شوند خروجی به این صورت است:
cant:3
یعنی از cant می توان بیشترین تعداد حرف را حذف کرد و این تعداد 3 تاست

الگوریتم این را هم بنویسید

 

[SABB]

برنامه اصلی:
1. n را بگیر.
2. برای i از 0 تا n-1 ، s
1.2. رشته ی s[i را از ورودی بگیر.
2.2. طول رشته ی فوق را در l[i بریز.
3. maximum=0
4. برای i ار 0 تا n-1
1.4. $ رشته ی s[i را در max بریز.
2.4. اگر max>maximum آنگاه max را در maximum بریز. و همچنین i را در j بریز.
5. چاپ کن: s[j]:maximum
6. پایان.

$ رشته ی s[i
0. رشته ی s را در رشته ی ch کپی کن. و maximum و m را برابر 0 قرار بده.
1.برای i از 0 تا l-1
2.1. برای j از i تا l-1
1.2.1. مقدار s[j+1 را در s[j بریز.
3.1. مقدار s[l را برابر 0 قرار بده.
4.1. l را یک واحد کم کن.
5.1. اگر s معنی دار است آنگاه:
{
*m را یک واحد افزایش بده و سپس ُ$ رشته ی جدید را حساب کن و خروجی اش را با m جمع کن.
*آگر maximum کوچکتر از m است maximum را برابر با m قرار بده.
}
6.1. مقدار maximum را به عنوان خروجی برگردان.
7.1. پایان

یه قطعه کد هم برای چک کردن معنی دار بودنه که آسونه

 

[Goharshady]

پس می ریم سوال بعد

 

[SABB]

یعنی درسته؟؟!

 

[Goharshady]

به شرطی که بتونید درست بنویسیدش!