داراي منطق يا ترفند رياضي هستند. همه الگوريتم هايي كه ياد مي گيريم از ديدگاه رياضي مشتق شده اند. در بيشتر مواقع ، رياضي به ما كمك مي كند تا س withinال را در محدوديت هاي زماني لازم حل كنيم.

همه موضوعات را نمي توان در يك مقاله واحد پوشش داد ، رياضي در برنامه نويسي  اما ما برخي از رايج ترين مفاهيم رياضي در كدگذاري رقابتي را بررسي خواهيم كرد. برخي از اين مفاهيم ممكن است در نگاه اول بسيار دشوار به نظر برسند اما به كار بردن آنها بر مشكلات آنها را براي شما آسان مي كند.

نكته ديگر اين است كه من فقط در مورد مواردي كه بايد به آنها بپردازيد و ترفندهايي براي انجام اين كار اشاره كردم ، اما مي توانيد از منابع آنلاين ديگر براي يادگيري و تمرين آنها كمك بگيريد.

1. BigInteger

براي e. گرم محاسبه فاكتورهاي اعداد بزرگ (فرض كنيد 100) يا تعداد زيادي ورودي در طول 100000 رقم در نظر بگيريد. در c ++ ، حتي اگر از long long int استفاده كنيم ، امكان ذخيره اين اعداد وجود ندارد. يك راه براي گرفتن اين نوع اعداد اين است كه آنها را در يك آرايه عاقلانه تر از بردار استفاده كنيد ... ه رياضي در برنامه نويسي  عدد داراي يك فهرست آرايه خواهد بود ، مانند اين كه عدد 12345 باشد ، سپس 12345٪ 10 = 5 در فهرست [4] و عدد در حال حاضر = 12345/10 = 1234. در حال حاضر 1234٪ 10 = 4 در [3] و به همين ترتيب تا 1٪ 10 = 1 در [0] است ، ايرانيان سايبر يا مي توانيد از رشته نيز استفاده كنيد ، اين كار آسان تر است زيرا آرايه char فقط 1 بايت براي هر شاخص اجازه مي دهد بنابراين شما براي متناسب كردن عدد در فهرست نيازي به عمليات مدولاسيون نداريد.

جاوا كلاس Biginteger را براي رسيدگي به اين امر ارائه مي دهد.

2. GCD ، LCM، الگوريتم اقليدسي ، الگوريتم اقليدسي گسترده

تعاريف GCD و LCM شناخته شده است ، (و در دوره راهنمايي تدريس مي شود) رياضي در برنامه نويسي  من از تعاريف صرف نظر مي كنم. همچنين از آنجا كه lcm (a، b) * gcd (a، b) = a * b ، محاسبه GCD معادل محاسبه LCM است.

حال ، چگونه GCD دو عدد را محاسبه كنيم؟

البته ما مي توانيم عوامل دو عدد را بيابيم و سپس بالاترين عامل مشترك را تعيين كنيم. هر چند كه اعداد بزرگتر مي شوند (مثلاً 155566328819) ، فاكتورسازي بي اثر مي شود.

اينجاست كه الگوريتم اقليدس به نجات ما مي آيد. اين الگوريتم براي اثبات رياضي در برنامه نويسي  آسان gcd (a، b) = gcd (b، r) استفاده مي كند ، كه وقتي a بر b تقسيم مي شود ، يا فقط a٪ b باقي مي ماند.

آيا مي توانيم اعداد (x، y) را طوري پيدا كنيم كه ux + vy = gcd (u، v) ؟. بي نهايت جفت وجود دارد - اين لماي بزوت است. الگوريتم توليد چنين جفت هايي را Extended Euclidean Algorithm مي نامند.

3. غربال اراتوستن و غربال قطعه قطعه شده

ايجاد سريع اعداد اوليه در برخي مشكلات بسيار مهم است. بياييد به دنبال آن باشيم و غربال اراتوستن  رياضي در برنامه نويسي را معرفي كنيم. مي توانيد از غربال اراتوستن براي يافتن همه اعداد اول كوچكتر يا مساوي يك عدد مشخص شده N استفاده كنيد يا اينكه بدانيد يك عدد يك عدد اول است يا خير.

ايده اصلي پشت غربال اراتوستن اين است كه در هر تكرار يك عدد اول جمع آوري مي شود و همه مضرب هاي آن حذف مي شوند. پس از اتمام فرآيند حذف ، همه اعداد بدون علامت كه باقي مي مانند اول هستند. فرض كنيد مي خواهيم همه اعداد اول را بين 2 تا 50 بيابيم. از 2 تا 50 را تكرار كنيد. ما با 2 شروع مي كنيم. از رياضي در برنامه نويسي  آنجا كه بررسي نشده است ، يك عدد اول است.