محدودیت زمانی برای شکل گیری مثلث

با توجه به مجموعه ای از اعداد صحیح مثبت ، تعداد مثلث هایی را که می توان با سه عنصر آرایه مختلف به عنوان سه طرف مثلث تشکیل داد ، پیدا کنید. برای اینکه یک مثلث از 3 مقدار امکان پذیر باشد ، جمع هر یک از دو مقدار (یا طرف) باید بیشتر از مقدار سوم (یا طرف سوم) باشد.

مثال ها:

ورودی: arr = خروجی: 3 توضیح: سه مثلث ممکن است ، و. توجه داشته باشید که یک مثلث ممکن نیست.

ورودی: arr =. خروجی: 6 توضیح: 6 مثلث ممکن وجود دارد: ، ، ، و

تمرین توصیه شده

رویکرد ساده لوح:برای حل مشکل ، ایده زیر را دنبال کنید:

روش Brute Force اجرای سه حلقه و پیگیری تعداد مثلث های ممکن تا کنون است. سه حلقه سه مقدار مختلف را از یک آرایه انتخاب می کنند. حلقه درونی برای خاصیت مثلث که میزان هر دو طرف را مشخص می کند باید بیشتر از مقدار طرف سوم باشد).

مراحل داده شده را برای حل مشکل دنبال کنید:

• سه حلقه تو در تو را اجرا کنید هر حلقه از شاخص حلقه قبلی تا انتهای آرایه یعنی حلقه اول را از 0 تا n ، حلقه J از I تا N و K از J تا N اجرا کنید
• Check if array[i] + array[j]>آرایه [k] ، یعنی جمع دو طرف بیشتر از سوم است
• شرایط 2 را برای همه ترکیب های طرفین با تعویض I ، J ، K بررسی کنید
• اگر هر سه شرط مطابقت دارد ، پس تعداد را افزایش دهید
• شمارش را چاپ کنید

در زیر اجرای رویکرد فوق آورده شده است:

C++

// کد C ++ برای شمارش تعداد مثلث های احتمالی با استفاده از // رویکرد نیروی بی رحمانه #عبارتند از با استفاده از namespace std ؛ // عملکرد برای شمارش تمام مثلث های ممکن با arr [] // عناصر int findNumberOfTriangles (int arr [] ، int n) // تعداد مثلث ها int count = 0 ؛ // سه حلقه سه مقدار مختلف را از // آرایه برای (int i = 0 ؛ iarr [k] && arr[i] + arr[k]>arr [j] && arr[k] + arr[j]>arr [i]) تعداد ++ ؛ تعداد بازگشت ؛ // کد درایور int main () int arr [] =<10, 21, 22, 100, 101, 200, 300>; اندازه int = sizeof (arr) / sizeof (arr [0]) ؛ // تماس عملکرد چاک<<"Total number of triangles possible is " <C // کد C برای شمارش تعداد مثلث های احتمالی با استفاده از // رویکرد نیروی بی رحمانه #عبارتند از // عملکرد برای شمارش تمام مثلث های ممکن با arr [] // عناصر int findNumberOfTriangles (int arr [] ، int n) // تعداد مثلث ها int count = 0 ؛ // سه حلقه سه مقدار مختلف را از // آرایه برای (int i = 0 ؛ iarr [k] && arr[i] + arr[k]>arr [j] && arr[k] + arr[j]>arr [i]) تعداد ++ ؛ تعداد بازگشت ؛ // کد درایور int main () int arr [] =<10, 21, 22, 100, 101, 200, 300>; اندازه int = sizeof (arr) / sizeof (arr [0]) ؛ // تماس عملکرد printf ("تعداد کل مثلث ممکن ٪ D است" ، FindNumberOfTriangles (ARR ، اندازه)) ؛ بازگشت 0 ؛ // این کد توسط Sania Kumari Gupta کمک می کند

جاوا

// کد جاوا برای شمارش تعداد مثلث های احتمالی با استفاده از // رویکرد نیروی بی رحمانه وارد کردن java. io.*؛ وارد کردن java. util.*؛ GFG کلاس< // عملکرد برای شمارش تمام مثلث های ممکن با arr [] // عناصر static int findNumberOfTriangles (int arr [] ، int n) // مرتب سازی آرایه arrays. sort (arr) ؛ // تعداد مثلث ها int count = 0 ؛ // سه حلقه سه مقدار مختلف را انتخاب می کنند // از آرایه برای (int i = 0 ؛ iarr [k]) تعداد ++ ؛ تعداد بازگشت ؛ // کد درایور عمومی استاتیک اصلی اصلی (رشته [] args) int arr [] =<10 , 21 , 22 , 100 , 101 , 200 , 300>; اندازه int = arr. l طول ؛ // تماس عملکرد system. out. println ( "تعداد کل مثلث ممکن است" + FindNumberOfTriangles (ARR ، اندازه)) ؛ // این کد توسط Sania Kumari Gupta کمک می کند

پایتون 3

C#

تعداد کل مثلث ممکن 6 است