توصیه شده, مسابقه

مسابقه دوم : چالش برنامه نویسی به زبان C

چالش زبان C

مسابقه اول سیسوگ (مسابقه اول: درک سخت افزار) انتقادهای زیادی رو در پی داشت تا جایی که حتی خودمم به نتیجه مسابقه شک کردم!!‌ یکی دو روز وقت گذاشتم و به بهینه‌ترین شکل ممکن برنامه را به زبان اسمبلی باز نویسی کردم و در کمال تعجب نه تنها نتیجه تغییر نکرد بلکه اختلاف حتی بیشتر هم شد اگر شما عملی تست کردید و نتیجه غیر از چیزی بود که ما اعلام کردیم خوشحال می‌شویم که نتیجه را با هم بررسی کنیم!!

بگذریم این بار قرار چالش ساده‌تر از قبل داشته باشم و فعلاً کاری به سخت افزار نداشته باشم و یکم مسابقه را نرم افزاری کنیم و باید زبان مورد استفاده زبان C است.

 

صورت مساله:

تابعی بنویسید که دو عدد (از نوع بدون علامت ۱۶ بیتی) را دریافت کند و بزرگ‌ترین عدد را برگرداند!


احتمالاً تا اینجا مقداری خنده دار به نظر می‌رسد چرا که به سادگی یک خط زیر می‌شود تابع را نوشت:

البته قرار نیست مسابقه این چنین ساده باشد و لازم است که شرط‌های دیگری هم به آن اضافه کنیم

  • نباید از هیچ گونه ساختار شرطی استفاده شود (حتی شرط‌های درون بدنه حلقه)
  • از هیچ تابعی نباید استفاده شود مگر آن که بدنه آن با توجه شرط اول باز نویسی شود.

احتمالاً مقداری کار سخت‌تر شد! ولی همچنان راه حل‌های فراوانی می‌توانید در اینترنت برای این مسئله پیدا کنید که چند نمونه از آنها را در ادامه قرار می‌دهیم.

یا 

و نمونه‌های زیاد دیگر! پس لازمه پیش شرط‌ها را سخت‌گیرانه‌تر کنیم.

 

پیش شرط ها

  • نباید از هیچ گونه ساختار شرطی استفاده شود ( <,>,==,<=,>=,&&,||,!,!= ) {حتی شرط‌های درون بدنه حلقه}
  • نباید از عملیات جمع و منهی استفاده شود (-,+,-=,+=)
  • نباید از عملیات ضرب و تقسیم استفاده شود (*,/,/=,*=)
  • از هیچ تابعی نباید استفاده شود مگر آن که بدنه آن با توجه شرط اول، دوم و سوم بازنویسی شود.
  • استفاده مستقیم و غیر مستقیم از دستورات اسمبلی مجاز نمی‌باشد.

 

اما جایزه

کسانی که بتوانند تابع را با توجه به پیش شرط‌ها پیاده سازی کنند به قید قرعه آموزش برنامه نویسی c برای میکروکنترلر مطابق سبک ناسا را به عنوان هدیه دریافت خواهد کرد.

که البته بعد از انجام مسابقه و با توجه به استقبال شرکت کنندگان, تهیه کننده آموزش نیز یک نسخه به عنوان جایزه در نظر گرفتند.

 

ارسال جواب

پاسخ‌های خود را در زیر همین پست کامنت کنید.

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

مهلت پاسخ هم تا اخر روز 29 اسفند ماه 98 هست.

 

 

شروع سال جدید و پایان چالش دوم سیسوگ

قبل از هر سخنی لازمه که پابان سال ۱۹۳۸ و شروع سال ۱۳۹۹ به تمام دوستان و همراهان سیسوگ تبریک عرض کنم. امیدوارم که در این سال تمام برنامه هاتون با کمترین خطای ممکن کامپایل بشه (بدون خطا که زندگی معنی نداره) و خواسته هاتون محقق بشه.  بگذارید بریم سر مسابقه! بگذارید بگم که واقعا انتظار چنین استقبالی رو نداشتم، مخصوصا حجم پاسخ های صحیح واقعا از چیزی که فکر می‌کردم بیشتر بود که واقعا برام جای خوشحالی داشت و داره.

همونطور که بیشتر دوستان حدس زدند برای حل این مساله باید دست به دامن گیت های دیجیتال شد و دقیقا مشابه کاری که توی ALU برای مقایسه بین اعداد انجام میشه رو اینجا پیاده سازی کنیم. که در واقع این میشه راه مستقیم و یه راه غیر مستفیم هم  وجود داره که میشه پیاده سازی توابع جمع و تفریق با کمک گیت های منطقی و استفاده از آنها مطابق معادلات ریاضی مربوطه.

همونطور که پیداست روش اول روش کوتاه تری است٬ و البته پیاده سازی آن هم ساده تر است پس ما هم به سراغ همین راه حل خواهیم رفت. مقایسه دو عدد با کمک گیت های منطقی واقعا ساده است٬ به جدول زیر دقت کنید 

جدول بالا مقایسه بین دو بیت است که اگر بخواهیم با گیت آن را پیاده سازی کنیم مداری معادل مدار زیر خواهد داشت

با توجه به نیاز مساله ما تنها نیاز به مثلا عبارت  A>B است داریم و برای پیاده سازی آن تنها به یک گیت not و یک گیت and نیاز است. اما متغییر های ما یک بیتی نیستند بلکه ۱۶ بیتی هستند در ضمن مساله که باید به آن توجه داشت ارزش بیت ها است که اگر هر کدام از آنها بیت با ارزش بیشتر داشت قطعا آن عدد بزرگ تر است. پس لازم است که ورودی از مقایسه در مرحله قبل را نیز داشته باشیم. که به سادگی با عبارت زیر قابل تشخصی خواهد بود

 

بر اساس همین عبارت و گسترش آن برای ۱۶ بیت به سادگی میتوان این مساله را حل کرد. تنها نکته ای که میماند انتخاب عدد بزرگتر است٬ عبارت فوق خروجی صفر یا یک خواهد داشت چطور می توانیم صفر یا یک را عدد بزرگتر تبدیل کنیم ؟؟؟؟

جواب ساده است با استفاده از آرایه. ایندکس صفر آرایه را عدد b قرار میدهیم و ایندکس یک آن را عدد a. وقتی خروجی عبارت یک باشد یعنی a بزرگتر است و ماا لازم است ایندکس یک آرایه را برگردانیم و وقتی صفر باشد که یعنی b بزرگتر است ایندکس صفر آرایه برمیگردانیم. به همین سادگی کار تمام است. به کد زیر دقت کنید :

 

 

خب دوازده نفر تا الان پاسخ درست را ارائه کردند که روش و راه حل اونها را میتونید در زیر ببنید 

 

نفر اول آقای محمود نقدی :

 

 

نفر دوم آقای محمدجواد واعظ :

 

 

نفر سوم آقای مهدی خلیلی فر :

 

 

نفر چهارم آقای شهرام نوربخش راد:

 

نفر پنجم آقای کامین جلیلی:

 

نفر ششم آقای سعید گرجی:

 

نفر هفتم آقای رسول بیرانوند:

 

نفر هشتم آقای مهدی راهی:

 

نفر نهم آقای علی ترابی

نفر دهم آقای پوریا