نمایش نتایج 1 تا 5 از 5

نام تاپیک: الگوریتم بازگشتی تعیین اول بودن یک عدد

  1. #1

    الگوریتم بازگشتی تعیین اول بودن یک عدد

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

  2. #2
    سلام
    این برنامه حداقل 5-4 تا الگوریتم مختلف داره. من الان 2 تا الگوریتم رو حضور ذهن دارم، ولی چون کی برد فارسی ندارم و تایپ فارسی برام سخته یکیشو میگم، اگر شد و تونستم تایپ کنم دومیشم به چشم.

    راه حل خیلی ساده ست، یه حلقه بازگشتی بنویس که عدد n (عدد مورد نظر) را به ترتیب بر اعداد 2 تا رادیکال n تقسیم کند و در اولین موردی که تقسیم پذیر بود از حلقه خارج شود. اگر هم مقسوم علیه از رادیکال n بزرگتر شد از حلقه خارج شده مقدار n را برگرداند. این الگوریتم در واقع الگوریتم prime number واقعی نیست، بلکه الگوریتم پیدا کردن کوچکترین مقسوم علیه است. ولی در این مورد نیز کاملا کاربردی ست.
    یکی از الگوریتم های اصلی این برنامه الگوریتم فرمت Fermat Test است که در سال 1637 میلادی توسط Pierre de Fermat ابداع گردید. اگه بتونم اونم می ذارم.

  3. #3
    کاربر دائمی آواتار manager
    تاریخ عضویت
    شهریور 1384
    محل زندگی
    Z
    سن
    38
    پست
    771

    Exclamation

    دوست عزیز این روش بازگشتی نیست..زمان مصرفیش جذر n هست و فکر کنم همون چیزی که این دوستمون مدنظرش بود ...
    void findPrimes(bignum topCandidate)
    {
    bignum candidate = 2;
    while(candidate <= topCandidate)
    {
    bignum trialDivisor = 2;
    int prime = 1;
    while(trialDivisor * trialDivisor <= candidate)
    {
    if(candidate % trialDivisor == 0)
    {
    prime = 0;
    break;
    }
    trialDivisor++;
    }
    if(prime) printPrime(candidate);
    candidate++;
    }
    }

    اگر بازگشتیش کنی زمان مصرفیش بسیار زیاد می شه و برای اعداد بزرگ نه تنها جواب نمی ده بلکه خودت پشیمون می شی از اجرای برنامه ..ولی اگر خواستی بگو برات می ذارم اینجا ...

    حالا من یه سوال دارم آیا کسی الگوریتم بهتری (با زمان مصرفی کمتری) سراغ داره ؟

  4. #4
    سام آقای aliji اول ازتون ممنون من اون چیزی که شما گفتین رو بلدم اما من الگوریتم بازگشتی می خوام!!!
    --------------------
    یک روش دیگر هم برای این کار هست با توجه به تعریف زیر:
    عددی اول هست که بر هیچ کدام از اعداد اول کوچکتر از خودش بخش پذیر نباشد
    آخرین ویرایش به وسیله kiani_behzad : پنج شنبه 25 آبان 1385 در 10:58 صبح دلیل: این پست به دلیل تکراری بودن بطور خودکار ادغام شده است.

  5. #5
    کاربر دائمی آواتار manager
    تاریخ عضویت
    شهریور 1384
    محل زندگی
    Z
    سن
    38
    پست
    771
    این از همون روش استفاده می کنه ولی بازگشتی !!

    function Prime( n)
    if IsPrime(n,2) then
    return true
    else
    return false
    end

    function IsPrime( n, trialDivisor)
    if ( n % trialDivisor =0)
    return false
    else if ( trialDivisor * trialDivisor > n)
    return true
    else
    return IsPrime( n, trialDivisor+1)
    end


    و این هم یه روش دیگه غیر بازگشتی :

    function IsPrime( n)
    if ( (n-1)!+1 % n =0)
    return true
    else return false
    end


    و این هم ابتدائی ترین روش با بدترین زمان مصرفی !!

    function Prime( n)
    if IsPrime(n,2) then
    return true
    else
    return false
    end

    function IsPrime( n, trialDivisor)
    if ( n % trialDivisor = 0 )
    return false
    else if ( trialDivisor>=n)
    return true
    else return IsPrime( n, trialDivisor+1)
    end


تاپیک های مشابه

  1. ساختن exe برنامه و تعیین آیکون آن
    نوشته شده توسط dorna1985 در بخش C#‎‎
    پاسخ: 5
    آخرین پست: سه شنبه 09 بهمن 1386, 11:52 صبح
  2. مشکل در تعیین فرم اصلی
    نوشته شده توسط fazel-d در بخش برنامه نویسی در Delphi
    پاسخ: 2
    آخرین پست: جمعه 05 بهمن 1386, 14:32 عصر

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •