فهم الگوریتم

[aezvenoos]

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

[one hacker alone]

يه روش هست كه ارايه بزرگي تعريف ميكني و عمليات رو از اخر ارايه به اول مياي من با اين روش تونستم فاكتوريل اعداد بزرگ رو حساب كنم مثلا فاكتوريل عدد 70000 شد 84 صفحه ورد يعني يه عدد 32 رقمي تقريبا
اما توضيحش مفصل هست و اينجوري نميشه توضيح داد از استادتون بپرسي بد نيست البته الگوريتمي كه مايكروسافت در ماشين حساب ويندوزش داره از مال من بهينه تر بود و زودتر جواب رو ميداد البته با نماد علمي نشون ميداد

[Ananas]

سلام.
با استفاده از فرمول استرلینگ و تابع gamma که ln هم توش داره من فرمولشو به زبان پاسکال نوشته بودم اگه شد برات c++ ش رو می نویسم. علی الحساب لینکای زیر رو ببین :
http://www.rskey.org/CMS/index.php/the-library/11
http://en.wikipedia.org/wiki/Factorial
با این فرموله فاکتوریل اعداد اعشاری رو هم میتونی حساب کنی مثلا 1.5 یا خود 0.5 مثل ماشین حساب ویندوز.

[maktoom]

سلام
به کتاب طراحی الگوریتم ها از نئوپولیتین هم نگاهی بندازید.

[Ananas]

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

long double gamma(const long double x)
{
#define pi 3.14159265358979L
long double x2 = x * x;
long double LnGamma = x * Ln(x) - x + Ln(sqrt(2.0 * pi / x));
long double xn = x;
LnGamma += 1.0L / (12.0L * xn);
xn *= x2;
LnGamma -= 1.0L / (360.0L * xn);
xn *= x2;
LnGamma += 1.0L / (1260.0L * xn);
xn *= x2;
LnGamma -= 1.0L / (1680.0L * xn);
xn *= x2;
LnGamma += 1.0L / (1888.0L * xn);
return exp(LnGamma) + 0.000001L;
}

long double factorial(const long double x)
{
return gamma(x + 1.0);
}

[aezvenoos]

يه روش هست كه ارايه بزرگي تعريف ميكني و عمليات رو از اخر ارايه به اول مياي من با اين روش تونستم فاكتوريل اعداد بزرگ رو حساب كنم مثلا فاكتوريل عدد 70000 شد 84 صفحه ورد يعني يه عدد 32 رقمي تقريبا
اما توضيحش مفصل هست و اينجوري نميشه توضيح داد از استادتون بپرسي بد نيست البته الگوريتمي كه مايكروسافت در ماشين حساب ويندوزش داره از مال من بهينه تر بود و زودتر جواب رو ميداد البته با نماد علمي نشون ميداد
با تشکر از همگی
این روشی که شما فرمودید را برنامش را دیدم اگه یه توضیح مختصر بدید واقعا ممنون می شم برنامش را دیدم واقعا یه جورایی گیج کننده هستش
استاد ما :لبخند: بی خیال

[aezvenoos]

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

long double gamma(const long double x)
{
#define pi 3.14159265358979L
long double x2 = x * x;
long double LnGamma = x * Ln(x) - x + Ln(sqrt(2.0 * pi / x));
long double xn = x;
LnGamma += 1.0L / (12.0L * xn);
xn *= x2;
LnGamma -= 1.0L / (360.0L * xn);
xn *= x2;
LnGamma += 1.0L / (1260.0L * xn);
xn *= x2;
LnGamma -= 1.0L / (1680.0L * xn);
xn *= x2;
LnGamma += 1.0L / (1888.0L * xn);
return exp(LnGamma) + 0.000001L;
}

long double factorial(const long double x)
{
return gamma(x + 1.0);
}

با تشکر از همگی
من فرمول ها را نگاه کردم راستشو بگم زیاد نفهمیدم اگه یه توضیح مختصر بدین از شما ممنون می شم
برنامه شما ارور می ده که Ln تعریف نشده این چه جوریاست؟
با تشکر

[Ananas]

فرمول رو تو آدرسی که گفتم توضیح داده من از رو همون نوشتم. تابع ln لگاریتم طبیعیه که تو فایل math باید پیداش کنی البته بعضی وقتا به شکل log تعریف میشه اگه ln نشد بجایش از log استفاده کن. exp هم ابع معکوس ln هست. اعداد 12 و 360 و 1260 و ... اعدادی هستن که از فرمول خاصی بدست میان و ثابت هستند که تا اینجا تا 6 رقم اعشار دقت فرمول رو بهمراه داره این اعداد ثابت رو خودتم می تونی محاسبه کنی ولی مثل 3.14159265358979 یک چیز ثابتی هست که قبلا حساب کردن و دیگه لازم نیست حساب کنیم. اینا تا بینهایت ادامه دارن ولی ما برای کار با نوع double تا همینجا لازم داریم. در آخر کار عدد رو به تابع exp می بریم تا از ln بیاد بیرون و من با 0.000001 جمع کردم تا رند بشه تو فرمول نبوده. تابع گاما تابعی هست که یکی عقب تر از فاکتوریل هست یعنی برای رسیدن به فاکتوریل باید ورودی گاما رو با 1 جمع کنیم یعنی gamma 5 = 24 ولی factorial 4 = 24. دیگه بقیشو نموتونم توضیح بدم چون نمی دونم و خیلی پیچیدس خودت می تونی تو اون سایته یا کتابای دانشگاهی توضیحشو بخونی من فقط فرمولی که اونجا بود برنامه نویسی کردم.

[aezvenoos]

اگه می تونید یه توضیحی در مورد توان اعداد بزرگ هم بدید با تشکر
من اصلا برنامه بدرد بخوری پیدا نکردم که ببینم چه طوری نوشته
با تشکر

[one hacker alone]

توان اعداد بزرگ يعني ضرب اعداد بزرگ كه من خودم چون براش راهي پيدا نكردم اومدم همون ضرب هاي كوچك رو داخل آرايه هاي بزرگ پياده سازي كردم

[aezvenoos]

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

long double gamma(const long double x)
{
#define pi 3.14159265358979L
long double x2 = x * x;
long double LnGamma = x * Ln(x) - x + Ln(sqrt(2.0 * pi / x));
long double xn = x;
LnGamma += 1.0L / (12.0L * xn);
xn *= x2;
LnGamma -= 1.0L / (360.0L * xn);
xn *= x2;
LnGamma += 1.0L / (1260.0L * xn);
xn *= x2;
LnGamma -= 1.0L / (1680.0L * xn);
xn *= x2;
LnGamma += 1.0L / (1888.0L * xn);
return exp(LnGamma) + 0.000001L;
}

long double factorial(const long double x)
{
return gamma(x + 1.0);
}

این الگوریتمش رو تقریبا فهمیدم ولی
من باید همش عدد باشه هنگ کردم شدید یکی راه حلی می تونه بذاره
با تشکر و غرض از مزاحمت

[Ananas]

ببین با نوع long double دیگه بیشتر ازین نمیتونی عددبزرگتر بنویسی. مشکل از نوع عددی هست که باهاش کار میکنی. اگه شما میخوای توانهای خیلی بزرگ رو محاسبه کنی یه راهش اینه که تابع فاکتوریل رو وارد exp نکنی. یعنی مرحله ی آخر رو انجام ندی ولی جواب رو به شکل exp(x) بنویسی. یا با لگاریتم 10 یه کارایی بکنی وگرنه نوع داده رو باید عوض کنی چون long double نمیکشه. من نمی دونم ماشین حساب ویندوز با چه نوع داده ای کار میکنه که 32 رقم اعشار هم دقت داره، مثلا باید از همچین چیزی استفاده کنی یا خودت یه سیستم طراحی کنی. یه چیزی تو c# شنیدم هست به اسم BigInteger که شاید با اون بتونی توانهای بزرگ رو حساب کنی.

[aezvenoos]

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

[aezvenoos]

توان اعداد بزرگ يعني ضرب اعداد بزرگ كه من خودم چون براش راهي پيدا نكردم اومدم همون ضرب هاي كوچك رو داخل آرايه هاي بزرگ پياده سازي كردم
می تونید یه توضیح مختصر بدین
یا اگه ممکنه کدش رو یه راهنمایی کنین
ممنون

[Ananas]

آها به توان رسوندن عدد بزرگ منظورتونه؟ خوب به خوب کسی مراجع کردی:
یه دستوری تو هلپ دلفی هست به عنوان نمونه که به توان اعداد صحیح رسوندن رو نوشته کدش به این شکله :

function Power(X: Real; Y: Integer): Real;
var
I: Integer;
begin
Result := 1.0;
I := Y;
while I > 0 do
begin
if Odd(I) then Result := Result * X;
I := I div 2;
X := Sqr(X);
end;
end;

که به c++ میشه :

long double Power(long double X, int Y)
{
long double output = 1.0L;
int i = Y;
while (i > 0)
{
if (i % 2 == 1)
output *= X;
i /= 2;
X *= X;
}
return output;
}

خوب حالا برای به توان عدد اعشاری رسوندن باید از بسط تیلور استفاده کنیم که خود c++ تو فایل math.h توابع محاسبه exp و log رو داره ولی اگه دوست داشتین میتونید فرمولشو خودتون بنویسید تو اینترنت دنبال سری تیلور برای exp و power بگردید. اما روش کلی به این شکله :

long double PowerReal(long double Base, long double Exponent)
{
return exp(log(Base) * Exponent);
}

که همه ی توان های اعشاری و صحیح رو جواب میده فقط بنا به تعریف پایه نباید کوچکتر و مساوی صفر باشه.

[aezvenoos]

آها به توان رسوندن عدد بزرگ منظورتونه؟ خوب به خوب کسی مراجع کردی:
یه دستوری تو هلپ دلفی هست به عنوان نمونه که به توان اعداد صحیح رسوندن رو نوشته کدش به این شکله :

function Power(X: Real; Y: Integer): Real;
var
I: Integer;
begin
Result := 1.0;
I := Y;
while I > 0 do
begin
if Odd(I) then Result := Result * X;
I := I div 2;
X := Sqr(X);
end;
end;

که به c++ میشه :

long double Power(long double X, int Y)
{
long double output = 1.0L;
int i = Y;
while (i > 0)
{
if (i % 2 == 1)
output *= X;
i /= 2;
X *= X;
}
return output;
}

خوب حالا برای به توان عدد اعشاری رسوندن باید از بسط تیلور استفاده کنیم که خود c++ تو فایل math.h توابع محاسبه exp و log رو داره ولی اگه دوست داشتین میتونید فرمولشو خودتون بنویسید تو اینترنت دنبال سری تیلور برای exp و power بگردید. اما روش کلی به این شکله :

long double PowerReal(long double Base, long double Exponent)
{
return exp(log(Base) * Exponent);
}

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

[aezvenoos]

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

[Ananas]

چرا از تابع pow() استفاده نمی شه کرد
باید از همین استفاده کنی ولی به نظرم اومد میخوای کد ریاضی ایش رو بدونی و کلا روابط ریاضی ایش رو میخوای و دوست داری خودت بنویسیشون وگرنه تابع pow هم داره همین کارو میکنه و به نظرم سرعتش بهتر از تابعی باشه که خودمون تعریف میکنیم.


حالا اگه من خواستم بخش پذیریش رو بر مثلا ۶ حساب کنم

یک راهش اینه که به 6 تقسیم کنی بعد ببینی عدد اعشاری هست یا صحیح شاید اعشار خیلی کوچیکی داشته باشه که مثلا میتونی بنویسی :

if (abs(int(X) - X) < 0.000001)
{

}

[aezvenoos]

باید از همین استفاده کنی ولی به نظرم اومد میخوای کد ریاضی ایش رو بدونی و کلا روابط ریاضی ایش رو میخوای و دوست داری خودت بنویسیشون وگرنه تابع pow هم داره همین کارو میکنه و به نظرم سرعتش بهتر از تابعی باشه که خودمون تعریف میکنیم.

یک راهش اینه که به 6 تقسیم کنی بعد ببینی عدد اعشاری هست یا صحیح شاید اعشار خیلی کوچیکی داشته باشه که مثلا میتونی بنویسی :

if (abs(int(X) - X) < 0.000001)
{

}

شرمنده از پر سوالی:خجالت:
این آخری چی شد ؟
یه عدد خیلی یزرگ که توانش رو حساب کردیم با تابع مگه به نماد علمی نیست؟
چه طور من بر 6 تقسیم کنم که ببینم باقیمانده داره یا نه ؟
سرریز نداره؟
آخه باید ببینم عددی که توان اون را حساب کردم بر هر عددی بخش پذیره یا نه ؟(منظورم عدد خیلی بزرگ هستش)
واقعا ممنون:خجالت:

[maktoom]

پیاده سازیش نه Ln می خواد نه لگاریتم و نه فرمول پیچیده ای. دو روش آرایه ای در کتاب نئوپولیتین وجود داره که اگه حوصله کنید و یه سری به مرجع اصلی طراحی الگوریتم ها بزنید واقعا به جواب می رسید.
واقعا در تعجبم! پاسخ واضح دقیقا چیزی که می خواید در یک کتاب مرجع که به زبان فارسیه و در همه دانشگاه ها بنظر باید وجود داشته باشه هست. اونوقت اینجا دارید با اما و اگرهای دوستان و قطعا برنامه ها سرو کله می زنید. یه کتاب مرجع توسط حداقل یه استاد مسلم اون نوشته شده، چرا توضیحات و نحوه بین اون رو میذارید کنار و خودتون رو با درگیر با چیزای دیگه می کنید که آخرشم یا اکتفا کنید با رفع نیاز فعلی یا سرخورده و شکست خورده رها کنید؟ خوب به مرجع اصلی که خیلی هم مناسب توضیح داده و عالی هم حل کرده مراجعه کنید.
نئوپولیتین دو جور حل کرده. هر دو هم با روش آرایه ای. روش اول قدری پیچیدگی زمانیش بالاست. واسه همینم یه تغییر جزئی بسیار قابل فهم داده و پیچیدگی زمانی رو بهبود داده.
ایرادی نه به شما گرفتم و نه از دوستان. خواستم شما به دردی که خودم اخیرا درمانش رو یافتم دچار نشید. به جای پرسشهای بسیار و جوابهای کم یا گاها بی ربط و نصفه، به مرجع اصلیش مراجعه کنید. مخصوصا طراحی الگوریتم. یکبار رجوع می کنید و یکبار به جواب می رسید. از همه مهمتر (با احترام به دوستان)... بی منّت یا سرزنش.

موفق باشید.

[Ananas]

ین آخری چی شد ؟
یه عدد خیلی یزرگ که توانش رو حساب کردیم با تابع مگه به نماد علمی نیست؟
چه طور من بر 6 تقسیم کنم که ببینم باقیمانده داره یا نه ؟
سرریز نداره؟
آخه باید ببینم عددی که توان اون را حساب کردم بر هر عددی بخش پذیره یا نه ؟(منظورم عدد خیلی بزرگ هستش)
واقعا ممنون:خجالت:

خوب اینو با روشی که گفتم نمیشه چون ارقام کوچیکش با به توان رسوندن از بین میرن اما maktoom (http://barnamenevis.org/member.php?123790-maktoom) درست میگه باید یه راه خاصی داشته باشه که تو مرجعی که maktoom (http://barnamenevis.org/member.php?123790-maktoom) گفته باید دنبالش باشی، بگرد اونو پیدا کن.