شرح مفصل لتنفيذ خوارزمية معامل الطاقة السريعة في لغة جافا

يُقترح إدخال خوارزمية معامل الطاقة السريعة من خلال قيود الخوارزمية الساذجة التي تأخذ معامل من العشرية ذات الأعداد الكبيرة. في الطريقة الساذجة ، نحسب رقمًا مثل 5^1003 ٪ 31 ، والذي يستهلك موارد الحوسبة لدينا كثيرًا. الشيء الأكثر إثارة للقلق في عملية الحساب بأكملها هي عملية 5^1003.

العيب 1: في عملية حساب الفهرس لاحقًا ، لا يتم زيادة جميع الأرقام المحسوبة ، والتي تشغل الكثير من موارد الحوسبة الخاصة بنا (بشكل رئيسي ، والمساحة)

العيب 2: الأرقام في حسابنا كبيرة لدرجة أن أجهزة الكمبيوتر الحالية لدينا لا يمكنها تسجيل مثل هذه البيانات الطويلة ، لذلك يجب أن نفكر في طريقة أكثر كفاءة لحل هذه المشكلة.

عندما نحسب AB ٪ C ، فإن الطريقة الأكثر ملاءمة هي استدعاء طريقة POW في وظيفة الرياضيات. ومع ذلك ، في بعض الأحيان يكون عدد A إلى قوة B أكبر من اللازم ، وحتى الدقة المزدوجة سوف يفيض. في هذا الوقت ، من أجل الحصول على نتيجة AB ٪ C ، سنختار استخدام خوارزمية معامل الطاقة السريعة للحصول على النتيجة التي نريدها ببساطة وبسرعة.

من أجل منع الأرقام من التفيض وتقليل التعقيد ، نحتاج إلى استخدام الصيغة التالية:

Abmod C = (A mod c) bmod c

معنى هذه الصيغة هو: المنتج يأخذ الباقي مساوياً للمنتج يأخذ الباقي. من السهل أن نرى أن هذه الصيغة متعدية ، حتى نتمكن من جعل أصغر وأصغر من خلال أخذ الباقي باستمرار لمنع الفائض.

من الناحية النظرية ، مع هذه الصيغة ، يمكننا كتابة التعليمات البرمجية. من خلال تعديل A المستمر ، نضمن أن النتيجة لن تتفوق. يمكن أن يحسب هذا بالفعل معامل القدرة على قوة أكبر ، لكن تعقيد هذه الطريقة لا يزال O (n) وليس سريعًا.

من أجل حساب معامل القوة بسرعة أكبر ، نحتاج أيضًا إلى الاعتماد على الصيغة التالية:

AB mod c = (a2) b/2 mod c ، b هو رقم زوجي
ab mod c = ((a2) b/2 ・ a) mod c ، b هو رقم فردي

هذه الصيغة بسيطة للغاية. المبدأ هو استبدال B باستمرار بمربع A واستبدال B بالنصف الأصلي. لأننا نعرف من خلال الصيغة الأولى أن وحدة الرقم لديها نفس القوة (هذه الجملة مربكة بعض الشيء ، مما يعني الصيغة واحدة). ثم تأثير استخدام نتيجة A*A ٪ C بدلاً من A هو نفسه.

لذلك وفقًا للصيغة المذكورة أعلاه ، نحصل على طريقة لحساب الطاقة السريعة مع التعقيد O (logn):

 استيراد java.util.scanner ؛ الطبقة العامة الرئيسية {public static void main (string [] args) {scanner in = new scanner (system.in) ؛ int a = in.nextint () ، b = in.nextint () ، c = in.nextint () ؛ int res = 1 ؛ ٪ = ج ؛ لـ (؛ b! = 0 ؛ b /= 2) {if (b ٪ 2 == 1) res = (res * a) ٪ c ؛ a = (a * a) ٪ c ؛ } system.out.println (res) ؛ }}

هذه الخوارزمية مثل هذا تقريبا. تتمثل الخطوة الأولى في تقليل ٪ = C لمنع الرقم من الفائض عند إجراء*A لأول مرة. في الحلقة for ، إذا كان B عبارة عن رقم فردي ، فدع Res = res*a ، ثم اضرب A في النتيجة أولاً ، ثم معالجتها. من أجل منع الرقم من الفائض ، يتم تشغيل النتيجة mod c of res*a مباشرة. في هذا للحلقة ، عاجلاً أم آجلاً ، سوف يساوي B 1 ، ويدخل الفرع if ، وأخيراً حساب قيمة res و mod c يخرج من الحلقة ، ثم النتيجة النهائية.

لخص

ما سبق هو كل التفسير المفصل لهذه المقالة حول تنفيذ خوارزمية معامل الطاقة السريعة للغة Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!