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

نام تاپیک: الگوریتمی می خواهم که a به توان n را به روش تقسیم و حل بدست بیاورد

  1. #1

    الگوریتمی می خواهم که a به توان n را به روش تقسیم و حل بدست بیاورد

    با سلام ؛

    الگوریتم تقسیم و حل برای a به توان n

  2. #2
    اگر aبه توان nرا برابر با mباشد و شما مقدار mو aرا داشته باشید
    کافی است یک حلقه whileنوشته که در ان
    while m>1
    m=m/a
    n=n+1
    wend
    print n

  3. #3
    کاربر تازه وارد آواتار MMMYousefMMM
    تاریخ عضویت
    اسفند 1384
    محل زندگی
    در پناه حق
    پست
    37
    روش تقسیم و حل با حلقه while نیست عزیز. بلکه برنامه باید بصورت بازگشتی باشد که کدش چنینه

    int power( int ,int );
    void main(){
    clrscr();
    int x = power(2, 5);
    cout<<x;
    getch();
    }
    int power(int m, int n){
    if(n > 0 )
    return m*power(m,n-1);
    return 1;
    }

  4. #4
    کاربر دائمی آواتار اَرژنگ
    تاریخ عضویت
    آبان 1384
    محل زندگی
    arjang8000@gmail.com
    پست
    2,736
    نقل قول نوشته شده توسط MMMYousefMMM
    روش تقسیم و حل با حلقه while نیست عزیز. بلکه برنامه باید بصورت بازگشتی باشد
    اگرچه از روشه که فرستاده شده بود سر درنیاوردم، ولی دلیلی نداره که روشه تقسیم و حل باید بصورت بازگشتی باشد، بلکه روشهایه بازگشتی معمولاً استعداد دارند که برایه روشه تقسیم و حل استفاده بشند.

  5. #5
    کاربر جدید آواتار k.robot
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    ارومیه
    پست
    24
    نقل قول نوشته شده توسط MMMYousefMMM
    روش تقسیم و حل با حلقه while نیست عزیز. بلکه برنامه باید بصورت بازگشتی باشد که کدش چنینه

    int power( int ,int );
    void main(){
    clrscr();
    int x = power(2, 5);
    cout<<x;
    getch();
    }
    int power(int m, int n){
    if(n > 0 )
    return m*power(m,n-1);
    return 1;
    }
    1این که تقسیم و غلبه نیست استقراست
    2 بهینه نیست
    3 درستش اینه:
    float pow(float x, int n)
    {
    if (n==1)
    return x;
    y=pow(x,n/2);
    if(n==n/2*2)
    return y*y;
    else
    return y*y*x
    }

  6. #6
    کاربر تازه وارد آواتار MMMYousefMMM
    تاریخ عضویت
    اسفند 1384
    محل زندگی
    در پناه حق
    پست
    37
    کاملا زیبا کار می کند و خیلی ساده و قابل درک است و این کد شماست که با وجود بهینگی نسبی درک آن مشکل است. در ضمن تقسیم و غلبه است

  7. #7
    کاربر جدید آواتار k.robot
    تاریخ عضویت
    فروردین 1385
    محل زندگی
    ارومیه
    پست
    24
    my friend
    let people judge about them;D

  8. #8
    کاربر دائمی آواتار اَرژنگ
    تاریخ عضویت
    آبان 1384
    محل زندگی
    arjang8000@gmail.com
    پست
    2,736
    نقل قول نوشته شده توسط MMMYousefMMM
    کاملا زیبا کار می کند و خیلی ساده و قابل درک است و این کد شماست که با وجود بهینگی نسبی درک آن مشکل است. در ضمن تقسیم و غلبه است
    با سلام،
    من تا ۲ ماه پیش مثله شما فکر میکردم منتها بعد از کلی برری به این نتیجه رسیدم که منظور از تقسیم (بعضیا بهش میگن غلبه) و حل با روشه اسنباطه یکمی فرق داره.
    در همینجا یک پست بود در مورد اسفاده از تقسیم و حل برایه فاکتوریل.
    من دقیاً همین اشکال شما را بازگو کردم ولی بد از بررسی ه این نکات پی بردم:
    ۱) روشه تقسیم و حل در هر قدم تقسیم مکنه و قسمهایه کوچکر را در دفعه بعد تقسیم مکنه.
    روشه استنباط که جنابه کی رباط بهش اشار کردن فقط از قسمته قبلی یکی کم میکن،
    برایه دیدن فرق بینه روشه استنباط (روشی که شما مثالش را زدید) و روشه تقسیم و حل که چنابه کی‌رباط مثال فرستادند،
    با کاغذ و قلم ۲ را به توانه ۹ برسانید. روشه استنباط :

    Pow(2,9) =
    2* Pow(2,8)=
    2*2* Pow(2,7)
    2*2*2* Pow(2^6)
    .
    .
    .
    2*2*2*2*2*2*2*2*2


    روشه تقسیم و حل:

    Pow(2,9)
    Pow(2,1)*Pow(2,8)
    Pow(2,1)*Pow(2,4)*Pow(2,4)
    Pow(2,1)*Pow(2,4)*Pow(2,2)
    Pow(2,1)*Pow(2,4)*Pow(2,1)*2
    2*2^4*2^2



    در ضمن کسی نگفت که روشه شما اشتباهه، فقط اینکه روشه استنباط را استفاده میکنه نه تقسیم و حل.
    با تشکر از شما و جنابه کی‌رباط برایه این بحض که فرقه بین روشها را کاملاً آشکار میکنه

  9. #9
    کاربر دائمی
    تاریخ عضویت
    مهر 1384
    محل زندگی
    اصفهان
    پست
    136
    این روش بهترین روش برای به توان رساندن است چون پیچیدگی اجرایی این الگوریتم log n است و در تمام الگوریتمهای به توان رساندن بهترین الگوریتم است البته من به صورت pcudocode نوشتم اگر غیر بازگشتی این الگوریتم را هم خواستی بگو تا برات بنویسم.

    ;(procedure power (a,n
    begin
    (if n=1 return(a
    if ((n mod 2)=0) then
    begin
    (p:= power(a,n div 2
    (return (p*p
    end
    else
    begin
    (p:=power(a,n div 2
    (return (p*p*a
    ;end
    ;end

  10. #10
    با عرض سلام خدمت دوستان ضمن احترام به نظر همه دوستان وقتی توان خیلی بزرگ میشه باید مبنای دو آن عدد را حساب کرد فرضا 100=1100100
    حال ه این شکل میشه توان 100 را نوشت
    a*a=a^2*a^2=a^4*a^4=a^8*a^8=a^16*a^16=a^32*a^32=a^ 64*a^64
    100=a^64*a^32*a^4
    پیچیدگی زمانی محاسبه مبنای 2 برابر است با log n
    با این روش خیلی سریع میتوان توان ها را حساب کرد که که log n مرحله است سپس آن های که لازمه در هم ضرب میکنیم
    فکر کنم توضیحات کامل باشه واسه کدش اول بیاین مبنا دئ حساب کنید بعدم حاصل اونهایی که لازمه اگه نتونستین بگین تا بذارم codesho چون باید خودم بنویسم

  11. #11
    کاربر دائمی آواتار reza6384
    تاریخ عضویت
    آبان 1386
    محل زندگی
    تهران - شهرک ژاندارمری
    سن
    39
    پست
    740
    int power( int ,int );
    void main(){
    clrscr();
    int x = power(2, 5);
    cout<<x;
    getch();
    }
    int power(int m, int n){
    if(n > 0 )
    return m*power(m,n-1);
    return 1;
    }
    این کد تقسیم و غلبه هست، (شرط Small داره و مسئله رو به 1 و n-1 زیر مسئله می شکنه ) . اما باید توجه کنی که آنالیز الگوریتم شما اینه :
    T(n) = T(n-1) + 1 , T(1) = 1 ; => T(n) = n

    این تابع هم همین کار رو می کنه و از زمان n هست :



    int pow(int m,int n)
    {
    int i,sum;
    sum = 1;
    for(i=0;i<n;i++)
    { sum *= m; }

    return sum;
    }

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

    در ضمن. یه کم با هم مهربونتر باشیییییییین!

  12. #12

    نقل قول: الگوریتمی می خواهم که a به توان n را به روش تقسیم و حل بدست بیاورد

    بهترین به نقل از k.robot
    float pow(float x, int n)
    {
    if (n==1)
    return x;
    y=pow(x,n/2);
    if(n==n/2*2)
    return y*y;
    else
    return y*y*x
    }

برچسب های این تاپیک

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

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