كيفية حل أول 100 مشكلة لمشروع أويلر 11-15

بي -11-15

إذا كنت جديدًا هنا، فابدأ بالجزء الأول . مرحبًا بكم في الجزء الثالث من سلسلة "حل مشكلات مشروع أويلر" حيث سنتناول بعض التحديات الممتازة في الرياضيات والبرمجة . ليس من الضروري أن تكون عبقريًا؛ كل ما تحتاجه هو الفضول وحب حل المشكلات. دعونا الغوص في!

المشكلة 11: أكبر منتج في الشبكة

فهم

لقد تم إعطاؤك شبكة من الأرقام مقاس 20 × 20. مهمتك هي العثور على المنتج الأكبر لأربعة أرقام متجاورة في أي اتجاه: أعلى، أسفل، يسار، يمين، أو قطريًا.

منطق القوة الغاشمة

قم بالتمرير عبر الشبكة، واحسب حاصل ضرب أربعة أرقام متجاورة في كل اتجاه من الاتجاهات المحتملة. تتبع أكبر منتج.

تطبيقات بايثون وجافا سكريبت

بايثون:

def أكبر_شبكة_منتج(شبكة): max_product = 0 صفوف، cols = len(grid)، len(grid[0]) for i in range(rows): for j in range(cols): # Horizontal if j <= cols - 4 : max_product = max(max_product, Grid[i][j] *grid[i][j + 1] *grid[i][j + 2] *grid[i][j + 3]) # Vertical if i < = صفوف - 4: max_product = max(max_product,grid[i][j] *grid[i + 1][j] *grid[i + 2][j] *grid[i + 3][j]) # قطري (من اليسار إلى اليمين) إذا كان i <= صفوف - 4 وj <= أعمدة - 4: max_product = max(max_product,grid[i][j] *grid[i + 1][j + 1] *grid[i + 2][j + 2] *grid[i + 3][j + 3]) # قطري (من اليمين إلى اليسار) إذا i >= 3 وj <= cols - 4: max_product = max(max_product,grid[i ] [j] * الشبكة [i - 1] [j + 1] * الشبكة [i - 2] [j + 2] * الشبكة [i - 3] [j + 3]) تُرجع max_product

جافا سكريبت:

دالة أكبرGridProduct(grid) { Let maxProduct = 0; صفوف ثابتة = الشبكة. الطول؛ const cols =grid[0].length; for (let i = 0; i <rows; i++) { for (let j = 0; j < cols; j++) { // أفقي if (j <= cols - 4) { maxProduct = Math.max(maxProduct,grid [i] [j] * الشبكة [i] [j + 1] * الشبكة [i] [j + 2] * الشبكة [i] [j + 3])؛ } // عمودي if (i <=rows - 4) { maxProduct = Math.max(maxProduct,grid[i][j] *grid[i + 1][j] *grid[i + 2][j] * الشبكة [i + 3] [ي])؛ } // قطري (من اليسار إلى اليمين) if (i <=rows - 4 && j <= cols - 4) { maxProduct = Math.max(maxProduct,grid[i][j] *grid[i + 1][j + 1] * الشبكة[i + 2] [j + 2] * الشبكة [i + 3] [j + 3])؛ } // قطري (من اليمين إلى اليسار) if (i >= 3 && j <= cols - 4) { maxProduct = Math.max(maxProduct,grid[i][j] *grid[i - 1][j + 1 ] * الشبكة[i - 2] [j + 2] * الشبكة [i - 3] [j + 3])؛ } } } return maxProduct; } 

الزمان والمكان وO الكبير

  • تعقيد الوقت: O (ن ^ 2)
  • تعقيد الفضاء: O(1)

المسألة 12: العدد الثلاثي القابل للقسمة بشدة

فهم

الرقم الثلاثي هو رقم يمكن تمثيله على شكل مثلث بنقاط. مهمتك هي العثور على الرقم الثلاثي الأول الذي يحتوي على أكثر من 500 مقسوم.

منطق القوة الغاشمة

قم بإنشاء أرقام مثلثية وعد قواسمها حتى تجد رقمًا به أكثر من 500 مقسومًا.

تطبيقات بايثون وجافا سكريبت

بايثون:

def count_divisors(n): العد = 0 لـ i في النطاق(1, int(n ** 0.5) + 1): إذا n % i == 0: count += 2 # i و n/i يُرجع العد def compute( ): n = 1 triangular_number = 0 بينما صحيح: triangular_number += n إذا count_divisors(triangular_number) > 500: إرجاع triangular_number n += 1

جافا سكريبت:

دالة countDivisors(n) { Let count = 0; for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i === 0) { count += 2; // i و n/i } } return count; } دالة computeTriangularNumber() { Let n = 1; دع الرقم الثلاثي = 0؛ while (true) { triangularNumber += n; if (countDivisors(triangularNumber) > 500) { return triangularNumber; } ن++; } } 

الزمان والمكان وO الكبير

  • تعقيد الوقت: O(n \sqrt{n})
  • تعقيد الفضاء: O(1)

المشكلة 13: مبلغ كبير

فهم

لديك قائمة مكونة من 100 رقم مكون من 50 رقمًا. مهمتك هي العثور على الأرقام العشرة الأولى من مجموع هذه الأرقام.

منطق القوة الغاشمة

اجمع كل الأرقام وخذ الأرقام العشرة الأولى من المجموع.

تطبيقات بايثون وجافا سكريبت

بايثون:

تعريف الحساب (الأرقام): Total_sum = مجموع (الأرقام) إرجاع str (total_sum) [:10]

جافا سكريبت:

وظيفة computeLargeSum(numbers) { const TotalSum = BigInt(numbers.reduce((a, b) => BigInt(a) + BigInt(b), 0)); إرجاع TotalSum.toString().substring(0, 10); } 

الزمان والمكان وO الكبير

  • تعقيد الوقت: O(n)
  • تعقيد الفضاء: O(1)

المشكلة 14: أطول تسلسل كولاتز

فهم

يبدأ تسلسل Collatz بأي عدد صحيح موجب n . الحد التالي في المتتابعة هو n/2 n /2 إذا n زوجية، و3n + 13 n +1 إذا n فردية. ينتهي التسلسل عندما يصل إلى 1. تطلب منك المشكلة العثور على الرقم الموجود أسفل المليون والذي ينتج عنه أطول تسلسل كولاتز.

منطق القوة الغاشمة

قم بالتكرار عبر جميع الأرقام الأقل من مليون وقم بإنشاء تسلسلات Collatz الخاصة بها، مع تتبع الأطول.

تطبيقات بايثون وجافا سكريبت

بايثون:

def Collatz_length(n): length = 1 while n > 1: length += 1 if n % 2 == 0: n //= 2 else: n = 3 * n + 1 return length def compute(): max_length = 0 الرقم = 0 لـ i في النطاق (1، 1000000): الطول = طول Collatz (i) إذا كان الطول > max_length: max_length = رقم الطول = أرجع الرقم

جافا سكريبت:

وظيفة CollatzLength(n) { Let length = 1; بينما (ن > 1) { الطول++؛ إذا (ن % 2 === 0) { ن /= 2; } else { n = 3 * n + 1; } } طول الإرجاع؛ } function computeLongestCollatz() { Let maxLength = 0; دع الرقم = 0؛ for (let i = 1; i < 1000000; i++) { const length = CollatzLength(i); if (length > maxLength) { maxLength = length; الرقم = أنا؛ } } رقم الإرجاع؛ } 

الزمان والمكان وO الكبير

  • تعقيد الوقت: O ( n log n )
  • تعقيد الفضاء: O(1)

المنطق الأمثل للمشكلة 14

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

تطبيقات بايثون وجافا سكريبت

بايثون:

مذكرة = {1: 1} def Collatz_length(n): إذا لم يكن n في المذكرة: مذكرة[n] = 1 + Collatz_length(n // 2) إذا n % 2 == 0 else 1 + Collatz_length(3 * n + 1) ) إرجاع المذكرة [n] def compute(): max_length = 0 number = 0 for i in range(1, 1000000): length = Collatz_length(i) if length > max_length: max_length = length number = i return number

جافا سكريبت:

مذكرة ثابتة = {1: 1}؛ وظيفة CollatzLength(n) { if (!memo[n]) { memo[n] = 1 + (n % 2 === 0 ? CollatzLength(n / 2) : CollatzLength(3 * n + 1)); } إرجاع المذكرة[n]; } function computeLongestCollatz() { Let maxLength = 0; دع الرقم = 0؛ for (let i = 1; i < 1000000; i++) { const length = CollatzLength(i); if (length > maxLength) { maxLength = length; الرقم = أنا؛ } } رقم الإرجاع؛ } 

الزمان والمكان وO الكبير

  • تعقيد الوقت: O ( n log n )
  • تعقيد الفضاء: O ( ن )

المشكلة 15: مسارات شعرية

فهم

لديك شبكة 20 × 20. بدءًا من الزاوية العلوية اليسرى وعدم قدرتك إلا على التحرك لليمين والأسفل، ما عدد المسارات المختلفة التي يمكنك اتباعها للوصول إلى الزاوية اليمنى السفلية؟

منطق القوة الغاشمة

احسب عدد المسارات بشكل متكرر لكل خلية حتى تصل إلى الخلية الوجهة.

تطبيقات بايثون وجافا سكريبت

بايثون:

def count_paths(x, y): if x == 0 or y == 0: return 1 return count_paths(x - 1, y) + count_paths(x, y - 1) # لا يوصى بتشغيله على شبكة 20x20 بسبب وقت حسابي مرتفع # print(count_paths(20, 20))

جافا سكريبت:

دالة countPaths(x, y) { if (x === 0 || y === 0) { return 1; } إرجاع countPaths(x - 1, y) + countPaths(x, y - 1); } // لا يُنصح بالتشغيل على شبكة 20 × 20 نظرًا لارتفاع وقت الحساب // console.log(countPaths(20, 20)); 

الزمان والمكان وO الكبير

  • التعقيد الزمني: O (2 n + m )، حيث n و m هما أبعاد الشبكة
  • تعقيد الفضاء: O ( n × m )

المنطق الأمثل للمشكلة 15

بالنسبة لشبكة بحجم m \times m × n ، يمكن حساب عدد المسارات الفريدة باستخدام الرياضيات التوافقية مثل {{m+n} \choose {m}}( m + n ​).

تطبيقات بايثون وجافا سكريبت

بايثون:

استيراد الرياضيات def compute(): m, n = 20, 20 return math.comb(m + n, m)

جافا سكريبت:

دالة computePaths() { const m = 20, n = 20; دع النتيجة = 1؛ for (let i = 0; i < Math.min(m, n); i++) { result *= (m + n - i); النتيجة /= (ط + 1)؛ } إرجاع النتيجة؛ } 

الزمان والمكان وO الكبير

  • التعقيد الزمني: O(1) (بما أن m و n ثوابت)
  • تعقيد الفضاء: O(1)

https://ahmedradwan.dev

تواصل معنا إذا كنت ترغب في الانضمام إلي وكتابة مقالات مع المهووسين 🙂


© 2024 · الطالب الذي يذاكر كثيرا المستوى التقنية

فئات

وسائل التواصل الاجتماعي

ابق على اتصال على وسائل التواصل الاجتماعي