قصد داریم چند مساله را که بیشتر جنبه ریاضی دارند، حل کرده و برنامه آنها را بنویسیم. بی شک یکی از تاثیرگذار ترین رشته ها در علوم کامپیوتر، ریاضی است. پس بد نیست کمی دید ریاضی خود را گسترش دهیم تا بتوانیم برنامه هایی بنویسیم که مسائل ریاضی را بسادگی و در کمترین زمان ممکن حل کنند.
مساله اول: برنامه ای بنویسید که 2 عدد را گرفته و بزرگ ترین مقسوم علیه مشترک آنها را چاپ کند.
چند روش برای محاسبه بزرگ ترین مقسوم علیه مشترک یا همان ب. م.م وجود دارد. یکی از روش ها این است که بیاییم تمام مقسوم علیه های 2 عدد را محاسبه کنیم و سپس اعداد مشترک را حساب کرده و در یک مجموعه ذخیره کنیم و بزرگ ترین عضو آن را به عنوان ب.م.م در نظر بگیریم. حال نکته این است که آیا این روش، روشی بهینه است؟ یعنی می توان راهی راحت تر و بهتر از این ارائه داد؟
پاسخ «آری» است. یکی دیگر از روش های محاسبه ب.م . م روش نردبانی یا همان روش تقسیمات متوالی است. در روش تقسیمات متوالی عدد بزرگ تر را بر عدد کوچک تر تقسیم می کنیم، اگر خارج قسمت برابر صفر شد، عدد کوچک تر ب.م.م است و اگر صفر نشد، مقسوم علیه را به عنوان عدد بزرگ تر در نظر می گیریم و باقیمانده را به عنوان عدد کوچک تر و سپس عدد بزرگ تر را بر عدد کوچک تر تقسیم می کنیم، آنقدر این کار را تکرار می کنیم که باقیمانده برابر صفر شود. وقتی باقیمانده برابر صفر شد، عدد بزرگ تر که مقسوم علیه مرحله پیشین است را به عنوان ب.م.م در نظر می گیریم.
int num1 = 48, num2 = 16, max , min, temp = 1;
max = num1 » num2 ? num1 : num2;
min = num1 « num2?num1:num2;
while (temp != 0) {
temp = max % min;
max = min;
min = temp;
}
cout «« max;
مساله دوم: مقدار تابع نمایی یک عدد را محاسبه کنید.
منظور از تابع نمایی، تابع e به توان x است. برای محاسبه این تابع می توان از بسط تیلور این تابع که به صورت زیر است، استفاده کرد:
خب، حال اگر بخواهیم سری را حساب کنیم، نیاز به یک حلقه داریم تا تک تک جملات سری را حساب کرده و با جملات قبلی جمع کنیم. در مواقعی که نیاز به محاسبه یک سری است باید به این نکته توجه داشت که سری همگراست یا واگرا. اگر واگرا بود جوابی برای مساله وجود نخواهد داشت چون هیچ وقت حلقه ما به پایان نمی رسد، ولی اگر همگرا بود، می توان با گذاشتن یک شرط تمام شدن آن را نشان داد. مثلا تفاضل جمله nام با جمله n-1ام از یک عدد بسیار کوچکی کمتر باشد یا شرایطی از این دست.
بسیار خب، برگردیم به مساله خودمان. می دانیم که این سری همگراست چون درجه رشد !x از x به توان n بیشتر است، پس همیشه به ازای مقادیر بزرگ، حاصلی کوچک تر از یک تولید می شود. مقدار همگرایی سری برابر جواب مساله یعنی همان مقدار تابع e به توان x است. خب حال مساله این است که چگونه سری را حساب کنیم؟
می دانیم که رشد عدد !x بسیار زیاد است مثلا !1000 یک عدد 154 رقمی می شود و می دانیم که متغیری به این اندازه در زبان های برنامه نویسی وجود ندارد و اگر هم وجود داشته باشد، میزان حافظه اشغالی زیادی نیاز دارد.
راه حل این مساله، استفاده از آرایه است که در شماره های قبلی در مورد آن توضیح داده شد.
یعنی !1000 را با یک آرایه پیاده سازی کنیم و همین طور !1001 و اعداد دیگر و اعمال ریاضی را روی این اعداد انجام دهیم. این راه حل منطقی نیست و زمان بر است، اما آیا این تنها راه حل است؟ پاسخ «نه» است.
در این مقاله قصد داریم راه حل دیگری ارائه دهیم که هم سرعت بیشتری دارد و هم حافظه مصرفی کمتری. در این راه حل برای محاسبه جمله کنونی از جمله پیشین استفاده می کنیم. این روش چند مزیت دارد چون از جمله قبلی استفاده می شود، به این صورت که اگر در مرحله nام باشیم و حاصل عبارت x باشد برای محاسبه جمله n+1 نیازی نداریم که x به توان n+1 تقسیم بر !(n+1) را حساب کنیم. کافی است جمله nام را در x/n+1 ضرب کنیم. با این روش دیگر نیازی به محاسبه اعداد بزرگ نیست و جواب را با کمترین میزان حافظه مصرفی و سرعت بیشتری پیدا می کنیم. مانند کد زیر:
const double epmax = 0.00000000000000005;
double number = 2, n = 0, newer = 0, older = 1, sum = 1;
while (older » epmax) {
n++;
newer = older * (number / n);
sum = sum + newer;
older = newer;
}
کد واضح است، می دانیم جملات سری در حال کوچک تر شدن هستند و در هر مرحله بررسی می کنیم که آیا مقدار older که آخرین جمله است از یک عدد بسیار کوچک بزرگ تر باشد. اگر کوچک تر باشد از حلقه خارج می شود و مقدار sum همان همگرایی سری و مقدار تابع e به توان x است که همان جواب مساله ماست.
منابع: www.ehow.com و en.wikipedia.org
امیربهاءالدین سبط الشیخ
تفکیک و پردازش داده ها
... شبه کد این الگوریتم به صورت زیر است: function merge_sort(m) { var list left, right, result if length(m) «= 1 return m var middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = merge_sort(left) right = merge_sort(right) result = merge(left, right) return result } function merge(left, right) { var list result while length(left) » 0 and length(right) » 0 if first(left)«=first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end while while length(left) » 0 append left to result while length(right) » 0 append right to result return result} پیچیدگی زمانی الگوریتم مرتب سازی ادغامی اگر زمان لازم برای مرتب سازی آرایه n عضوی به روش ادغام برابر (t(n باشد داریم: t(n) = 2t(n/2) + n در این الگوریتم در هر مرحله آرایه به 2 آرایه شکسته می شود و در هر مرحله از ادغام نیز باید n مقایسه صورت بگیرد ...
بهتر از این هم می شود کار کرد!
... 0; y = power3a*x*x + power2b*i; } 2 ارجعات به عناصر آرایه اگر هنگام کدنویسی دقت لازم را نداشته باشیم این محاسبات اضافه که در بالا توضیح داده شد، به پردازش عناصر یک آرایه نیز سرایت می کند و باعث کندی اجرای قطعه کد ما و اتلاف زمان پردازشگر شود ... بگزارید این موضوع را با یک مثال نشان دهیم: فرض کنید دنبال دانشجویانی با اسم “آرش” می گردیم، یک راه این است که “آرش” را با نام همه دانشجویان مقایسه کنیم و کسانی که اسم آنها “آرش” است را در یک لیست ذخیره کنیم، این راه درست است و مشکلی ندارد ولی آیا این راه یک راه بهینه برای حل مساله است؟ پاسخ خیر است، چون در بدترین حالت نام های “آرش” در انتهای لیست هستند و برای یافتن فهرست آنها نیازمند پردازش کل آرایه تا انتها است ... درست است ما یک زمان اضافی برای مرتب سازی آرایه ها صرف کردیم ولی در دفعات بعد برای داده های دیگر نیازی به این عمل نیست چون فقط یک بار داده ها مرتب می شوند و در دفعات بعدی از نتیجه مرتب سازی استفاده می شود ...
عبارات ریاضی در کامپیوتر
... در مورد پشته پیش از این صحبت کردیم، اما برای یاد آوری:پشته یک آرایه است که از ساختار lifo (last input first output) پیروی می کند، یعنی اولین عنصر ورودی آخرین عنصر خروجی است ...
سری اعداد فیبوناچی
... کد روش بازگشتی به صورت زیر است: long fibonaccirecursive(int no) { if ((no == 1) || (no == 2)) return 1; else if (no == 0) return 0; else return fibonaccirecursive(no - 1) + fibonaccirecursive(no - 2); } در هر دو روش ممکن است عدد فیبوناچی حاصل بقدری بزرگ باشد که در متغیر های معمول زبان های برنامه نویسی جای نگیرد، آن وقت تکلیف چیست؟ برای حل این مشکل باید عدد حاصل را یک آرایه تعریف کرده و فرض کنید هر رقم از آرایه یک رقم از عدد است ...
نگاهی به مجموعه نرم افزار koffice2/0
... اگر کاربران در نخستین مواجهه با آرایه ای از dockerها، دچار وحشت یا اضطراب نشوند، دراین صورت به مرور خواهند دید که 2 /0 koffice همه چیز بیشتر در دسترس بوده و در مقایسه با نسخه های قبلی استفاده از آن ها نیز آسان تر است ...
انواع فناوریlcd
... smectic پرکاربردترین آرایه در بین کریستال های مایع nematic است ... کریستالهای مایع فروالکتریک(flc ها) در آرایه ای به همراه مولکول های semectic نوع c از کریستال های مایعی که دارای مولکول های chiral هستند، استفاده می کنند، زیرا طبیعت مارپیچی آن ها اجازه می دهد که وضعیت قرارگیری مولکول ها را در کسری از ثانیه تغییر دهند به همین دلیل flc ها برای استفاده در نمایشگرهای پیشرفته که تصاویرمتحرک با نرخ نوسازی بالا را پخش می کنند، بسیار مناسب هستند ...
انواع raid در سرورها
... در این مقاله پیکربندی آرایه ای و برنامه ای،برای چندین هارد دیسک ارزان قیمت برای داشتن قابلیت fault telorance یا همان کاهش نرخ خطا و همچنین بهبود و افزایش نرخ دسترسی داده ها مهیا شد ...
20 پروژه تحقیقاتی کامپیوتری (2)
... محققان دانشگاه ماساچوست امرس شیوه ای را برای ردیف کردن نوع خاصی از مولکول ها در قالب آرایه های کاملی در نواحی به نسبت گسترده ابداع کرده اند ...
بازی بزرگان
... یکی از ساده ترین روش ها، ذخیره سازی ارقام اعداد در آرایه و انجام عملیات مورد نظر روی آرایه هاست ... حالا بیایید ببینیم که چگونه 2عدد بزرگ را که در آرایه ذخیره شده اند با هم جمع کنیم ... ما اعداد را به صورت آرایه ای از کاراکترها از کاربر دریافت می کنیم ... این عدد به این صورت در آرایه قرار گرفته است: 4خانه باقی مانده بلااستفاده هستند ... ما توسط تابع reverse خانه های آرایه را جابه جا می کنیم و سپس به اندازه اختلاف طول 2عدد با طول بیشتر یا همان len در کد بالا صفر اضافه می کنیم ... در نهایت، حاصل جمع 2عدد در آرایه num1 قرار می گیرد و سپس باید num1 نیز بر عکس شود تا حاصل، نتیجه دلخواه ما باشد ...
|
صفحه 1
|
2 | 3 | 4 |
|
