هل يحتوي نطاق الأعداد الصحيحة على مربع كامل واحد على الأقل؟

Question

نظرا لعددين صحيحين a و b, هل هناك طريقة فعالة لاختبار ما إذا كان هناك عدد صحيح آخر n مثل ذلك a ≤ n2 < b?

لا أحتاج أن أعرف n, ، فقط ما إذا كان واحدا على الأقل من هذا القبيل n موجود أم لا، لذلك آمل أن يكون تجنب حساب الجذور التربيعية من أي أرقام في الفترة.

بالرغم من اختبار ما إذا كان عدد صحيح فردي هو مربع كامل أسرع من حساب الجذر التربيعي, ، قد يكون النطاق كبيرًا وأفضل أيضًا تجنب إجراء هذا الاختبار لكل رقم داخل النطاق.

أمثلة:

• intervalContainsSquare(2, 3) => خطأ
• intervalContainsSquare(5, 9) => خطأ (ملاحظة:9 خارج هذا الفاصل الزمني)
• intervalContainsSquare(9, 9) => خطأ (هذا الفاصل الزمني فارغ)
• intervalContainsSquare(4, 9) => صحيح (4 داخل هذه الفترة)
• intervalContainsSquare(5, 16) => صحيح (9 داخل هذه الفترة)
• intervalContainsSquare(1, 10) => صحيح (1، 4، 9 كلها تقع داخل هذه الفترة)

Answer 1

حساب ما إذا كان الرقم مربعًا أم لا ، ليس أسرع من حساب جذره التربيعي في الحالات الصعبة ، على حد علمي. ما هو صحيح هو أنه يمكنك القيام بتكريم لعلم أنه ليس مربعًا ، مما قد يوفر لك الوقت في المتوسط.

وبالمثل ، في هذه المشكلة ، يمكنك القيام بتكريم محدد لتحديد أن SQRT (B) -SQRT (A)> = 1 ، مما يعني أن A و B متكافئان بما يكفي لدرجة أنه يجب أن يكون هناك مربع بينهما. مع بعض الجبر ، يكون عدم المساواة هذا مكافئًا للحالة (BA-1)^2> = 4*A +ب). لذلك يمكن القيام بهذه التركيب المسبق بدون جذور مربعة ، فقط مع منتج عدد صحيح واحد وبعض الإضافات والطرح.

إذا كان A و B متماثلين تمامًا تقريبًا ، فلا يزال بإمكانك استخدام خدعة النظر إلى أرقام ثنائية منخفضة الترتيب كحجة مسبقة لمعرفة أنه لا يوجد مربع بينهما. لكن يجب أن يكونوا قريبين جدًا لدرجة أن هذه التسمم المسبق قد لا تستحق ذلك.

إذا كانت هذه الحواسيب المسبقة غير حاسمة ، فلا يمكنني التفكير في أي شيء آخر غير حل أي شخص آخر ، A <= Ceil (SQRT (A))^2 <B.

---

نظرًا لوجود مسألة القيام بالجبر بشكل صحيح:

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)
(b-a-1)^2 >= 4*a

---

أيضًا: بشكل عام عندما يكون A رقمًا كبيرًا ، يمكنك حساب SQRT (أ) باستخدام طريقة نيوتن ، أو مع جدول بحث متبوعًا ببعض خطوات طريقة نيوتن. من المعدل أن يحسب السقف (SQRT (A)) من SQRT (A) ، لأنه يمكن تبسيط الحساب النقطة العائمة إلى حساب صحيح ، ولأنك لا تحتاج أنت فقط سوف ترمي بعيدا. ولكن في الممارسة العملية ، يمكن أن تكون وظيفة المكتبة العددية أسرع بكثير إذا كانت تستخدم جذور مربعة يتم تنفيذها في رمز صغير. إذا لم يكن لديك أي رمز صغير لأي سبب من الأسباب ، فقد يكون من المفيد أن يستحق كل من السقف الرمز اليدوي (SQRT (A)). ربما تكون الحالة الأكثر إثارة للاهتمام إذا كانت A و B هي أعداد صحيحة غير محدودة (مثل ، ألف رقم). ولكن بالنسبة للأعداد الصحيحة الحجم العادية على جهاز كمبيوتر عادي غير عادي ، لا يمكنك التغلب على FPU.

Answer 2

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

تحتاج فقط إلى حساب جذر مربع واحد بهذه الطريقة.

من أجل تجنب مشكلة عندما يكون A يساوي B ، يجب عليك التحقق من ذلك أولاً. لأن هذه الحالة خاطئة دائما.

Answer 3

إذا كنت تقبل حساب جذور مربعة ، بسبب رتابة ذلك ، لديك عدم المساواة هذا الذي يعادل جولة البداية الخاصة بك:

sqrt(a) <= n < sqrt(b)

وهكذا ، إذا floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 مضمون ليكون مثل هذا n.

Answer 4

1. احصل على الجذر التربيعي للرقم السفلي وتجوله
2. احصل على الجذر التربيعي للعدد الأعلى وقم بدوره إلى أسفل
3. إذا كان 1 أقل أو متساوية 2 ، فسيكون هناك مربع مثالي

Answer 5

أوجد الجزء المتكامل من sqrt(a) وsqrt(b)، على سبيل المثال sa وsb.

إذا سا² = أ، ثم إخراج نعم.

إذا بينالي الشارقة² = b وsa = sb-1، ثم لا يوجد إخراج.

إذا كان الناتج sa <sb نعم.

آخر رقم الإخراج.

يمكنك تحسين ما سبق للتخلص من حساب sqrt(b) (على غرار إجابة JDunkerly).

أم أنك تريد تجنب حساب الجذور التربيعية لـ a وb أيضًا؟

---

يمكنك تجنب حساب الجذور التربيعية تمامًا باستخدام طريقة مشابهة للبحث الثنائي.

عليك أن تبدأ بتخمين n، n = 1 وحساب n²

فكر في ما إذا كان <= n < b، فيمكنك التوقف.

إذا n < a < b، فإنك تضاعف تخمينك n.إذا كان a < b < n، فإنك تجعله قريبًا من متوسط ​​التخمين الحالي + التخمين السابق.

سيكون هذا هو الوقت O(logb).

Answer 6

بالإضافة إلى حل Jdunkerley الجميل (+1) ، قد يكون هناك تحسن محتمل يجب اختباره واستخدامه الجذور عدد صحيح مربع لحساب الجذور المربعة الصحيح

Answer 7

لماذا تأمل في تجنب الجذور المربعة تمامًا؟ حتى قبل أن تصل إلى الطريقة الأكثر فاعلية لحل هذا ، فقد رأيت أساليب تدعو إلى جذور مربعة فقط. لقد تم ذلك في وقت o (1) ، لذلك يبدو لي أن أي تحسن يمكن أن تأمل في القيام به سيستغرق وقتًا أطول للتفكير أكثر مما يوفر لك وقت الحوسبة. هل أنا مخطئ؟

Answer 8

طريقة واحدة هي استخدام طريقة نيوتن للعثور على جذر عدد صحيح إلى عن على b. ثم يمكنك التحقق مما إذا كان هذا الرقم يقع في النطاق. أشك في أنه أسرع من مجرد استدعاء وظيفة الجذر التربيعي ، لكنه بالتأكيد أكثر إثارة للاهتمام:

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}