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

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

چالش زبان C

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

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

 

صورت مساله:

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


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

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

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

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

یا 

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

 

پیش شرط ها

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

 

اما جایزه

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

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

 

ارسال جواب

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

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

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

 

 

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

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

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

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

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

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

 

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

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

 

 

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

 

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

 

 

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

 

 

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

 

 

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

 

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

 

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

 

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

 

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

 

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

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

نفر یادهم آقای محسنیان

 

نفر دوازدم آقای اصغر گرزین:

نفر سیزدهم آقای احمد:

 

نفر چهاردهم عنایت جوادی :

نفر پانزدهم آقا یا خانم M4M :

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

 

 

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

 

 

اعلام برنده های مسابقه:

خب بعد از بررسی های کاملتر و اینکه جواب برخی هم به عنوان هرزنامه شناخته شده بود تعداد جوابهای صحیح 17 نفری  شدند که ما بصورت نرم افزاری قرعه کشی کردیم و دو نفر از دوستان به عنوان برنده انتخاب شدند:

 

قرعه کشی برنامه

 

و برنده ها عبارتند از آقایان :

  • نفر نهم آقای علی ترابی
  • نفر سیزدهم آقای احمد

ممنون میشم دوستان برنده به آی دی تلگرام سیسوگ @Sisoogos پیغام بدند تا جایزه خدمتشون ارائه بشه.

 

انتشار مطالب با ذکر نام و آدرس وب سایت سیسوگ، بلامانع است.

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

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

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

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

  1. مهدی رهی مهدی گفت:

    سلام عید مبارک
    مسابقه جالبی بود
    کوتاهترین پاسخ مال خود سیسوگه که حدود 10 خط و طولانی ترینش هم 325 خطه!!!!!!!!!!!!!!!!!!!!!!
    وقتی مسابقه رو دیدم وقت نداشتم فکر کنم فقط شروع کردم به کد زدن، حاصل کد بدون فکر شده 32 برابر که این باعث میشه توی یه برنامه واقعی معایب زیر رو داشته باشیم:
    1) حجم فلش مصرفی زیاد
    2) سرعت اجرا بشدت کند
    3) حافظه اشغالی برای stack بدلیل فراخونی ها زیاد بشه
    4) رم اسفاده شده هم زیاد بشه
    —————
    دوست عزیزی که این مسابقه رو بی ارزش دونستن:
    مزایای همچین مسابقه ای:
    1) حس رقابت بین برنامه نویسان که نتیجش افزایش خلاقیت میشه
    2) نشون دادن اینکه برای انجام یه هدف حداقل چقدر میشه راه حل داشته باشیم
    3) ارتباط بیشتر برنامه نویسان با هم
    4) نکته مهم: زبان c یه زبان خاصه، چون این قابلیت رو داره که دستورات جدیدی باهاش ساخت و این همون دلیلیه که اکثر زبان های جدید بیسشون زبان c هست و زمانی که شما بخواین یه دستور جدید تولید کنید دقیقا به چالشی مثل همین مسابقه روبه رو میشین چرا که در این مسابقه با کنار گذاشتن دستورات پایه شما رو مجبور میکنه که اون دستورات رو خودتون بسازید، حالا مگه پیش میاد که ما بخوایم یه دستور جدید بسازیم؟
    بله
    مخصوصا زمانی که بخواین به سخت افزار ها نفوذ کنید، یا بخواید مسایلی رو حل کنید که محدودیت هایی توی زبان c و زبان های های دیگه وجود داره که این قسمت بیشتر برای بخش R&D (تحقیق و توسعه) شرکت ها پیش میاد.

    دوستان سیسوگی بابت این مسابقه و هزینه (مالی و زمانی) که بابتش کردید دومو آریگاتو گوزایماشتا، دوزو…

    1. Sisoog Os Sisoog Os گفت:

      سلام عید شما هم مبارک و بابت انرژی که تزریق کردید
      ممنون بابت توضیحات کاملتون 🙂 و جوابی که به جای ما دادید :-))

  2. محمد مهدی مرادی M4m گفت:

    سلام
    من دو لینک فرستاده بودم که برای کد و توضیح بود ولی ارسال نشده 🙁

    1. زئوس Zeus زئوس Zeus گفت:

      عجیبه واقعا ، با ایدی تلگرام سیسوگ در ارتباط باشید

      1. محمد مهدی مرادی m4m گفت:

        گفتن که کامنتم رفته توی هرزنامه چون لینک داشته، و برسی خواهیم کرد کد رو

        1. زئوس Zeus زئوس Zeus گفت:

          بسیار عالی امروز بررسی میکنم کد های جا مونده رو

  3. هیچکس گفت:

    به نظرم این مسابقه در واقع هیچ ربطی به دانش زبان سی و کد نویسی نرم افزاری ندارد
    اینکه قابلیت های اصلی زبان رو ازش بگیریم و بخواهیم یک مساله رو حل کنیم هرگز در دنیای حقیقی واقع نخواهد شد.
    در واقع یکطور هنرنمایی است. یا یک استفاده غیر معمول از سی برای توصیف سخت افزار.
    به نظرم بی ارزشه

    1. Sisoog Os Sisoog Os گفت:

      ممنون از نظر شما دوست عزیز

  4. محم گفت:

    مگه نگفتید شرط استفاده نشه؟ بجز جواب فونیکس همشون از if استفاده کردند چرا؟!

    1. Sisoog Os Sisoog Os گفت:

      اون قسمت کدی هست که ما نوشتیم تا حالتهای مختلف را تست کنیم و جزء تابع نیست

  5. مرتضی گفت:

    طبق جمله زیر که بیان فرمودید
    “همونطور که بیشتر دوستان حدس زدند برای حل این مساله باید دست به دامن گیت های دیجیتال شد و دقیقا مشابه کاری که توی ALU برای مقایسه بین اعداد انجام میشه رو اینجا پیاده سازی کنیم. که در واقع این میشه راه مستقیم و یه راه غیر مستفیم هم وجود داره که میشه پیاده سازی توابع جمع و تفریق با کمک گیت های منطقی و استفاده از آنها مطابق معادلات ریاضی مربوطه.”
    بنده بهترین کد رو نوشتم و فقط از گیت های منطقی برای پیاده سازی عمل تفریق استفاده کردم و از آنجا که میدانستم عدد 16 بیتی هست بنده حاصلضرب sizeof(int) * 8 را برابر 32 دیگر نوشتم و البته میتوانستم عمل ضرب را نیز با گیت های منطقی و بدون هیچگونه شرطی پیاده سازی کنم. و کد بنده به شرح زیر نیز هست و کلیه قوانینم بیشتر همه رعایت کردم و درصورتی که اکثر جوابهایی که صحیح بیان کردید همه از دستور IF و حلقه FOR باشرط استفاده کرده اند. میتوانید این نظر را نیز با بقیه دوستان به اشتراک بزارید. اگر جواب بنده صحیح نباشه واقعا چالش مسخره ای است. چون من همه قوانین را رعایت کردم.
    #include

    // Subtraction two numbers without using the ‘-‘ operator
    int subtract(int x, int y)
    {
    // Iterate till there
    // is no carry
    while (y)
    {
    // borrow contains common
    // set bits of y and unset
    // bits of x
    int borrow = (~x) & y;

    // Subtraction of bits of x
    // and y where at least one
    // of the bits is not set
    x = x ^ y;

    // Borrow is shifted by one
    // so that subtracting it from
    // x gives the required sum
    y = borrow <> (sizeof(int) * 8 – 1)));
    // sizeof(int) = 4 byte =====> 4*8 = 32
    return subtract(x,(subtract(x,y) & (subtract(x,y) >> subtract(32,1))));
    }

    int main()
    {
    int x,y;
    printf (“Please enter a : “);
    scanf(“%d”,&x);
    printf (“Please enter b : “);
    scanf(“%d”,&y);
    printf(“Max is %d”, Max(x, y));
    return 0;
    }

    1. زئوس Zeus زئوس Zeus گفت:

      سلام دوست عزیز فکر میکنم سوءتفاهم پیش آمده و لازمه توضیحاتی و خدمتتون بدم که این مساله حل بشه !
      توضیح اول در خصوص وجود if و for در کدهای : در واقع این کد ها کد های تست بنده برای بررسی عملکرد صحیح توابع ارسالی است – تمام حالت های ورودی A,B رو به توابع دوستان میدیم و با مقدار بزرگتر چک میکنیم ! اگر اختلافی وجود داشته باشه لاگ میگیریم. که دوستان به اشتباه اون تست کد رو بع عنوان کد دوستان منتشر کردن! توابع ارسالی دوستان تابع zMax هست اگه توی اون توابع تناقض پیدا کردید حق با شماست.

      توضیح دوم در خصوص وجود حلقه توی کد شما و چرایی این که چرا قابل پذیرش نیست : ببینید توی کد یکی از دوستان حلقه به شکل زیر استفاده شده

      for(int i=0; i<16; i++) AgB |= (AcoB <

      1. مرتضی گفت:

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

        1. زئوس Zeus زئوس Zeus گفت:

          ذکر کردم {حتی شرط‌های درون بدنه حلقه} ! صرفا این معنی بکار بردن علامت نیست ! حتی نفس شرط هم مشکل داره که شما استفاده کردید
          می تونستند! توی کامنتشون هم دقیقا اشاره کردند :

          البته میدونم که نوشتن for یک کوچولو تقلب حساب میشه چون این نوع for هم درون خودش شرط پایان رو چک میکنه. اما چون به راحتی میشه این for رو باز کرد و دو خطی که توش هست رو برای مقادیر مختلف “i” نوشت (همونطوری که دیشب بدون for این سوال رو حل کردم)، من این تقلب کوچولو رو کردم که فقط کد تمیزتر بشه.

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

  6. علی ترابی علی ترابی گفت:

    پس برنامه من کو ؟ چون زیاد بود با لینک ارسال کردم

    1. Sisoog Os Sisoog Os گفت:

      دوست عزیز کمی صبور باشید تعداد پاسخ ها خیلی زیاد بودند هنوز نیمی از اونها هم بررسی نشده

  7. محمد امین باقری هامانه گفت:

    typedef enum{
    true,
    false
    }bool;
    unsigned int larg_uint( unsigned int a,unsigned int b);
    int main()
    {

    printf(“\n\n number is : %d”, larg_uint(2000,200));
    }

    unsigned int larg_uint(unsigned int a,unsigned int b){

    unsigned int arr[]={a,b};
    return arr[((bool)(b>>a))];

    }

    1. زئوس Zeus زئوس Zeus گفت:

      سلام با این که تایم تمام شده ولی من بررسی کردم کد رو برای ورودی های زیر درست کار نکرد

      A=2,B=3 Max=2
      A=3,B=4 Max=3
      A=3,B=5 Max=3
      A=3,B=6 Max=3
      A=3,B=7 Max=3

  8. ali asghar gorzin گفت:

    https://paste.ubuntu.com/p/MsKW6fS83v/
    سلام میدونم وقت تموم شده اما خواستم راه خودم رو به صورت تمیز و خلاصه شده هم بفرستم. برای درک ساده تر.

    1. ali asghar gorzin گفت:

      البته میدونم که نوشتن for یک کوچولو تقلب حساب میشه چون این نوع for هم درون خودش شرط پایان رو چک میکنه. اما چون به راحتی میشه این for رو باز کرد و دو خطی که توش هست رو برای مقادیر مختلف “i” نوشت (همونطوری که دیشب بدون for این سوال رو حل کردم)، من این تقلب کوچولو رو کردم که فقط کد تمیزتر بشه.

      1. زئوس Zeus زئوس Zeus گفت:

        اوکی مشکلی نداشت – توی کامنت توضیح دادم که چون میشه حلقه رو باز کرد مشکلی نداره استفاده ازش

    2. زئوس Zeus زئوس Zeus گفت:

      ممنون این کد بهتری است 🙂

  9. ehsan گفت:

    https://repl.it/@ehsan00m/test
    سلام پاسخ رو توی لینک بالا گذاشتم ایده کار هم مشابه مدار مقایسه کننده چهار بیتی که در کتاب مدار منطقی مانو هست